Аннотация 2
Введение 5
1 Обзор методов решения задачи нахождения собственных значений симметричных матриц большой размерности 7
1.1 Постановка задачи нахождения собственных значений 7
1.2 Точные алгоритмы нахождения собственных значений 9
1.2.1 Метод А.М. Данилевского 9
1.2.2 Метод Леверрье-Фаддеева 10
1.3 Итерационные методы нахождения собственных значений 13
1.3.1 Степенной метод 13
1.3.2 Метод скалярный произведений 14
1.3.3 Метод вращений Якоби 16
1.3.4 Метод QR 19
2 Программная реализация методов нахождения собственных значений 24
2.1 Структура программы 24
2.2 Реализация методов нахождения собственных значений 26
2.2.1 Степенной метод 26
2.2.2 Реализация метода вращения Якоби 28
2.2.3 Реализация метода QL со сдвигом 28
2.3 Интерфейс разработанного приложения 29
2.4 Тестирование реализации алгоритмов 32
3 Сравнительный анализ реализаций 34
3.1 Формат проводимых экспериментов 34
3.2 Результаты экспериментов 35
3.3 Сравнение результатов работы методов 40
Заключение 43
Список используемой литературы 45
Собственные значения и соответствующие собственные вектора матрицы - это одни из важных понятий в линейной алгебре. Множество собственных значений, или так называемый спектр матрицы, характеризует некоторые свойства систем, полезные для проведения анализов.
При работе с динамическими системами и соответствующими системами линейных дифференциальных уравнений вычисление собственных значений матриц этих систем позволяет определить особенности их поведения во времени, а также оценить устойчивость такой системы. Поэтому нахождение и оценка спектральных свойств матриц - это задачи, часто возникающие перед специалистами во многих областях, от астрофизики до машиностроения.
Соответственно, актуальность проблемы, рассматриваемой в данной выпускной квалификационной работе тесно связана с возникновением подобных проблем в физики и механике. Для матриц больших размерностей эта задача связана с огромным количеством алгебраический действий, что говорит о большой вычислительной сложности, и приводит к большой трудоёмкости решения даже для современных компьютеров.
Целью бакалаврской работы является сравнительный анализ методов нахождения собственных значений симметричных матриц большой размерности и их программная реализация.
Объектом исследования данной бакалаврской работы являются алгоритмы поиска собственных значений симметричных матриц большой размерности.
Предметом исследования является процесс решения задачи собственных значений симметричных матриц большой размерности.
Задачи, которые необходимо решить для достижения указанной цели, это:
1) выбрать методы для исследования, рассмотрев математическое описание задачи и существующие методы решения;
2) реализовать вычисление собственных значений симметричных матриц большой размерности несколькими различными методами на языке С++;
3) провести вычислительные эксперименты и собрать данные для анализа;
4) провести сравнительных анализ результатов и сделать выводы.
Данная выпускная квалификационная работа состоит из введения, трёх глав и заключения:
В первой главе представлено математическое описание решения задачи нахождения собственных значений матрицы, рассмотрены точные (Метод Данилевского и метод Леверрье-Фадеева) и итерационные алгоритмы (Степенной метод, метод скалярный произведений, метод вращений Якоби, метод QR) решения этой задачи, выбраны методы для дальнейшей реализации.
Во второй главе описана программная реализация алгоритмов на языке С++.
В третьей главе представлены результаты вычислительных экспериментов и их сравнительных анализ.
В ходе выполнения выпускной квалификационной работы было проведено исследование, объектом которого являлась задача нахождения собственных значений для симметричных матриц большой размерности.
Целью данной выпускной квалификационной работы был сравнительный анализ алгоритмов нахождения собственных значений матриц большой размерности и их программная реализация. В ходе данной работы были поставлены и выполнены следующих задачи.
1) Рассмотрены основные существующие алгоритмы решения задачи поиска собственных значений, а именно метод Данилевского, метод Леверрье-Фадеева, степенной метод, метод вращений Якоби, а также же QR метод и его модификация метод QL со сдвигом.
2) В ходе рассмотрения методов для решения поставленной задачи для реализации были выбраны вращения Якоби, QL со сдвигом, а также степенной метод.
3) Разработано приложение на языке программирования C++ в среде Qt-creator, реализующий перечисленные выше алгоритмы, а также проводящая замер данных, необходимых для сравнительного анализа алгоритмов.
4) Проведены эксперименты с использованием разработанной программы и получены результаты для анализа.
5) Проведен сравнительный анализ полученных результатов и сделаны соответствующие выводы.
В результате проведенного сравнительного анализа, были сделаны следующие выводы из проделанной работы:
1) Самым простым и быстрым методом является степенной метод, во много превосходя остальные по количеству итерации и скорости работы. Но при этом он имеет значительные минусы. Во-первых, он решает неполную задачу нахождения собственных значений, находя только максимальное значение, что сильно сужает вариативность его применения. Во-вторых, эффективность данного метода во многом зависит от того, насколько точно подобрано начальное приближение, несмотря на то что у данного метода хорошая устойчивость к разбросу значений матрицы.
2) Метод Якоби показывает самую большую вычислительную сложность, количество итераций и скорость работы, но при этом у него лучшая точность для матриц с большим диапазоном значений.
3) Метод QL со сдвигом показывает лучшую эффективности среди рассмотренных методов. Данный метод демонстрирует лучшую точность работы алгоритма для матриц с небольшим разбросом диапазона значений, показывает небольшую скорость работы и затраченное количество итераций. При этом данный метод, как и метод Якоби, решает полную задачу нахождения собственных значений, то есть находит все собственные значения матрицы, что расширяет вариативность его применения.
