Презентация на тему Решение дифференциальных уравнений. Метод прогонки.

линейных алгебраических уравнений с трехдиагональной матрицей. Если матрица системы

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

что, используя специфику структуры матрицы системы уравнений (наличие трех

диагоналей), удается получить рекуррентные формулы для вычисления последовательности коэффициентов прогонки,которые позволяют на обратном ходу вычислить значения функции в узлах сетки. Рассматривая конечно-разностное уравнение для первой тройки узлов:
b1U1+c1U2=-a1U0,
видим, что оно связывает между собой два соседних значения U1, и U2. Перепишем его в виде:
d1U2+e=U1, (1)
где d1 и е1вычисляются по известным значениям. Наблюдательный читатель заметит, что это справедливо только для задач первого рода. Чуть позже мы получим общее решение. Теперь мы можем исключить £/, из уравнения для следующей тройки узлов:
a2U1+b2U2+c2U2=f2,
подставив значение U1 из уравнения (8). После этой процедуры последнее уравнение также может быть приведено к виду:
d3U3+e2=U2,
Подстановки можно продолжать и дальше, но для получения рекуррентного соотношения, достаточно рассмотреть одну из них для произвольного индекса i. Подставив
di-1Ui+ei-1=Ui-1,
в уравнение
aiUi-1+biUi+ciUi+1=fi,
получим:
Ui=-[CiUi+1/(aidi-1+bi)]+[fi-ai+1*ei+1/(aidi-1+bi)] (2)
Это соотношение дает две рекуррентные формулы для коэффициентов:
di=-Ci/(ai*di-1+bi) (3)
ei=(fi-ai*ei-1)/(aidi-1+bi) (4)

с этими формулами носит название прямого хода прогонки.
do=yo, eo=бo,
Цикл прямого

хода повторяется N-1 раз. Последними будут вычислены коэффициенты dN-1 и eN-1, которые связывают функции в двух узлах вблизи правой границы:
Un-1=dn-1Un+en-1 (5)
Если на правой границе задано условие первого рода Un = с, то уже можно вычислить Un-1 и далее продолжать обратный ход прогонки при I = N - 1,..., 1, 0. Если условие более сложное, то надо рассмотреть уравнение (6), определяющее граничное условие на правой границе. Напомним его:
Un=ynUn-1+бn (6)
Соотношения (6) и (5) составляют систему из двух уравнений с двумя неизвестными. Используя определители, запишем ее решение.
Un-1=(en-1+бndn-1)/(1-yndn-1) (7)
Un=(бn+ynen-1)/(1-yndn-1)
Таким образом, мы нашли значения в двух узлах, лежащих вблизи правой границы расчетной области. Теперь, используя формулу (2) и уменьшая индекс i от N= 2 до 0, можно вычислить все неизвестные £/.. Этот процесс носит название обратного хода прогонки. Почему-то в голову приходит лозунг нашего времени: «Цели ясны, задачи определены.

Матрица A=[aij] называется (2m+1) – диагональной, если aij=0 при

|i-j|>m.
Для решения систем уравнений такого вида часто наиболее целесообразно применять метод Гаусса при естественном порядке исключения неизвестных. В случае, когда этот метод применяется для решения СЛАУ, его называют методом прогонки.

следующего рекуррентного соотношения:

,(2)
получаем:

Эти формулы представляют собой прямой проход метода. Обратный проход:
Остальные xi находим из формулы (2).
Для применимости метода прогонки достаточно, чтобы матрица A была с диагональным преобладанием.

элементы расширенной матрицы
2.     Проверяем матрицу на диагональное преобладание
3.     Если

матрица с диагональным преобладанием тогда п.4, иначе п.8
4.     Выполняем прямой ход метода (формулы (3), (4)): c[1]:=A[1,2]/A[1,1]; d[1]:=A[1,stlb]/A[1,1];
c[i]:= (-A[i,i+1])/(A[i,i-1]*c[i-1]+A[i,i]);
d[i]:= (A[i,stlb]-A[i,i-1]*d[i-1])/(A[i,i-1]*c[i-1]+A[i,i])
5.     Далее обратный ход (формулы (2),(5)):
x[str]:=(A[str,stlb]-A[str,str-1]*d[str-1])/(A[str,str]+A[str,str-1]*c[str-1]);
x[i]:=c[i]*x[i+1]+d[i];
6.     Выводим x;
7.     Проверки на невязку;
8.     Заканчиваем алгоритм.
В программе: A[i,i+1] = Bi, A[i,i] = Ci, A[i,i-1] = Ai, A[i,stlb] = bi, d[i] = ?i, c[i] = ?i, str = n.
Описание входной информации: Str (Stlb) – количество строк (столбцов) в расширенной матрице, A [i, j] – матрица A (i – строки, j – столбцы)

содержит большое число нулевых элементов, то применяют еще одну

модификацию метода Гаусса - метод прогонки. Рассмотрим систему уравнений с трехдиагональной матрицей:





Преобразуем первое уравнение системы к виду
  , где  , 
Подставим полученное выражение во второе уравнение системы и преобразуем его к виду 
и т.д.

, где 
На m-ом шаге подстановка

в последнее уравнение выражения   дает возможность определить значение   :
. Значения остальных неизвестных
находятся по формулам: 
, i = m-1, m-2, ..., 1.

или, что то же самое,

 (1)
используется метод прогонки, основанный на предположении, что искомые неизвестные связаны рекуррентным соотношением:
    , где   (2)
Используя это соотношение, выразим xi-1 и xi через xi+1 и подставим в уравнение (1):

где Fi — правая часть i-го уравнения. Это соотношение будет выполняться независимо от решения, если потребовать


Отсюда следует:
Из первого уравнения получим:

используя уравнение (2), получим решение системы. При этом,


      Другим

способом объяснения существа метода прогонки, более близким к терминологии конечно-разностных методов и объясняющим происхождение его названия, является следующий: преобразуем уравнение (1) к эквивалентному ему уравнению
         ( (1')
c надиагональной матрицей







Вычисления проводятся в два этапа. На первом этапе вычисляются компоненты матрицы  и вектора  , начиная с  i=2   до i=n 



На втором этапе, для  вычисляетсяi=n, n-1,…1 решение:

Такая схема вычисления объясняет также английский термин этого метода «shuttle».
Для применимости формул метода прогонки достаточно свойства диагонального преобладания у матрицы A.
Описание выходной информации: x – матрица-ответ