реферат, рефераты скачать Информационно-образоательный портал
Рефераты, курсовые, дипломы, научные работы,
реферат, рефераты скачать
реферат, рефераты скачать
МЕНЮ|
реферат, рефераты скачать
поиск
Метод прогонки решения систем с трехдиагональными матрицами коэффициентов

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

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

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

Реферат

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

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

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



© 2003-2013
Рефераты бесплатно, рефераты литература, курсовые работы, реферат, доклады, рефераты медицина, рефераты на тему, сочинения, реферат бесплатно, рефераты авиация, курсовые, рефераты биология, большая бибилиотека рефератов, дипломы, научные работы, рефераты право, рефераты, рефераты скачать, рефераты психология, рефераты математика, рефераты кулинария, рефераты логистика, рефераты анатомия, рефераты маркетинг, рефераты релиния, рефераты социология, рефераты менеджемент.