Уровень алгоритма

Участник:Test/87

Материал из Алговики
< Участник:Test
Версия от 20:15, 3 декабря 2015; Test (обсуждение | вклад) (Новая страница: «{{subst:level-a}} {{subst:algorithm | name = Разложение Холецкого | serial_complexity = <math>O(n^3)</math> | pf_height =…»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к навигации Перейти к поиску


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


Основные авторы описания: А.В.Фролов, Вад.В.Воеводин (раздел 2.2), А.М.Теплов (разделы 2.4, 2.5)

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

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

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

  1. Commandant Benoit, Note sur une méthode de résolution des équations normales provenant de l'application de la méthode des moindres carrés à un système d'équations linéaires en nombre inférieur à celui des inconnues (Procédé du Commandant Cholesky), Bulletin Géodésique 2 (1924), 67-77.
  2. Banachiewicz T. Principles d'une nouvelle technique de la méthode des moindres carrês. Bull. Intern. Acad. Polon. Sci. A., 1938, 134-135.
  3. Banachiewicz T. Méthode de résoltution numérique des équations linéaires, du calcul des déterminants et des inverses et de réduction des formes quardatiques. Bull. Intern. Acad. Polon. Sci. A., 1938, 393-401.
  4. Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.
  5. Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.
  6. Фаддеев Д.К., Фаддева В.Н. Вычислительные основы линейной алгебры. М.-Л.: Физматгиз, 1963.