Метод прогонки решения систем с трехдиагональными матрицами коэффициентов

 

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

Рассмотрим случай системы линейных уравнений с матрицей коэффициентов ленточной структуры шириной три. К таким системам приводят задачи о сплайн-интерполяции, о решении разностными методами обыкновенных дифференциальных уравнений и уравнений в частных производных. Система линейных уравнений имеет трехдиагональную структуру:

, (6.5)

т.е. каждое уравнение связывает три соседних неизвестных:

, i=1, 2, …, n,

. (6.6)

Выразим из первого уравнения x через x:

;

из второго x через x:

 

;

и т.д. Из последнего уравнения:

 

.

Таким образом, для i=1, 2, …, n:

, где (6.7)

, . (6.8)

Так как , и .

 

Таким образом, решение системы линейных уравнений (6.6) сводится к двум этапам:

1. Вычисление прогоночных коэффициентов P, Q, i=1, 2, …, n по формулам (6.8) – прямая прогонка.

2. Вычисление неизвестных x при i=n, n–1, …, 1 по формулам (6.7) – обратная прогонка.

Обозначим , тогда , при i=2,…,n.

Непосредственной проверкой можно убедиться, что имеет место представление A=LU, где

.

Таким образом, LU-разложение трехдиагональной матрицы A может быть выполнено простым алгоритмом, вычисляющим R, P при возрастающих значениях i.

 

Можно вычислить и определитель матрицы A

det A= . (6.9)

 

Контроль точности и уточнение приближенного решения в рамках прямых методов

 

Прямые методы приводят к точному решению СЛАУ при точном выполнении предусматриваемых соответствующими алгоритмами арифметических операций. Реальные же вычисления производятся приближенно. Как отражается на результате решения системы подмена арифметики действительных чисел машинной арифметикой, зависит от самой решаемой системы, параметров применяемого компьютера, способов реализации алгоритма. В любом случае, практически вместо точного решения СЛАУ прямой метод дает приближенное решение.

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

Недостаточно малая величина, то следует искать вектор поправку такой, что , т.е. . Следовательно .   Нахождение поправки сводится к решению той же системы уравнений, где в качестве столбца свободных членов берется вектор невязки. Так как матрица коэффициентов левой части системы не меняется, нет надобности прямого хода преобразований коэффициентов при неизвестных (другими словами – LU-разложения), достаточно выполнить действия с новыми свободными членами. Прибавив найденную поправку, получаем уточненное решение . Если величина

Или

Окажется недостаточно малой, процесс уточнения может быть повторен: ищется поправка как приближенное решение системы , где ; тогда более точным должно быть решение . Но сходимость к нулю невязок в таком процессе может и не наблюдаться. Обычно делают не более двух-трех шагов уточнения, причем рекомендуется производить вычисление невязок в режиме накопления. если в этом процессе не происходит сближения при k=2,3,…, то это говорит скорее всего о плохой обусловленности данной системы и о том, что ее решение не может быть уточнено таким способом. Описанный контроль точности по невязкам не требует большого увеличения вычислительных затрат, но требуется отводить дополнительное место в памяти под хранение исходных данных.