МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ
РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ОБРАЗОВАНИЯ
«ТОЛЬЯТТИНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»
ИНСТИТУТ МАТЕМАТИКИ, ФИЗИКИ И ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ
Кафедра «Прикладная математика и информатика»
02.03.03. Математическое обеспечение и администрирование информационных систем
Мобильные и сетевые технологии
Выпускная квалификационная работа
(Бакалаврская работа)
на тему «Сравнительный анализ алгоритмов нахождения собственных значений симметричных матриц большой размерности»
Студент: С.А. Скоков
Руководитель: М.А. Тренина
Тольятти
2021
Аннотация
Выпускная квалификационная работа посвящена сравнительному анализу алгоритмов нахождения собственных значений симметричных матриц большой размерности.
Ключевые слова: симметричная, матрица, собственные значения, алгоритмы.
При работе с динамическими системами и соответствующими системами линейных дифференциальных уравнений вычисление собственных значений матриц этих систем позволяет определить особенности их поведения во времени, а также оценить устойчивость такой системы. Поэтому нахождение и оценка спектральных свойств матриц - это задачи, часто возникающие перед специалистами во многих областях, от астрофизики до машиностроения.
Объектом исследования данной бакалаврской работы являются алгоритмы поиска собственных значений симметричных матриц большой размерности.
Предметом исследования является процесс решения задачи собственных значений симметричных матриц большой размерности.
Целью данной бакалаврской работы является сравнительный анализ методов нахождения собственных значений симметричных матриц большой размерности и их программная реализация.
В ходе выполнения выпускной работы было проведено исследование с применением разработанного на языке C++ приложения, а также сделаны выводы о работе алгоритмов.
Выпускная квалификационная работа представлена на 46 страницах, включает 13 иллюстраций, 7 таблиц, 48 формул, и список используемой литературы, состоящий из 20 источников.
Abstract
The title of the graduation work is « Comparative analysis of algorithms for finding the eigenvalues of symmetric matrices of large dimension»
The graduation work consists of an explanatory note on 46 pages, includes 13 illustrations, 7 tables, 48 formulas, the list of n references including n foreign source.
The object of this work is algorithms for finding eigenvalues of symmetric matrices of large dimension.
The subject of this work is the process of solving the problem of eigenvalues of symmetric matrices of large dimension
The aim of the graduation work is comparative analysis of methods for finding eigenvalues of symmetric matrices of large dimension and their software implementation
The graduation work may be divided into several logically connected parts.
In the first part we start with the statement of the problem and then logically pass over to its possible solutions. In the second part we describe the process of developing a software application, which we will use in future experiments. And finally, in the third part we present the results of experiments and on their basis, we can draw conclusions about the work of the above algorithms.
In the conclusion, conclusions are drawn about the specifics of the work of the algorithms given, and so an analysis of their work is carried out based on the accuracy, the work time of the algorithm and the number of iterations with different ranges of matrix values.
Содержание
Введение
1. Обзор методов решения задачи нахождения собственных значений симметричных матриц большой размерности
1.1 Постановка задачи нахождения собственных значений
1.2 Точные алгоритмы нахождения собственных значений
1.2.1 Метод А.М. Данилевского
1.2.2. Метод Леверрье-Фаддеева
1.3 Итерационные методы нахождения собственных значений
1.3.1 Степенной метод
1.3.2. Метод скалярный произведений
1.3.3 Метод вращений Якоби
1.3.4 Метод QR
1.4 Выводы по главе 1
2. Программная реализация методов нахождения собственных значений
2.1 Структура программы
2.2 Реализация методов нахождения собственных значений
2.2.1 Степенной метод
2.2.2 Реализация метода вращения Якоби
2.2.3 Реализация метода QL со сдвигом
2.3 Интерфейс разработанного приложения
2.4 Тестирование реализации алгоритмов
2.5 Выводы по главе 2
3. Сравнительный анализ реализаций
3.1 Формат проводимых экспериментов
3.2 Результаты экспериментов
3.3 Сравнение результатов работы методов
3.4 Выводы по главе 3
Заключение
Список используемой литературы
Введение
Собственные значения и соответствующие собственные вектора матрицы - это одни из важных понятий в линейной алгебре. Множество собственных значений, или так называемый спектр матрицы, характеризует некоторые свойства систем, полезные для проведения анализов.
При работе с динамическими системами и соответствующими системами линейных дифференциальных уравнений вычисление собственных значений матриц этих систем позволяет определить особенности их поведения во времени, а также оценить устойчивость такой системы. Поэтому нахождение и оценка спектральных свойств матриц - это задачи, часто возникающие перед специалистами во многих областях, от астрофизики до машиностроения.
Соответственно, актуальность проблемы, рассматриваемой в данной выпускной квалификационной работе тесно связана с возникновением подобных проблем в физики и механике. Для матриц больших размерностей эта задача связана с огромным количеством алгебраический действий, что говорит о большой вычислительной сложности, и приводит к большой трудоёмкости решения даже для современных компьютеров.
Целью данной бакалаврской работы является сравнительный анализ методов нахождения собственных значений симметричных матриц большой размерности и их программная реализация.
Объектом исследования данной бакалаврской работы являются алгоритмы поиска собственных значений симметричных матриц большой размерности.
Предметом исследования является процесс решения задачи собственных значений симметричных матриц большой размерности.
Задачи, которые необходимо решить для достижения указанной цели, это:
1) выбрать методы для исследования, рассмотрев математическое описание задачи и существующие методы решения;
2) реализовать вычисление собственных значений симметричных матриц большой размерности несколькими различными методами на языке С++;
3) провести вычислительные эксперименты и собрать данные для анализа;
4) провести сравнительных анализ результатов и сделать выводы.
Данная выпускная квалификационная работа состоит из введения, трёх глав и заключения:
В первой главе представлено математическое описание решения задачи нахождения собственных значений матрицы, рассмотрены точные (Метод Данилевского и метод Леверрье-Фадеева) и итерационные алгоритмы (Степенной метод, метод скалярный произведений, метод вращений Якоби, метод QR) решения этой задачи, выбраны методы для дальнейшей реализации. алгоритм симметричная матрица размерность
Во второй главе описана программная реализация алгоритмов на языке С++.
В третьей главе представлены результаты вычислительных экспериментов и их сравнительных анализ.
1. Обзор методов решения задачи нахождения собственных значений симметричных матриц большой размерности
1.1 Постановка задачи нахождения собственных значений
Следует начать математическое описание задачи с определения собственных значений. Данное определение проще сформулировать через собственные вектора. Вектор, умножение матрицы на который в результате даст тот же вектор, но умноженный на определенную скалярную величину называется собственным вектором матрицы, при этом данная скалярная величина и будет искомым собственным значением. То есть, если имеется некая квадратная матрица с размерностью , то её собственное значение будет удовлетворять равенству (1.1)
(1.1)
где - собственные вектор матрицы ;
- собственное значение.
Также следует отметить, что существует условие существования собственных значений, которое выражается в требовании (1.2)
(1.2)
где - единичная матрица.
Говоря о собственных значениях, следует помнить, что данные значения могут быть и комплексными, и возникают в случаях, когда рассматриваемая матрица не является симметричной. В такой ситуации собственные значения матрицы являются комплексно-сопряженными числа вида (1.3)
(1.3)
Если же матрица симметрична, всё её значения гарантированно являются вещественными и при этом все собственные вектора будут ортогональны между собой.
Классические методы нахождения спектральный свойств матрицы сводятся к решению её характеристического уравнения вида (1.4)
(1.4)
где - корни многочлена кратности .
Такие методы получили название точных (или прямых) и имеют определенные недостатки. Дело в том, что при увеличении размерности матрицы растёт и сложность вычисления корней многочлена (1.4), и при больших размерностях становится слишком трудно решаемой задачей.
Поэтому чаще используются итерационные методы, которые находят приближение к собственным значениям, не используя характеристическое уравнение. Итерационные методы обладают достаточно высокой точностью и упрощают вычислительный процесс.
Таким образом глобально все методы можно разделить на два типа:
1) точные, основанные на нахождении и решении характеристического многочлена (1.4) (методы Данилевского, Леверрье-Фадеева и др.);
2) итерационные, реализующий поиск значений путем множества итераций, приближающий значения к истинным с некоторой точностью (степенной метод, метод QR, метод вращений Якоби и т.д.).
Помимо этого, саму задачу поиска собственных значений можно разделить на два типа, в зависимости от цели решения задачи:
1) полная проблема собственных значений, то есть отыскание всех имеющихся собственных чисел;
2) частичная проблема собственных значений, то есть нахождение только некоторых собственных чисел (зачастую максимальное либо минимальное).
Далее подробно рассмотрим некоторые алгоритмы решения данной задачи.
1.2 Точные алгоритмы нахождения собственных значений
1.2.1 Метод А.М. Данилевского
Метод А. М. Данилевского - точный метод решения полной задачи нахождения собственных значений матриц, основанный на поиске и решении характеристического уравнения. Суть метода А.М. Данилевского заключается в преобразовании исходной квадратной матрицы (1.5)
(1.5)
в подобную ей матрицу Фробениуса (1.6)
(1.6)
с помощью матрицы подобия по формуле (1.7)
(1.7)
(1.8)
(1.9)
где - элементы матрицы подобия , стоящие на n-1 строке,
- элементы матрицы смежности графа, стоящие на n строке.
Для матрицы характеристический многочлен может быть найден, если последовательно раскладываться определитель по элементам первого столбца. В результате получается:
(1.10)
Из последнего соотношения видно, что элементы 1-й строки матрицы в форме Фробениуса являются коэффициентами её собственного многочлена и, следовательно, собственного многочлена исходной матрицы .
Решив полученное уравнение (1.10), найдём собственные значения матрицы . Далее, матрица , полученная в ходе решения методом Данилевского, может использоваться при нахождении собственных векторов матрицы .
1.2.2. Метод Леверрье-Фаддеева
Метод Леверрье основан на применении формул Ньютона для сумм степеней корней алгебраического уравнения.
Пусть
(1.11)
характеристический многочлен матрицы и - это полная совокупность его корней, то есть каждый корень повторяется столько раз, какова его кратность.
Если обозначим . Тогда получаем, что при , справедливы формулы Ньютона (1.12):
(1.12)
Если все числа известны, то, решив полученную реккурентную систему (1.13) можно найти необходимые для решения уравнения (1.12) коэффициенты :
(1.13)
Также при этом числа и будут являться собственными значения матрицы , а и - это будет сумма элементов главной диагонали матрицы , степени находятся непосредственным перемножением.
Таким образом, общая схема раскладывания определителя по методу Леверрье состоит в следующем:
1) вычисляются - степени данной матрицы ;
2) находятся соответствующие - суммы элементов главных диагоналей матриц ;
3) по формулам (1.13) определяются искомые коэффициенты .
В дальнейшем Д.К. Фадеев предложил видоизменить представленный метод Леверрье. В результате метод Леверрье-Фадеева по сравнению с методом Леверрье более прост в процессе вычисления коэффициентов характеристического уравнения, а также позволяет определить ещё и обратную матрицы и собственные вектора.
Основная суть всех изменений заключается в том, что вместо использования последовательности , в данной модификации метода используется последовательность , построенной по схеме, приведенной на рисунке 1.1.
Рисунок 1.1 - схема вычисления по методу Леверрье-Фадеева
На рисунке 1.1 - это единичная матрица того же порядка, что и матрица . Таким образом, коэффициенты характеристического уравнения можно определить, используя данную схему.