10.Решение систем специальной структуры. Метод прогонки. Общая характеристика метода.

 

Пусть дана система линейных уравнений с невырожденной  трехдиагональной матрицей:          

                                  

 

 

Такую систему можно записать в виде:                           

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

Метод прогонки состоит из прямого и обратного хода.

Прямой ход  заключается в определении коэффициентов, связывающих  и :

 ,    k = 1,2,...n-1.

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

Описание алгоритма и расчётные формулы.

Прямой ход метода прогонки.

Находим  и .                                         

 Вычисляем    для   k = 2, 3, ...n-1.:          

                                            

Обратный ход метода прогонки.

Находим              .

Вычисляем                по формулам:

                               k = n-1, n-2, ..1.        

Поскольку при решении задачи на ЭВМ нужно хранить в памяти только ненулевые элементы ,,  то такая структура матрицы позволяет экономить память. Сокращается также  время расчётов, т.к. операции с нулевыми элементами не производятся: вычисления  методом прогонки осуществляются  примерно в 9n арифметических операций. Таким образом, этот метод намного экономнее других методов исключения.

Если в матрице  А выполнено условие преобладания главной диагонали  а также некоторые дополнительные условия, то метод прогонки устойчив к ошибкам округления..