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

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

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

Реферат

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

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

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

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

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

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

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

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

b>i>x>i>>-1>+c>i>x>i>+d>i>x>i>=r>i> (1)

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

c>1> d>1> 0 0 ... 0 0 0 x>1> r>1>

b>2 > c>2> d>2> 0 ... 0 0 0 x>2> r>2>

0 b>3 > c>3 >d>3> ... 0 0 0 x>3 >> > r>3>> >

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

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>1>=0, процесс вычисления δ>i>> >, λ>i>> > может быть начат со значений

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

и продолжен далее по формулам (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>1> при 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>1>|>|d>1>|≥0

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

|δ>1>|=|- d>1>/ c>1>|<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), удовлетворяющих условиям теоремы, и пусть

δ>1>= - d>1>/ c>1> , δ>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>1 > 0 0 0 ... 0 0 0

b>2 > ∆>2> 0 0 ... 0 0 0

L= 0 b>3 > ∆>3 >0 ... 0 0 0

…………………………

0 0 0 0 ... b>n>>-1 >∆>n>>-1 >0> >

0 0 0 0 ... 0 b>n>> > ∆>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 = c>1> ∏ ∆>i> .

i=2

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

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

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