Метод прогонки

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

В предыдущем разделе была сформулирована так называемая первая краевая задача, в которой требуется найти значения функции во внутренних узлах сетки при условии, что на границах области они известны. В теории и на практике рассматриваются задачи с более сложными граничными условиями. Например, когда на одной из границ известна не функция, а ее первая производная — граничное условие второго рода. Имеют место и постановки задач с граничными условиями третьего рода, когда на границе должно выполняться какое-то известное заранее соотношение между функцией и ее первой производной. С точки зрения численной реализации все три типа задач можно описать с помощью соотношений одного и того же вида:

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-приложения.