Обсуждение участника:Amirida: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
 
(не показана 1 промежуточная версия 1 участника)
Строка 44: Строка 44:
  
 
2.7 - Писали сами
 
2.7 - Писали сами
 +
 +
=== Новые замечания и вопросы ===
 +
 +
Замечания:
 +
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-2) Имелась в виду [[Глоссарий#Эффективность реализации|эффективности реализации]].
 +
 +
3) В данном алгоритме не происходила обработка случая с кратными собственными значениями. Для обработки такого случая нужно доработать используемый алгоритм метода Ньютона для нахождения корней уравнения.

Текущая версия на 13:35, 1 февраля 2017

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

Источник — https://algowiki-project.org/w/ru/index.php?title=Обсуждение_участника:Amirida&oldid=21938