Дипломная работа: Сравнительный анализ алгоритмов нахождения собственных значений симметричных матриц большой размерности

Таблица 3.5 Результаты работы метода QL с диапазоном от 0 до 1

Таблица 3.6 Результаты работы метода QL со сдвигом с диапазоном от 0 до 100

Рисунок 3.3 - График зависимости метода QL со сдвигом.

Собрав все экспериментальные данные, можно приступать к сравнительному анализу алгоритмов, с учетами всех особенностей данных методов и полученных во время эксперимента данных.

3.3 Сравнение результатов работы методов

Сравним все методы по каждому из полученных показателей. Начнем с одного из ключевых показателей - точности работы. В ходе экспериментов лучший результат по точности показал метод QL со сдвигом () на матрице с диапазоном значений от 0 до 1.

При этом, данный метод показывает более плохой результат () на матрице с диапазоном от 0 до 100, что говорит о чувствительности данного метода к разбросу значений. При этом на данном диапазоне лучший результат показывает метод Якоби (), хоть и тоже теряет в точности при увеличении разброса.

Степенной же демонстрирует высокую устойчивость к увеличению разницы значений, содержащийся в матрице, показывая практически идентичные результаты (и соответственно).

Далее рассмотрим методы по количеству итераций для достижения сходимости алгоритма. Ожидаемо, лучшие результаты здесь показывает степенной метод, так как он использует начальное приближение и определенную точность для сходимости, в результате чего обрабатывает матрицу с любым диапазоном значений за несколько итераций (от 5 до 15, в зависимости от того, насколько удачно было сгенерировано начальное приближение).

Совершенно обратную ситуацию демонстрирует метод Якоби, проводя большое количество итераций и вращений матрицы, необходимых для достижения условий сходимости. Здесь демонстрируется равномерный рост количества итераций в зависимости от размерности матрицы и доходящий до 12 тысяч для матрицы размером 10001000, что в тысячу раз больше значения для степенного метода и в 4 раза больше для метода QL со сдвигом, что говорит о высокой вычислительной сложности метода, вне зависимости от диапазона разброса значений матрицы.

Метод QL со сдвигом демонстрирует умеренные результаты по количеству итераций. Тот же равномерный рост в зависимости от размерности матрицы как у метода Якоби, но значения в 4 раза меньше, до 3500 итераций для матрицы размером 10001000. Это говорит о небольшой сложности вычислительной сложности алгоритма, несмотря на то что данный алгоритм самый сложный в реализации и требует подготовки матрицы и её специальной трансформации в трехдиагональную форму.

Рассматривая же время выполнения алгоритмов, ситуация здесь аналогична ситуации с количеством итераций. Степенной метод показывает лучшие результаты, отрабатывая матрицы любой размерности и с любый диапазоном за несколько миллисекунд (до 12 мс в рассмотренных примерах), но имея неравномерный рост, который увеличивает время работы в случае неудачно выбранного начального приближения.

Метод Якоби и QL со сдвигом, наоборот, демонстрируют равномерный рост времени выполнения в зависимости от размерности матрицы, при этом не имея заметной зависимости от диапазона рассматриваемых значений матрицы. Но нельзя не заметить, что скорость работы метода Якоби хуже времени выполнения метода QL со сдвигом, проигрывая по скорости до 13 раз (26110 мс и 2115 мс соответственно для матриц размерностей 10001000 и в диапазоне от 0 до 100), и только увеличивает разрыв в зависимости от размерности матрицы.

3.4 Выводы по главе 3

Подводя итоги сравнительного анализа, можно сделать следующие выводы:

1) Самым простым и быстрым методом является степенной метод, во много превосходя остальные по количеству итерации и скорости работы. Но при этом он имеет значительные минусы. Во-первых, он решает неполную задачу нахождения собственных значений, находя только максимальное значение, что сильно сужает вариативность его применения. Во-вторых, эффективность данного метода во многом зависит от того, насколько точно подобрано начальное приближение, несмотря на то что у данного метода хорошая устойчивость к разбросу значений матрицы.

2) Метод Якоби показывает самую большую вычислительную сложность, количество итераций и скорость работы, но при этом у него лучшая точность для матриц с большим диапазоном значений.

3) Метод QL со сдвигом показывает лучшую эффективности среди рассмотренных методов. Данный метод демонстрирует лучшую точность работы алгоритма для матриц с небольшим разбросом диапазона значений, показывает небольшую скорость работы и затраченное количество итераций. При этом данный метод, как и метод Якоби, решает полную задачу нахождения собственных значений, то есть находит все собственные значения матрицы, что расширяет вариативность его применения.

Заключение

В ходе выполнения выпускной квалификационной работы было проведено исследование, объектом которого являлась задача нахождения собственных значений для симметричных матриц большой размерности.

Целью данной выпускной квалификационной работы был сравнительный анализ алгоритмов нахождения собственных значений матриц большой размерности и их программная реализация. В ходе данной работы были поставлены и выполнены следующих задачи.

1) Рассмотрены основные существующие алгоритмы решения задачи поиска собственных значений, а именно метод Данилевского, метод Леверрье-Фадеева, степенной метод, метод вращений Якоби, а также же QR метод и его модификация метод QL со сдвигом.

2) В ходе рассмотрения методов для решения поставленной задачи для реализации были выбраны вращения Якоби, QL со сдвигом, а также степенной метод.

3) Разработана программная на языке программирования C++ в среде программирования Qt-creator, реализующий перечисленные выше алгоритмы, а также проводящая замер данных, необходимых для сравнительного анализа алгоритмов.

4) Проведены эксперименты с использованием разработанной программы и получены результаты для анализа

5) Проведен сравнительный анализ полученных результатов и сделаны соответствующие выводы.

В результате проведенного сравнительного анализа, были сделаны следующие выводы из проделанной работы:

1) Самым простым и быстрым методом является степенной метод, во много превосходя остальные по количеству итерации и скорости работы. Но при этом он имеет значительные минусы. Во-первых, он решает неполную задачу нахождения собственных значений, находя только максимальное значение, что сильно сужает вариативность его применения. Во-вторых, эффективность данного метода во многом зависит от того, насколько точно подобрано начальное приближение, несмотря на то что у данного метода хорошая устойчивость к разбросу значений матрицы.

2) Метод Якоби показывает самую большую вычислительную сложность, количество итераций и скорость работы, но при этом у него лучшая точность для матриц с большим диапазоном значений.

3) Метод QL со сдвигом показывает лучшую эффективности среди рассмотренных методов. Данный метод демонстрирует лучшую точность работы алгоритма для матриц с небольшим разбросом диапазона значений, показывает небольшую скорость работы и затраченное количество итераций. При этом данный метод, как и метод Якоби, решает полную задачу нахождения собственных значений, то есть находит все собственные значения матрицы, что расширяет вариативность его применения.

Список используемой литературы

1) Агарагимов М.Р., Паштаев Б.Д., Мазанов Р.Р. Решение проблемы собственных значений матрицы / Инновационные технологии в АПК. Сборник научных трудов Всероссийской научно-практической конференции с международным участием., 2017. С. 213-218

2) Ануфриев И.Е. MATLAB 7 / И.Е. Ануфриев, А.Б. Смирнов, Е.Н. Смирнова. - СПб.: БХВ-Петербург, 2005. - 1104 с.

3) Атискова О.П., Нурдавлетова Л. А. Сравнительных анализ методов нахождения собственных значений матрицы. Достижения и приложения современной информатики, математики и физики. Материалы III Всероссийской научно-практической заочной конференции. А.Н. Вильданов. 2014. C 9-12.

4) Банников А.С. Численные методы. - Ученое пособие / А.С. Банников, И. Н Ким, Латыпова Н.В. - М.: Удмуртский государственный университет (Ижевск), 2018 - 78 с.

5) Бабенко К.И. Основы численного анализа / К.И. Бабенко. - М., Ижевск: НИЦ «Регулярная и хаоптическая динамика», 2002. - 848 с.

6) Бахвалов Н.С. Численные методы в задачах и упражнениях: учебное пособие / Н.С. Бахвалов, А.В. Лапин, Е. В. Чижонков; ред. В.А. Садовничий. М.: Изд-во "Лаборатория знаний" (ранее "БИНОМ. Лаборатория знаний") 3-е издание, 2013. - 240 с.

7) Вержбицкий В.М. Численные методы. Линейная алгебра и нелинейные уравнения / В.М. Вержбицкий. - М.: Оникс 21 век, 2-е издание, 2005. - 430 с.

8) Деммель Дж. Вычислительная линейная алгебра. Теория и приложения / Дж. Деммель. - М.: Мир, 2001. - 430 c.

9) Долгой В.Е. Построение эффективных итерационных алгоритмов для решения систем линейных алгебраических уравнений с плохо обусловленными матрицами // Известия Южного федерального университета. Технические науки. - 2010. - N 6. - С. 39-42.

10) Долгополов Д.В. Методы нахождения собственных значений и собственных векторов матриц / Д.В. Долгополов. -Санкт-Петербург: СПбГТИ(ТУ), 2005. - 39с.

11) Калиткин Н.Н. Численные методы/ Н.Н Калиткин - М., БХВ-Петербург Учебная литература для вузов, 2011, 592 стр.

12) Козин Р.Г. Алгоритмы численных методов линейной алгебры и их программная реализация: Учебно-методическое пособие / Р.Г. Козин. - М.: НИЯУ МИФИ, 2012. - 192 с.

13) Саад, Ю. Итерационные методы для разреженных линейных систем: в 2 т. / Ю. Саад; пер. с англ. Х.Д. Икрамова. - М.: Изд-во Московского университета, 2013. - Т. 1. - 344 с.

14) Уилкинсон Дж.Х. Справочник алгоритмов на языке АЛГОЛ. Линейная алгебра. Перевод с английского под ред. д-ра техн. наук проф. Ю. И. Топчеева. М., ?Машиностроение?, 1976 г. С. 216-221.

15) Фаддеев Д.К., Вычислительные методы линейной алгебры / Д.К. Фаддеев, В.Н. Фаддеева. - Учебники для вузов. Специальная литература М.: Изд-во «Лань», 4-е издание 2009. - 736 с.

16) Stroustrup B. The C++ Programming Language. Fourth Edition. / B. Stroustrup - Addison-Wesley Professional, 4th edition, 2013 - 1376 p.

17) Gregoire M. Professional C++. Third Edition. / M. Gregoire - Wrox, 3rd edition, 2014 - 984 pp.

18) Nocedal J., Numerical Methods for Solving Inverse Eigenvalue Problems. / J. Nocedal - Forgotten Books, 2017 - 24 p.

19) Wilkinson J. H., The Algebraic Eigenvalue Problem. // J. H. Wilkinson - Clarendon Press, Oxford, 1965 - 662 p.

20) Z. Li, C. Bu and H. Wang, "Inverse Eigenvalue Problem for Generalized Arrow-Like Matrices," Applied Mathematics, Vol. 2 No. 12, 2011, p. 1443-1445