Шаблон:Main page/Featured: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][выверенная версия]
 
(не показано 12 промежуточных версий 2 участников)
Строка 1: Строка 1:
 +
<div style="font-size: 160%; font-weight: bold; text-align: center;">
 +
Разложение Холецкого (метод квадратного корня)
 +
</div>
  
----
+
{| style="float:{{{float|right}}}; clear:right;margin-left: 1em; width:{{{width|40%}}};" cellpadding=8 cellspacing=1 border=0
<br />
 
Читать полностью: [[Разложение_Холецкого_(метод_квадратного_корня)]]<br />
 
<br />
 
----
 
 
 
{| style="float:{{{float|right}}}; clear:right;margin-left: 1em; width:{{{width|30%}}};" cellpadding=8 cellspacing=1 border=0
 
 
|-
 
|-
 
|align=left width=100% style="background-color:#f3f3ff; border:1px solid"|  
 
|align=left width=100% style="background-color:#f3f3ff; border:1px solid"|  
Строка 17: Строка 14:
 
|}
 
|}
  
== Описание свойств и структуры алгоритма ==
+
== Свойства и структура алгоритма ==
  
 
=== Общее описание алгоритма ===
 
=== Общее описание алгоритма ===
Строка 27: Строка 24:
 
Для разреженных матриц разложение Холецкого также широко применяется в качестве основного этапа прямого метода решения линейных систем. В этом случае используют специальные упорядочивания для уменьшения ширины профиля исключения, а следовательно и уменьшения количества арифметических операций. Другие упорядочивания используются для выделения независимых блоков вычислений при работе на системах с параллельной организацией.
 
Для разреженных матриц разложение Холецкого также широко применяется в качестве основного этапа прямого метода решения линейных систем. В этом случае используют специальные упорядочивания для уменьшения ширины профиля исключения, а следовательно и уменьшения количества арифметических операций. Другие упорядочивания используются для выделения независимых блоков вычислений при работе на системах с параллельной организацией.
  
=== Математическое описание ===
+
=== Математическое описание алгоритма ===
  
 
Исходные данные: положительно определённая симметрическая матрица <math>A</math> (элементы <math>a_{ij}</math>).
 
Исходные данные: положительно определённая симметрическая матрица <math>A</math> (элементы <math>a_{ij}</math>).
Строка 47: Строка 44:
 
В ряде реализаций деление на диагональный элемент выполняется в два этапа: вычисление <math>1/l_{ii}</math> и затем умножение на него всех (видоизменённых) <math>a_{ji}</math> . Здесь мы этот вариант алгоритма не рассматриваем. Заметим только, что он имеет худшие параллельные характеристики, чем представленный.
 
В ряде реализаций деление на диагональный элемент выполняется в два этапа: вычисление <math>1/l_{ii}</math> и затем умножение на него всех (видоизменённых) <math>a_{ji}</math> . Здесь мы этот вариант алгоритма не рассматриваем. Заметим только, что он имеет худшие параллельные характеристики, чем представленный.
  
=== Последовательная сложность алгоритма ===
+
:''[[Разложение Холецкого (метод квадратного корня)|Читать полностью…]]''
 
 
Для разложения матрицы порядка n методом Холецкого в последовательном (наиболее быстром) варианте требуется:
 
 
* <math>n</math> вычислений квадратного корня,
 
* <math>\frac{n(n-1)}{2}</math> делений,
 
* <math>\frac{n^3-n}{6}</math> сложений (вычитаний),
 
* <math>\frac{n^3-n}{6}</math> умножений.
 
 
 
Умножения и сложения (вычитания) составляют ''основную часть алгоритма''.
 
 
При этом использование режима накопления требует совершения умножений и вычитаний в режиме двойной точности (или использования функции вроде DPROD в Фортране), что ещё больше увеличивает долю умножений и сложений/вычитаний во времени, требуемом для выполнения метода Холецкого.
 
 
 
При классификации по последовательной сложности, таким образом, метод Холецкого относится к алгоритмам ''с кубической сложностью''.
 

Текущая версия на 17:01, 29 июля 2015

Разложение Холецкого (метод квадратного корня)

Свойства алгоритма:

  • Последовательная сложность алгоритма: [math]O(n^3)[/math]
  • Высота ярусно-параллельной формы: [math]O(n)[/math]
  • Ширина ярусно-параллельной формы: [math]O(n^2)[/math]
  • Объём входных данных: [math]\frac{n (n + 1)}{2}[/math]
  • Объём выходных данных: [math]\frac{n (n + 1)}{2}[/math]

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

Разложение Холецкого впервые предложено французским офицером и математиком Андре-Луи Холецким в конце Первой Мировой войны, незадолго до его гибели в бою в августе 1918 г. Идея этого разложения была опубликована в 1924 г. его сослуживцем. Потом оно было использовано поляком Т. Банашевичем в 1938 г. В советской математической литературе называется также методом квадратного корня [1-3]; название связано с характерными операциями, отсутствующими в родственном разложении Гаусса.

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

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

1.2 Математическое описание алгоритма

Исходные данные: положительно определённая симметрическая матрица [math]A[/math] (элементы [math]a_{ij}[/math]).

Вычисляемые данные: нижняя треугольная матрица [math]L[/math] (элементы [math]l_{ij}[/math]).

Формулы метода:

[math] \begin{align} l_{11} & = \sqrt{a_{11}}, \\ l_{j1} & = \frac{a_{j1}}{l_{11}}, \quad j \in [2, n], \\ l_{ii} & = \sqrt{a_{ii} - \sum_{p = 1}^{i - 1} l_{ip}^2}, \quad i \in [2, n], \\ l_{ji} & = \left (a_{ji} - \sum_{p = 1}^{i - 1} l_{ip} l_{jp} \right ) / l_{ii}, \quad i \in [2, n - 1], j \in [i + 1, n]. \end{align} [/math]

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

В ряде реализаций деление на диагональный элемент выполняется в два этапа: вычисление [math]1/l_{ii}[/math] и затем умножение на него всех (видоизменённых) [math]a_{ji}[/math] . Здесь мы этот вариант алгоритма не рассматриваем. Заметим только, что он имеет худшие параллельные характеристики, чем представленный.

Читать полностью…