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

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

Прямой ход состоит в следующем:

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

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

Рассмотрим процесс исключения подробнее:

На -ом шаге исключается

Запишем -ое уравнение:

Исключим с помощью этого уравнения из уравнения с номером

Для исключения из -го уравнения вычитаем -ое , умноженное на .

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

При этом изменяется свободный член

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

Обратный ход метода Гаусса состоит в последовательном вычислении искомых неизвестных, начиная с . Сначала находится . Далее, используя это значение, находится и так далее.

Например:

На - ом шаге обратного хода неизвестные находятся с помощью выражения.

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

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

В методе Гаусса объём вычислений пропорционален . Существует практически значимые случаи, когда объём вычислений при решении СЛАУ можно резко сократить.

Метод 15

Метод прогонки.

Метод прогонки является модификацией метода Гаусса для частного случая с трёхдиагональной матрицей. Такие системы возникают при численном решении уравнений математической физики.

Другой пример: коэффициенты сплайна третьей степени находятся путём решения систем с трёхдиагональной матрицей.

В методе прогонки объём вычислений растет пропорционально . Запишем систему уравнений, которая решается методом прогонки.

Общий вид уравнений с трёхдиагональной матрицей

Решение системы с трёхдиагональной матрицей, как и в методе Гаусса, состоит из двух этапов. Прямой прогонки и обратной прогонки.

Рассмотрим первый этап (прямой ход метода прогонки)

Для этого неизвестный выражаем через , таким образом:

,

где , - неизвестные пока (прогоночные) коэффициенты. На первом как раз и находится эти коэффициенты. Сравним это уравнение при с первым уравнением системы

И из сравнения находим, что

Заменим i-ое уравнение системы, выразив в нём с помощью

Сравнивая с

Получаем рекуррентные соотношения для нахождения прогоночных коэффициентов.

После того как найдены все прогоночные коэффициенты в результате прямого хода метода, находят . Для этого сравниваем последние уравнения системы с последним прогоночным соотношением. В результате получаем систему из двух уравнений с двумя неизвестными.

Отсюда

Это фактически начало обратного хода метода прогонки.

После этого последовательно находим …….и т.д. вплоть до .

Метод 16