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

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

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

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

    Реферат

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

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

    Выполнил:

    студент группы ЭА-04-2

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

    Проверил:

    Королева В.В.

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

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

    определённую структуру. Среди таких систем выделим системы с матрицами ленточной структуры, в которых ненулевые элементы располагаются на главной диагонали и на нескольких побочных

    диагоналях. Для решения систем с ленточными матрицами коэффициентов метод Гаусса можно трансформировать в более эффективные методы.

    Рассмотрим наиболее простой случай ленточных систем, к которым, как увидим впоследствии, сводится решение задач сплайн-интерполяции функций, дискретизации краевых задач для

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

    неизвестных:

    где

    =1,2,...,

    0. Такие уравнения называются трехточечными разностными уравнениями второго порядка. Система (1) имеет трёхдиагональную структуру, что хорошо видно из следующего, эквивалентного

    (1), векторно-матричного представления:

    3 ...

    Как и в решении СЛАУ методом Гаусса, цель избавится от ненулевых элементов в поддиаганальной части матрицы системы, предположим, что существуют такие наборы чисел

    =1,2

    ,...,

    , при которых

    i+1+

    т.е. трехточечное уравнение второго порядка (1) преобразуется в двухточечное уравнение первого порядка (2). Уменьшим в связи (2) индекс на единицу и

    полученое выражение

    подставим в данное уравнение (1):

    i-1 x

    i+ b

    i+ d

    i+1= r

    откуда

    i= -((d

    i /( c

    i+ b

    i-1)) x

    i-1+(r

    i - b

    )/( c

    i - b

    Последнее равенство имеет вид (2) и будет точно с ним совпадать, иначе говоря, представление (2) будет иметь место, если при всех

    =1,2,…,

    выполняются рекуррентные соотношения

    i = - d

    i /( c

    i+ b

    i-1) ,

    i - b

    )/( c

    i - b

    Легко видеть, что, в силу условия

    , процесс вычисления

    может быть начат со значений

    1 = - d

    1/ c

    и продолжен далее по формулам (3) последовательно при

    =2,3,...,

    , причем при

    в силу

    получим

    0.Следовательно, полагая в (2)

    ,будем иметь

    n – b

    )/( c

    n – b

    (где

    уже известные с предыдущего шага числа). Далее по формулам (2) последовательно находятся

    ,…,

    при

    -2,...,1

    соответственно.

    Таким образом, решение уравнений вида (1) описываем способом, называемым методом прогонки, сводится к вычислениям по трём

    простым формулам: нахождение так называемых прогоночных коэффициентов

    по формулам (3) при

    =1,2,…,

    (прямая прогонка) и затем неизвестных

    по формуле (2) при

    -2,...,1

    (обратная прогонка).

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

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

    Будем называть прогонку корректной, если знаменатели прогоночных коэффициентов

    (3) не обращаются в нуль, и устойчивой, если |

    1 при всех

    {1,2,...,

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

    Теорема

    Пусть коэффициенты

    уравнения (1) при

    =2,3,...,

    -1 отличны от нуля и пусть

    =1,2,…,

    Тогда прогонка

    (3), (2) корректна и устойчива (т.е. с

    0, |

    Д о к а з а т е л ь с т в о.

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

    При

    1, в силу (4), имеем:

    |>=

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

    |=|-

    Предположим, что знаменатель (

    -1)-

    прогоночных коэффициентов не равен нулю и что |

    1. Тогда, используя свойства модулей, условия теоремы и индукционные предположения, получаем:

    |>=|

    | - |

    | - |

    |= |

    (1 - |

    |) |

    а с учетом этого

    |=|- d

    i-1|=|

    i-1|

    Следовательно, с

    0 и |

    1 при всех

    {1,2,...,

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

    Пусть А – матрица коэффициентов данной системы (1), удовлетворяющих условиям теоремы, и пусть

    = - d

    1/ c

    =|- d

    i/ c

    (i=2,3,...,n-1),

    прогоночные коэффициенты, определяемые первой из формул (3), а

    = с

    =2,3,...,

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

    , где

    …………………………

    -1 ...

    Забрать файл

    Похожие материалы:


ПИШЕМ УНИКАЛЬНЫЕ РАБОТЫ
Заказывайте напрямую у исполнителя!


© 2006-2016 Все права защищены