Momotik.ru

Народный проект

Метки: Метод прогонки алгоритм, метод прогонки c++, метод прогонки как решать, метод прогонки уравнение пуассона.

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

Содержание

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

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

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

где 

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

,

где Fi — правая часть 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  (англ.)

Tags: Метод прогонки алгоритм, метод прогонки c++, метод прогонки как решать, метод прогонки уравнение пуассона.