Магнитогорский Государственный Технический Университет имени Г.И.Носова
Кафедра математики
Реферат
Тема: Метод прогонки решения систем с трехдиагональными матрицами коэффициентов
Выполнил: студент группы ЭА-04-2
Романенко Н.А.
Проверил: Королева В.В.
Магнитогорск 2004
Часто возникает необходимость в решении линейных алгебраических систем,
матрицы которых, являясь слабо заполненными, т.е. содержащими немного
ненулевых элементов, имеют определённую структуру. Среди таких систем
выделим системы с матрицами ленточной структуры, в которых ненулевые
элементы располагаются на главной диагонали и на нескольких побочных
диагоналях. Для решения систем с ленточными матрицами коэффициентов метод
Гаусса можно трансформировать в более эффективные методы.
Рассмотрим наиболее простой случай ленточных систем, к которым, как
увидим впоследствии, сводится решение задач сплайн-интерполяции функций,
дискретизации краевых задач для дифференциальных уравнений методами
конечных разностей, конечных элементов и др. А именно, будем искать решение
такой системы, каждое уравнение которой связывает три “соседних”
неизвестных:
bixi-1+cixi+dixi=ri (1)
где i=1,2,...,n; b1=0, dn=0. Такие уравнения называются трехточечными
разностными уравнениями второго порядка. Система (1) имеет трёхдиагональную
структуру, что хорошо видно из следующего, эквивалентного (1), векторно-
матричного представления:
c1 d1 0 0 ... 0 0 0 x1 r1 b2 c2 d2 0 ... 0 0 0 x2 r2
0 b3 c3 d3 ... 0 0 0 x3 r3
. . . . ... . . . * ...
= ...
0 0 0 0 ... bn-1cn-1 dn-1 xn-1 rn-1
0 0 0 0 ... 0 bn cn xn rn
Как и в решении СЛАУ методом Гаусса, цель избавится от ненулевых
элементов в поддиаганальной части матрицы системы, предположим, что
существуют такие наборы чисел ?i и ?i (i=1,2,...,n), при которых
xi= ?ixi+1+ ?i (2)
т.е. трехточечное уравнение второго порядка (1) преобразуется в
двухточечное уравнение первого порядка (2). Уменьшим в связи (2) индекс на
единицу и полученое выражение xi-1= ?i-1xi+ ?i-1 подставим в данное
уравнение (1):
bi?i-1 xi+ bi ?i-1+ cixi+ dixi+1= ri
откуда xi= -((di /( ci+ bi?i-1)) xi-1+(ri - bi ?i-1)/( ci -
bi ?i-1)).
Последнее равенство имеет вид (2) и будет точно с ним совпадать, иначе
говоря, представление (2) будет иметь место, если при всех i=1,2,…,n
выполняются рекуррентные соотношения
?i = - di /( ci+ bi?i-1) , ? i=(ri - bi ?i-1)/( ci
- bi ?i-1) (3)
Легко видеть, что, в силу условия b1=0, процесс вычисления ?i , ?i
может быть начат со значений
?1 = - d1/ c1 , ?1 = r1/ c1
и продолжен далее по формулам (3) последовательно при i=2,3,...,n, причем
при i=n, в силу dn=0, получим ?n=0.Следовательно, полагая в (2) i=n,будем
иметь
xn = ?n = (rn – bn ?n-1)/( cn – bn ?n-1)
(где ?n-1 , ?n-1 – уже известные с предыдущего шага числа). Далее по
формулам (2) последовательно находятся xn-1 , xn-2 ,…, x1 при i=n-1, n-
2,...,1 соответственно.
Таким образом, решение уравнений вида (1) описываем способом,
называемым методом прогонки, сводится к вычислениям по трём простым
формулам: нахождение так называемых прогоночных коэффициентов ?i , ?i по
формулам (3) при i=1,2,…,n (прямая прогонка) и затем неизвестных xi по
формуле (2) при i=n-1, n-2,...,1 (обратная прогонка).
Для успешного применения метода прогонки нужно, чтобы в процессе
вычислений не возникало ситуаций с делением на нуль, а при больших
размерностях систем не должно быть строгого роста погрешностей округлений.
Будем называть прогонку корректной, если знаменатели прогоночных
коэффициентов (3) не обращаются в нуль, и устойчивой, если |?i||bi|+|di| i=1,2,…,n. (4)
Тогда прогонка (3), (2) корректна и устойчива (т.е. сi+bi?i-1?0,
|?i||d1|?0
- неравенство нулю первой пары прогоночных коэффициентов, а так же
|?1|=|- d1/ c1| |di|>0
а с учетом этого
|?i|=|- di/ сi+bi?i-1|=|?i|/| сi+bi?i-1|