Файл: Численные методы решения систем линейных алгебраических уравнений.docx

РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ

«НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

Кафедра вычислительной техники

Отчет

По лабораторной работе №2

По дисциплине: «Вычислительная математика»

Тема: «Численные методы решения систем линейных

алгебраических уравнений»

Вариант 1

Факультет: АВТФ

Группа:

Студенты:

Преподаватель:
Защита: 5 баллов

1) Объясните и продемонстрируйте по материалам своего отчета сущность и основные свойства рассмотренных в ЛР 2-х числ. методов разного типа.
2) Перечислите основные способы проверки на достоверность и точность решений Систем ЛинАлг. уравнений и в чем преимущества выбранного Вами в работе способа проверки перед остальными и почему?
3) Каким образом можно обеспечить возможность применение метода простых итераций для решения СЛАУ? Если да, то продемонстрируйте это на примере своей задачи.
4) Продемонстрируйте на примере из Вашей ЛР связь обусловленности задачи и числ. метода с точностью решений.
5) Локальная и глобальная сходимость , необходимые и достаточные условия сходимости итерационных методов (по выбору)
Новосибирск 2021

3.1. Метод Крамера для решения систем линейных алгебраических уравнений. Реализация в MathCAD 5

3.1.1. Вывод по методу Крамера 6

3.2. Метод Гаусса 7

3.2.1. Вывод по методу Гаусса 8

3.3. Метод простых итераций 9

3.3.1. Вывод по методу простых итераций 11

8.Контрольные вопросы 15

Введение

Лабораторная работа №2 посвящена численным методам решения СЛАУ.

Необходимость отыскания корней СЛАУ встречается в решении нелинейных уравнений, в аналитической геометрии, описании важных геометрических плоскостей и прямых в задачах моделирования.

1. Описание задания

Номер набора методов	Методы	Значения a,b,c,d
1	Метод Крамера, Метод Гаусса, метод итерации	5502

1.2. Цели и задачи работы

1. В соответствии с вариантом контрольного задания исследуйте существование и найдите

решение системы уравнений от значений a, b, c, d (a, b, c, d - последние цифры номера

зачетной книжки студента) с точностью , не ниже 0,00001, тремя методами:

• методом Крамера;

• методом Гаусса;

• методом итераций.

2. Написать программы, реализующие алгоритмы решения СЛАУ прямым и

итерационным методом.

3. Для дублирования решений систем линейных алгебраических уравнений применить

существующие стандартные функции МСАД, аналогичные заданным методам.

4. Для каждого метода и способа решения исследовать ресурсоемкость программ

вычислений и факторы, влияющие на точность результатов.

5. Сравнить методы и способы решения СЛАУ по быстродействию и точности, выбрать

наиболее эффективный вычислительный процесс поставленной задачи.

6. Проанализировать результаты работы и сделать выводы.

Результаты численных расчетов должны быть оформлены по всем правилам записи

приближенных чисел, т.е. запись приближенного решения только с верными значащими

цифрами и допускаемой погрешностью. Анализ численных результатов должен дать ответ

на вопрос, соответствуют ли полученные результаты искомому решению поставленной

задачи и почему. В отчете обязательно сформулируйте необходимые и достаточные

условия существования решений и сходимости методов; проверьте точность решений.

Проанализируйте особенности применения рассмотренных методов, дайте рекомендации

по решению соответствующих задач на ЭВМ.

2. Описание методов

2.1 Метод Крамера

«Узкий» метод решения, ведь матрица должна иметь n количество линейных уравнений с n количеством переменных, и с определителем (∆) матрицы отличным от нуля. Корни системы находятся по формуле: x_n =

.

Алгоритм:

Сначала надо посчитать определитель матрицы, если он не равен нулю, а количество уравнений равно количеству переменных, то корни в такой матрице можно находить методом Крамера.
Дальше считаем определитель матрицы, подставляя значения вектора в столбцы матрицы с перового по n.
Затем находим корни СЛАУ по формуле: x_n = .

Метод Крамера требует O(n⁴) арифметических операций. Хотя в 2010 году было показано, что возможно реализовать этот метод со сложностью O(n³) как у метода Гаусса.

2.2. Метод Гаусса

Суть метода заключается в последовательном методе исключения переменных, когда с помощью элементарных преобразований система уравнений приводится к равносильной системе треугольного вида, из которой последовательно, начиная с последних (по номеру), находятся все переменные системы.

Критерием совместимости является Теорема Кронекера – Капелли. Для того, чтобы система являлась совместной, необходимо и достаточно, чтобы ранг расширенной матрицы этой системы был равен рангу её основной матрицы.

Алгоритм:

Путём осуществления прямого хода с помощью элементарных преобразований над строками, приводим систему к треугольной форме, либо доказываем, что она несовместна.
Дальше, путём обратного хода выражаем все получившиеся базисные переменные через небазисные, и строим фундаментальную систему решений. Если все переменные являются базисными, то составляем единственное решение системы линейных уравнений.

Метод Гаусса требует O(n³) арифметических операций.

2.3 Метод Итерации

Суть метода заключается в нахождении по приближённому значению величины следующего приближения (являющегося более точным).

Метод позволяет получить значения корней системы с заданной точностью в виде предела последовательности некоторых векторов (итерационный процесс). Характер сходимости и сам факт сходимости метода зависит от выбора начального приближения корня x₀.

Алгоритм:

Предполагая, что диагональные коэффициенты a_ii не равны 0 (i = 1,2,…,n), разрешим первое уравнение системы относительно x₁, второе – относительно x₂ и т. д. Тогда получим эквивалентную систему.
Вводим матрицы a и b.
Тогда эквивалентную систему можно записать в матричной форме X = b + aX, а любое (k+1) приближение вычисляется по формуле X⁽^k⁺¹⁾ = b + aX⁽^k⁾.

3. Ход работы

3.1. Метод Крамера для решения систем линейных алгебраических уравнений. Реализация в MathCAD

3.1.1. Вывод по методу Крамера

Метод Крамера имеет достаточно простую структуру реализации на практике.

3.2. Метод Гаусса

3.2.1. Вывод по методу Гаусса

Метод Гаусса подходит для вычислений любой системы линейных алгебраических уравнений.

3.3. Метод простых итераций

3.3.1. Вывод по методу простых итераций

Метод простых итераций имеет громоздкий программный модуль ввиду условия сходимости. Программа не посчитала корни, так как не выполняется условие диагонального преобладания исходной матрицы.

4. Сравнение методов решения СЛАУ по скорости

При помощи функции time определяем скорость вычисления программного модуля для каждого из методов.

Функция timeвыводит результат в миллисекундах. Для сравнения результатов сделаем табличку, расставляя затраченное время на вычисление от самого маленького к самому большому.

Метод простых итераций	Метод Крамера	Метод Гаусса
270 мс	128 мс	34 мс

С данной матрицей лучше всего подходит решение методом Гаусса, поскольку занимает наименьшее количество времени, метод Крамера на втором месте, метод итераций на третьем.

5. Рекомендации по использованию средств MathCAD для решения СЛАУ

При решении нелинейных уравнений, в первую очередь, рассчитайте аналитически корни данного уравнения, чтобы в дальнейшем была возможность сравнить полученные результаты.

При написании программного модуля называйте функцию так, чтобы было сразу понятно, по какому методу будет решено нелинейное уравнение. Также добавляйте большестрок через функцию Addline, так как лишние можно будет легко удалить, а если не хватит строки, то добавление ещё одной потребует небольших, но всё же усилий.

6. Решение заданной СЛАУ с помощью стандартных функций.

7. Вывод

В ходе лабораторной работы №2 прошло ознакомление с различными методами для решения систем линейных алгебраических уравнений. На практике были реализованы три метода: Крамера, Гаусса, простых итераций. Ответы совпали с заданной точностью при решении разными методами. Время расчета по каждому методу составило меньше одной секунды.

8.Контрольные вопросы

Объясните и продемонстрируйте по материалам своего отчета сущность и основные свойства рассмотренных в ЛР 2-х числ. методов разного типа.

Метод Крамера.

«Узкий» метод решения, ведь матрица должна иметь n количество линейных уравнений с n количеством переменных, и с определителем (∆) матрицы отличным от нуля. Метод Крамера требует O(

) арифметических операций. Хотя в 2010 году было показано, что возможно реализовать этот метод со сложностью O(

) как у метода Гаусса.

Метод Гаусса

Суть метода заключается в последовательном методе исключения переменных, когда с помощью элементарных преобразований система уравнений приводится к равносильной системе треугольного вида, из которой последовательно, начиная с последних (по номеру), находятся все переменные системы. Метод Гаусса требует O(

) арифметических операций.
Метод Итерации

Суть метода заключается в нахождении по приближённому значению величины следующего приближения (являющегося более точным). Метод позволяет получить значения корней системы с заданной точностью в виде предела последовательности некоторых векторов (итерационный процесс). Характер сходимости и сам факт сходимости метода зависит от выбора начального приближения корня