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

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

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

Реферат

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

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

Выполнил: студент группы ЭА-04-2

Романенко Н.А.

Проверил: Королева В.В.

Магнитогорск 2004

Часто возникает необходимость в решении линейных алгебраических систем, матрицы которых, являясь слабо заполненными, т.е. содержащими немного ненулевых элементов, имеют определённую структуру. Среди таких систем выделим системы с матрицами ленточной структуры, в которых ненулевые элементы располагаются на главной диагонали и на нескольких побочных диагоналях. Для решения систем с ленточными матрицами коэффициентов метод Гаусса можно трансформировать в более эффективные методы.

Рассмотрим наиболее простой случай ленточных систем , к которым, как увидим впоследствии, сводится решение задач сплайн-интерполяции функций, дискретизации краевых задач для дифференциальных уравнений методами конечных разностей, конечных элементов и др. А именно, будем искать решение такой системы, каждое уравнение которой связывает три “соседних” неизвестных:

b_i x_{i -1} + c_i x_i + d_i x_i = r_i (1)

где i =1,2 ,...,n ; b ₁ = 0, d_n = 0. Такие уравнения называются трехточечными разностными уравнениями второго порядка . Система (1) имеет трёхдиагональную структуру, что хорошо видно из следующего, эквивалентного (1), векторно-матричного представления:

c₁ d₁ 0 0 ... 0 0 0 x₁ r₁

b₂ c₂ d₂ 0...0 0 0 x₂ r₂

0 b₃ c₃ d₃ ...0 0 0 x₃ r₃

. . . . ... . . . * ... = ...

0 0 0 0 ... b_{n -1} c_{n -1} d_{n -1} x_{n -1} r_n-1

0 0 0 0 ... 0 b_n c_n x_n r_n

Как и в решении СЛАУ методом Гаусса, цель избавится от ненулевых элементов в поддиаганальной части матрицы системы, предположим, что существуют такие наборы чисел δ _i и λ _i ( i =1,2 ,...,n ) , при которых

x_i = δ _i x_i+1 + λ _i (2)

т.е. трехточечное уравнение второго порядка (1) преобразуется в двухточечное уравнение первого порядка (2). Уменьшим в связи (2) индекс на единицу и полученое выражение x_{i -1} = δ _{i -1} x_i + λ _{i -1} подставим в данное уравнение (1):

b_i δ_i-1 x_i + b_i λ _i-1 + c_i x_i + d_i x_i+1 = r_i

откуда

x_i = - ((d_i /( c_i + b_i δ_i-1 )) x_i-1 + (r_i - b_i λ _i-1 )/( c_i - b_i δ _i-1 )).

Последнее равенство имеет вид (2) и будет точно с ним совпадать, иначе говоря, представление (2) будет иметь место, если при всех i =1,2,…, n выполняются рекуррентные соотношения

δ_i = - d_i /( c_i + b_i δ_i-1 ) , λ _i = (r_i - b_i λ _i-1 )/( c_i - b_i δ _i-1 ) (3)

Легко видеть, что, в силу условия b ₁ =0 , процесс вычисления δ _i , λ _i может быть начат со значений

δ₁ = - d₁ / c₁ , λ ₁ = r₁ /c₁

и продолжен далее по формулам (3) последовательно при i =2,3,..., n , причем при i = n , в силу d_n =0, получим δ _n = 0.Следовательно, полагая в (2) i = n ,будем иметь

x_n = λ _n = (r_n – b_n λ _n-1 )/( c_n – b_n δ _n-1 )

(где λ _{n -1} , δ _{n -1} – уже известные с предыдущего шага числа). Далее по формулам (2) последовательно находятся x_{n -1} , x_{n -2} ,…, x ₁ при i = n -1, n -2,...,1 соответственно.

Таким образом, решение уравнений вида (1) описываем способом, называемым методом прогонки , сводится к вычислениям по трём простым формулам: нахождение так называемых прогоночных коэффициентов δ _i , λ _i по формулам (3) при i =1,2,…, n (прямая прогонка ) и затем неизвестных x_i по формуле (2) при i = n -1, n -2,...,1 (обратная прогонка ).

Для успешного применения метода прогонки нужно, чтобы в процессе вычислений не возникало ситуаций с делением на нуль, а при больших размерностях систем не должно быть строгого роста погрешностей округлений.

Будем называть прогонку корректной , если знаменатели прогоночных коэффициентов (3) не обращаются в нуль, и устойчивой , если |δ _i |< 1 при всех i € {1,2, ..., n }.

Приведем простые достаточные условия корректности и устойчивости прогонки, которые во многих приложениях метода автоматически выполняются.

Теорема

Пусть коэффициенты b_i и d_i уравнения (1) при i =2,3,..., n -1 отличны от нуля и пусть

| c_i |>| b_i |+| d_i | i =1,2,…, n . (4)

Тогда прогонка (3), (2) корректна и устойчива (т.е. с _i + b_i δ_{i -1} ≠ 0, |δ _i |< 1).

Д о к а з а т е л ь с т в о. Воспользуемся методом математической индукции для установления обоих нужных неравенств одновременно.

При i = 1, в силу (4), имеем:

| c₁ |>| d ₁ |≥ 0

- неравенство нулю первой пары прогоночных коэффициентов, а так же

|δ ₁ |=|- d₁ / c₁ |< 1

Предположим, что знаменатель (i -1)-x прогоночных коэффициентов не равен нулю и что |δ _{i -1} |< 1. Тогда, используя свойства модулей, условия теоремы и индукционные предположения, получаем:

|с _i + b_i δ_{i -1} |≥| c_i | - | b_i δ_{i -1} |>| b_i |+| d_i | - | bi |*| δi _-1 |= | d_i |+| bi | (1 - |δ_{i -1} |)> | d_i | >0

а с учетом этого

|δ _i |=|- d_i / с _i +b_i δ_i-1 |=| δ _i |/| с _i +b_i δ_i-1 |< |δ _i |/ |δ _i |= 1

Следовательно, с _i + b_i δ_{i -1} ≠ 0 и |δ _i |< 1 при всех i € {1,2, ..., n }, т.е. имеет место утверждаемая в данных условиях корректность и устойчивость прогонки. Теорема доказана.

Пусть А – матрица коэффициентов данной системы (1), удовлетворяющих условиям теоремы, и пусть

δ ₁ = - d₁ / c₁ , δ _i =|- d_i / c_i +b_i δ_i-1 (i=2,3,...,n -1 ),δ _n =0

- прогоночные коэффициенты, определяемые первой из формул (3), а

∆ _i = с _i + b_i δ_{i -1} (i =2,3,..., n )

- знаменатели этих коэффициентов (отличные от нуля согласно утверждению теоремы). Непосредственной проверкой легко убедится, что имеет место представление A = LU , где

c₁ 0 0 0 ... 0 0 0

b₂ ∆₂ 0 0...0 0 0

L= 0b₃ ∆₃ 0 ...0 0 0

…………………………

0 0 0 0 ... b_{n -1} ∆ _n-1 0

0 0 0 0 ... 0 b_n ∆ _n

1 -δ₁ 0 0 ... 0 0 0

01 δ₂ 0...0 0 0

U= 0 01δ₃ ...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 = c₁ ∏ ∆ _i .

ⁱ⁼²

В заключение этого пункта заметим, что, во-первых, имеются более слабые условия корректности и устойчивости прогонки, чем требуется в теореме условие строгого диагонального преобладания в матрице А . Во-вторых, применяется ряд других, отличных от рассмотрения нами правой прогонки, методов подобного типа, решающих как поставленную здесь задачу (1) для систем с трехдиагональными матрицами (левая прогонка, встречная прогонка, немонотонная, циклическая, ортогональная прогонки и т.д.), так и для более сложных систем с матрицами ленточной структуры или блочно-матричной структуры (например, матричная прогонка).

Список используемой литературы

В.М. Вержбитский «Численные методы. Линейная алгебра и нелинейные уравнения», Москава «Высшая школа 2000».