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

Метод прогонки или алгоритм Томаса (англ. Thomas algorithm) используется для решения систем линейных уравнений вида , где A — трёхдиагональная матрица.

Содержание

1 Описание метода
2 Пример реализации на Си
3 Литература
4 Ссылки

Описание метода

Система уравнений равносильна соотношению

Метод прогонки основывается на предположении, что искомые неизвестные связаны рекуррентным соотношением:

где

Используя это соотношение, выразим x_i-1 и x_i через x_i+1 и подставим в уравнение (1):

где F_i — правая часть i-го уравнения. Это соотношение будет выполняться независимо от решения, если потребовать

$\begin{cases} A_i\alpha_i\alpha_{i+1} + C_i\alpha_{i+1} + B_i = 0\\ A_i\alpha_i\beta_{i+1} + A_i\beta_i + C_i\beta_{i+1} - F_i = 0 \end{cases}$

Отсюда следует:

$\begin{cases} \alpha_{i+1} = \frac{-B_i}{A_i\alpha_i + C_i} \\ \beta_{i+1} = \frac{F_i - A_i\beta_i}{A_i\alpha_i + C_i}\end{cases}$

Из первого уравнения получим:

$\begin{cases} \alpha_2 = \frac{-B_1}{C_1} \\ \beta_2 = \frac{F_1}{C_1}\end{cases}$

После нахождения прогоночных коэффициентов и , используя уравнение (2), получим решение системы. При этом,

Другим способом объяснения существа метода прогонки, более близким к терминологии конечно-разностных методов и объясняющим происхождение его названия, является следующий: преобразуем уравнение (1) к эквивалентному ему уравнению

c надиагональной (наддиагональной) матрицей

$A' = \begin{pmatrix} C_1' & B_1 & 0 & 0 & \cdots & 0 & 0 \\ 0 & C_2' & B_2 & 0 & \cdots & 0 & 0 \\ 0 & 0 & C_3' & B_3 & \cdots & 0 & 0 \\ \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots \\ \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots \\ \cdots & \cdots & \cdots & \cdots & 0 & C'_{n-1} & B_{n-1} \\ 0 & 0 & 0 & 0 & \cdots & 0 & C_{n}' \end{pmatrix}$ .

Вычисления проводятся в два этапа. На первом этапе вычисляются компоненты матрицы и вектора , начиная с до

На втором этапе, для вычисляется решение:

Такая схема вычисления объясняет также английский термин этого метода «shuttle».

Для применимости формул метода прогонки достаточно свойства строгого диагонального преобладания у матрицы A.

Пример реализации на Си

Данный код работает при предположении, что a[0] = 0, b[n-1] = 0.

        /**
         * n - число уравнений (строк матрицы)
         * b - диагональ, лежащая над главной (нумеруется: [0;n-2])
         * c - главная диагональ матрицы A (нумеруется: [0;n-1])
         * a - диагональ, лежащая под главной (нумеруется: [1;n-1])
         * f - правая часть (столбец)
         * x - решение, массив x будет содержать ответ
         */
void solveMatrix (int n, double *a, double *c, double *b, double *f, double *x)
{
        double m;
        for (int i = 1; i < n; i++)
        {
                m = a[i]/c[i-1];  
                c[i] = c[i] - m*b[i-1];
                f[i] = f[i] - m*f[i-1];
        }
 
        x[n-1] = f[n-1]/c[n-1]; 
 
        for (int i = n - 2; i >= 0; i--) 
                x[i]=(f[i]-b[i]*x[i+1])/c[i];
 
}

Литература

Introduction to Numerical Methods in Chemical Engineering 1.1 "Tridiagonal matrix algorithm (TDMA)" (англ.)

Ссылки

The Thomas Algorithm (англ.)

Light-industry-up.ru

Экосистема промышленности