Метод прогонки решения систем с трехдиагональными матрицами коэффициентов
Магнитогорский Государственный Технический Университет имени Г.И.Носова
Кафедра математики
Реферат
Тема: Метод прогонки решения систем с трехдиагональными
матрицами коэффициентов
Выполнил: студент группы ЭА-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|<1 при всех iтВм{1,2,..,n }.
Приведем простые достаточные условия корректности и устойчивости прогонки, которые во многих приложениях метода автоматически выполняются.
Теорема
Пусть коэффициенты bi и di уравнения (1) при i=2,3,..,n-1 отличны от нуля и пусть
|ci|>|bi|+|di| i=1,2,тАж,n. (4)
Тогда прогонка (3), (2) корректна и устойчива (т.е. сi+biОґi-1тЙа0, |Оґi|<1).
Д о к а з а т е л ь с т в о. Воспользуемся методом математической индукции для установления обоих нужных неравенств одновременно.
При i=1, в силу (4), имеем:
|c1|>|d1|тЙе0
- неравенство нулю первой пары прогоночных коэффициентов, а так же
|Оґ1|=|- d1/ c1|<1
Предположим, что знаменатель (i-1)-x прогоночных коэффициентов не равен нулю и что |Оґi-1|<1. Тогда, используя свойства модулей, условия теоремы и индукционные предположения, получаем:
|сi+biОґi-1|тЙе|ci| - |biОґi-1|>|bi|+|di| - |bi|*|Оґi-1|= |di|+|bi|(1 - | Оґi-1|)> |di|>0
а с учетом этого
|Оґi|=|- di/ сi+biОґi-1|=|Оґi|/| сi+biОґi-1|<|Оґi|/|Оґi|=1
Следовательно, сi+biОґi-1 тЙа0 и |Оґi|<1 при всех iтВм{1,2,..,n }, т.е. имеет место утверждаемая в данных условиях корректность и устойчивость прогонки. Теорема доказана.
Пусть А тАУ матрица коэффициентов данной системы (1), удовлетворяющих условиям теоремы, и пусть
Оґ1= - d1/ c1 , Оґi=|- di/ ci+biОґi-1 (i=2,3,..,n-1), Оґn=0
- прогоночные коэффициенты, определяемые первой из формул (3), а
тИЖi= сi+biОґi-1 (i=2,3,..,n)
- знаменатели этих коэффициентов (отличные от нуля согласно утверждению теоремы). Непосредственной проверкой легко убедится, что имеет место представление A=LU, где
c1 0 0 0 .. 0 0 0
b2 тИЖ2 0 0 .. 0 0 0
L= 0 b3 тИЖ3 0 .. 0 0 0
тАжтАжтАжтАжтАжтАжтАжтАжтАжтАж
0 0 0 0 .. bn-1 тИЖn-1 0
0 0 0 0 .. 0 bn тИЖn
1 -Оґ1 0 0 .. 0 0 0
0 1 Оґ2 0 .. 0 0 0
U= 0 0 1 Оґ3 .. 0 0 0
тАжтАжтАжтАжтАжтАжтАжтАжтАжтАж
0 0 0 0 .. 0 1 -Оґn-1
0 0 0 0 .. 0 0 1
Единственное в силу утверждение теоремы LU-разложения матриц. Как видим, LU-разложение трехдиагональной матрицы А может быть выполнено очень простым алгоритмом, вычисляющем тИЖi Оґi при возрастающих значениях i. При необходимости попутно может быть вычислен
n
det A = c1 тИП тИЖi .
i=2
В заключение этого пункта заметим, что, во-первых, имеются более слабые условия корректности и устойчивости прогонки, чем требуется в теореме условие строгого диагонального преобладания в матрице А. Во-вторых, применяется ряд других, отличных от рассмотрения нами правой прогонки, методов подобного типа, решающих как поставленную здесь задачу (1) для систем с трехдиагональными матрицами (левая прогонка, встречная прогонка, немонотонная, циклическая, ортогональная прогонки и т.д.), так и для более сложных систем с матрицами ленточной структуры или блочно-матричной структуры (например, матричная прогонка).
Список используемой литературы
В.М. Вержбитский ВлЧисленные методы. Линейная алгебра и нелинейные уравненияВ», Москава ВлВысшая школа 2000В».
Вместе с этим смотрят:
Метода последовательных уступокМетоды и алгоритмы построения элементов системМетоды и приемы решения задачМетоды спуска