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

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

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

Реферат

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

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

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

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

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

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

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

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

ix_i-1+ix_i<+d_ix_i<=r_i (1)

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

1 аd₁ 0 а0 а... 0 0 0 1 r₁

2 а2 d₂ 0 а... 0 0а а0 2 r₂а

0 а3 а3 аd₃... 0 0 0 3 аr₃

.. ..... ... *... <=а...

0а 0а 0а 0... n_-1c_n-1 d_n-1 аn_-1 r_n-1

0а 0а 0а 0... 0 n_а аn x_{n а}аr_n

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

i= δ_ix_i+1+ λ_i (2)

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

iδ_i-1 x_i+ b_i λ_i-1+ c_ix_i+ d_ix_i+1= r_i

откуда

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 = - d_i /( c_i+ b_iδ_i-1) , λ _i=(r_i - b_i λ_i-1)/( c_i - b_i δ_i-1) (3)

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

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

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

n = λ_n = (r_n - b_n λ_n-1)/( c_n Ц b_n δ_n-1)

(где λ_n-1, δ_n-1 - же известные с предыдущего шага числа). Далее по формулам (2) последовательно находятся n_-1 , n_-2,Е, 1 при

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

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

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

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

Теорема

Пусть коэффициенты i и d_iа равнения (1) при

<|i<|>|i<|+|d_i<|

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

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

При

|1<|>|d₁|≥0

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

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

Предположим, что знаменатель (i_-1|<1. Тогда, используя свойства модулей, словия теоремы и индукционные предположения, получаем:

<|с_i+iδ_i-1|≥|i<| - |iδ_i-1|>|i<|+|d_i<| - |-1|= |d_i<|+|i_-1|)> |d_i<|>0

с четом этого

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

Следовательно, с_i+iδ_i-1 ≠0 и |δ_i|<1 при всех

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

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

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

∆_i= с_i+iδ_i-1 (

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

1а а0 а0а а0а... 0 0а 0

2 аа∆₂ 0а 0а... 0 а0 0

L<= 0а 3 а∆₃ 0а... 0а 0 0

0 0 0 0... n_-1 ∆_n<-1 0

0 0 0 0... 0 n_а а∆_n

1а <-δ₁ а0 0а... 0 0 0

0 1а аδ₂а 0а... а0 0 0

U<= 0а а0 1 δ₃а... 0 0 0

0 0 0 0а а... а0 1а <-δ_n-1

0 0 0 0а а... 0 0 1

Единственное в силу тверждение теоремы LU<-разложения матриц. Как видим, LU<-разложение трехдиагональной матрицы А может быть выполнено очень простым алгоритмом, вычисляющема ∆_i δ_i при возрастающих значениях

_n

det A = c₁ ∏ ∆_i.

ⁱ⁼²

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

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

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