Метод сдваивания Стоуна для решения двудиагональных СЛАУ

Свойства и структура алгоритмов

Общее описание алгоритма

Алгоритм сдваивания Стоуна для решения двухдиагональных СЛАУ - часть метода сдваивания Стоуна для решения СЛАУ вида [math]\displaystyle{ Ax = b }[/math], где

[math]\displaystyle{ A = \begin{bmatrix} a_{11} & a_{12} & 0 & \cdots & \cdots & 0 \\ a_{21} & a_{22} & a_{23}& \cdots & \cdots & 0 \\ 0 & a_{32} & a_{33} & \cdots & \cdots & 0 \\ \vdots & \vdots & \ddots & \ddots & \ddots & 0 \\ 0 & \cdots & \cdots & a_{n-1 n-2} & a_{n-1 n-1} & a_{n-1 n} \\ 0 & \cdots & \cdots & 0 & a_{n n-1} & a_{n n} \\ \end{bmatrix}, x = \begin{bmatrix} x_{1} \\ x_{2} \\ \vdots \\ x_{n} \\ \end{bmatrix}, b = \begin{bmatrix} b_{1} \\ b_{2} \\ \vdots \\ b_{n} \\ \end{bmatrix} }[/math]

Метод сдваивания Стоуна впервые предложен в начале 70-х гг. 20го века в качестве альтернативы другим параллельным алгоритмам решения трёхдиагональных СЛАУ, например, методу циклической редукции.

Здесь рассматривается его вторая часть - решение двух двухдиагональных СЛАУ. Оно использует представление матрицы

[math]\displaystyle{ A = \begin{bmatrix} a_{11} & a_{12} & 0 & \cdots & \cdots & 0 \\ a_{21} & a_{22} & a_{23}& \cdots & \cdots & 0 \\ 0 & a_{32} & a_{33} & \cdots & \cdots & 0 \\ \vdots & \vdots & \ddots & \ddots & \ddots & 0 \\ 0 & \cdots & \cdots & a_{n-1 n-2} & a_{n-1 n-1} & a_{n-1 n} \\ 0 & \cdots & \cdots & 0 & a_{n n-1} & a_{n n} \\ \end{bmatrix} }[/math]

в виде произведения матриц

[math]\displaystyle{ L = \begin{bmatrix} 1 & 0 & 0 & \cdots & \cdots & 0 \\ l_{21} & 1 & 0 & \cdots & \cdots & 0 \\ 0 & l_{32} & 1 & \cdots & \cdots & 0 \\ \vdots & \vdots & \ddots & \ddots & \ddots & 0 \\ 0 & \cdots & \cdots & l_{n-1 n-2} & 1 & 0 \\ 0 & \cdots & \cdots & 0 & l_{n n-1} & 1 \\ \end{bmatrix} }[/math]

и

[math]\displaystyle{ U = \begin{bmatrix} u_{11} & u_{12} & 0 & \cdots & \cdots & 0 \\ 0 & u_{22} & u_{23}& \cdots & \cdots & 0 \\ 0 & 0 & u_{33} & \cdots & \cdots & 0 \\ \vdots & \vdots & \ddots & \ddots & \ddots & 0 \\ 0 & \cdots & \cdots & 0 & u_{n-1 n-1} & u_{n-1 n} \\ 0 & \cdots & \cdots & 0 & 0 & u_{n n} \\ \end{bmatrix} }[/math]

Важным моментом является то, что алгоритм Стоуна использует то же самое разложение, что вычисляется не только в первой части метода (алгоритме сдваивания Стоуна для LU-разложения трёхдиагональной матрицы), но и в устойчивой компактной схеме метода Гаусса.

При уже полученном разложении матрицы решение СЛАУ [math]\displaystyle{ Ax = b }[/math] можно поменять на последовательное решение двух СЛАУ [math]\displaystyle{ Ly = b }[/math] и затем [math]\displaystyle{ Ux = y }[/math]. При этом вторую СЛАУ тоже можно решить как последовательность СЛАУ [math]\displaystyle{ Dz = y }[/math] и [math]\displaystyle{ D^{-1}Ux = z }[/math], где [math]\displaystyle{ D }[/math] - диагональная матрица, составленная из диагональных элементов матрицы [math]\displaystyle{ U }[/math].

Схема реализации последовательного алгоритма

Метод Стоуна изначально спроектирован для параллельного исполнения, поскольку является по отношению к, например, классической прогонке, алгоритмом с избыточными вычислениями. Смысла в его последовательной реализации нет ещё и из-за того, что он неустойчив.

Программная реализация алгоритма

Особенности реализации последовательного алгоритма

Из-за большой избыточности вычислений метод Стоуна никогда не предназначался для последовательной реализации. После обнаружения неустойчивости его первой части стало ясно, что и в будущем он не будет реализован на последовательных архитектурах.

Существующие реализации алгоритма

Из-за неустойчивости первой части метода его не используют на практике, поэтому планировавшаяся в исходной публикации замена более популярной циклической редукции не удалась. Реализаций схемы Стоуна отсутствуют в пакетах программ, даже в её второй (устойчивой) части.