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

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

Магнитогорский Государственный Технический Университет имени Г.И.Носова

Кафедра математики

Реферат

Тема: Метод прогонки решения систем с трехдиагональными

матрицами коэффициентов

Выполнил: студент группы ЭА-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||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».