Главная    Почта    Новости    Каталог    Одноклассники    Погода    Работа    Игры     Рефераты     Карты
  
по Казнету new!
по каталогу
в рефератах

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



 Другие рефераты
Метод конечных разностей или метод сеток Метод последовательных уступок (Теория принятия решений) Методика изучения числовых систем Методы и алгоритмы построения элементов систем статистического моделирования

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

                       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 }.
      Приведем простые достаточные условия корректности и устойчивости
прогонки, которые во многих приложениях метода автоматически выполняются.

                 Теорема

           Пусть коэффициенты 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    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».

скачать работу


 Другие рефераты
Полиметилметакрилат. Органическое стекло
Исследование факторов эмоционального выгорания педагогов
Влияние использования схем, чертежей, иллюстраций на формирование ЗУН при обучении младших школьников решению задач на движение
Типы биотических отношений


 

Отправка СМС бесплатно

На правах рекламы


ZERO.kz
 
Модератор сайта RESURS.KZ