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

• Автор: Мацех, Анна Михайловна
• Шифр специальности: 01.01.07
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Новосибирск
• Количество страниц: 154 с. : ил.

Глава 1 Современное состояние исследований

1.1 Алгебраическая проблема собственных значении

1.2 Сингулярное разложение

1.3 Проблема Уилкинсона

1.4 Последовательности Штурма

1.5 Методы определения спектральных и сингулярных характеристик и их реализация

1.0 Выводы и постановка задачи

Глава 2 Методы бисекций и обратной итерации с оцениваемой точностью

2.1 Метод бисекций с оцениваемой точностью

2.2 Метод обратной итерации с оцениваемой точностью

2.2.1 Определение собственного вектора

2.2.2 Выбор сдвига
2.2.3 Определение начальных векторов
2.2.4 Расчет нескольких собственных векторов
2.3 Выводы
Глава 3 Метод Ланцоша с оцениваемой точностью
3.1 Особенности реализации
3.2 Алгоритм определения собственных чисел
3.3 Особенности расчета сингулярных чисел

3.4 Алгоритм определения сингулярных чисел
3.5 Выноды
Гласа 4 Библиотека Sturm
4.1 Общая характеристика
4.2 Вычислительные схемы
4.3 Верификация и вычислительный эксперимент
4.3.1 Полное спектральное разложение
4.3.2 Частичное спектральное разложение
4.3.3 Частичное сингулярное разложение
4.4 Выводы
Заключение
Приложение А Описание основных программных модулей
библиотеки Sturm
Литература

Актуальность работы
Проблема разработки быстрых алгоритмов, гарантирующих точность при определении спектральных и сингулярных характеристик матриц конечно-разностных и консчпо-элсмептпых аппроксимаций дифференциальных операторов, является центральной проблемой современной вычислительной алгебры. Знание спектральных характеристик необходимо при решении задач моделирования электромагнитных полей |40, 3|, в задачах структурной механики [5, 21], ядерной физики, квантовой химии, при решении задач, описывающих свойства диэлектрических волноводов, при анализе океанографических моделей и во многих других приложениях математической физики [47, 59]. Сингулярное разложение (SVD) используется для распознавания, сжатия и восстановления изображений в компьютерной графике, а в генетике и биологии позволяет делать выводы о эволюции генов и связях между протеинами. Знание пулевых сингулярных чисел произвольной матрицы позволяет определить ее ранг, а также необходимо для построения обобщенного нормального решения систем уравнений, у которых число уравнений не совпадает с числом неизвестных.
Сложность определения спектральных и сингулярных характеристик матриц, возникающих при моделирования физических процессов как правило обусловлена необходимостью определения близких, почти кратных собственных значений и соответствующих им почти коллинсарных собственных векторов, при расчете которых стандартными вычислительными методами наблюдается медленная сходимость, обусловленная потерей ортогональности и точности. Не менее важной является проблема реализации методов определения спектральных и сингулярных характеристик в

тода бисекций с гарантированной точностью [83] для расчета собственных интервалов (2.1) матрицы (1.13) и приближенных собственных значении
А; — (+ + )/2,
где 0 < к < і < тп < п, с точностью
(2.2)
в ІЕЕЕ-754 модели арифметики.
Принципиальным отличием реализации метода бисекций с оцениваемой точностью от реализации с гарантированной точностью является то, что при расчете всех или значительного числа собственных значений исходные интервалы определяются не по теореме Гершгорина (теорема 3), а при помощи С)Г1 метода в реализации Пола, Вокера и Кахана, исключающей извлечение квадратных корней, вычислительная сложность которо-їх) составляет 3 ^ 12 п2 арифметических операций [31]. Вычислительная сложность метода бисскций при расчете всех собственных значений, когда исходные интервалы оцениваются но теореме Гершгорина, составляет 5 ~ 2 кн2 арифметических операций |18|, где к представляет собой число 7-ичпых цифр мантиссы (в ІЕЕЕ-754 модели арифметики с двойной точностью к = 53).
Пусть числа А* Лт, т—к+1 > [п/10], обозначают собственные значения матрицы Т, приближенно рассчитанные (^11 методом в реализации, исключающей извлечение квадратных корней. Метод бисекций с гарантированной точностью применяется к интервалам
[Аі - 2Єшасьш(Т), А,. + 2щшс1і ЩТ)} (2.3)
В этом случае метод фактически применяется для уточнения грубо определенных собственных интервалов (2.3), причем сходимость достигается за несколько шагов.
Характерной особенностью метода бисскций с гарантированной точностью является дополнительное уточнение границ рассматриваемых интср51= шах (А+ - А-)
О <к<і<т<п