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

Рисунок 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 - Технические данные ПК

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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