§ 1. Классификация задач на собственные числа Перечислим некоторые возможные постановки проблемы собственных значений. 1) Полная проблема собственных значений. Заключается в задаче поиска всех собственных чисел заданной матрицы. В некоторых случаях вычисление также и собственных векторов. 2) Частичная проблема собственных значений. Заключается в вычислении некоторого подмножества собственных чисел, а также, возможно, требуется соответствующих им собственных векторов. Этим подмножеством может быть: а) к наибольших (наименьших) собственных чиселб) собственные значения, принадлежащие заданному интервалу. С другой стороны, при решении проблемы собственных значений все матрицы разбиваются на два класса, существенно различающих по свойствам: эрмитовы матрицы (в вещественном случае симметричные) и неэрмитовы (в вещественном случае нессиметричные). По этому признаку выделяют симметричную проблему собственных значений и несимметричную. Каждый из этих классов в свою очередь может быть разбит на подклассы. При этом удобно выделять в подклассы матрицы, для которых развиты какиенибудь специальные методы или имеются эффективные модификации методов, применяемых в общем случае. Отдельной задачей, представляющей существенный интерес для различных инженерных расчетов, выделяют проблему собственных значений для матрицы АА (или, А А), то есть задачу вычисления сингулярных чисел (возможно, и сингулярных векторов). Для задач подобного рода имеется отдельная группа алгоритмов. Для задач средних размеров, матрицы которых могут быть целиком размещены в оперативной памяти, используются обычно численные методы, основанные на итерационном приведении исходной матрицы, А общего вида с помощью преобразований подобия к матрице В специального вида (например, диагонального или треугольного), для которой проблема собственных значений решается достаточно просто. В целях экономии памяти для некоторых матриц (симметричных, ленточных, симметричных) может быть использована компактная форма хранения. Для задач больших размеров, матрицы которых, как правило, являются разреженными, обеспечивающих возможно как использование хранение специальных данных в памяти, методов, так и компактное оптимальную по сложности реализацию алгоритма (см., например, [12]). Наибольший интерес представляют следующие типы матриц: вещественные симметричные, вещественные несимметричные, разреженные, симметричные трехдиагональные, почти треугольные). Классификации матриц и видов решаемых задач представлены на рис. 1 и 2. матрицы Хессенберга (несимметричные Виды матриц, А Симметричная Несимметричная т, Плотная Плотная «W Разреженная >w Разреженная Трехдиагональная e H T O шая) г Почти треугольная Симметричная проблема собственных значений Несимметричная проблема собственных значений Рис. 1. Виды задач Искать все собств. числа Искать собств. векторы Не искать собств. векторы Искать несколько собств. чисел Искать собств. векторы Не искать собств. векторы Полная проблема собственных значений Частичная проблема собственных значений Рис. 2.§ 2. О предмете данной диссертации Предметом данной диссертации являются новые алгоритмы: 1) Алгоритм, вычисляющий наибольшее собственное число симметричной вещественной матрицы- 2) Алгоритм, вычисляющий наибольшее сингулярное число несимметричной вещественной матрицы. Идея алгоритмов представлена в § 1 главы 2. Вычислительные схемы и доказательства сходимости предложенных алгоритмов даны в § 2 и § 3 главы 2. Параграфы 4, 5 и 6 дают необходимую программной реализации предложенных информацию для эффективной алгоритмов. Параграфы 7, 8, 9 описывают возможные модификации предложенных алгоритмов.
Заключение
.
В диссертации получены следующие научные результаты.
1. Предложен новый алгоритм, вычисляющий наибольшее собственное число симметричной матрицы, а также новый алгоритм, вычисляющий наибольшее сингулярное число несимметричной матрицы.
2. Линейная сходимость предложенных алгоритмов теоретически доказана, эмпирически проверена.
3. Установлена связь между предложенными алгоритмами и методом релаксации отношения Релея.
4. Построена наиболее оптимальная реализация предложенных алгоритмов, обеспечивающая в вычислительном процессе минимальное количество арифметических операций на каждом шаге.
5. Установлены оптимальные критерии, позволяющие останавливать вычислительный процесс при достижении заданной точности.
6. Предлагаются некоторые модификации, позволяющие ускорить сходимость (в частности, применение техники верхней релаксации).
7. Построена вычислительная схема, позволяющая применять матрицы отражения вместо матриц вращения.
8. Произведено сравнение предложенных алгоритмов с ранее известными алгоритмами на основе их программной реализации и тестовых испытаний. Эксперименты проводились для матриц различной размерности, для различных относительных точностей расчета, для матриц с различной близостью старших собственных (сингулярных) чисел, для вычислительных процессов с разным коэффициентом верхней релаксации. Эмпирически установлены различные зависимости, выявлены наиболее эффективные алгоритмы для каждой конкретной задачи.
Публикации по теме диссертации.
1. Борзых А. Н. О сходимости одного оптимизационного алгоритма вычисления наибольшего собственного значения симметричной матрицы // Записки научных семинаров ПОМИ. Численные методы и вопросы организации вычислений. Т. 346. СПб., 2007. С. 5−20.
2. Борзых А. Н. Об одном оптимизационном алгоритме, вычисляющем наибольшее син1улярное число вещественной матрицы // Вестн. С-Петерб. ун-та. Серия «Математика. Механика. Астрономия». СПб., 2008. С. 56−67.
3. Борзых А. Н. Новый алгоритм быстрого решения частичной проблемы собственных значений // Известия СПбГЭТУ «ЛЭТИ». Серия Информатика, управление и компьютерные технологии. Вып. 1. 2004. С. 27−36.
4. Борзых А. Н. Эффективный подход к решению на ЭВМ частичной проблемы собственных значений // Материалы семинаров политехнического симпозиума. Май-июнь 2004 г. Изд-во СПбГПУ. 2004. С. 28−29.
5. Борзых А. Н. Эффективный подход к решению на ЭВМ частичной проблемы собственных значений // Девятая Санкт-Петербургская ассамблея молодых ученых и специалистов. Изд-во СПбГУ. 2004. С. 18.
6. Борзых А. Н. Оптимизация алгоритмов вычисления собственных чисел симметричной матрицы // Математика. Компьютер. Образование. Тезисы. Вып. № 12. М.- Ижевск: РХД, 2005. С. 86.
7. Борзых А. Н. Анализ динамики сходимости различных методов решения частичной проблемы собственных значений // Научная сессия МИФИ-2005: Сборник научных трудов. Т. 12. Изд-во МИФИ. 2005. С. 173−174.
8. Борзых А. Н. Оценка спектрального радиуса трехдиагональной матрицы // Материалы семинаров политехнического симпозиума. Июнь 2005 г. Изд-во СПбГПУ. 2005. С. 9−13.
9. Борзых А. Н. Оценка спектрального радиуса плотной симметричной матрицы // Труды политехнического симпозиума. Апрель — декабрь 2004 г. Изд-во СПбГПУ. 2005. С. 53−54.
10.Борзых А. Н. Вычислительная сложность методов расчета максимального собственного значения симметричной матрицы // Известия СПбГЭТУ «ЛЭТИ». Сер. Информатика, управление и компьютерные технологии. 2005. Вып. 1/2005. С. 48−56.
11 .Борзых А. Н. Исследование и анализ методов расчета собственных значений симметричных матриц // Десятая Санкт-Петербургская ассамблея молодых ученых и специалистов. Изд-во СПбГУ. 2005. С. 14.
12. Борзых А. Н. Эффективная локализация собственных значений симметричных матриц высокого порядка // Научная сессия МИФИ-2006. Сборник научных трудов. Т. 7. Изд-во МИФИ. 2006. С. 159−160.
13. Борзых А. Н. Об одном алгоритме вычисления максимального собственного значения симметричной матрицы // Математика. Компьютер. Образование. Тезисы. Вып. № 15. М.- Ижевск: РХД, 2008. С. 50.
