Оценки погрешности методов Ланцоша и Арнольди в точной и машинной арифметике

Оглавление
Краткое описание проблемы и основных результатов .... 10
1 Введение 13
1.1 Семейство крыловских методов .............................13
1.2 Метод Арнольди. Роль теоретического использования поля
значений и операторного спектра...........................16
1.3 Метод Ланцоша. Роль теоретического использования че-
бышёвских рекуррентных соотношений........................22
1.4 Структура и обзор содержания диссертации..................25
Часть I Методы Ланцоша и спектрального разложения
Ланцоша в точной арифметике: неадаптивные оценки 38
2 Метод спектрального разложения Ланцоша в точной арифметике 38
2.1 Введение .................................................38
2.2 Метод операторных рядов Чебышева..........................40
2.3 Метод спектрального разложения Ланцоша: оценка погреш-
ности в терминах коэффициентов смещённого ряда Чебышева вычисляемой функции.......................................42
2.4 Приложение к решению задачи Коши для параболического
уравнения.................................................45
2.5 Приложение к решению задачи Коши для гиперболического уравнения..................................................51
2
1
2.6 Приложение к решению краевой задачи для эллиптическо-
го уравнения с коэффициентами, не зависящими от одной переменной...............................................54
2.7 Приложение к решению задачи Коши для параболического
уравнения методами расщепления...........................55
2.8 Краткие выводы...........................................58
3 Метод Ланцоша в точной арифметике 60
3.1 Введение ................................................60
3.2 Оценка качества аппроксимации собственного значения, не
учитывающая отделённость.................................61
3.3 Оценка качества аппроксимации собственного значения, учитывающая отделённость.........................................62
3.4 Краткие выводы...........................................64
Часть II Методы Ланцоша и спектрального разложения Ланцоша в машинной арифметике 66
4 Метод спектрального разложения Ланцоша в машинной арифметике 66
4.1 Введение ................................................66
4.2 Начальные сведения о простом процессе Ланцоша............67
4.3 Возмущённые чебышёвские рекуррентные соотношения . . 68
4.4 Оценка погрешности метода спектрального разложения Ланцоша в машинной арифметике....................................70
4.5 Пример запуска...........................................73
4.6 Краткие выводы...........................................74
5 Феномен Ланцоша и расположение чисел Ритца 76
5.1 Введение.................................................76
5.2 Феномен Ланцоша без учёта отделённости...................77
-3-
5.3 Кластеризация чисел Ритца.................................80
5.4 Феномен Ланцоша с учётом отделённости.....................83
5.5 О числе элементов промежуточного кластера.................89
5.6 Числа Ритца на последовательных шагах Ланцоша.............93
5.7 Результаты численных экспериментов........................97
5.8 Конкретизированная форма теоремы 5.1.....................100
5.9 Краткие выводы...........................................101
6 Гауссова квадратурная формула, порождаемая простым процессом Ланцоша, и её приложения 103
6.1 Введение ................................................103
6.2 Скалярные произведения матричных многочленов Чебышева 105
6.3 Оценки погрешности гауссовой квадратурной
формулы и родственные утверждения.........................109
6.4 Возможные приложения.....................................113
6.4.1 Вычисление (/(Л)</?, (р)............................113
6.4.2 Решение некорректных задач с помощью вариаци-онной регуляризации......................................116
6.4.3 Феномен Ланцоша.....................................117
6.5 Краткие выводы...........................................118
Часть III Методы Арнольди и спектрального разложения Арнольди: неадаптивные оценки 119
7 Метод спектрального разложения Арнольди: общие оценки 119
7.1 Введение ...............................................119
7.2 Описание метода.........................................120
7.3 Разложение в ряд Фабера.................................122
7.4 Возмущённые фаберовские рекуррентные соотношения . . .124
7.5 Теорема об оценке погрешности..........................126
7.6 Пример: системы линейных уравнений.....................130
7.7 Пример: транспонированные жордановы клетки.............132
7.8 Краткие выводы.........................................134
8 Оценки погрешности метода Арнольди и метода спектрального разложения Арнольди: случай нормальной матрицы и крайних изолированных собственных значений 135
8.1 Введение.................................................135
8.2 Аппроксимация крайних собственных пар нормальной матрицы ......................................................136
8.3 Невозможность существенного улучшения оценок предложения 8.1 в неэрмитовом случае..............................143
8.4 Вычисление матричной функции с особенностями, лежащими среди крайних собственных значений.....................146
8.5 Краткие выводы...........................................153
9 Оценки погрешности метода Арнольди и метода спектрального разложения Арнольди: случай крайних изолированных собственных значений 155
9.1 Введение ................................................155
9.2 Постановка задачи и вспомогательные результаты...........156
9.3 Аппроксимация собственных пар с внешними собственными значениями...............................................160
9.4 Резольвенты и сопутствующие матрицы......................165
9.5 Вычисление матричной функции.............................170
9.6 Численные примеры........................................172
9.7 Краткие выводы...........................................175
Часть
IV Методы Ланцоша, Арнольди, спектрального раз-
ложения Ланцоша и спектрального разложения Арнольд и: адаптивные оценки 178
10 Об адаптации методов Ланцоша и Арнольди к спектру, или почему два этих метода так мощны 178
10.1 Введение ................................................178
10.2 Решение линейных уравнений — общий случай................180
10.3 Решение линейных уравнений — самосопряжённый случай 184
10.4 Оценка погрешности методов спектрального разложения Ланцоша и Арнольди...........................................186
10.5 Вычисление собственной пары — общий случай ..............189
10.6 Вычисление собственной пары — самосопряжённый случай .........................................................192
10.7 Результаты численных экспериментов.......................196
10.7.1 Общий случай......................................196
10.7.2 Самосопряжённый случай ...........................197
10.8 Краткие выводы...........................................202
11 Квадратура Гаусса-Арнольд и для функции {{zl—ср) и Паде-подобная рациональная аппроксимация функций марковского типа 203
11.1 Введение ................................................203
11.1.1 Аппроксимация Паде функций марковского типа. Выделение полюсов.........................................203
11.1.2 Связь квадратуры Гаусса-Арнольди и аппроксимации типа Падс с полюсами в числах Ритца ................204
11.1.3 Структура оставшейся части главы .................205
11.2 Квадратура Гаусса-Арнольди: случай нормального оператора ........................................................206
11.3 Квадратура Гаусса-Арнольди: случай ненормального оператора ......................................................211
11.4 Представление суммы конечного числа простых полюсов с вещественным положительным суммарным вычетом в виде, соответствующем квадратуре Гаусса-Арнольди...............213
11.5 Комплексное рациональное возмущение функции марковского типа: выделение простых полюсов с помощью метода Арнольди.....................................................215
11.6 Численный пример с кратным полюсом......................220
11.7 Краткие выводы..........................................228
12 Заключение, задачи, другие подходы и благодарности 229
12.1 Заключение..............................................229
12.2 Задачи..................................................230
12.3 Другие подходы и родственные результаты других авторов 231
12.3.1 Подход Э. Гринбаум к теории простого процесса Ланцоша.................................................231
12.3.2 Методы Ланцоша и Арнольди и теория ортогональных многочленов.........................................232
12.3.3 Псевдоспектр (спектральный портрет матрицы) . . 233
12.3.4 Условные минимизационные задачи теории потенциала и адаптация к спектру.............................233
12.3.5 Методы с рестартами..............................234
12.3.6 Итерации подпространства.........................234
12.3.7 Крыловские процессы с преобразованным оператором235
12.4 Благодарности...........................................235
Литература 237
Обозначение Смысл
<*,*> Скалярное произведение
< То же, что О
> Обращение <
= Равенство по определению; сравнение по модулю аддитивной подгруппы
□ Конец доказательства
Таблица 1: Обозначения (математические символы).
Сокращение Расшифровка
МЛИ Метод локальных итераций
МОРЧ Метод операторных рядов Чебышева
МСРЛ Метод спектрального разложения Ланцоша
Таблица 2: Сокращения (русский алфавит).
Обозначение или сокращение Смысл или расшифровка
С Расширенная комплексная плоскость
сар1(0 Логарифмическая ёмкость
сагс1(*) Мощность множества
сз Положительные константы (разные в разных главах)
Со(-) Выпуклая оболочка плоского множества
diag{■) Диагональная матрица, составленная из заданных диагональных компонент
сНаш(*) Диаметр множества в метрическом пространстве
сНв^*, •} Расстояние в метрическом пространстве
ез _7-ый единичный орт. Верхний индекс, если он есть, обозначает размерность пространства
Метод полной ортогонализации
СМПЕБ Обобщённый метод минимальных невязок
I Единичная матрица или тождественный оператор. Если есть индекс, то он обозначает размерность
КГЧ-г) 771-мерное подпространство Крылова
Мп(к) Кольцо матриц размера п х п над полем к
N. 0, К, С Множества соответственно натуральных, рациональных, вещественных и комплексных чисел
й, 5 Вещественная и мнимая части комплексного числа
Вр(-) Спектр матрицы или линейного оператора
8рап{-,...,-} Подпространство, натянутое на заданные векторы
Эирр(-) Носитель меры
Тк, ик Многочлены Чебышёва первого и второго рода
Таблица 3: Обозначения и сокращения (латинский алфавит).
Краткое описание проблемы и основных результатов
Крыловские методы приближённого решения задач математической физики очень популярны, поскольку они часто эффективны и поскольку при этом основной операцией в них является умножение матрицы (оператора) на вектор — одна из простейших операций матричной алгебры.
Среди крыловских методов выделяются своей надёжностью (невозможностью преждевременных обрывов и переполнений, гарантией сходимости при определённых предположениях) классические методы Ланцо-ша и Арнольди, предназначенные соответственно для самосопряжённых и несамосопряжённых операторов. Однако существовавшая ранее теория сходимости методов Ланцоша и Арнольди была, на наш взгляд, в неудовлетворительном состоянии, так как содержала частные результаты или оценки не ошибок методов, а промежуточных величин.
В этой диссертации мы систематически излагаем построенную нами новую общую теорию сходимости известных и важнейших для практики методов Ланцоша и Арнольди, основываясь на полученных и опубликованных нами (частично с соавторами) в 1980-х — 2000-х годах результатах. Мы обсуждаем решение спектральных задач и вычисление матричных (операторных) функций, умноженных на вектор. По мере возможности мы изучаем поведение методов как в точной, так и в машинной арифметике.
На наш взгляд, в излагаемой теории наиболее существенны следующие достижения:
1. Систематическое использование поля значений (числового образа) матрицы (оператора) в оценках погрешности метода Арнольди как метода частичного вычисления спектра ограниченного оператора и как метода вычисления операторной функции, умноженной на вектор.
Было до нас: Оценки промежуточных величин, не влекущие оценок
- 10-
ошибки вычисления элемента спектра. Верхняя граница погрешности вычисления собственного значения, не стремящаяся к нулю с ростом номера шага. Оценки погрешности вычисления отдельных операторных функций.
Стало: Оценки ошибок вычисления элементов спектра; достаточные условия сходимости (в операторном случае). Оценки погрешности вычисления операторных функций общего вида.
2. Получение улучшенных по порядку или не имевших аналогов оценок вычисления элементов спектра симметричных матриц методом Ланцоша и оценок вычисления умноженных на вектор функций от симметричных матриц методом Ланцоша в условиях машинной арифметики с помощью техники возмущённых чебышёвских рекурсий.
Было до пас: Оценки промежуточных величин. Сведение исследования процесса Ланцоша в машинной арифметике к исследованию процесса Ланцоша в идеальной арифметике с точностью до корня четвёртой степени из элементарной машинной ошибки округления.
Стало: Оценки погрешности вычисления методом Ланцоша в машинной арифметике матричных функций, квадратур и элементов спектра с точностью до умеренных кратных элементарной ошибки округления. Понимание того, что процесс Ланцоша в машинной арифметике может порождать на промежуточных шагах результаты, существенно различающиеся на разных компьютерах, но что это не мешает получению правильных финальных результатов.
3. Использование операторного спектра в оценках погрешности методов Ланцоша и Арнольди в точной арифметике.
Было до нас: Отдельные рассуждения об адаптации методов Ланцоша и Арнольди к спектру (зависимости результатов от спектра, позволяющей усилить оценки, основанные только на поле значений)
- 11 -
и частные результаты о родственных методах.
Стало: Оценки погрешности методов Ланцоша и Арнольди в терминах операторного спектра. Открытие и объяснение явления сходимости на подпоследовательности шагов.
Результаты численных экспериментов подтверждают неулучшаемость многих наших оценок.
- 12 -
Глава 1 Введение
1.1 Семейство крыловских методов
Численное решение дифференциальных и интегральных уравнений после дискретизации (см., например, [4, 13, 39, 40, 41, 51, 52]) часто сводится к выбору приближённого решения из так называемого подпространства Крылова [31]
где А е МП(К) — матрица размера п х п и (р е К74. Это случается при решении эллиптических уравнений, при реализации явных по времени разностных схем для параболических и гиперболических уравнений, при реализации схем расщепления.
В наше время хорошо известно, что непосредственная работа со степенным базисом
обычно приводит к вычислительной неустойчивости из-за того, что умножение на А методично «убивает» все моды, кроме тех, что соответствуют собственному значению (собственным значениям) с наибольшим модулем. Классическое исключение составляет степенной метод (см. [63, § 9.2], [65, § 53]) вычисления собственного значения с наибольшим модулем, но он уступает в производительности современным методам и потому не в счёт.
/Ст(Л, р) = 8рап{Л°(^, Л V,..., Ат 1р}
ал)
(Л1V, А'V,... ,Ат- V)
(1.2)
13
Средством борьбы с вычислительной неустойчивостью при работе с подпространством (1.1) является та или иная форма ортогонализации1 степенного базиса (1.2). Соответствующие популярные методы решения систем линейных уравнений изложены в учебниках [113, гл. 2-5], [166, гл. 6, 7], [185]; применяемые в этих методах способы перестройки базиса приложимы к вычислению иных (отличных от Л“1) матричных функций и к решению спектральных задач.
Форма ортогонализации определяет возможность получения прямых априорные? оценок погрешности метода.3 Имеются два варианта.
1. Осуществляется в неявном виде (чтобы не работать со степенями А3) ортогонализация по Граму-Шмидту4 базиса (1.2). Соответствующие методы в случаях эрмитовой и неэрмитовой матрицы Л называются методами Ланцоша и Арнольди. Подчеркнём, что под методом Ланцоша мы понимаем классический (эрмитов) метод Ланцоша.
Напомним содержание т шагов процесса Арнольди с матрицей Л и начальным вектором (р ф 0, который мы для простоты считаем нормированным (т шагов процесса дают т базисных векторов подпространства Крылова). Положим <34 = р. Выберем целое пог^ € {2,3} (число ортого-нализаций на каждом шаге, нужных для поддержания должного уровня ортогональности, см. [7, 86]). Выполним следующие действия:
РО 3=1, т
ч=Ац(з); Ь(1:^)=0 РО 1огЬ=1,погЬ РО ±=1,з
1 Ортогонализация не гарантирует устойчивого вычисления определённого базиса. См. по поводу числа обусловленности базиса работы [81, 137, 139, 140, 152].
2Т. е. не требующих знания результатов вычислений; см. [2, с. 61-62]. Примеры априорной и апостериорной (требующей знания результатов вычислений) оценок ошибки можно найти в [155, § 12.4].
3Под погрешностью метода мы понимаем отклонение искомой величины от выдаваемого методом приближения (а не оценки промежуточных величин). См. [2, с. 23-24].
4Как любезно сообщили автору С. А. Горейнов и В. И. Лебедев, эта процедура исторически связана также с именами Лапласа, Сонина и Чебышёва.
- 14-
5=В0Т_РК0РиСТ(ы^(1)); w=w-sq(i); Ь(1, j)=h(i ,.р+Б ЕШ РО ЕШ РО
Ь(^+1, ^=погт(и); q( j^-l) =w/h( j-^-l, j)
ЕЛО РО
В методе Ланцоша полагают пог^ = 1 и вместо цикла РО 1=1, д выполняют цикл РО 1=^—1, з Таким образом, метод Ланцоша — не совсем частный случай метода Арнольди из-за разной длины рекурсии и разного тшсла ортогонализаций в этих методах, что в условиях точной арифметики влияет только на число арифметических операций, но в условиях машинной арифметики играет огромную роль в плане устойчивости / неустойчивости.
Свой вклад в теоретическое обоснование методов Ланцоша и Арнольди призвана внести данная диссертация, содержащая большое количество априорных оценок ошибки.
2. Все другие случаи. Сюда относится построение квазиортогональ-ного базиса (когда в определении «скалярного произведения» отсутствует черта, обозначающая комплексное сопряжение), построение биорто-гональных или квазибиортогональных базисов (когда вместе с (1.2) используется ещё п базис, порождённый матрицей А* или Ат и, возможно, другим — отличным от р — вектором). Методы этого семейства (неэрмитовы обобщения метода Ланцоша и др.) также широко используются на практике, но их применение подобно прохождению минного поля и требует постоянного контроля. В них возможны «вырубания» — например, в случае получения ненулевого вектора, квазиортогоналы 10-го самому себе. Возможны «почти вырубания», когда в знаменателях расчётных формул появляются маленькие числа. Для борьбы с этими явлениями разработаны приёмы вроде «заглядывания вперёд» [158], что приводит к увеличению ширины ленты в матрице коэффициентов рекурсии. Обычно эти методы можно использовать, когда имеется хороший
- 15-
предобуславливатель, но и в этом случае нужен «глаз да глаз» (причём программно реализованный). Известные автору оценки погрешности носят условный характер: если рекурсия не прерывается и коэффициенты рекурсии (рекурсий) ограниченны, то можно что-то сказать о погрешности. Автор не видит путей получения априорных оценок для методов этого семейства. Единственным светлым пятном можно считать работы, касающиеся квазиортогональных многочленов (см. ссылки в гл. 11), которые можно переформулировать в терминах крыловских методов с квазиортогонализацией, но соответствующие результаты носят частный характер.
1.2 Метод Арнольди. Роль теоретического использования поля значений и операторного спектра
Мы будем работать как с матрицами, так и с линейными операторами в бесконечномерных пространствах. К матрицам не применимы некоторые оценки с пределами при тп -> оо (а другие применимы к семействам матриц). Преимущества работы со спектрами бесконечной мощности средствами теории потенциала, а также встречающиеся при этом некоторые трудности детально описаны в [88]. Отметим также, что целая книга [146] посвящена использованию теории ограниченных операторов в методах, основанных на подпространствах Крылова; работая с операторами, мы обычно интересуемся «линейной» сходимостью в смысле главы 3 этой книги.
Метод Арнольди ([71], [23, § 16]) вычисления собственных пар неэрмитовых матриц и нссамосопряжённых операторов был, после некоторого периода забвения, оживлён в 1980-х годах благодаря работам Ю. Саа-да. В наше время метод Арнольди применяется во многих задачах: собственно для вычисления спектра [160, 161]; как средство решения систем линейных алгебраических уравнений [163, 167]; для локализации спектра в итерационных методах решения линейных систем [99, 119]; при
- 16-
решении жёстких систем обыкновенных дифференциальных уравнений [78, 106]; для вычисления матричной экспоненты [105, 120, 122, 164].
Пусть А — ограниченный оператор в гильбертовом пространстве Я, Є Я, ІМІ = П5 Процесс Арнольди в Я с А и ір основан на ор-тогонализации по Граму-Шмидту степенного базиса подпространства Крылова6
/С°°(А, V?) = 8рап{А°<^> • • •}•
Первые тп шагов процесса Арнольди можно выразить соотношением
АС} = (2Н 4" ^т+1 »тфп+І^т» (1*^)
где (5 = т) — набор первых т ортонормированных векторов
Арнольди, а верхняя хессенбергова тп х тп-матрица Я — (к^) содержит коэффициенты рекурсии. В ходе процесса векторы qi и компоненты матриц Я накапливаются (посчитанные на предыдущих шагах величины не затираются).
Из (1.3) и ортонормированности7
ОГЯ = I (1.4)
следует, что Я = С2*А<3 и что если (0*, 5,) — собственные пары Я (г = 1,..., тп), то (ві} С^Яі) — пары Ритца для А на /Ст(А, <р), рассматриваемые как приближения к собственным парам А, т. е.
АС^Бі - ОіС^Зі _І_ К1П(А, р), г = 1,..., тп.
5Если не считать нормированным вектором, то его норма появится во многих формулах, но принципиальных изменении это не вызовет.
бМы в дальнейшем в случае сІітК = оо без ограничения общности предполагаем, что процесс Арнольди не обрывается, то есть сНт/С°°(Л, у?) = оо, а также что /С°°(.Д, у) всюду плотно в 'Н.
7Для краткости обозначений мы будем использовать матрицы с операторными компонентами и работать с ними по обычным матричным правилам. Например, при Н Є Я символ /і4 будет обозначать линейный функционал її* : Я —> С, д «-» (д, Н). Оператор А будет действовать на матрицы покомпонентным образом, скажем, А (г і.. .гя) = ... Ага). Положим также (д^)* = (<£), ду Є Я.
Многочлены С)і (г Є №), такие что Qi(A)^p = д,-+1, (эрмитово) орто-нормированы относительно скалярного произведения
Отметим, что числа Ритца не обязаны лежать в спектре 5 оператора А; они находятся в так называемом «поле значений» (множестве значений отношения Рэлея)8 {{А'ф^'ф} ] ф Є ||^|| = 1}. Замыкание поля значений будем обозначать К.
Предпринятые до наших работ попытки оценить скорость сходимости метода Арнольди для матриц не привели, на наш взгляд, к получению законченных естественных результатов. В [165, глава VI, § 7] расстояние от собственного вектора до крыловского подпространства (1.1) оценено 10. Саадом через коэффициенты разложения р по собственным векторам А и значения многочленов степени не выше т — 1 в точках спектра:
где ось — коэффициенты разложения р = Хд-^1 ак*к входного вектора (р по набор)' нормированных собственных векторов матрицы А. Коэффициенты а* могут быть велики при больших перекосах где-то в спектре А. Таким образом, плохая обусловленность «неинтересной» моды может послужить причиной «развала» оценки для искомой собственной пары. Кроме того, оценить расстояние от собственного вектора до крыловского подпространства недостаточно: из малости этого расстояния не следует малость расстояния от искомого собственного вектора до какого-либо вектора Ритца. Теорема 3.10 из [176, гл. 4] распространяет результат
8Этот исторически сложившийся матрично-алгебраический термин не имеет отношения к нолю как целостному кольцу с делением. Эквивалентные термины — «числовой образ», «числовая область» и «хаусдорфово множество».
</,3) = и(.А)ч>,9{А)ф), },д& С [і].
сііві (^,/Стп(А, р)) (1.5)
тах Ь(А)1,
\<к<п, кр]
Саада на недиагонализируемые матрицы, но она оценивает то же расстояние и в правой части также может содержать необоснованно большие величины. В [126, следствие 4.2] погрешность аппроксимации собственного значения Aj на шаге т оценена по порядку корнем m-ой степени из расстояния от соответствующего собственного вектора zj до подпространства (1.1):
где 6 = sin Z (zj, /Ст(Л, р)). Мы увидим в гл. 9, что в одной из типичных ситуаций указанное расстояние убывает со скоростью геометрической прогрессии при росте 7П, а тогда из оценки (1.6) вряд ли можно извлечь что-либо полезное.
Для сравнения скажем, что одна из наших простейших оценок погрешности решения спектральной задачи имеет следующий вид: если есть конечное количество s собственных значений Ai,..., Л5, не принадлежащих полю значений К сужения оператора А на подпространство, дополнительное к интересующим нас s модам (это условие даёт возможность вывести из оценок расстояний от нужных собственных векторов до крыловского подпространства оценки ошибок соответствующих векторов Ритца), то оценка погрешности вычисления A j (1 < j < s) равна 0(p™mc), где числа 0 < рj < 1 определяются взаимным расположением
/N /Ч
Aj и Ку с — константа, зависящая от формы границы К, и под знаком О не скрыты никакие перекосы (перекосы влияют на К). В общем случае оценка не может быть существенно улучшена. Из этого следует, что оценки (1.5) и (1.6), игнорирующие поле значений сужения оператора, в принципе не могут даже гарантировать факт сходимости при т —У оо для оператора или семейства матриц, удовлетворяющих условиям нашей оценки.
В тот же период Ю. Саадом была дана оценка погрешности решения системы линейных уравнений Аи = р с помощью обобщённого метода
- 19-
минимальных невязок GMR.ES, использующего базис, построенный процессом Арнольди (см. [166, предложение 6.32], а также [41]). В этой оценке также (как и в (1.5)) фигурируют коэффициенты разложения правой части р по системе собственных векторов А.
В [25], [26, § 4], [130, § 2, 3], [132, § 5] автором получены оценки погрешности предложенного им в 1991 г. метода спектрального разложения Арнольди, т. е. варианта метода Арнольди, предназначенного для вычисления произведения матричной (операторной) функции на вектор (см. также [120]). Если функция / аналитична в окрестности 5 = Эр(А) и окрестности Эр (Я) — спектра Я, то метод спектрального разложения Арнольди в качестве приближения к вектору
и = /(А)ір
выдаёт вектор
ит = <?/(Я)е і. (1.8)
В частном случае /(А) = А~1 получается метод полной ортогонализа-ции (РОМ). Хорошо известно (следует из рекурсии (1.3)), что метод спектрального разложения Арнольди точен ДЛЯ многочленов степени <771—1, то есть
/{А)р = <3/(Я)еі, /Є СИ, с^/< 771-1. (1.9)
Если / аналитична на всём компакте Я, то её можно разложить там в ряд Фабера9 и благодаря (1.9) свести оценку погрешности метода спектрального разложения Арнольди к оценке хвоста ряда Фабера. Использование поля значений А в статье [25] благодаря оценке нормы резольвенты вне К освободило нас от необходимости явным образом отражать в оценке погрешности метода перекосы в спектре. Случай функций, которые могут иметь особенности между несколькими «внешними» собственными значениями А, рассмотрен нами в работах [26] и [132]; там с
9См. определения многочленов и рядов Фабера в § 7.3.
(1.7)
аналогичной целью мы использовали поле значений сужения А на подходящее инвариантное подпространство. А в работе [130] мы получили результаты, учитывающие спектр оператора (здесь — не матрицы) А; в частности, для РОМ показана сходимость на некоторой последовательности шагов, если 0 лежит в неограниченной связной компоненте С\8р(А),
0 чём не было речи в старой матричной теории.
В [26, § 2], [130, § 4], [132, § 3] мы также получили оценки для вычисления собственных пар. Первое, что приходит в голову сделать для оценки качества выделения собственной пары (А, г), — воспользоваться формулой (1.9) и взять многочлен / степени не выше т — 1, равный
1 в точке А и принимающий как можно меньшие значения на остальной части спектра или на поле значений ограничения А на подходящее инвариантное подпространство («дополнительное» к Сх). В сущности, так и делается, но сит)гация осложняется ненормальностью оператора А и ненормальностью Н. Часть оценок представляет собой обычные неравенства, но некоторые оценки получаются коши-адамаровского типа: оценивается верхний ИЛИ НИЖНИЙ предел 771-го корня ошибки в терминах функции Грина (с особенностью в бесконечности)10 дополнения к полю значений или неограниченной компоненты дополнения к спектру. Нижним пределом приходится довольствоваться, когда поле значений (по которому «гуляют» числа Ритца) ограничения А на инвариантное подпространство «налезает» на искомое собственное значение.
Наши оценки для спектральной задачи также сформулированы в терминах упомянутых функций Грина для подходящего сужения оператора; соответственно, в доказательствах используются элементы теории потенциала. То, что было сказано выше об отсутствии необходимости явно учитывать перекосы в спектре и об оценках, верных для подпоследовательностей, справедливо и здесь. Использование в формулировках функции Грина позволяет рассматривать произвольные, а не частные
10См. определение функции Грина в § 10.2.
- 21 -
(отрезки, эллипсы) поля значений.
В работах [79, 102] была введена квадратура Гаусса-Арнольди, т. е. приближённое равенство (}(А)р,д(А)р) « (/(Я)ех, <7(Я)е1), где функции / и д аналитичны на спектрах А и Я; при этом оставался открытым вопрос о том, быстрее ли сходится квадратура по сравнению с приближённым вычислением векторов /(А)р и д{А)р с помощью метода спектрального разложения Арнольди. В статье [29] мы для частного случая /(А) = (Я—А)-1 и д = 1 установили в терминах операторов жёсткие ограничения на Л, при выполнении которых от квадратуры есть толк.
1.3 Метод Ланцоша. Роль теоретического использования чебышёвских рекуррентных соотношений
Как уже говорилось, теоретически метод Ланцоша [138] представляет собой метод Арнольди, применённый к самосопряжённому оператору: А* = А. В этом случае матрица Я коэффициентов рекурсии является вещественной симметричной трёхдиагональной, а многочлены (){ ортогональны на вещественной оси и удовлетворяют трёхчленному рекуррентному соотношению. Компакт К превращается в отрезок вещественной оси; соответственно, ряд Фабера функции / на К становится сдвинутым рядом Чебышёва.
Эрмитовость матрицы Я сильно облегчает построение теории в точной арифметике.
Общая оценка погрешности метода спектрального разложения Ланцоша (МСРЛ; эрмитов аналог метода спектрального разложения Арнольди) была получена для точной арифметики В. Л. Друскиным и автором в [20]. Хотя сам метод спектрального разложения Ланцоша использовался на практике, наши оценки были первыми оценками его скорости сходимости как в общем случае функции, аналитической на спектральном интервале, так и в нескольких практически употребительных частных
- 22-
случаях.
Для метода Ланцоша как метода вычисления спектра симметричной матрицы широко известны оценки Каниэля и Саада для получаемых методом Ланцоша приближённых собственных пар (см. [127, 161], [45, § 12.4]), оценивающие качество приближения j-го точного собственного значения Xj j-ым же числом Ритца Oj. Оценки эффективны, если число этих собственных значений существенно меньше, чем размерность подпространства Крылова т.11
Используя равенство (1.9), В. Л. Друскин и автор получили в работе [91] априорные оценки ошибки вычисления не обязательно близкого к краю спектра собственного значения методом Ланцоша.
Ситуация, однако, существенно усложняется при переходе к машинной арифметике (естественно, в случае матриц; см., например, [12, 45, 107]). Долгое время метод Ланцоша просто боялись применять из-за сильной вычислительной неустойчивости. Было выяснено, что векторы Ланцоша qj теряют ортогональность и даже становятся почти линейно зависимыми после того, как хорошо сойдётся какое-либо собственное значение. Процесс Ланцоша с одной и той же парой (А, р) может по-разному идти на компьютерах разных типов или даже на одном компьютере при разных способах компиляции программы. Причина в том, что в процессе Ланцоша при стандартной реализации вследствие теоретической трёх-диагоналыюсти Н новый вектор Ланцоша ортогонализуется только к двум предыдущим, а не ко всем, в отличие от метода Арнольди.
Анализу ошибок округления в процессе Ланцоша в условиях машинной арифметики12 посвящены основополагающие работы К. Пэйджа [149,150, 151], в которых виртуозно вскрыт механизм появления неустойчивости в процессе Ланцоша и влияние неустойчивости на базовые ма-
пПарлетт пишет, с точностью до обозначений, следующее в [156, § 12.5]: All the bounds become wortliless as j increases too much because there arc only m O’s to n A’s and quite soon Xj will not be the closest eigenvalue to 03.
12Мы занимаемся исследованием поведения в машинной арифметике только простого, т. е. без дополнительной ортогонализащш, процесса Ланцоша.
- 23-