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

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

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

Реферат

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

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

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

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

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

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

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

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

                            bixi-1+cixi+dixi=ri                                                 (1)

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

/>/>/>/>/>/>                                   c1 d10  0  ...  0   0   0                   x1                    r1

                                   b2 c2 d20 ... 0   0   0                   x2                    r2 

                                   0 b3  c3  d3...  0   0  0                   x3                             r3        

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

                                   0  0  0  0    ...  bn-1cn-1dn-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<sub/>, λi<sub/> можетбыть начат со значений

                                      δ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<sub/>, λi  поформулам (3) при i=1,2,…,n(прямая прогонка) изатем неизвестных xi по формуле (2) при i=n-1,n-2,...,1 (обратнаяпрогонка).

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

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

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

Теорема

Пусть коэффициенты bi<sub/>и 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    0              

                                   b2   ∆20  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<sub/> 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».