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

Материал из Алговики
Перейти к навигации Перейти к поиску

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

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

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


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