Метод сдваивания Стоуна

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

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

Метод сдваивания Стоуна - один из вариантов замены прогонки в приложении к решению СЛАУ вида [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{ LU }[/math]-разложении матрицы исходной СЛАУ и состоит из двух существенно различных по свойствам частей: алгоритма сдваивания Стоуна для LU-разложения трёхдиагональной матрицы и метода сдваивания Стоуна для решения двухдиагональных СЛАУ.