Не следует путать с матрицей Якоби отображения.
Трёхдиагональной матрицей или матрицей Якоби[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.
См. также
Примечания
- ↑ Прасолов В. В. Задачи и теоремы линейной алгебры. — М.: Наука, 1996. — ISBN 5-02-014727-3.
Для улучшения этой статьи желательно:
После исправления проблемы исключите её из списка. Удалите шаблон, если устранены все недостатки. |