Метод разностной прогонки

Решаем систему линейных уравнений, основная матрица которой является невырожденной(сущесвует единственное решение) и трехдиагональной вида:

$$\left(\begin{array}{ccccccc}{a}_1& b_1& 0& \cdots & 0& 0& 0\\ c_1& a_2& b_2& \cdots & 0& 0& 0\\ 0& c_2& a_3& \cdots & 0& 0& 0\\ ⋮& ⋮& ⋮& \ddots & ⋮& ⋮& ⋮\\ 0& 0& 0& \cdots & c_{n-2}& a_{n-1}& b_{n-1}\\ 0& 0& 0& \cdots & 0& c_{n-1}& a_n\end{array}\right)\left(\begin{array}{c}{x}_1\\ x_2\\ x_3\\ ⋮\\ x_{n-1}\\ x_n\end{array}\right)=\left(\begin{array}{c}{d}_1\\ d_2\\ d_3\\ ⋮\\ d_{n-1}\\ d_n\end{array}\right)$$

Алгоритм разностной прогонки, также известный как алгоритм Томаса, представляет собой эффективный метод решения таких систем

Работа алгоритма

Прямой ход

На этом этапе исключаются элементы под главной диагональю, преобразуя систему к виду, где каждое $x_i$​ выражается через $x_{i+1}$. Для этого вводятся вспомогательные коэффициенты ${\alpha }_i$ и ${\beta }_i$, $i=1,\dots ,n$

Инициализация

​Рассмотрим $1$-е уравнение системы:

$$a_1{x}_1+b_1{x}_2=d_1$$

Выразим из него $x_1$:

$$x_1=\frac{d_1}{a_1}-\frac{b_1}{a_1}{x}_2\text{\hspace{1em}(1)}$$

Обозначим:

$${\beta }_1=\frac{d_1}{a_1},{\alpha }_1=\frac{b_1}{a_1}$$

Тогда $(1)$ станет выглядеть так:

$$x_1={\beta }_1-{\alpha }_1{x}_2$$

Рассмотрим $2$-е уравнение системы:

$$c_1{x}_1+a_2{x}_2+b_2{x}_3=d_2$$

Подставим выраженный на предыдущем шаге выше $x_1$:

$$c_1({\beta }_1-{\alpha }_1{x}_2)+a_2{x}_2+b_2{x}_3=d_2$$

Упростим, приведем подобные, слева оставим $x_2$, $x_3$:

$$(a_2-{\alpha }_1{c}_1)x_2+b_2{x}_3=d_2-c_1{\beta }_1$$

Выразим $x_2$:

$$x_2=\frac{d_2-c_1{\beta }_1}{a_2-{\alpha }_1{c}_1}-\frac{b_2}{a_2-{\alpha }_1{c}_1}{x}_3\text{\hspace{1em}(2)}$$

Обозначим:

$${\beta }_2=\frac{d_2-c_1{\beta }_1}{a_2-{\alpha }_1{c}_1},{\alpha }_2=\frac{b_2}{a_2-{\alpha }_1{c}_1}$$

Тогда $(2)$ станет выглядеть так:

$$x_2={\beta }_2-{\alpha }_2{x}_3$$

Процесс

Рассмотрим $i$-е уравнение системы, $i=3,n-1$:

$$c_{i-1}{x}_{i-1}+a_i{x}_i+b_i{x}_{i+1}=d_i$$

Подставим выраженный на предыдущем шаге выше $x_{i-1}$:

$$c_{i-1}({\beta }_{i-1}-{\alpha }_{i-1}{x}_i)+a_i{x}_i+b_i{x}_{i+1}=d_i$$

Упростим, приведем подобные, слева оставим $x_i$, $x_{i+1}$:

$$(a_i-{\alpha }_{i-1}{c}_{i-1})x_i+b_i{x}_{i+1}=d_i-c_{i-1}{\beta }_{i-1}$$

Выразим $x_i$:

$$x_i=\frac{d_i-c_{i-1}{\beta }_{i-1}}{a_i-{\alpha }_{i-1}{c}_{i-1}}-\frac{b_i}{a_i-{\alpha }_{i-1}{c}_{i-1}}{x}_{i+1}\text{\hspace{1em}(3)}$$

Обозначим:

$${\beta }_i=\frac{d_i-c_{i-1}{\beta }_{i-1}}{a_i-{\alpha }_{i-1}{c}_{i-1}},{\alpha }_i=\frac{b_i}{a_i-{\alpha }_{i-1}{c}_{i-1}}$$

Тогда $(3)$ станет выглядеть так:

$$x_i={\beta }_i-{\alpha }_i{x}_{i+1}$$

Заключение

Рассмотрим $n$-е уравнение системы:

$$c_{n-1}{x}_{n-1}+a_n{x}_n=d_n$$

Подставим выраженный на предыдущем шаге выше $x_{n-1}$:

$$c_{n-1}({\beta }_{n-1}-{\alpha }_{n-1}{x}_n)+a_n{x}_n=d_n$$

Выразим $x_n$:

$$x_n=\frac{d_n-c_{n-1}{\beta }_{n-1}}{a_n-c_{n-1}{\alpha }_{n-1}}$$

На этом прямой ход алгоритма заканчивается. По итогу его работы имеем:

• Рассчитанные в процессе работы ${\alpha }_i,{\beta }_i,i=1,\dots ,n-1$
• Отношения $x_i$ c $x_{i+1}$, выраженные через ${\alpha }_i,{\beta }_i$: $x_i={\beta }_i-{\alpha }_i{x}_{i+1}$, $i=1,\dots ,n-1$
• значение $x_n$

Этих данных достаточно, чтобы на втором шаге алгоритма найти решение системы:

Обратный ход

Процесс

Для всех $i=n-1,\dots ,1$

Находим значение $x_i$:

$$x_i={\beta }_i-{\alpha }_i{x}_{i+1}$$

Заключение

На этом обратный ход алгоритма заканчивается. По итогу его работы нашли искомое решение:

$$(x_1,x_2,\dots ,x_n)$$