Обсуждение участника: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)
- Для ускорение дальнейшей проверки укажите на этой странице (в данном разделе) подробно источники, из которых брались разделы и их части. Если раздел писался самостоятельно - укажите это.
Разделы:
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) В данном алгоритме не происходила обработка случая с кратными собственными значениями. Для обработки такого случая нужно доработать используемый алгоритм метода Ньютона для нахождения корней уравнения.
