Метод прогонки. 
Численные методы: введение в теорию разностных схем

Наиболее прост алгоритм вычисления разностного решения у явных схем. Однако явные методы устойчивы лишь при определенных соотношениях между шагами сетки. Выполнение требований устойчивости приводит к необходимости очень мелкой дискретизации временной переменной, что увеличивает время счета.

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

Эффективным методом решения систем уравнений, порожденных разностными схемами, является метод прогонки. Рассмотрим его алгоритм на примере разностного решения первой краевой задачи для уравнения теплопроводности. Для краевой задачи в прямоугольной области.

рассмотрим неявную разностную схему.

Здесь Ai = Ci = 1, Bi = 1 + /?.²/(2ат), Д = li²{-u"  — г/")/(2ат). В нашем случае Aj, Д и С* не зависят от индекса i, однако если шаг сетки будет переменным, то все коэффициенты будут зависеть от номера узла. Важно отметить, что А{, Bj, Ci, g^n+l, /ⁿ⁺¹ — известные величины. Соотношение (7.2) представляет собой систему линейных уравнений для неизвестных Uq⁺, Мдг⁺ .

Распшренная матрица этой системы имеет вид.

В этой матрице ненулевые элементы расположены по главной диагонали и двум соседним. Матрицу такого вида называют трехдиагональной.

Наличие левого граничного условия (mq⁺¹ = </<sup>n+1) позволяет искать решение в виде (для простоты обозначений верхний индекс у неизвестной опущен) соотношения.

Оно называется прогоночным соотношением, а входящие в него входящие в него коэффициенты A'*_i и Li- — прогоночными коэффициентами. Для i = 1 (7.1) выполняется, если принять.

Таким образом устанавливаются начальные значения про гоночных коэффициентов.

Исключим с помощью прогоиочного соотношения (7.3) неизвестную щ-1 из (7.2):

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

в форме, совпадающей с прогоночным соотношением. Сравнение (7.5) и (7.3) дает рекуррентные соотношения для прогоночных коэффициентов:

Пользуясь начальными значениями Ко = 0, Lq = </, можно последовательно вычислить К, L], К2,^2, …, Ln- — компоненты векторов прогоночных коэффициентов. Этот вычислительный процесс называют прямой прогонкой. Нетрудно убедиться, что прямая прогонка с помощью элементарных преобразований переводит трехдиагональную матрицу исходной линейной системы в верхнюю двухдиагональную, причем число арифметических операций (из-за особого вида исходной матрицы) пропорционально числу неизвестных¹.

Двухдиагональный вид полученной матрицы позволяет легко построить процесс вычисления неизвестных. Прогоночное соотношение для последнего узла wjv-i = Kn-Un + L^~ 1, совместно с правым краевым условием = I, позволяет вычислить идг_ 1, а затем по рекуррентной формуле (7.3) последовательно определить все неизвестные un-2, un-3, …, щ разностной задачи. Последовательное вычисление неизвестных с помощью прогоночного соотношения (7.3) называют обратной прогонкой. По своей сути, метод прогонки представляет собой вариант гауссового исключения, который учитывает особенности структуры трехдиагональной матрицы и устраняет операции над ее нулевыми элементами.

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

Другим важным обстоятельством, с доказательством которого можно ознакомиться в специальной литературе, является вычислительная устойчивость метода прогонки^[1][2]. Это означает, что точность полученного решения будет такой же, как и точность проводимых промежуточных вычислений.

Впервые метод прогонки был предложен советскими математиками Гельфондом и Локуциевским в 1950;е годы для численного решения краевых задач. Экономичность и устойчивость метода сделали его в свое время основным элементом решения неявных разностных схем. Применение идей расщепления по пространственным переменным позволило распространить прогоиочные алгоритмы и на класс многомерных задач. В последние годы, благодаря стремительному росту ресурсов вычислительной техники (в основном, это касается оперативной памяти), стали широко применяться и другие алгоритмы решения алгебраических систем большой размерности с разреженной матрицей, которая, в отличие от метода прогонки, не связана таким жестким требованием, как трехдиагональность.

• [1] Отклонения от двухдиагональности для последней переменной в случае краевого условия второго или третьего рода легко преодолеваются.
• [2] Условис устойчивости выполняется, если матрица обладает свойством диагонального преобладания. Это свойство выполняется для матриц, порожденныхразностными схемами рассматриваемого класса.