Трёхдиагональная матрица

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

${\displaystyle x_{i}=\alpha _{i+1}x_{i+1}+\beta _{i+1}\,\!}$      , где ${\displaystyle ~i=n-1,n-2,\dots ,1}$                                      (2)

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

${\displaystyle \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}$ ,

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

${\displaystyle {\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}}}$ 

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

${\displaystyle \alpha _{i+1}={\frac {-B_{i}}{A_{i}\alpha _{i}+C_{i}}}}$ 

${\displaystyle \beta _{i+1}={\frac {F_{i}-A_{i}\beta _{i}}{A_{i}\alpha _{i}+C_{i}}}}$ 

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

${\displaystyle \alpha _{2}={\frac {-B_{1}}{C_{1}}}}$ 

${\displaystyle \beta _{2}={\frac {F_{1}}{C_{1}}}}$ 

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

${\displaystyle x_{i}={\alpha _{i+1}x_{i+1}+\beta _{i+1}},\!}$      ${\displaystyle i=n-1..1\,\!}$ 

${\displaystyle x_{n}={\frac {F_{n}-A_{n}\beta _{n}}{C_{n}+A_{n}\alpha _{n}}}}$ 

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

${\displaystyle ~A'x=F'}$         (1')

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

${\displaystyle 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 &\cdots &C'_{n-1}&B_{n-1}\\0&0&0&0&\cdots &0&C_{n}'\end{pmatrix}}}$ .

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

${\displaystyle ~C'_{1}=C_{1};}$ 

${\displaystyle C'_{i}=C_{i}-{\frac {A_{i}B_{i-1}}{C'_{i-1}}},}$ 

и

${\displaystyle ~F'_{1}=F_{1};}$ 

${\displaystyle F'_{i}=F_{i}-{\frac {A_{i}F'_{i-1}}{C'_{i-1}}}.}$ 

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

${\displaystyle x_{n}={\frac {F'_{n}}{C'_{n}}};}$ 

${\displaystyle x_{i}={\frac {F'_{i}-B_{i}x_{i+1}}{C'_{i}}}.}$ 

Такая схема вычисления объясняет также английский термин этого метода «shuttle». Стоит отметить, однако, что на англоязычной версии Википедии этот алгоритм фигурирует как Tridiagonal matrix algorithm, или, Thomas algorithm (http://en.wikipedia.org/wiki/Tridiagonal_matrix_algorithm)

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

См. также

• Континуанта

Примечания