Методы решения СЛАУ с трёхдиагональными матрицами: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
Frolov (обсуждение | вклад) м Frolov переименовал страницу Решения СЛАУ с трёхдиагональными матрицами в Методы решения СЛАУ с трёхдиагональными матрицами: неточнос… |
Frolov (обсуждение | вклад) Нет описания правки |
||
| Строка 12: | Строка 12: | ||
</math> | </math> | ||
На этой странице представлены разные методы решения такой СЛАУ. | |||
=== | === Методы, основанные на стандартном <math>LU</math>-разложении трёхдиагональной матрицы <math>A</math> на две двухдиагональные === | ||
==== Метод прогонки ==== | |||
== | [[Прогонка]]<ref name="setki">Самарский А.А., Николаев Е.С. Методы решения сеточных уравнений. М.: Наука, 1978.</ref> – последовательный алгоритм решения трёхдиагональной СЛАУ – является частным случаем общего метода исключения неизвестных, однако получила специальное название из-за распространённости задач такого типа в прикладных исследованиях. В математической литературе<ref name="setki" /> указано, что применение метода прогонки эквивалентно последовательному решению двух задач: <math>LU</math>-разложению трёхдиагональной матрицы <math>A</math> на две двухдиагональные с помощью [[Компактная схема метода Гаусса для трёхдиагональной матрицы, последовательный вариант|компактной схемы метода Гаусса]] и затем решению двух СЛАУ с двухдиагональными матрицами с помощью обычной [[Обратная подстановка в СЛАУ с двухдиагональной матрицей|обратной подстановки]]. Метод почти последователен (исключением является то, что решение первой из двухдиагональных СЛАУ можно выполнять почти параллельно с разложением трёхдиагональной матрицы). | ||
==== Метод сдваивания Стоуна ==== | |||
[[Метод сдваивания Стоуна]]<ref>Stone H.S. An Efficient Parallel Algorithm for the Solution of a Tridiagonal Linear System of Equations // J. ACM, Vol. 20, No. 1 (Jan. 1973), P. 27-38.</ref><ref>Stone H.S. Parallel Tridiagonal Equation Solvers // ACM Trans. on Math. Software, Vol. 1, No. 4 (Dec. 1975), P. 289-307.</ref> разработан в начале 70-х гг. 20го века. Как и [[Прогонка|прогонка]], которую он должен был заменить, [[Метод сдваивания Стоуна|метод сдваивания Стоуна для решения СЛАУ с трёхдиагональными матрицами]] состоит из двух частей: [[Алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы|алгоритма сдваивания Стоуна для LU-разложения трёхдиагональной матрицы]] и [[Метод сдваивания Стоуна для решения двухдиагональных СЛАУ|метода сдваивания Стоуна для решения двухдиагональных СЛАУ]]. По ряду причин, изложенных на соответствующих страницах, первый из них не применяется на практике, а второй - малораспространён. | |||
[[Метод | |||
==== Последовательно-параллельный вариант прогонки ==== | |||
=== | === Другие методы === | ||
==== Метод циклической редукции ==== | |||
[[Метод циклической редукции]]<ref>Buneman O. A Compact Non-iterative Poisson Solver // Rep. 294, Inst. for Plasma Res., Stanford U., Stanford, Calif., 1969.</ref><ref>Buzbee B.L., Golub G.H., Nielson C.W. On Direct Methods for Solving Poisson's Equations // SIAM J. Numer. Anal., Vol. 7, No. 4 (Dec. 1970), P. 627-656.</ref> | |||
=== | ==== Метод окаймления ==== | ||
[[Метод окаймления]] | |||
== Литература == | == Литература == | ||
Версия от 11:54, 9 июля 2015
Методы решения СЛАУ с трёхдиагональными матрицами
Во многих математических моделях удаётся свести задачу к СЛАУ[1][2] [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} }[/math]
На этой странице представлены разные методы решения такой СЛАУ.
Методы, основанные на стандартном [math]\displaystyle{ LU }[/math]-разложении трёхдиагональной матрицы [math]\displaystyle{ A }[/math] на две двухдиагональные
Метод прогонки
Прогонка[3] – последовательный алгоритм решения трёхдиагональной СЛАУ – является частным случаем общего метода исключения неизвестных, однако получила специальное название из-за распространённости задач такого типа в прикладных исследованиях. В математической литературе[3] указано, что применение метода прогонки эквивалентно последовательному решению двух задач: [math]\displaystyle{ LU }[/math]-разложению трёхдиагональной матрицы [math]\displaystyle{ A }[/math] на две двухдиагональные с помощью компактной схемы метода Гаусса и затем решению двух СЛАУ с двухдиагональными матрицами с помощью обычной обратной подстановки. Метод почти последователен (исключением является то, что решение первой из двухдиагональных СЛАУ можно выполнять почти параллельно с разложением трёхдиагональной матрицы).
Метод сдваивания Стоуна
Метод сдваивания Стоуна[4][5] разработан в начале 70-х гг. 20го века. Как и прогонка, которую он должен был заменить, метод сдваивания Стоуна для решения СЛАУ с трёхдиагональными матрицами состоит из двух частей: алгоритма сдваивания Стоуна для LU-разложения трёхдиагональной матрицы и метода сдваивания Стоуна для решения двухдиагональных СЛАУ. По ряду причин, изложенных на соответствующих страницах, первый из них не применяется на практике, а второй - малораспространён.
Последовательно-параллельный вариант прогонки
Другие методы
Метод циклической редукции
Метод циклической редукции[6][7]
Метод окаймления
Литература
- ↑ Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.
- ↑ Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.
- ↑ 3,0 3,1 Самарский А.А., Николаев Е.С. Методы решения сеточных уравнений. М.: Наука, 1978.
- ↑ Stone H.S. An Efficient Parallel Algorithm for the Solution of a Tridiagonal Linear System of Equations // J. ACM, Vol. 20, No. 1 (Jan. 1973), P. 27-38.
- ↑ Stone H.S. Parallel Tridiagonal Equation Solvers // ACM Trans. on Math. Software, Vol. 1, No. 4 (Dec. 1975), P. 289-307.
- ↑ Buneman O. A Compact Non-iterative Poisson Solver // Rep. 294, Inst. for Plasma Res., Stanford U., Stanford, Calif., 1969.
- ↑ Buzbee B.L., Golub G.H., Nielson C.W. On Direct Methods for Solving Poisson's Equations // SIAM J. Numer. Anal., Vol. 7, No. 4 (Dec. 1970), P. 627-656.