|
Прогонкой называется модификация метода Гаусса
для решения систем линейных алгебраических
уравнений с трехдиагональной матрицей. Если
матрица системы обладает определенными
свойствами, то метод прогонки является численно
устойчивым и очень эффективным методом, который
позволяет практически мгновенно решать
одномерные краевые задачи, одну из которых мы
рассмотрели в предыдущем разделе. Большинство
корректно поставленных физических задач приводит
к системе уравнений с хорошей матрицей, и в этих
случаях метод прогонки проявляет слабую
чувствительность как к погрешностям задания
начальных условий, так и к погрешностям
вычислительного характера.
В предыдущем разделе была сформулирована так
называемая первая краевая задача, в которой
требуется найти значения функции во внутренних
узлах сетки при условии, что на границах области
они известны. В теории и на практике
рассматриваются задачи с более сложными
граничными условиями. Например, когда на одной
из границ известна не функция, а ее первая
производная — граничное условие второго рода.
Имеют место и постановки задач с граничными
условиями третьего рода, когда на границе должно
выполняться какое-то известное заранее
соотношение между функцией и ее первой
производной. С точки зрения численной реализации
все три типа задач можно описать с помощью
соотношений одного и того же вида:
U0=y0U1+б0,
(6)
Un=ynUn-1+бn,
(7)
Они связывают значения разностных аналогов Ui,
непрерывной функции U(x) в двух узлах,
прилегающих к левой или правой границе. Так,
граничное условие первого рода иUo
= с может быть задано с помощью пары
параметров: у0=
0, б0 = с, а условие второго рода dU/dx|0= с
с помощью другой лары: у0
= 1,бo=ch, где h — это шаг сетки. В нашем
приложении будет работать немодальный диалог,
который позволит пользователю задавать различные
типы граничных условий, изменяя численные
значения четырех коэффициентов уo, бo,
yn, бn
Суть метода прогонки заключается в том, что,
используя специфику структуры матрицы системы
уравнений (наличие трех диагоналей), удается
получить рекуррентные формулы для вычисления
последовательности коэффициентов прогонки,
которые позволяют на обратном ходу вычислить
значения функции в узлах сетки. Рассматривая
конечно-разностное уравнение для первой тройки
узлов:
b1U1+c1U2=-a1U0,
видим, что оно совпадает по форме с обобщенным
граничным условием (6) и связывает между собой
два соседних значения U1, и U2.
Перепишем его в виде:
d1U2+e=U1,
(8)
где 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)]
(9)
Это соотношение дает две рекуррентные формулы
для коэффициентов:
di=-Ci/(ai*di-1+bi) (10)
ei=(fi-ai*ei-1)/(aidi-1+bi) (11)
Цикл вычисления последовательности коэффициентов
в соответствии с этими формулами носит название
прямого хода прогонки. Начальные значения
коэффициентов определяются предварительно
заданным граничным условием (6):
do=yo,
eo=бo,
Цикл прямого хода повторяется N-1 раз.
Последними будут вычислены коэффициенты dN-1
и eN-1,
которые связывают функции в двух узлах вблизи
правой границы:
Un-1=dn-1Un+en-1 (12)
Если на правой границе задано условие первого
рода Un = с, то уже можно
вычислить Un-1 по формуле (12)
и далее продолжать обратный ход прогонки,
используя уравнения (9) при I = N - 1,..., 1, 0.
Если условие более сложное, то вместе с
уравнением (12) надо рассмотреть уравнение (7),
определяющее граничное условие на правой
границе. Напомним его:
Un=ynUn-1+бn
(7)
Соотношения (7) и (12) составляют систему из
двух уравнений с двумя неизвестными. Используя
определители, запишем ее решение.
Un-1=(en-1+бndn-1)/(1-yndn-1) (13)
Un=(бn+ynen-1)/(1-yndn-1)
Таким образом, мы нашли значения в двух узлах,
лежащих вблизи правой границы расчетной области.
Теперь, используя формулу (9) и уменьшая индекс
i от N= 2 до 0, можно вычислить все неизвестные
£/.. Этот процесс носит название обратного хода
прогонки. Почему-то в голову приходит лозунг
нашего времени: «Цели ясны, задачи определены.
За работу, товарищи!» Нам осталось всего лишь
реализовать описанный алгоритм в виде
MFC-приложения. |