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

Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ

РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ОБРАЗОВАНИЯ

«ТОЛЬЯТТИНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

ИНСТИТУТ МАТЕМАТИКИ, ФИЗИКИ И ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

Кафедра «Прикладная математика и информатика»

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 - это единичная матрица того же порядка, что и матрица . Таким образом, коэффициенты характеристического уравнения можно определить, используя данную схему.

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

1.3 Итерационные методы нахождения собственных значений

1.3.1 Степенной метод

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

Если матрица имеет размеры , то у неё обязательно имеются собственных чисел, при этом данные собственные числа не обязательно должны быть различны, и, предположим, что матрица имеет собственных векторов и полную систему из собственных векторов. Тогда это даёт возможность разложить любой вектор в линейную комбинацию собственных векторов (1.14). Далее, умножая уравнение (1.1) на исходную матрицу, получим выражение (1.15), проведя данное умножение k раз получаем равенство (1.16) и выполнив его преобразования получим (1.17):

(1.14)

где - собственные вектора.

(1.15)

(1.16)

(1.17)

Таким образом, воспользовавшись всеми введёнными утверждениями и формулами можно сделать вывод, что данным метод решения частичной задачи нахождения собственного значения реализуется с помощью алгоритма:

1) выбирается или случайно генерируется вектор начального приближения;

2) по формулам (1.18) и (1.19) строится приближение вектора:

(1.18)

(1.19)

где не противоречит условию

3) Итерационно строим приближения, пока не будет достигнуто условие сходимости (1.20):

(1.20)

где - заданная точность;

4) при достижении условия сходимости полученное приближение будет являться собственным вектором, используя который, можно найти собственное значение по формуле (1.21):

(1.21)

поскольку .

1.3.2. Метод скалярный произведений

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

(1.22)

где - матрица, транспонированная с матрицей ,

- выбранный каким-либо образом начальный вектор.

Пусть - действительная матрица и - ее собственные значения, которые предполагаются различными, причем

(1.23)

Возьмем некоторый ненулевой вектор и с помощью матрицы построим последовательность итерации

(1.24)

Для вектора образуем также с помощью транспонированной матрицы вторую последовательность итерации

(1.25)

где

В пространстве выберем два собственных базиса и соответственно для матриц и , удовлетворяющих условиям биортонормировки: .в базисе - через , т. е.

(1.26)

отсюда

(1.27)

(1.28)

Составим скалярное произведение

(1.29)

таким образом,

(1.30)

1.3.3 Метод вращений Якоби

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

Дадим определение матрице вращения. Ортогональная матрица

(1.31)

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

(1.32)

где - заданные целые числа.

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

Далее опишем основную идею метода вращений Якоби. Как уже говорилось матрица - симметричная матрица. Образуем матрицу , столбцами которой будут ортонормированные собственные векторы . для данной матрицы справедлива формула (1.33)

(1.33)

 где -- диагональная матрица с элементами на диагонали.

В методе вращения Якоби матрица строится как предел последовательности ортогональных матриц так, что:

(1.34)

причем при каждом матрица конструируется как произведение матриц вращения.

Образуем по исходной матрице матрицу , и подбираем параметры матрицы вращения, то есть значения , так, чтобы матрица была максимально близка к диагональной. Опуская простые вычисления, представим формулу для вычисления суммы квадратов внедиагональных элементов матрицы :

(1.35)

Далее, определим числа k,l из условия (1.36):

(1.36)

и затем угол ц из условия (1.37)

(1.37)

 (1.38)

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

Опишем и сам алгоритм метода вращений Якоби. Пусть = A. Образуем последовательность матриц , при помощи рекуррентной формулы (1.39):

(1.39)

где параметры матрицы вращения задаются так, что сумма квадратов внедиагональных элементов матрицы уменьшается, то есть используя формулы вида (1.27-1.29). Продолжаем итерации до тех пор, пока все внедиагональные элементы матрицы не станут достаточно малыми.

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

1.3.4 Метод QR

Далее приведем описание метода QR. Данный алгоритм использует плоские преобразования вращений Гивенса. Матрица, определяющая эти преобразования имеет вид . Данная матрица имеет структуру, похожею на матрицу плоских вращений Якоби , только здесь двумерная подматрица из элементов, стоящих на пересечении и ?? строк и столбцов, используется в виде (1.40):

(1.40)

Данные числа ?? и ?? связываются соотношением . Первый полный шаг преобразования Гивенса, применяемого к матрице Хессенберга ??-го порядка в рамках ???? метода, состоит из элементарных подшагов, основной целью которых является последовательное обнуление всех поддиагональных элементов в столбцах от первого до -го [7]. В результате получим разложение матрицы Хессенберга в виде произведения ортогональной и треугольной матриц.

Для определения и на первом промежуточном шаге, используется произведение матриц (1.41):

(1.41)

При этом и берутся такими, что . Это означает, что в результате первого промежуточного шага матрица , полученная при использовании таких и , не будет содержать ненулевых элементов под диагональю в первом столбце.

Аналогично совершается второй промежуточный шаг: матрица получается из предыдущей с помощью матрицы Гивенса , отличающейся от тем, что подматрица смещается на одну позицию вдоль диагонали и угол поворота подбирается так, чтобы в матрице обнулить элементы .

Продолжив далее преобразования Гивенса, в итоге получим правую треугольную матрицу:

(1.42)

Последнее равенство можно переписать в виде:

(1.43)

который позволяет считать выполненным требуемое при разложение

(1.44)

где - ортогональная, а - правая треугольная матрицы. При этом матрица

(1.45)

являющаяся результатом первого полного шага QR метода, сохраняет не только спектр данной матрицы, но и форму Хессенберга, благодаря чему приведение исходной матрицы к почти треугольному виду достаточно сделать только один раз [7].

Очевидно, скалярные параметры и матриц Гивенса , благодаря которым происходит переход от матрицы Хессенберга через матрицы Хессенберга к матрице Хессенберга , можно вычислять на ??-ом промежуточном шаге () по формулам:

(1.46)

(1.47)

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

Алгоритм со сдвигами состоит в следующем. Положить и выполнить:

1. выбрать сдвиг s вблизи некоторого собственного значения ;

2. вычислить по схеме QR разложение для матрицы

3. определить матрицу

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

Матрицы ) и в QR алгоритме со сдвигами будут ортогонально подобными:

 (1.48)

Если - точное собственное значение матрицы ), то QR-итерация сойдется за один шаг.

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

Также следует упомянуть что не обязательно брать верхнюю треугольною матрицу R, точно также можно выбрать нижнюю треугольную. Это приведёт к QL алгоритму, поскольку данное разложение будет представлено в виде A=QL

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

1.4 Выводы по главе 1

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

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

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

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

2. Программная реализация методов нахождения собственных значений

2.1 Структура программы

Как уже было сказано, для сравнения и реализации были выбраны три основных метода нахождения собственных значений: степенной метод, метод вращений Якоби, и метод QL со сдвигом. Данные методы реализованы на языке C++ в среде Qt Creator.

Qt Сreator - это кроссплатформенная свободная среда программирования для разработки на языках С и С++. Разработана для работы с фреймворком Qt и включает в себя графический интерфейс отладчика и визуальные средства разработки интерфейса.

Основа структуры программы включает в себя:

1) подключенные библиотеки (iostream, math, ctime);

2) функция генерации матрицы заданной размерности, использующая генератор псевдослучайный чисел rand;

3) функция вывода матрицы;

4) функция, реализующая степенной метод;

5) функция, реализующая метод вращения Якоби;

6) функция, реализующая преобразование Хаусхолдера, используемая для реализации метода QL;

7) вспомогательная и основная функции, реализующие метод QL со сдвигом;

8) основная часть;

9) интерфейс программы;

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

Работа программы начинается с ввода пользователем размерности матрицы. Учитывая, что рассматриваемые матрица должна быть квадратной и симметричной, вызывается функция Gen_matrix, которая, используя генератор псевдослучайных чисел создает симметричную квадратную матрицу заданной размерности заполняя её числами в диапазоне от 0 до 1. Пример сгенерированной матрицы приведен на рисунке 2.1.

Рисунок 2.1 - Пример сгенерированной матрицы

После этого пользователь выбирает один из трех методов нахождения поиска собственных значений представленной в программе функция Pow_Meth, Jacobi_Meth, QL_Meth, каждая из который принимает на вхож матрицу и её размерность, после чего выводится матрица с помощью функции Print_Matrix, выводятся собственные значения матрицы и данные для анализа, а именно время выполнения алгоритма, количество итераций и максимальное собственное значение матрицы. Блок-схема главной функции программы приведена на рисунке 2.2.

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



Рисунок 2.2- Блок-схема главной функции программы

2.2 Реализация методов нахождения собственных значений.

2.2.1 Степенной метод

Степенной метод реализован в функции Pow_Meth и принимает на вход матрицу и её размерность. Далее генерируется начальное приближение с помощью генератора псевдослучайный числе rand(), проводится основной блок вычислений и выводятся собственное значение и данные для дальнейшего анализа. В связи с простотой данного алгоритма его проще представить в виде блок-схемы. Блок-схема данного метода приведена на рисунке 2.3.



Рисунок 2.3 - Блок-схема степенного метода.

В коде функции важные переменные это:

1) Matr - исходная матрица;

2) n - размерность матрицы;

3) w0 - вектор начального приближения;

4) eps - точность сходимости;

5) eigenvalue - максимальное собственное значение.

К особенностям реализации степенного метода следует отнести несколько важных пунктов. Во-первых, этот метод решает неполную задачу поиска собственных значений, в данном случае он находит только одно максимальное собственное значение. Во-вторых, скорость сходимости и количество итераций метода зависит от того, насколько близко будет сгенерировано начальное приближение к истинному значению. И в-третьих, данный метод использует точность eps для определения погрешности, которая является константой и задаётся вручную.

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

2.2.2 Реализация метода вращения Якоби

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

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

В коде функции важные переменные это:

1) Matr - исходная матрица;

2) n - размерность матрицы;

3) d - массив собственных значений матрицы;

4) переменные с и s - это cos и sin угла поворота;

5) tresh - порог, используемый для обнуление элементов по модулю больших, чем данное значение.

2.2.3 Реализация метода QL со сдвигом

QL метод со сдвигом является одним из самых сложный в реализации методов. В его реализацию включены три функции:

1) Householder_transform.

Эта функция реализует редукцию Хаусхолдера для приведения симметричной матрицы в трехдиагональную форму, необходимую для эффективного использования алгоритма QL со сдвигом. На вход данная функция принимает симметричную матрицу в обычной форме, её размерность и два дополнительных массива d и е. Массив d возвращает диагональ трехдиагональной матрицы, а массив e возвращает внедиагональные элементы.

2) QL_Alg.

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

3) QL_Meth.

Функция, включающая в себя вызов предыдущих двух функций. Эта функция создаёт все необходимые промежуточные переменные, использует алгоритм трансформации Хаусхолдера, полученную трехдиагональную матрицу применяет в функции QL_Alg, и выводит массив полученных собственных значений и данные о работе алгоритма, для анализа.

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

2.2 Интерфейс разработанного приложения

Для того, чтобы работа с приложением была удобна был разработан пользовательский интерфейс с помощью редактора, интегрированного в QT-creator.

Пример реализованного интерфейса приведен на рисунке 2.4



Рисунок 2.4 - Пример реализованного интерфейса

В данном интерфейсе реализованы 4 кнопки и 2 текстовых окна. Кнопка «Create Matrix» создает симметричную матрицу указанной размерности и выводит её в первое текстовое окно «Created Matrix». Ввод размерности матрицы происходит после нажатия на кнопку в диалоговом окне, представленном на рисунке 2.5

Рисунок 2.5 - Ввод размерности матрицы

Ввод размерности матрицы предусмотрен при нажатии на любую из кнопок. Далее, нажимая на кнопки, подписанные как методы, будет происходить вывод и отработка соответствующего метода, а результаты помещены во второе текстовое окно «Results».

Помимо этого, учитывая, что программа рассчитана на работу с матрицами большой размерности, и, исходя из предположения, что для анализа полученных результатов нет необходимости в отслеживании абсолютно всех собственных значений и печати матрицы целиком было реализовано дополнительное ограничение. Данное ограничение заключается в том, что в текстовые поля могут быть выведены только первые 1010 значений строк и столбцов матрицы, а также только 10 собственных значений. Пример такого вывода приведен на рисунках 2.6 и 2.7 соответственно. Для примера была подана размерность матрицы в 100 на 100 элементов.

Рисунок 2.7 - Предупреждение о неполном выводе результатов



Рисунок 2.7 - Результат работы метода Якоби при неполном выводе

2.4 Тестирование реализации алгоритмов

Для проверки работоспособности реализованных алгоритмов проведем контрольное тестирование, подав для всех алгоритмов одинаковые входные данные в виде матрицы размерности 55 и сверив результаты выполнения функцией, встроенной в пакет Matlab Результаты тестирования приведены на рисунках 2.8-2.9. Для этого сгенерируем случайную матрицу и подадим одинаковые входные данные для всех функций.

Рисунок 2.8 - Результаты тестирования алгоритмов



Рисунок 2.9 - Контрольные данные из пакета Matlab

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

2.5 Выводы по главе 2

Таким образом, были описаны программные реализации описанных методов на языке С++ с использованием QT-creator. В результате разработано приложение, которое будет использоваться для проведения вычислительных экспериментов.

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

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

3. Сравнительный анализ реализаций

3.1 Формат проводимых экспериментов

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

Вычислительные эксперименты проводились на персональном компьютере со следующими характеристиками, приведенными в таблице 1.

Таблица 3.1 - Технические данные ПК

Процессор	AMD Ryzen 5 2600 Six-Core Processor 3.40 GHz
Оперативная память	16 GB
Операционная система	Microsoft Windows 10

Эксперименты проводились на случайно сгенерированных квадратных симметричных плотных матриц с разным диапазоном значений с плавающей точкой. Принятые диапазоны: от 0 до 1, и от 0 до 100.

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

3.2 Результаты экспериментов

Эксперименты проводились в порядке рассмотренных методов. Рассмотрим данные каждого метода в отдельности, собирая данные в таблицу и построив графики зависимости времени работы от размерности матрицы.

Степенной метод отличается от остальных двух методов по многим признакам. Во-первых, данный метод используется для решения неполной задачи нахождения собственных векторов, то есть находит только одно, максимальное собственное значение. Также данный метод является самым настраиваемым, то есть его показатели скорости схождения во многом зависят от начального приближения и заданной точности (eps). В ходе проводимых экспериментов начальное приближение генерировалось случайным образом, а значение eps было . Для наглядности результаты сведены в таблицу 3.3 для диапазона от 0 до 1 и в таблицу 3.4 для диапазона от 0 до 100.

График зависимости размерности от времени для степенного метода приведен на рисунке 3.1

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

Размер матрицы	Точность	Количество итераций	Время работы
500500		12	12 мс
600600		6	9 мс
700700		6	11 мс
800800		8	20 мс
900900		9	29 мс
10001000		8	31 мс

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

Размер матрицы	Точность	Количество итераций	Время работы
500500		8	8 мс
600600		8	11 мс
700700		7	14 мс
800800		7	18 мс
900900		9	23 мс
10001000		12	33 мс

Рисунок 3.1 - График зависимости степенного метода

По приведенным результатам сразу можно наблюдать особенности степенного метода. Для матрицы с диапазоном значений от 0 до 1. Рост времени и количество итераций неравномерный. Это можно связать с тем, что для матрицы размером 500 было сгенерировано самое неудачное начальное приближение, в связи с чем на лицо замедление времени работы и увеличение количества итераций.

Далее приведены результаты для метода Якоби. Следует напомнить, что метод Якоби решает полную задачу нахождения собственных значений, а значит время выполнения и количество итераций ожидается значительно больше, чем для степенного метода. Результаты сведены в таблицы 3.3 и 3.4, график представлен на рисунке 3.2

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

Размер матрицы	Точность	Количество итераций	Время работы
500500		5501	2524
600600		6601	3906
700700		7701	7017
800800		8801	10159
900900		10801	15838
10001000		12001	26110

Таблица 3.4 Результаты работы метода Якоби с диапазоном от 0 до 100

Размер матрицы	Точность	Количество итераций	Время работы
500500		5501	2549
600600		6601	4164
700700		7701	7020
800800		8801	10173
900900		10801	15684
10001000		12001	25979

Рисунок 3.2 - График зависимостей метода Якоби

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

Далее рассмотри метод QL со сдвигом, учитывая, что для данного метода проводилась дополнительные преобразования матрицы, ожидается улучшение показателей по сравнению с методом Якоби. Результаты работы метода QL сведены в таблицы 3.5 и 3.6, график представлен на рисунке 3.3

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

Размер матрицы	Точность	Количество итераций	Время работы
500500		1803	257
600600		2177	460
700700		2529	729
800800		2833	1081
900900		3257	1559
10001000		3601	2115

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

Размер матрицы	Точность	Количество итераций	Время работы
500500		1816	262
600600		2165	366
700700		2537	730
800800		2882	1082
900900		3242	1541
10001000		3585	2191



Рисунок 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

Размещено на Allbest.ru

...