Уровень метода

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

Материал из Алговики
Перейти к навигации Перейти к поиску
[выверенная версия][выверенная версия]
 
(не показаны 42 промежуточные версии 4 участников)
Строка 1: Строка 1:
 +
{{level-m}}
 +
 
Основные авторы описания: [[Участник:Frolov|А.В.Фролов]]
 
Основные авторы описания: [[Участник:Frolov|А.В.Фролов]]
  
 
== Компактная схема метода Гаусса для трёхдиагональной матрицы и её модификации ==
 
== Компактная схема метода Гаусса для трёхдиагональной матрицы и её модификации ==
  
Треугольное разложение трёхдиагональной матрицы базируется на формулах этого же разложения для матриц общего вида<ref>Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.</ref><ref>Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.</ref>. Обычно встречающиеся в прикладных задачах трёхдиагональные матрицы имеют свойство диагонального преобладания. Поэтому нужды в перестановках не возникает. Использование свойств, базирующихся на формуле Бине-Коши для миноров произведения двух матриц, показывает, что для трёхдиагональной матрицы <math>LU</math>-разложение будет содержать '''две двухдиагональные матрицы'''. Поэтому формулы компактной схемы метода Гаусса и её модификаций существенно упрощаются.  
+
Треугольное разложение трёхдиагональной матрицы базируется на формулах треугольного разложения для матриц общего вида<ref name="VOLA">Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.</ref><ref name="MIV">Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.</ref>. Обычно встречающиеся в прикладных задачах трёхдиагональные матрицы имеют свойство диагонального преобладания, поэтому не возникает необходимости в применении перестановок для повышения устойчивости разложения. Использование свойств, базирующихся, например, на [http://stu.sernam.ru/lect_alg.php?id=71 формуле Бине-Коши] в её приложении к минорам матриц<ref name="MIV" />:
 +
 
 +
{{Шаблон:Бине-Коши}}
 +
 
 +
для миноров произведения двух матриц, показывает<ref name="VOLA" />, что для трёхдиагональной матрицы  
 +
 
 +
{{Шаблон:Трёхдиагональная_матрица_стандартной_формы}}
 +
 
 +
<math>LU</math>-разложение будет содержать '''две двухдиагональные матрицы''':
 +
 
 +
:<math>
 +
L = \begin{bmatrix}
 +
l_{11} & 0  & 0 &    \cdots & \cdots & 0 \\
 +
l_{21} & l_{22}  & 0 &  \cdots & \cdots & 0 \\
 +
0 &  l_{32} & l_{33}  &    \cdots & \cdots & 0 \\
 +
\vdots & \vdots & \ddots & \ddots & \ddots & 0 \\
 +
0 & \cdots & \cdots & l_{n-1 n-2} & l_{n-1 n-1}  & 0 \\
 +
0 & \cdots & \cdots & 0 & l_{n n-1}  & l_{n n} \\
 +
\end{bmatrix}, 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>
 +
 
 +
Поэтому формулы компактной схемы метода Гаусса и её модификаций существенно упрощаются.  
  
 
=== <math>LU</math>-разложение ===
 
=== <math>LU</math>-разложение ===
Строка 9: Строка 39:
 
==== Компактная схема метода Гаусса для трёхдиагональной матрицы ====
 
==== Компактная схема метода Гаусса для трёхдиагональной матрицы ====
  
Компактная схема метода Гаусса вычисляет такое <math>LU</math>-разложение на две двухдиагональные матрицы, в котором нижняя двухдиагональная матрица <math>L</math> имеет на диагонали только единицы. Формулы метода следующие:
+
[[Компактная схема метода Гаусса для трёхдиагональной матрицы, последовательный вариант|'''Компактная схема метода Гаусса для трёхдиагональной матрицы''']] вычисляет такое <math>LU</math>-разложение на две двухдиагональные матрицы, в котором у нижней двухдиагональной матрицы <math>L</math> на диагонали стоят только единицы:
 +
 
 +
{{Шаблон:L2dUniDiag}}
 +
 
 +
Формулы метода следующие:
 +
 
 +
<math>u_{11} = a_{11}</math>
 +
 +
<math>u_{i i+1} = a_{i i+1}</math>, <math>\quad i \in [1, n-1]</math>
 +
 +
<math>l_{i+1 i} = a_{i+1 i} / u_{i i} </math>, <math>\quad i \in [1, n-1] </math>
  
:<math>
+
<math>u_{ii} = a_{ii} - l_{i i-1} u_{i-1 i}</math>, <math>\quad i \in [2, n] </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>
 
  
 
Подробно её свойства описаны на [[Компактная схема метода Гаусса для трёхдиагональной матрицы, последовательный вариант|соответствующей странице]]. В неизменённом виде не подлежит распараллеливанию, алгоритм чисто последовательный.Существует и блочная версия разложения - для блочно-трёхдиагональных матриц.
 
Подробно её свойства описаны на [[Компактная схема метода Гаусса для трёхдиагональной матрицы, последовательный вариант|соответствующей странице]]. В неизменённом виде не подлежит распараллеливанию, алгоритм чисто последовательный.Существует и блочная версия разложения - для блочно-трёхдиагональных матриц.
 +
Компактная схема метода Гаусса легко подвергается модификации, в которой не в матрице <math>L</math>, а в матрице <math>U</math> на диагонали только единицы. Это используется, например, в качестве части метода [[Прогонка, точечный вариант|прогонки]].
  
 
==== Алгоритм Стоуна для <math>LU</math>-разложения трёхдиагональной матрицы ====
 
==== Алгоритм Стоуна для <math>LU</math>-разложения трёхдиагональной матрицы ====
  
[[Алгоритм Стоуна для LU-разложения трёхдиагональной матрицы]] является частью алгоритма Стоуна<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> для решения трёхдиагональных СЛАУ и является '''первым параллельным''' алгоритмом <math>LU</math>-разложения трёхдиагональной матрицы. Математическая его основа - линейная рекуррентная формула для главных миноров раскладываемой матрицы. После записи этой рекуррентной формулы в матричном виде оказывается, что можно воспользоваться ассоциативностью операции перемножения матриц. Стоун использовал для распараллеливания схему сдваивания. Однако область устойчивости этого метода гораздо уже, чем у компактной схемы метода Гаусса, несмотря на то, что искомые матрицы - те же самые. Блочная схема метода для блочно-трёхдиагональных матриц не разрабатывалась, хотя теоретически и может существовать, из-за неустойчивости схемы.   
+
[[Алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы]] является частью [[Метод сдваивания Стоуна|алгоритма Стоуна]]<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> для решения трёхдиагональных СЛАУ и является '''первым''' параллельным алгоритмом <math>LU</math>-разложения трёхдиагональной матрицы. Математическая его основа - линейная рекуррентная формула для главных миноров раскладываемой матрицы. После записи этой рекуррентной формулы в матричном виде оказывается, что можно воспользоваться ассоциативностью операции перемножения матриц. Стоун использовал для распараллеливания схему сдваивания. Однако область устойчивости этого метода гораздо уже, чем у компактной схемы метода Гаусса, несмотря на то, что искомые матрицы - те же самые. Блочная схема метода для блочно-трёхдиагональных матриц не разрабатывалась, хотя теоретически и может существовать, из-за неустойчивости схемы.   
  
Подробно свойства алгоритма Стоуна описаны на [[Алгоритм Стоуна для LU-разложения трёхдиагональной матрицы|соответствующей странице]].
+
Подробно свойства алгоритма Стоуна описаны на [[Алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы|соответствующей странице]].
  
 
==== Последовательно-параллельный алгоритм для <math>LU</math>-разложения трёхдиагональной матрицы ====
 
==== Последовательно-параллельный алгоритм для <math>LU</math>-разложения трёхдиагональной матрицы ====
  
[[Последовательно-параллельный алгоритм для LU-разложения трёхдиагональной матрицы]] придуман для распараллеливания нахождения того же <math>LU</math>-разложения трёхдиагональной матрицы, что получается из компактной схемы метода Гаусса, с сохранением характеристик её устойчивости. Как и метод Стоуна, использует ассоциативность умножения матриц, но использует также нормировку в последовательных ветвях вычислений. Для блочно-трёхдиагональных матриц существует блочная версия метода, для которой необходима невырожденность блоков на одной из побочных диагоналей матрицы.  
+
[[Последовательно-параллельный алгоритм для LU-разложения трёхдиагональной матрицы]] разработан<ref>А.В.Фролов. Ещё один метод распараллеливания прогонки с использованием ассоциативности операций // Суперкомпьютерные дни в России: Труды международной конференции (28-29 сентября 2015 г., г. Москва). – М.: Изд-во МГУ, 2015. с. 151-162</ref> для распараллеливания нахождения того же <math>LU</math>-разложения трёхдиагональной матрицы, что получается из [[Компактная схема метода Гаусса для трёхдиагональной матрицы, последовательный вариант|компактной схемы метода Гаусса]]. Как и [[Алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы|метод Стоуна]], использует ассоциативность умножения матриц, но использует также нормировку в последовательных ветвях вычислений, что даёт схеме большую область устойчивости, чем у схемы Стоуна. Для блочно-трёхдиагональных матриц существует блочная версия метода, для которой, однако, необходима невырожденность блоков не только на главной, но и на одной из побочных диагоналей матрицы.
 +
 
 +
=== <math>LDU</math>-разложение ===
 +
 
 +
В случае, если существует <math>LU</math>-разложение на две двухдиагональные матрицы, в котором нижняя двухдиагональная матрица <math>L</math> имеет на главной диагонали только единицы, легко можно найти и <math>LDU</math>-разложение, в котором и верхняя двухдиагональная матрица также имеет на главной диагонали только единицы:
 +
 
 +
{{Шаблон:U2dUniDiag}}
 +
 
 +
Формулы видоизменённой компактной схемы метода Гаусса для нахождения этого разложения выглядят следующим образом:
  
Подробно свойства последовательно-параллельного алгоритма для LU-разложения трёхдиагональной матрицы описаны на [[Последовательно-параллельный алгоритм для LU-разложения трёхдиагональной матрицы|соответствующей странице]]
+
<math>d_{11} = a_{11} </math>
  
=== <math>LDU</math>-разложение ===
+
<math>u_{i i+1} = a_{i i+1} / d_{i i}, \quad i \in [1, n-1] </math>
  
В случае, если существует <math>LU</math>-разложение на две двухдиагональные матрицы, в котором нижняя двухдиагональная матрица <math>L</math> имеет на главной диагонали только единицы, легко можно найти и <math>LDU</math>-разложение, в котором и верхняя двухдиагональная матрица также имеет на главной диагонали только единицы. Формулы видоизменённой компактной схемы метода Гаусса для нахождения этого разложения выглядят так:
+
<math>l_{i+1 i} = a_{i+1 i} / d_{i i} , \quad i \in [1, n-1] </math>
  
:<math>
+
<math>d_{ii} = a_{ii} - l_{i i-1} a_{i-1 i}, \quad i \in [2, n] </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>
 
  
Аналогично, добавлением делений, можно видоизменить и формулы метода Стоуна и последовательно-параллельного метода разложения.  
+
Аналогично, добавлением делений можно видоизменить и формулы метода Стоуна и последовательно-параллельного метода разложения.  
  
 
Получаемое разложение легче использовать для решения трёхдиагональных СЛАУ, поскольку в обоих подстановках деление не будет перемежаться с операциями умножения-сложения/вычитания.
 
Получаемое разложение легче использовать для решения трёхдиагональных СЛАУ, поскольку в обоих подстановках деление не будет перемежаться с операциями умножения-сложения/вычитания.
Строка 49: Строка 88:
 
== Компактная схема треугольного разложения для трёхдиагональной эрмитовой матрицы и её модификации ==
 
== Компактная схема треугольного разложения для трёхдиагональной эрмитовой матрицы и её модификации ==
  
Эрмитовость трёхдиагональной матрицы позволяет вычислять такое её разложение, которое можно хранить в меньшей памяти.  
+
Эрмитовость трёхдиагональной матрицы позволяет вычислять такое её разложение, которое можно хранить в меньшей памяти с учетом симметрии разложения.  
  
 
=== <math>LL^*</math>-разложение ===
 
=== <math>LL^*</math>-разложение ===
Строка 55: Строка 94:
 
Для вычисления <math>LL^*</math>-разложения матрицы логично использовать [[Разложение Холецкого (метод квадратного корня)|метод Холецкого]], формулы которого после коррекции будут адаптированы под трёхдиагональность исходной матрицы и двухдиагональность результата:
 
Для вычисления <math>LL^*</math>-разложения матрицы логично использовать [[Разложение Холецкого (метод квадратного корня)|метод Холецкого]], формулы которого после коррекции будут адаптированы под трёхдиагональность исходной матрицы и двухдиагональность результата:
  
:<math>
+
<math>l_{11} = \sqrt{a_{11}}, </math>
l_{11} = \sqrt{a_{11}}, \\
+
 
l_{i+1 i} = \frac{a_{i+1 i}}{l_{ii}}, \quad i \in [1, n-1], \\
+
<math>l_{i+1 i} = \frac{a_{i+1 i}}{l_{ii}}, \quad i \in [1, n-1], </math>
l_{ii} = \sqrt{a_{ii} - |l_{i i-1}|^2}, \quad i \in [2, n]. \\
+
 
</math>
+
<math>l_{ii} = \sqrt{a_{ii} - |l_{i i-1}|^2}, \quad i \in [2, n]. </math>
  
 
Аналогичные изменения можно провести в методах Стоуна и последовательно-параллельного <math>LU</math>-разложения.  
 
Аналогичные изменения можно провести в методах Стоуна и последовательно-параллельного <math>LU</math>-разложения.  
Строка 66: Строка 105:
 
=== <math>LDL^*</math>-разложение ===
 
=== <math>LDL^*</math>-разложение ===
  
<math>LDL^*</math>-разложение для трёхдиагональной эримтовой матрицы - самое экономное из последовательных её разложений. Его формулы таковы:
+
<math>LDL^*</math>-разложение для трёхдиагональной эрмитовой матрицы - самое экономное из последовательных её разложений. Формулы разложения имеют вид:
 +
 
 +
<math>d_{11} = a_{11} </math>
 +
 
 +
<math>l_{i+1 i} = a_{i+1 i} / d_{i i} , \quad i \in [1, n-1] </math>
  
:<math>
+
<math>d_{ii} = a_{ii} - l_{i i-1} a_{i i-1}^*, \quad i \in [2, n] </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>-разложения легче решаются полученные двухдиагональные СЛАУ.  
+
Как и для <math>LDU</math>-разложения, при решении СЛАУ с трёхдиагональной матрицей с помощью <math>LDL^*</math>-разложения легче решаются полученные двухдиагональные СЛАУ.
  
 
== Разложения для трёхдиагональных матриц специального вида ==
 
== Разложения для трёхдиагональных матриц специального вида ==
  
Многие матрицы специального вида, получаемые из известных операторов математической физики, в том числе и трёхдиагональные, имеют известные и давно рассчитанные характеристики, в том числе и значения главных миноров. Несмотря на это, широко распространено явление, когда работающие с такими матрицами вместо того, чтобы взять и найти готовые формулы разложений, применяют к ним вышеописанные методы, тратя время.  
+
Для некоторых матриц специального вида, получаемых из известных операторов математической физики, в том числе и для трёхдиагональных матриц, известны аналитические выражения для их характеристик, в том числе и значения главных миноров. Несмотря на это, широко распространено явление, когда исследователи, работающие с такими матрицами, вместо того, чтобы воспользоваться готовыми формулами разложений, применяют к ним вышеописанные методы, нерационально тратя компьютерное время.  
  
 
[[Разложения для трёхдиагональных матриц специального вида]] можно найти на специальной отдельной странице.
 
[[Разложения для трёхдиагональных матриц специального вида]] можно найти на специальной отдельной странице.
Строка 85: Строка 124:
 
== Использование разложений ==
 
== Использование разложений ==
  
Обычно разложения трёхдиагональных матриц в произведение двухдиагональных (и, возможно, ещё одной диагональной) используют для [[Решения СЛАУ с трёхдиагональными матрицами|решения СЛАУ с трёхдиагональной матрицей]], полученной из какой-либо физической модели. Поэтому зачастую полезность того или иного метода разложения нужно сравнивать не только с другими методами разложения трёхдиагональных матриц, но и с различными методами решения СЛАУ с такими матрицами, в том числе и не использующими такие разложения.  
+
Обычно разложения трёхдиагональных матриц в произведение двухдиагональных (и, возможно, ещё одной диагональной) используют для [[Решения СЛАУ с трёхдиагональными матрицами|решения СЛАУ с трёхдиагональной матрицей]], полученной из какой-либо физической модели. Поэтому зачастую полезность того или иного метода разложения следует сравнивать не только с другими методами разложения трёхдиагональных матриц, но и с различными методами решения СЛАУ с такими матрицами, в том числе и не использующими такие разложения - например, такими, как [[Метод циклической редукции|метод циклической редукции]] или [[Метод окаймления|метод окаймления]].
  
 
== Литература ==
 
== Литература ==
Строка 91: Строка 130:
 
<references />
 
<references />
  
 +
[[Категория:Законченные статьи]]
 +
[[Категория:Разложения матриц]]
 +
[[Категория:Решение систем линейных уравнений]]
  
[[Категория:Законченные статьи]]
+
[[en:Compact scheme for Gaussian elimination and its modifications: Tridiagonal matrix]]

Текущая версия на 16:42, 16 марта 2018


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

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

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

[math] A \begin{pmatrix} \alpha_{1} & \alpha_{2} & \cdots & \alpha_{k} \\ \beta_{1} & \beta_{2} & \cdots & \beta_{k} \\ \end{pmatrix} = \sum_{\begin{smallmatrix} \gamma_{1} \lt \gamma_{2} \lt \cdots \lt \gamma_{k} \end{smallmatrix}} L \begin{pmatrix} \alpha_{1} & \alpha_{2} & \cdots & \alpha_{k} \\ \gamma_{1} & \gamma_{2} & \cdots & \gamma_{k} \\ \end{pmatrix} U\begin{pmatrix} \gamma_{1} & \gamma_{2} & \cdots & \gamma_{k} \\ \beta_{1} & \beta_{2} & \cdots & \beta_{k} \\ \end{pmatrix} [/math]

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

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

[math] L = \begin{bmatrix} l_{11} & 0 & 0 & \cdots & \cdots & 0 \\ l_{21} & l_{22} & 0 & \cdots & \cdots & 0 \\ 0 & l_{32} & l_{33} & \cdots & \cdots & 0 \\ \vdots & \vdots & \ddots & \ddots & \ddots & 0 \\ 0 & \cdots & \cdots & l_{n-1 n-2} & l_{n-1 n-1} & 0 \\ 0 & \cdots & \cdots & 0 & l_{n n-1} & l_{n n} \\ \end{bmatrix}, 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]

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

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

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

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

[math] 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]u_{11} = a_{11}[/math]

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

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

[math]u_{ii} = a_{ii} - l_{i i-1} u_{i-1 i}[/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{bmatrix} 1 & u_{12} & 0 & \cdots & \cdots & 0 \\ 0 & 1 & u_{23}& \cdots & \cdots & 0 \\ 0 & 0 & 1 & \cdots & \cdots & 0 \\ \vdots & \vdots & \ddots & \ddots & \ddots & 0 \\ 0 & \cdots & \cdots & 0 & 1 & u_{n-1 n} \\ 0 & \cdots & \cdots & 0 & 0 & 1 \\ \end{bmatrix} [/math]

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

[math]d_{11} = a_{11} [/math]

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

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

[math]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}}, [/math]

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

[math]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} [/math]

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

[math]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. 1,0 1,1 Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.
  2. 2,0 2,1 Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.
  3. 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.
  4. А.В.Фролов. Ещё один метод распараллеливания прогонки с использованием ассоциативности операций // Суперкомпьютерные дни в России: Труды международной конференции (28-29 сентября 2015 г., г. Москва). – М.: Изд-во МГУ, 2015. с. 151-162