Метод 16

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

Метод 15

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

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

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

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

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

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

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

,

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

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

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

Сравнивая с

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

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

Отсюда

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

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

Уточнение решения (итерационный метод).

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

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

……………………………

Пусть на k-ом итерационном шаге получено решение в виде,,…,, где k-это номер итерационного шага.

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

В результате получим систему

……………………………

Вычтем из каждого уравнения 1-ой системы уравнение 2-ой системы и получим систему вида

……………………………

Отсюда

Это невязка для уравнений с соответствующим номером.

Теперь мы получаем систему решением, которой будут соотношения уточняющие решение.

………………..

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

Дата добавления: 2014-01-06