Компактная схема метода Гаусса для трёхдиагональной матрицы и её модификации: различия между версиями
[непроверенная версия] | [непроверенная версия] |
Frolov (обсуждение | вклад) |
Frolov (обсуждение | вклад) |
||
Строка 9: | Строка 9: | ||
==== Компактная схема метода Гаусса для трёхдиагональной матрицы ==== | ==== Компактная схема метода Гаусса для трёхдиагональной матрицы ==== | ||
− | Компактная схема метода Гаусса вычисляет такое , в котором матрица <math>L</math> имеет на диагонали только единицы. Формулы метода следующие: | + | Компактная схема метода Гаусса вычисляет такое <math>LU</math>-разложение на две двухдиагональные матрицы, в котором нижняя двухдиагональная матрица <math>L</math> имеет на диагонали только единицы. Формулы метода следующие: |
:<math> | :<math> | ||
Строка 18: | Строка 18: | ||
</math> | </math> | ||
− | Подробно её свойства описаны на [[Компактная схема метода Гаусса для трёхдиагональной матрицы, последовательный вариант|соответствующей странице]] | + | Подробно её свойства описаны на [[Компактная схема метода Гаусса для трёхдиагональной матрицы, последовательный вариант|соответствующей странице]]. В неизменённом виде не полежит распараллеливанию, алгоритм чисто последовательный. |
==== Алгоритм Стоуна для <math>LU</math>-разложения трёхдиагональной матрицы ==== | ==== Алгоритм Стоуна для <math>LU</math>-разложения трёхдиагональной матрицы ==== | ||
− | [[Алгоритм Стоуна для LU-разложения трёхдиагональной матрицы]] является частью алгоритма Стоуна для решения трёхдиагональных СЛАУ и является '''первым параллельным''' алгоритмом <math>LU</math>-разложения трёхдиагональной матрицы. Математическая его основа - линейная рекуррентная формула для главных миноров раскладываемой матрицы. После записи этой рекуррентной формулы в матричном виде оказывается, что можно воспользоваться ассоциативностью операции перемножения матриц. Стоун использовал для распараллеливания схему сдваивания. | + | [[Алгоритм Стоуна для LU-разложения трёхдиагональной матрицы]] является частью алгоритма Стоуна для решения трёхдиагональных СЛАУ и является '''первым параллельным''' алгоритмом <math>LU</math>-разложения трёхдиагональной матрицы. Математическая его основа - линейная рекуррентная формула для главных миноров раскладываемой матрицы. После записи этой рекуррентной формулы в матричном виде оказывается, что можно воспользоваться ассоциативностью операции перемножения матриц. Стоун использовал для распараллеливания схему сдваивания. Однако область устойчивости этого метода гораздо уже, чем у компактной схемы метода Гаусса, несмотря на то, что искомые матрицы - те же самые. |
Подробно свойства алгоритма Стоуна описаны на [[Алгоритм Стоуна для LU-разложения трёхдиагональной матрицы|соответствующей странице]]. | Подробно свойства алгоритма Стоуна описаны на [[Алгоритм Стоуна для LU-разложения трёхдиагональной матрицы|соответствующей странице]]. | ||
+ | |||
+ | ==== Последовательно-параллельный алгоритм для <math>LU</math>-разложения трёхдиагональной матрицы ==== | ||
+ | |||
+ | [[Последовательно-параллельный алгоритм для LU-разложения трёхдиагональной матрицы]] придуман для распараллеливания нахождения того же <math>LU</math>-разложения трёхдиагональной матрицы, что получается из компактной схемы метода Гаусса, с сохранением характеристик её устойчивости. Как и метод Стоуна, использует ассоциативность умножения матриц, но использует также нормировку в последовательных ветвях вычислений. | ||
+ | |||
+ | Подробно свойства последовательно-параллельного алгоритма для LU-разложения трёхдиагональной матрицы описаны на [[Последовательно-параллельный алгоритм для LU-разложения трёхдиагональной матрицы|соответствующей странице]] | ||
=== <math>LDU</math>-разложение === | === <math>LDU</math>-разложение === |
Версия 20:03, 1 июля 2015
Основные авторы описания: А.В.Фролов
Содержание
- 1 Компактная схема метода Гаусса для трёхдиагональной матрицы и её модификации
- 2 Компактная схема метода Гаусса для трёхдиагональной эрмитовой матрицы и её модификации
- 3 Разложения для трёхдиагональной эрмитовой матрицы специального вида
- 4 Существующие реализации алгоритма
- 5 Литература
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]-разложение
2 Компактная схема метода Гаусса для трёхдиагональной эрмитовой матрицы и её модификации
2.1 [math]LL^T[/math]-разложение
2.2 [math]LDL^T[/math]-разложение
3 Разложения для трёхдиагональной эрмитовой матрицы специального вида
4 Существующие реализации алгоритма
5 Литература
- Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.
- Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.