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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Описание метода[править | править исходный текст]

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

~A_{i}x_{i-1}+C_{i}x_{i}+B_{i}x_{i+1} = F_{i}.\qquad\qquad(1)

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

x_i = \alpha_{i+1}x_{i+1} + \beta_{i+1},\,\! где ~i=n-1,n-2,\dots,1.\qquad\qquad(2)

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

\left(A_i\alpha_i\alpha_{i+1} + C_i\alpha_{i+1} + B_i\right)x_{i+1} + A_i\alpha_i\beta_{i+1} + A_i\beta_i + C_i\beta_{i+1} - F_i = 0,

где 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}

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

x_i = {\alpha_{i+1}x_{i+1} + \beta_{i+1}},\! i=n-1..1 \,\!
 x_n = \frac{F_n-A_n\beta_n}{C_n+A_n\alpha_n}

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

~A' x=F'\qquad\qquad(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}
  .

Вычисления проводятся в два этапа. На первом этапе вычисляются компоненты матрицы ~C_i' и вектора ~F', начиная с ~i=2 до ~i=n:

~C'_1=C_1;
C'_i=C_i-\frac{A_i}{C'_{i-1}} B_{i-1},

и

~F'_1=F_1;
F'_i=F_i-\frac{A_i}{C'_{i-1}} F'_{i-1}.

На втором этапе, для i=n, n-1, \dots, 1 вычисляется решение:

x_n=\frac{F'_n}{C'_n};


x_i=\frac{F'_i-B_i x_{i+1}}{C'_i}.

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

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

Ссылки[править | править исходный текст]