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

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
Строка 65: Строка 65:
  
 
=== <math>LDL^*</math>-разложение ===
 
=== <math>LDL^*</math>-разложение ===
 +
 +
<math>LDL^*</math>-разложение для трёхдиагональной эримтовой матрицы - самое экономное из последовательных её разложений. Его формулы таковы:
 +
 +
:<math>
 +
d_{11} = a_{11} \\
 +
l_{i+1 i} = a_{i+1 i} / d_{i i} , \quad i \in [1, n-1] \\
 +
d_{ii} = a_{ii} - l_{i i-1} a_{i i-1}^*, \quad i \in [2, n] \\
 +
</math>
 +
 +
Аналогично, можно видоизменить и формулы метода Стоуна и последовательно-параллельного метода разложения.
 +
Как и для <math>LDU</math>-разложения, при решении СЛАУ с трёхдиагональной матрицей с помощью <math>LDL^*</math>-разложения легче решаются полученные двухдиагональные СЛАУ.
  
 
== Разложения для трёхдиагональной эрмитовой матрицы специального вида ==
 
== Разложения для трёхдиагональной эрмитовой матрицы специального вида ==

Версия 15:27, 2 июля 2015

Основные авторы описания: А.В.Фролов

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

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

1.1 [math]LU[/math]-разложение

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

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

[math] u_{11} = a_{11} \\ u_{i i+1} = a_{i i+1}, \quad i \in [1, n-1] \\ l_{i+1 i} = a_{i+1 i} / u_{i i} , \quad i \in [1, n-1] \\ u_{ii} = a_{ii} - l_{i i-1} u_{i-1 i}, \quad i \in [2, n] \\ [/math]

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

1.1.2 Алгоритм Стоуна для [math]LU[/math]-разложения трёхдиагональной матрицы

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

Подробно свойства алгоритма Стоуна описаны на соответствующей странице.

1.1.3 Последовательно-параллельный алгоритм для [math]LU[/math]-разложения трёхдиагональной матрицы

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

Подробно свойства последовательно-параллельного алгоритма для LU-разложения трёхдиагональной матрицы описаны на соответствующей странице

1.2 [math]LDU[/math]-разложение

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

[math] d_{11} = a_{11} \\ u_{i i+1} = a_{i i+1} / d_{i i}, \quad i \in [1, n-1] \\ l_{i+1 i} = a_{i+1 i} / d_{i i} , \quad i \in [1, n-1] \\ d_{ii} = a_{ii} - l_{i i-1} a_{i-1 i}, \quad i \in [2, n] \\ [/math]

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

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

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

Эрмитовость трёхдиагональной матрицы позволяет вычислять такое её разложение, которое можно хранить в меньшей памяти.

2.1 [math]LL^*[/math]-разложение

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

[math] l_{11} = \sqrt{a_{11}}, \\ l_{i+1 i} = \frac{a_{i+1 i}}{l_{ii}}, \quad i \in [1, n-1], \\ l_{ii} = \sqrt{a_{ii} - |l_{i i-1}|^2}, \quad i \in [2, n]. \\ [/math]

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

2.2 [math]LDL^*[/math]-разложение

[math]LDL^*[/math]-разложение для трёхдиагональной эримтовой матрицы - самое экономное из последовательных её разложений. Его формулы таковы:

[math] d_{11} = a_{11} \\ l_{i+1 i} = a_{i+1 i} / d_{i i} , \quad i \in [1, n-1] \\ d_{ii} = a_{ii} - l_{i i-1} a_{i i-1}^*, \quad i \in [2, n] \\ [/math]

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

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

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

5 Литература

  1. Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.
  2. Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.