Иллюстрированный самоучитель по Visual Studio.Net
Метод
прогонки
Прогонкой называется
модификация метода Гаусса для решения систем линейных алгебраических уравнений
с трехдиагональной матрицей. Если матрица системы обладает определенными свойствами,
то метод прогонки является численно устойчивым и очень эффективным методом,
который позволяет практически мгновенно решать одномерные краевые задачи, одну
из которых мы рассмотрели в предыдущем разделе. Большинство корректно поставленных
физических задач приводит к системе уравнений с хорошей матрицей, и в этих случаях
метод прогонки проявляет слабую чувствительность как к погрешностям задания
начальных условий, так и к погрешностям вычислительного характера.
В предыдущем
разделе была сформулирована так называемая первая краевая задача, в которой
требуется найти значения функции во внутренних узлах сетки при условии, что
на границах области они известны. В теории и на практике рассматриваются задачи
с более сложными граничными условиями. Например, когда на одной из границ известна
не функция, а ее первая производная — граничное условие второго рода. Имеют
место и постановки задач с граничными условиями третьего рода, когда на границе
должно выполняться какое-то известное заранее соотношение между функцией и ее
первой производной. С точки зрения численной реализации все три типа задач можно
описать с помощью соотношений одного и того же вида:
U
0
=y
0
U
1
+б
0
,
(6)
U
n
=y
n
U
n-1
+б
n
,
(7)
Они связывают
значения разностных аналогов Ui, непрерывной функции U(x) в двух узлах, прилегающих
к левой или правой границе. Так, граничное условие первого рода
и
Uo
= с
может быть задано с помощью пары параметров: у
0
=
0, б
0
= с, а условие второго рода dU/dx|
0
=
с
с помощью другой лары: у
0
= 1,бo=ch, где h —
это шаг сетки. В нашем приложении будет работать немодальный диалог, который
позволит пользователю задавать различные типы граничных условий, изменяя численные
значения четырех коэффициентов у
o
, бo, yn
,
бn
Суть метода
прогонки заключается в том, что, используя специфику структуры матрицы системы
уравнений (наличие трех диагоналей), удается получить рекуррентные формулы для
вычисления последовательности коэффициентов прогонки
,
которые позволяют
на обратном ходу вычислить значения функции в узлах сетки. Рассматривая конечно-разностное
уравнение для первой тройки узлов:
b
1
U
1
+c
1
U
2
=-a
1
U
0
,
видим, что
оно совпадает по форме с обобщенным граничным условием (6) и связывает между
собой два соседних значения U
1
, и U
2
.
Перепишем его в виде:
d
1
U
2
+e=U
1
,
(8)
где d
1
и е
1
вычисляются по известным значениям. Наблюдательный
читатель заметит, что это справедливо только для задач первого рода. Чуть позже
мы получим общее решение. Теперь мы можем исключить £/, из уравнения для
следующей тройки узлов:
a
2
U
1
+b
2
U
2
+c
2
U
2
=f
2
,
подставив значение
U
1
из уравнения (8). После этой процедуры последнее уравнение
также может быть приведено к виду:
d
3
U
3
+e
2
=U
2
,
Подстановки
можно продолжать и дальше, но для получения рекуррентного соотношения, достаточно
рассмотреть одну из них для произвольного индекса i. Подставив
d
i-1
U
i
+e
i-1
=U
i-1
,
в уравнение
a
i
U
i-1
+b
i
U
i
+c
i
U
i+1
=f
i
,
получим:
U
i
=-[C
iUi+1
/(a
i
d
i-1
+b
i
)]+
[f
i-ai+1
*ei+1
/(a
i
d
i-1
+b
i
)]
(9)
Это соотношение
дает две рекуррентные формулы для коэффициентов:
d
i
=-C
i
/(a
i
*d
i-1
+b
i
)
(10)
e
i
=(f
i-
a
i*ei-1)
/(a
i
d
i-1
+b
i
)
(11)
Цикл вычисления
последовательности коэффициентов в соответствии с этими формулами носит название
прямого хода прогонки. Начальные значения коэффициентов определяются предварительно
заданным граничным условием (6):
d
o
=y
o
,
e
o
=б
o
,
Цикл прямого
хода повторяется N-1 раз. Последними будут вычислены коэффициенты d
N-1
и e
N-1
, которые связывают функции в двух узлах
вблизи правой границы:
Un-1=d
n-1
U
n
+en-1
(12)
Если на правой
границе задано условие первого рода
U
n
= с,
то уже можно вычислить
U
n-1
по формуле (12) и далее продолжать обратный ход прогонки,
используя уравнения (9) при I = N - 1,..., 1, 0. Если условие более сложное,
то вместе с уравнением (12) надо рассмотреть уравнение (7), определяющее граничное
условие на правой границе. Напомним его:
U
n
=y
n
U
n-1
+б
n
(7)
Соотношения
(7) и (12) составляют систему из двух уравнений с двумя неизвестными. Используя
определители, запишем ее решение.
U
n-1
=(e
n-1
+б
n
d
n-1
)/(1-y
n
dn-1)
(13)
U
n
=(б
n
+y
n
e
n-1
)/(1-y
n
d
n-1
)
Таким образом,
мы нашли значения в двух узлах, лежащих вблизи правой границы расчетной области.
Теперь, используя формулу (9) и уменьшая индекс i от N= 2 до 0, можно вычислить
все неизвестные £/.. Этот процесс носит название обратного хода прогонки.
Почему-то в голову приходит лозунг нашего времени: «Цели ясны, задачи определены.
За работу, товарищи!» Нам осталось всего лишь реализовать описанный алгоритм
в виде MFC-приложения.