Обсуждение участника:Amirida

1 Статья Участник:Amirida/Метод «разделяй и властвуй» вычисления собственных значений и векторов симметричной трехдиагональной матрицы

1.1 Отсутствующие части

• Пропущен раздел описания 2.4. Масштабируемость алгоритма и его реализации. Александр Сергеевич Антонов (обсуждение) 11:25, 9 ноября 2016 (MSK)
• Не заполнен раздел 2.4 описания. Александр Сергеевич Антонов (обсуждение) 15:28, 16 ноября 2016 (MSK)

1.2 Замечания по тексту

• В разделе 1.4 требуется привести описание алгоритма на верхнем уровне (на основе макроопераций). Александр Сергеевич Антонов (обсуждение) 11:25, 9 ноября 2016 (MSK)
• В разделе 1.5 кроме кода нужны также текстовые пояснения. Александр Сергеевич Антонов (обсуждение) 11:25, 9 ноября 2016 (MSK)
• Граф, приведённый в разделе 1.7 не является информационным графом (ациклический граф, вершины - операции, дуги - информационные зависимости). Александр Сергеевич Антонов (обсуждение) 11:25, 9 ноября 2016 (MSK)
• В разделе 1.8 используется непонятный термин "высота алгоритма". Александр Сергеевич Антонов (обсуждение) 11:25, 9 ноября 2016 (MSK)
• В разделе 1.10 не нужно дублировать последовательную сложность алгоритма, но требуется привести оценку вычислительной мощности. Александр Сергеевич Антонов (обсуждение) 11:25, 9 ноября 2016 (MSK)
• Отсутствует информация в разделе 2.7 (по текущей нумерации 2.6). Александр Сергеевич Антонов (обсуждение) 11:25, 9 ноября 2016 (MSK)

1.3 Дополнительно (03.12)

Участник:chernyavskiy

• Для ускорение дальнейшей проверки укажите на этой странице (в данном разделе) подробно источники, из которых брались разделы и их части. Если раздел писался самостоятельно - укажите это.

Разделы:

1.1 - Джеймс Деммель. Вычислительная линейная алгебра. стр. 228

1.2 - Джеймс Деммель. Вычислительная линейная алгебра. стр. 228-233

1.3 - Джеймс Деммель. Вычислительная линейная алгебра. стр. 232

1.4 - Джеймс Деммель. Вычислительная линейная алгебра. стр. 232

1.5 - Джеймс Деммель. Вычислительная линейная алгебра. стр. 232

1.6 - Джеймс Деммель. Вычислительная линейная алгебра. стр. 232, https://en.wikipedia.org/wiki/Divide-and-conquer_eigenvalue_algorithm

1.7 - Писали сами

1.8 - Писали сами

1.9 - Писали сами

1.10 - Джеймс Деммель. Вычислительная линейная алгебра

2.4 - Писали сами

2.7 - Писали сами

1.4 Новые замечания и вопросы

Замечания: 1) Необходимо исправить ошибки в разделе 1.2. 2) Необходимо изменить информационный граф: не видна связь между шагами "разделяй" и "властвуй". 3) В разделе 1.1 написано:

"В наихудшем случае алгоритм «разделяй-и-властвуй» требует [math] O(n^{3})[/math] операций, но константа, на практике оказывается весьма малой. На большой выборке случайных тестовых матриц в среднем затрачивается лишь [math] O(n^{2.3})[/math] операций с плавающей точкой, а для некоторых специальных распределений собственных значений — [math] O(n^{2})[/math] (подробнее в разделе 1.6 Последовательная сложность алгоритма)."

Во-первых, не работает ссылка, а во-вторых, в разделе 1.6. я не вижу обоснования приведенным здесь оценкам.

4) В разделе 1.6. встречается слово "дефляция". Больше в описании про дефляцию ни слова. Необходимо добавить. И определение, и роль в алгоритме.

Также прошу ответить на несколько вопросов: 1) Что такое общая эффективность программы? 2) Чем общая эффективность программы отличается от эффективности программы? 3) Как алгоритм работает с кратными собственными значениями?

1.5 Ответы на вопросы

Правки по указанным замечаниям были внесены.

Ответы:

1-2) Имелась в виду эффективности реализации.

3) В данном алгоритме не происходила обработка случая с кратными собственными значениями. Для обработки такого случая нужно доработать используемый алгоритм метода Ньютона для нахождения корней уравнения.