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

(Назад) (Cкачать работу)

Магнитогорский Государственный Технический Университет имени Г.И.Носова Кафедра математики Реферат Тема: Метод прогонки решения систем с трехдиагональными

матрицами коэффициентов Выполнил: студент группы ЭА-04-2

Романенко Н.А. Проверил: Королева В.В. Магнитогорск 2004

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

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

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

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

c1 d1 0 0 ... 000x1r1

b2 c2 d2 0 ... 000x2r2

0 b3 c3 d3 ... 000x3r3

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

0 0 0 0... bn-1cn-1 dn-1xn-1rn-1

0 0 0 0... 0bncnxnrn

Как и в решении СЛАУ методом Гаусса, цель избавится от ненулевых элементов в поддиаганальной части матрицы системы, предположим, что существуют такие наборы чисел δ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 (обратная прогонка).

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

Похожие работы