Введение к работе
Актуальность работы. Проблема разработки алгоритмов, имеющих низкую вычислительную сложность и гарантирующих точность при определении спектральных и сингулярных характеристик матриц конечно-разностных и конечно-элементных аппроксимаций дифференциальных операторов, является центральной проблемой современной вычислительной алгебры
Знание спектральных характеристик необходимо при решении задач моделирования электромагнитных полей, в задачах структурной механики, ядерной физики, квантовой химии, при решении задач, описывающих свойства диэлектрических волноводов, при анализе океанографических моделей и во многих других приложениях математической физики Знание нулевых сингулярных чисел произвольной матрицы позволяет определить ее ранг, а также необходимо для построения обобщенного нормального решения систем уравнений, у которых число уравнений не совпадает с числом неизвестных Сингулярное разложение (SVD) используется для распознавания, сясатия и восстановления изображений, а в генетике и биологии позволяет делать выводы о эволюции генов и связях между протеинами
Сложность определения спектральных и сингулярных характеристик матриц конечно-разностных и конечно-элементных аппроксимаций дифференциальных операторов обусловлена сложными спектральными свойствами, большим размером и разреженной структурой этих матриц Не менее важной является проблема реализации методов определения спектральных и сингулярных характеристик матриц дискретных аппроксимаций дифференциальных операторов в виде библиотек подпрограмм и прикладных пакетов для современных вычислительных систем
Цель работы Целью диссертации является разработка методов определения спектральных характеристик симметричных вещественных матриц и сингулярных характеристик несимметричных вещественных матриц с оцениваемой точностью и реализация этих методов в виде комплекса программ, предназначенного для решения задач моделирования физических процессов современными вычислительными средствами Под реализацией методов решения задач на собственные значения с оцениваемой точностью подразумевается реализация этих методов в стандартной IEEE-754 модели арифметики, основанная на использовании собственных интервалов и, при необходимости, двусторонних последовательностей Штурма
Защищаемые положения. На защиту выносятся
метод обратной итерации с оцениваемой точностью, предназна
ченный для расчета заданного числа собственных векторов сим
метричных вещественных трехдиагональных и трехдиагонализован-
ных матриц и сингулярных векторов несимметричных вещественных
двухдиагональных и двухдиагонализованных матриц,
в метод Ланцоша с оцениваемой точностью, предназначенный для расчета заданного числа различных собственных значений и собственных векторов симметричных вещественных разреженных матриц большого размера, а также для расчета заданного числа различных сингулярных чисел и сингулярных векторов несимметричных вещественных разреженных матриц большого размера,
библиотека ANSI С-программ Sturm, модули которой реализуют ме
тоды обратной итерации, Ланцоша и бисекций с оцениваемой точно
стью, предназначенные для определения спектральных и сингуляр
ных характеристик матриц, возникающих в дискретных аппрокси
мациях задач моделирования физических процессов
Научная новизна. В методе обратной итерации с оцениваемой точностью при выборе сдвига используются собственные интервалы - наименьшие машинно-представимые интервалы, гарантированно содержащие собственные значения рассматриваемой матрицы Формулируется и доказывается теорема о выборе сдвига в методе обратной итерации с оцениваемой точностью Расчет собственных интервалов производится методом бисекций с оцениваемой точностью, представляющем собой новую реализацию метода бисекций в сочетании с QR-методом При определении неколлинеарной системы векторов начального приближения, соответствующих почти кратным и численно кратным собственным значениям, используется новая вычислительная схема неполного спектрального исчерпывания Вычислительная схема спектральной рекурсии используется для расчета вектора начального приближения, соответствующего изолированному собственному значению
В методе Ланцоша с оцениваемой точностью собственные интервалы используются для корректной идентификации истинных собственных значений Метод обратной итерации с оцениваемой точностью применяется для оценки точности собственных и сингулярных чисел, а также при расчете собственных и сингулярных векторов Частичная двухдиагонализация Голуба-Кахана-Ланцоша без реортогона-лизации применяется при расчете сингулярных характеристик несимметричных матриц
Практическая значимость работы. Алгоритмы, описывающие методы обратной итерации, Ланцоша и бисекций с оцениваемой точностью, были реализованы в виде программных модулей ANSI С библиотеки Sturm, реализованной в стандартной модели арифметики ПСЕЕ-754 с двойной точностью для операционной системы Linux Библиотека Sturm является отчуждаемым программным комплексом, предназначенным для определения с оцениваемой точностью спектральных ха-
рактеристик симметричных вещественных матриц и сингулярных характеристик несимметричных вещественных матриц дискретных аппроксимаций задач моделирования физических процессов Вычислительный эксперимент демонстрирует высокую эффективность и точность программных модулей библиотеки Sturm
Достоверность полученных результатов проверялась в ходе сравнительного анализа результатов решения задач моделирования физических процессов в библиотеке Sturm с результатами решения этих же задач в библиотеке LAPACK и пакете Matlab Тестирование проводилось на матрицах из наборов данных Matrix Market, Harwell-Boemg, NEP, SPARSKIT и TOKAMAK, возникающих в конечно-разностных и конечно-элементных аппроксимациях задач моделирования конвективно-диффузионных процессов, задач моделирования электромагнитных полей в ускорителях элементарных частиц и в диэлектрических волноводах, а также на серии матриц большой размерности, генерируемых при решении задачи моделирования электрического поля в нефтяной скважине векторным методом конечных элементов
Апробация работы. Результаты исследований докладывались автором на семинаре С К Годунова 'Математика в приложениях' в ИМ СО РАН, на семинарах ИВМиМГ СО РАН и ИВТ СО РАН, на Всероссийской конференции по вычислительной математике 'КВМ-07' (Новосибирск, Россия, 2007г), на минисимпозиуме 'Последние достижения в плотной линейной алгебре' в рамках конференции 'Современный уровень развития научных и параллельных вычислений' (Умеа, Швеция, 2006г) по приглашению организаторов минисимпозиума, на 13-ой Конференции международного общества линейной алгебры (Амстердам, Нидерланды, 2006г), в форме доклада по запросу группы разработчиков библиотеки LAPACK, на Восьмой конференции по ите-
рационным методам (Коппер Маунтейн, Колорадо, США, 2004г), на Восьмой конференции общества индустриальной и прикладной математики (Уильямсбург, Вирджиния, США, 2003г), на Шестом международном симпозиуме по итерационным методам в научных вычислениях (третье призовое место в конкурсе статей аспирантов, Денвер, Колорадо, США, 2003г), на Международной конференции молодых ученых по математическому моделированию и информационным технологиям (Новосибирск, Россия, 2002г), на Конференции молодых ученых СО РАН, посвященной М М Лаврентьеву (Новосибирск, Россия, 2001 г), на Международной конференции 'Современные проблемы прикладной математики и механики теория, эксперимент и практика', посвященной 80-летию академика Н Н Яненко (Новосибирск, Россия, 2001 г), на Конференции молодых ученых, посвященной 10-летию ИВТ СО РАН (Новосибирск, Россия, 2000г), на XV конференции по интервальной математике в рамках конференции 'Вычислительные технологии 2000' (ИВТ СО РАН, Новосибирск, Россия, 2000г)
Публикации. По материалам диссертации опубликовано 10 работ статья в рецензируемом журнале, рекомендованном ВАК для представления докторских диссертаций [1], статья в зарубежном рецензируемом журнале [2], статья в рецензируемом журнале СО РАН [3], публикации в трудах международных и российских конференций [4, 5, 6, 7, 8, 9, 10]
Личиый вклад автора. В работе [1] автор участвовал в постановке задачи Автором лично разработаны и реализованы схема неполного спектрального исчерпывания, методы Ланцоша, бисекций и обратной итерации с оцениваемой точностью, проведен вычислительный эксперимент и написан первый вариант статьи В работах [2, 3] автором лично разработан и реализован метод Годунова-обратной итерации, проведен вычислительный эксперимент и написана статья В публикациях [4, 5, 6, 8, 10] автором лично разработаны и реализова-
ны представленные вычислительные схемы и алгоритмы, проведен вычислительный эксперимент, описаны результаты В публикациях [7, 9] автор участвовал в постановке задачи Автором лично разработаны и реализованы представленные алгоритмы, проведен вычислительный эксперимент, описаны результаты
Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, приложения и списка литературы Работа изложена на 154-х страницах, содержит 12 рисунков и 19 таблиц Список литературы содержит 94 наименования
