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

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

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

Реферат

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

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

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


1 Star2 Stars3 Stars4 Stars5 Stars (No Ratings Yet)
Loading...
Метод прогонки решения систем с трехдиагональными матрицами коэффициентов