Компактная схема метода Гаусса для трёхдиагональной матрицы и её модификации

1 Компактная схема метода Гаусса для трёхдиагональной матрицы и её модификации

Треугольное разложение трёхдиагональной матрицы базируется на формулах треугольного разложения для матриц общего вида [1] [2] . Обычно встречающиеся в прикладных задачах трёхдиагональные матрицы имеют свойство диагонального преобладания, поэтому не возникает необходимости в применении перестановок для повышения устойчивости разложения. Использование свойств, базирующихся, например, на формуле Бине-Коши в её приложении к минорам матриц [2] :

[math] A \begin \alpha_ & \alpha_ & \cdots & \alpha_ \\ \beta_ & \beta_ & \cdots & \beta_ \\ \end = \sum_ L \begin \alpha_ & \alpha_ & \cdots & \alpha_ \\ \gamma_ & \gamma_ & \cdots & \gamma_ \\ \end U\begin \gamma_ & \gamma_ & \cdots & \gamma_ \\ \beta_ & \beta_ & \cdots & \beta_ \\ \end [/math]

для миноров произведения двух матриц, показывает [1] , что для трёхдиагональной матрицы

[math] A = \begin a_ & a_ & 0 & \cdots & \cdots & 0 \\ a_ & a_ & a_& \cdots & \cdots & 0 \\ 0 & a_ & a_ & \cdots & \cdots & 0 \\ \vdots & \vdots & \ddots & \ddots & \ddots & 0 \\ 0 & \cdots & \cdots & a_ & a_ & a_ \\ 0 & \cdots & \cdots & 0 & a_ & a_ \\ \end [/math]

[math]LU[/math] -разложение будет содержать две двухдиагональные матрицы:

[math] L = \begin l_ & 0 & 0 & \cdots & \cdots & 0 \\ l_ & l_ & 0 & \cdots & \cdots & 0 \\ 0 & l_ & l_ & \cdots & \cdots & 0 \\ \vdots & \vdots & \ddots & \ddots & \ddots & 0 \\ 0 & \cdots & \cdots & l_ & l_ & 0 \\ 0 & \cdots & \cdots & 0 & l_ & l_ \\ \end, U = \begin u_ & u_ & 0 & \cdots & \cdots & 0 \\ 0 & u_ & u_& \cdots & \cdots & 0 \\ 0 & 0 & u_ & \cdots & \cdots & 0 \\ \vdots & \vdots & \ddots & \ddots & \ddots & 0 \\ 0 & \cdots & \cdots & 0 & u_ & u_ \\ 0 & \cdots & \cdots & 0 & 0 & u_ \\ \end [/math]

Поэтому формулы компактной схемы метода Гаусса и её модификаций существенно упрощаются.

1.1 [math]LU[/math] -разложение 1.1.1 Компактная схема метода Гаусса для трёхдиагональной матрицы

Компактная схема метода Гаусса для трёхдиагональной матрицы вычисляет такое [math]LU[/math] -разложение на две двухдиагональные матрицы, в котором у нижней двухдиагональной матрицы [math]L[/math] на диагонали стоят только единицы:

[math] L = \begin 1 & 0 & 0 & \cdots & \cdots & 0 \\ l_ & 1 & 0 & \cdots & \cdots & 0 \\ 0 & l_ & 1 & \cdots & \cdots & 0 \\ \vdots & \vdots & \ddots & \ddots & \ddots & 0 \\ 0 & \cdots & \cdots & l_ & 1 & 0 \\ 0 & \cdots & \cdots & 0 & l_ & 1 \\ \end [/math]

Формулы метода следующие:

[math]u_ = a_[/math] , [math]\quad i \in [1, n-1][/math]

[math]l_ = a_ / u_ [/math] , [math]\quad i \in [1, n-1] [/math]

[math]u_ = a_ - l_ u_[/math] , [math]\quad i \in [2, n] [/math]

Подробно её свойства описаны на соответствующей странице. В неизменённом виде не подлежит распараллеливанию, алгоритм чисто последовательный.Существует и блочная версия разложения - для блочно-трёхдиагональных матриц. Компактная схема метода Гаусса легко подвергается модификации, в которой не в матрице [math]L[/math] , а в матрице [math]U[/math] на диагонали только единицы. Это используется, например, в качестве части метода прогонки.
1.1.2 Алгоритм Стоуна для [math]LU[/math] -разложения трёхдиагональной матрицы
Алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы является частью алгоритма Стоуна [3] для решения трёхдиагональных СЛАУ и является первым параллельным алгоритмом [math]LU[/math] -разложения трёхдиагональной матрицы. Математическая его основа - линейная рекуррентная формула для главных миноров раскладываемой матрицы. После записи этой рекуррентной формулы в матричном виде оказывается, что можно воспользоваться ассоциативностью операции перемножения матриц. Стоун использовал для распараллеливания схему сдваивания. Однако область устойчивости этого метода гораздо уже, чем у компактной схемы метода Гаусса, несмотря на то, что искомые матрицы - те же самые. Блочная схема метода для блочно-трёхдиагональных матриц не разрабатывалась, хотя теоретически и может существовать, из-за неустойчивости схемы.

Подробно свойства алгоритма Стоуна описаны на соответствующей странице.
1.1.3 Последовательно-параллельный алгоритм для [math]LU[/math] -разложения трёхдиагональной матрицы
Последовательно-параллельный алгоритм для LU-разложения трёхдиагональной матрицы разработан [4] для распараллеливания нахождения того же [math]LU[/math] -разложения трёхдиагональной матрицы, что получается из компактной схемы метода Гаусса. Как и метод Стоуна, использует ассоциативность умножения матриц, но использует также нормировку в последовательных ветвях вычислений, что даёт схеме большую область устойчивости, чем у схемы Стоуна. Для блочно-трёхдиагональных матриц существует блочная версия метода, для которой, однако, необходима невырожденность блоков не только на главной, но и на одной из побочных диагоналей матрицы.
1.2 [math]LDU[/math] -разложение
В случае, если существует [math]LU[/math] -разложение на две двухдиагональные матрицы, в котором нижняя двухдиагональная матрица [math]L[/math] имеет на главной диагонали только единицы, легко можно найти и [math]LDU[/math] -разложение, в котором и верхняя двухдиагональная матрица также имеет на главной диагонали только единицы:

[math] U = \begin 1 & u_ & 0 & \cdots & \cdots & 0 \\ 0 & 1 & u_& \cdots & \cdots & 0 \\ 0 & 0 & 1 & \cdots & \cdots & 0 \\ \vdots & \vdots & \ddots & \ddots & \ddots & 0 \\ 0 & \cdots & \cdots & 0 & 1 & u_ \\ 0 & \cdots & \cdots & 0 & 0 & 1 \\ \end [/math]

Формулы видоизменённой компактной схемы метода Гаусса для нахождения этого разложения выглядят следующим образом:

[math]u_ = a_ / d_, \quad i \in [1, n-1] [/math]

[math]l_ = a_ / d_ , \quad i \in [1, n-1] [/math]

[math]d_ = a_ - l_ a_, \quad i \in [2, n] [/math]

Аналогично, добавлением делений можно видоизменить и формулы метода Стоуна и последовательно-параллельного метода разложения.

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

2 Компактная схема треугольного разложения для трёхдиагональной эрмитовой матрицы и её модификации

Эрмитовость трёхдиагональной матрицы позволяет вычислять такое её разложение, которое можно хранить в меньшей памяти с учетом симметрии разложения.
2.1 [math]LL^*[/math] -разложение
Для вычисления [math]LL^*[/math] -разложения матрицы логично использовать метод Холецкого, формулы которого после коррекции будут адаптированы под трёхдиагональность исходной матрицы и двухдиагональность результата:

[math]l_ = \sqrt , \quad i \in [2, n]. [/math]

Аналогичные изменения можно провести в методах Стоуна и последовательно-параллельного [math]LU[/math] -разложения. Однако на практике использование схемы с квадратными корнями для трёхдиагональных матриц не нужно, поскольку есть более быстрое [math]LDL^*[/math] -разложение.
2.2 [math]LDL^*[/math] -разложение
[math]LDL^*[/math] -разложение для трёхдиагональной эрмитовой матрицы - самое экономное из последовательных её разложений. Формулы разложения имеют вид:

[math]l_ = a_ / d_ , \quad i \in [1, n-1] [/math]

[math]d_ = a_ - l_ a_^*, \quad i \in [2, n] [/math]

Аналогично, можно видоизменить и формулы метода Стоуна и последовательно-параллельного метода разложения. Как и для [math]LDU[/math] -разложения, при решении СЛАУ с трёхдиагональной матрицей с помощью [math]LDL^*[/math] -разложения легче решаются полученные двухдиагональные СЛАУ.

3 Разложения для трёхдиагональных матриц специального вида

Для некоторых матриц специального вида, получаемых из известных операторов математической физики, в том числе и для трёхдиагональных матриц, известны аналитические выражения для их характеристик, в том числе и значения главных миноров. Несмотря на это, широко распространено явление, когда исследователи, работающие с такими матрицами, вместо того, чтобы воспользоваться готовыми формулами разложений, применяют к ним вышеописанные методы, нерационально тратя компьютерное время.

4 Использование разложений

Обычно разложения трёхдиагональных матриц в произведение двухдиагональных (и, возможно, ещё одной диагональной) используют для решения СЛАУ с трёхдиагональной матрицей, полученной из какой-либо физической модели. Поэтому зачастую полезность того или иного метода разложения следует сравнивать не только с другими методами разложения трёхдиагональных матриц, но и с различными методами решения СЛАУ с такими матрицами, в том числе и не использующими такие разложения - например, такими, как метод циклической редукции или метод окаймления.
📎📎📎📎📎📎📎📎📎📎