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

• Разделы:
  • См. также
  • Примечания

Не следует путать с матрицей Якоби отображения.

Трёхдиагональной матрицей или матрицей Якоби[1] называют матрицу следующего вида:

A=(C1B100…000A2C2B20…0000A3C3B3…000⋮⋮⋮⋮⋱⋮⋮⋮0000…An−1Cn−1Bn−10000…0AnCn){displaystyle A={begin{pmatrix}C_{1}&B_{1}&0&0&dots &0&0&0\A_{2}&C_{2}&B_{2}&0&dots &0&0&0\0&A_{3}&C_{3}&B_{3}&dots &0&0&0\vdots &vdots &vdots &vdots &ddots &vdots &vdots &vdots \0&0&0&0&dots &A_{n-1}&C_{n-1}&B_{n-1}\0&0&0&0&dots &0&A_{n}&C_{n}end{pmatrix}}}.

Системы линейных алгебраических уравнений с такими матрицами встречаются при решении многих задач математики и физики. Краевые условия x1{displaystyle x_{1}} и xn{displaystyle x_{n}}, которые берутся из контекста задачи, задают первую и последнюю строки. Так краевое условие первого рода F(x=x1)=F1{displaystyle F(x=x_{1})=F_{1}} определит первую строку в виде C1=1{displaystyle C_{1}=1}, B1=0{displaystyle B_{1}=0}, а условие второго рода dF/dx(x=x1)=F1{displaystyle dF/dx(x=x_{1})=F_{1}} будет соответствовать значениям C1=−1{displaystyle C_{1}=-1}, B1=1{displaystyle B_{1}=1}.

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

Для решения систем вида  Ax=F{displaystyle ~Ax=F}

  или, что то же самое,

 Aixi−1+Cixi+Bixi+1=Fi{displaystyle ~A_{i}x_{i-1}+C_{i}x_{i}+B_{i}x_{i+1}=F_{i}}  (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{displaystyle ~i=n-1,n-2,dots ,1}                                      (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{displaystyle alpha _{i+1}={frac {-B_{i}}{A_{i}alpha _{i}+C_{i}}}} 

βi+1=Fi−AiβiAiαi+Ci{displaystyle beta _{i+1}={frac {F_{i}-A_{i}beta _{i}}{A_{i}alpha _{i}+C_{i}}}} 

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

α2=−B1C1{displaystyle alpha _{2}={frac {-B_{1}}{C_{1}}}} 

β2=F1C1{displaystyle beta _{2}={frac {F_{1}}{C_{1}}}} 

После нахождения прогоночных коэффициентов α{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′{displaystyle ~A’x=F’}         (1′)

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

A′=(C1′B100⋯000C2′B20⋯0000C3′B3⋯00⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯Cn−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 &cdots &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−AiBi−1Ci−1′,{displaystyle C’_{i}=C_{i}-{frac {A_{i}B_{i-1}}{C’_{i-1}}},} 

и

 F1′=F1;{displaystyle ~F’_{1}=F_{1};} 

Fi′=Fi−AiFi−1′Ci−1′.{displaystyle F’_{i}=F_{i}-{frac {A_{i}F’_{i-1}}{C’_{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».Стоит отметить, однако, что на англоязычной версии Википедии этот алгоритм фигурирует как Tridiagonal matrix algorithm, или, Thomas algorithm (http://en.wikipedia.org/wiki/Tridiagonal_matrix_algorithm)

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

См. также

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

Примечания

1. ↑ Прасолов В. В. Задачи и теоремы линейной алгебры. — М.: Наука, 1996. — ISBN 5-02-014727-3.