.

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

Язык: русский
Формат: реферат
Тип документа: Word Doc
0 482
Скачать документ

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

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

Реферат

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

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

Выполнил: студент группы ЭА-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|<1 при всех i?{1,2,...,n }./L | ~ ? ‚ „ † E oooooooooooooeaOAeAeAeAe?„µy`„µygd_^R„e„Ae^„e/h‘h‘h‘h‘h‘h‘h‘h‘h‘h‘h‘h‘h‘h‘h‘h‘//!е условия корректности и устойчивости прогонки, которые во многих приложениях метода автоматически выполняются.ТеоремаПусть коэффициенты 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|>|d1|?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 0b2 ?2 0 0 ... 0 0 0L= 0 b3 ?3 0 ... 0 0 0…………………………0 0 0 0 ... bn-1 ?n-1 00 0 0 0 ... 0 bn ?n1 -?1 0 0 ... 0 0 00 1 ?2 0 ... 0 0 0U= 0 0 1 ?3 ... 0 0 0…………………………0 0 0 0 ... 0 1 -?n-10 0 0 0 ... 0 0 1Единственное в силу утверждение теоремы LU-разложения матриц. Как видим, LU-разложение трехдиагональной матрицы А может быть выполнено очень простым алгоритмом, вычисляющем ?i ?i при возрастающих значениях i. При необходимости попутно может быть вычисленndet A = c1 ? ?i .i=2В заключение этого пункта заметим, что, во-первых, имеются более слабые условия корректности и устойчивости прогонки, чем требуется в теореме условие строгого диагонального преобладания в матрице А. Во-вторых, применяется ряд других, отличных от рассмотрения нами правой прогонки, методов подобного типа, решающих как поставленную здесь задачу (1) для систем с трехдиагональными матрицами (левая прогонка, встречная прогонка, немонотонная, циклическая, ортогональная прогонки и т.д.), так и для более сложных систем с матрицами ленточной структуры или блочно-матричной структуры (например, матричная прогонка).Список используемой литературыВ.М. Вержбитский «Численные методы. Линейная алгебра и нелинейные уравнения», Москава «Высшая школа 2000».

Нашли опечатку? Выделите и нажмите CTRL+Enter

Похожие документы
Обсуждение
    Заказать реферат
    UkrReferat.com. Всі права захищені. 2000-2019