Магнитогорский Государственный Технический Университет имени Г.И.Носова
Кафедра математики
Реферат
Тема: Метод прогонки решения систем с трехдиагональными
матрицами коэффициентов
Выполнил: студент группы ЭА-04-2
Романенко Н.А.
Проверил: Королева В.В.
Магнитогорск 2004
Часто возникает необходимость в решении линейных алгебраических систем, матрицы которых, являясь слабо заполненными, т.е. содержащими немного ненулевых элементов, имеют определённую структуру. Среди таких систем выделим системы с матрицами ленточной структуры, в которых ненулевые элементы располагаются на главной диагонали и на нескольких побочных диагоналях. Для решения систем с ленточными матрицами коэффициентов метод Гаусса можно трансформировать в более эффективные методы.
Рассмотрим наиболее простой случай ленточных систем
, к которым, как увидим впоследствии, сводится решение задач сплайн-интерполяции функций, дискретизации краевых задач для дифференциальных уравнений методами конечных разностей, конечных элементов и др. А именно, будем искать решение такой системы, каждое уравнение которой связывает три “соседних” неизвестных:
bi
xi
-1
+
ci
xi
+
di
xi
=
ri
(1)
где i
=1,2
,...,n
; b
1
=
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
-1
cn
-1
dn
-1
xn
-1
rn-1
0 0 0 0 ... 0 bn
cn
xn
rn
Как и в решении СЛАУ методом Гаусса, цель избавится от ненулевых элементов в поддиаганальной части матрицы системы, предположим, что существуют такие наборы чисел δ
i
и λ
i
(
i
=1,2
,...,n
)
, при которых
xi
=
δ
i
xi+1
+
λ
i
(2)
т.е. трехточечное уравнение второго порядка (1) преобразуется в двухточечное уравнение первого порядка (2). Уменьшим в связи (2) индекс на единицу и полученое выражение xi
-1
= δ
i
-1
xi
+ λ
i
-1
подставим в данное уравнение (1):
bi
δi-1
xi
+ bi
λ
i-1
+ ci
xi
+ di
xi+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)
Легко видеть, что, в силу условия b
1
=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
,…, x
1
при 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
|>|
d
1
|≥
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=
0b3
∆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
01 δ2
0...0 0 0
U=
0 01δ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».