wiki

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

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

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

Система уравнений  Ax=F{displaystyle ~Ax=F}

  равносильна соотношению

 Aixi−1+Cixi+Bixi+1=Fi.(1){displaystyle ~A_{i}x_{i-1}+C_{i}x_{i}+B_{i}x_{i+1}=F_{i}.qquad qquad (1)} 

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

xi=αi+1xi+1+βi+1,{displaystyle x_{i}=alpha _{i+1}x_{i+1}+beta _{i+1},,!}  где  i=n−1,n−2,…,1.(2){displaystyle ~i=n-1,n-2,dots ,1.qquad qquad (2)} 

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

(Aiαiαi+1+Ciαi+1+Bi)xi+1+Aiαiβi+1+Aiβi+Ciβi+1−Fi=0{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} ,

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

{Aiαiαi+1+Ciαi+1+Bi=0Aiαiβi+1+Aiβi+Ciβi+1−Fi=0{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}=0end{cases}}} 

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

{αi+1=−BiAiαi+Ciβi+1=Fi−AiβiAiαi+Ci{displaystyle {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}}} 

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

{α2=−B1C1β2=F1C1{displaystyle {begin{cases}alpha _{2}={frac {-B_{1}}{C_{1}}}\beta _{2}={frac {F_{1}}{C_{1}}}end{cases}}} 

После нахождения прогоночных коэффициентов α{displaystyle alpha }

  и β{displaystyle beta } , используя уравнение (2), получим решение системы. При этом,

xi=αi+1xi+1+βi+1,{displaystyle x_{i}={alpha _{i+1}x_{i+1}+beta _{i+1}},!}  i=n−1..1{displaystyle i=n-1..1,!} 
xn=Fn−AnβnCn+Anαn{displaystyle x_{n}={frac {F
_{n}-A_{n}beta _{n}}{C_{n}+A_{n}alpha _{n}}}} 

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

 A′x=F′(1′){displaystyle ~A’x=F’qquad qquad (1′)} 

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

A′=(C1′B100⋯000C2′B20⋯0000C3′B3⋯00⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯0Cn−1′Bn−10000⋯0Cn′){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 &0&C’_{n-1}&B_{n-1}\0&0&0&0&cdots &0&C_{n}’end{pmatrix}}} .

Вычисления проводятся в два этапа. На первом этапе вычисляются компоненты матрицы  Ci′{displaystyle ~C_{i}’}

  и вектора  F′{displaystyle ~F’} , начиная с  i=2{displaystyle ~i=2}  до  i=n:{displaystyle ~i=n:} 

 C1′=C1;{displaystyle ~C’_{1}=C_{1};} 
Ci′=Ci−AiCi−1′Bi−1,{displaystyle C’_{i}=C_{i}-{frac {A_{i}}{C’_{i-1}}}B_{i-1},} 

и

 F1′=F1;{displaystyle ~F’_{1}=F_{1};} 
Fi′=Fi−AiCi−1′Fi−1′.{displaystyle F’_{i}=F_{i}-{frac {A_{i}}{C’_{i-1}}}F’_{i-1}.} 

На втором этапе, для i=n,n−1,…,1{displaystyle i=n,n-1,dots ,1}

  вычисляется решение:

xn=Fn′Cn′;{displaystyle x_{n}={frac {F’_{n}}{C’_{n}}};} 

xi=Fi′−Bixi+1Ci′.{displaystyle x_{i}={frac {F’_{i}-B_{i}x_{i+1}}{C’_{i}}}.} 

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

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

Ссылки

Читайте также