Метод 16
Метод прогонки.
Метод 15
Метод прогонки является модификацией метода Гаусса для частного случая с трёхдиагональной матрицей. Такие системы возникают при численном решении уравнений математической физики.
Другой пример: коэффициенты сплайна третьей степени находятся путём решения систем с трёхдиагональной матрицей.
В методе прогонки объём вычислений растет пропорционально . Запишем систему уравнений, которая решается методом прогонки.
Общий вид уравнений с трёхдиагональной матрицей
Решение системы с трёхдиагональной матрицей, как и в методе Гаусса, состоит из двух этапов. Прямой прогонки и обратной прогонки.
Рассмотрим первый этап (прямой ход метода прогонки)
Для этого неизвестный выражаем через , таким образом:
,
где , - неизвестные пока (прогоночные) коэффициенты. На первом как раз и находится эти коэффициенты. Сравним это уравнение при с первым уравнением системы
И из сравнения находим, что
Заменим i-ое уравнение системы, выразив в нём с помощью
Сравнивая с
Получаем рекуррентные соотношения для нахождения прогоночных коэффициентов.
После того как найдены все прогоночные коэффициенты в результате прямого хода метода, находят . Для этого сравниваем последние уравнения системы с последним прогоночным соотношением. В результате получаем систему из двух уравнений с двумя неизвестными.
Отсюда
Это фактически начало обратного хода метода прогонки.
После этого последовательно находим …….и т.д. вплоть до .
Уточнение решения (итерационный метод).
Решения, получаемые с помощью прямых методов обычно содержат погрешности. В ряде случаев, особенно если объём системы велик, эти погрешности могут быть значительными.
Рассмотрим итерационный процесс позволяющий уточнить решения на следующем итерационном шаге. Пусть решается система
……………………………
Пусть на k-ом итерационном шаге получено решение в виде , ,…, , где k-это номер итерационного шага.
Подставим полученное решение в левые части уравнений системы, результат вычислений этих уравнений обозначим , , .
В результате получим систему
……………………………
Вычтем из каждого уравнения 1-ой системы уравнение 2-ой системы и получим систему вида
……………………………
Отсюда
Это невязка для уравнений с соответствующим номером.
Теперь мы получаем систему решением, которой будут соотношения уточняющие решение.
………………..
Преимуществом этого метода является то, что на каждом итерационном шаге решается система с одной и той же матрицей. Это позволяет оптимизировать вычислительный процесс, строить экономичные алгоритмы.