Метод прогонки
Метод прогонки
Прогонкой называется модификация метода Гаусса для решения систем линейных алгебраических уравнений с трехдиагональной матрицей. Если матрица системы обладает определенными свойствами, то метод прогонки является численно устойчивым и очень эффективным методом, который позволяет практически мгновенно решать одномерные краевые задачи, одну из которых мы рассмотрели в предыдущем разделе. Большинство корректно поставленных физических задач приводит к системе уравнений с хорошей матрицей, и в этих случаях метод прогонки проявляет слабую чувствительность как к погрешностям задания начальных условий, так и к погрешностям вычислительного характера.
В предыдущем разделе была сформулирована так называемая первая краевая задача, в которой требуется найти значения функции во внутренних узлах сетки при условии, что на границах области они известны. В теории и на практике рассматриваются задачи с более сложными граничными условиями. Например, когда на одной из границ известна не функция, а ее первая производная — граничное условие второго рода. Имеют место и постановки задач с граничными условиями третьего рода, когда на границе должно выполняться какое-то известное заранее соотношение между функцией и ее первой производной. С точки зрения численной реализации все три типа задач можно описать с помощью соотношений одного и того же вида:
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-приложения.
