Оценки погрешности методов Ланцоша и Арнольди в точной и машинной арифметике тема диссертации и автореферата по ВАК РФ 01.01.07, доктор физико-математических наук Книжнерман, Леонид Аронович

• Книжнерман, Леонид Аронович
• доктор физико-математических наук
• 2012

Оглавление диссертации доктор физико-математических наук Книжнерман, Леонид Аронович

Краткое описание проблемы и основных результатов

1 Введение

1.1 Семейство крыловских методов

1.2 Метод Арнольди. Роль теоретического использования поля значений и операторного спектра.

1.3 Метод Ланцоша. Роль теоретического использования че-бышёвских рекуррентных соотношений.

1.4 Структура и обзор содержания диссертации.

Часть I Методы Ланцоша и спектрального разложения Ланцоша в точной арифметике: неадаптивные оценки

2 Метод спектрального разложения Ланцоша в точной арифметике

2.1 Введение

2.2 Метод операторных рядов Чебышёва.

2.3 Метод спектрального разложения Ланцоша: оценка погрешности в терминах коэффициентов смещённого ряда Чебышёва вычисляемой функции.

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

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

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 Вычисление (f(A)(p,tp).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—А)~гср, tp) и Паде-подобная рациональная аппроксимация функций марковского типа 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: Сокращения (русский алфавит).

Обозначение или сокращение Смысл или расшифровка

С Расширенная комплексная плоскость capl(-) Логарифмическая ёмкость card(-) Мощность множества

CJ Положительные константы (разные в разных главах)

Со(.) Выпуклая оболочка плоского множества diag{-, .,•} Диагональная матрица, составленная из заданных диагональных компонент diam(-) Диаметр множества в метрическом пространстве dist{-, •} Расстояние в метрическом пространстве ej единичный орт. Верхний индекс, если он есть, обозначает размерность пространства

FOU Метод полной ортогонализации

GMRES Обобщённый метод минимальных невязок

I Единичная матрица или тождественный оператор. Если есть индекс, то он обозначает размерность т-мерное подпространство Крылова

Mn(k) Кольцо матриц размера п х п над полем к

N, Q, R, С Множества соответственно натуральных, рациональных, вещественных и комплексных чисел

S Вещественная и мнимая части комплексного числа

Sp(-) Спектр матрицы или линейного оператора span{-, .,•} Подпространство, натянутое на заданные векторы

Supp(-) Носитель меры

Tk, Uk Многочлены Чебышёва первого и второго рода

Таблица 3: Обозначения и сокращения (латинский алфавит).

Краткое описание проблемы и основных результатов

Крыловские методы приближённого решения задач математической физики очень популярны, поскольку они часто эффективны и поскольку при этом основной операцией в них является умножение матрицы (оператора) на вектор — одна из простейших операций матричной алгебры.

Среди крыловских методов выделяются своей надёжностью (невозможностью преждевременных обрывов и переполнений, гарантией сходимости при определённых предположениях) классические методы Ланцо-ша и Арнольди, предназначенные соответственно для самосопряжённых и несамосопряжённых операторов. Однако существовавшая ранее теория сходимости методов Ланцоша и Арнольди была, на наш взгляд, в неудовлетворительном состоянии, так как содержала частные результаты или оценки не ошибок методов, а промежуточных величин.

В этой диссертации мы систематически излагаем построенную нами новую общую теорию сходимости известных и важнейших для практики методов Ланцоша и Арнольди, основываясь на полученных и опубликованных нами (частично с соавторами) в 1980-х — 2000-х годах результатах. Мы обсуждаем решение спектральных задач и вычисление матричных (операторных) функций, умноженных на вектор. По мере возможности мы изучаем поведение методов как в точной, так и в машинной арифметике.

На наш взгляд, в излагаемой теории наиболее существенны следующие достижения:

1. Систематическое использование поля значений (числового образа) матрицы (оператора) в оценках погрешности метода Арнольди как метода частичного вычисления спектра ограниченного оператора и как метода вычисления операторной функции, умноженной на вектор.

Было до нас: Оценки промежуточных величин, не влекущие оценок ошибки вычисления элемента спектра. Верхняя граница погрешности вычисления собственного значения, не стремящаяся к нулю с ростом номера шага. Оценки погрешности вычисления отдельных операторных функций.

Стало: Оценки ошибок вычисления элементов спектра; достаточные условия сходимости (в операторном случае). Оценки погрешности вычисления операторных функций общего вида.

2. Получение улучшенных по порядку или не имевших аналогов оценок вычисления элементов спектра симметричных матриц методом Ланцоша и оценок вычисления умноженных на вектор функций от симметричных матриц методом Ланцоша в условиях машинной арифметики с помощью техники возмущённых чебышёвских рекурсий.

Было до нас: Оценки промежуточных величин. Сведение исследования процесса Ланцоша в машинной арифметике к исследованию процесса Ланцоша в идеальной арифметике с точностью до корня четвёртой степени из элементарной машинной ошибки округления.

Стало: Оценки погрешности вычисления методом Ланцоша в машинной арифметике матричных функций, квадратур и элементов спектра с точностью до умеренных кратных элементарной ошибки округления. Понимание того, что процесс Ланцоша в машинной арифметике может порождать на промежуточных шагах результаты, существенно различающиеся на разных компьютерах, но что это не мешает получению правильных финальных результатов.

3. Использование операторного спектра в оценках погрешности методов Ланцоша и Арнольди в точной арифметике.

Было до нас: Отдельные рассуждения об адаптации методов Ланцоша и Арнольди к спектру (зависимости результатов от спектра, позволяющей усилить оценки, основанные только на поле значений) и частные результаты о родственных методах.

Стало: Оценки погрешности методов Ланцоша и Арнольди в терминах операторного спектра. Открытие и объяснение явления сходимости на подпоследовательности шагов.

Результаты численных экспериментов подтверждают неулучшаемость многих наших оценок.

Заключение диссертации по теме «Вычислительная математика», Книжнерман, Леонид Аронович

Основные результаты диссертации опубликованы в статьях [20, 21, 25, 26, 27, 28, 29, 90, 94, 114, 132], вышедших в журналах из списка ВАК. Другие результаты диссертации опубликованы в работах [91, 133]. Обзорные статьи, а также статьи с результатами, родственными вошедшим в диссертацию: [18, 89, 91, 94].

Ссылки на статьи автора по теме диссертации можно найти в книгах [11, предисловие], [110, § 7.5, 8.0], [113, гл. 4], [118, § 13.5-13.6], [142, § 3.11], [156, § 13.11], [182, гл. VI, § 28] и в статьях разных авторов.

19Автор полагает, что он был среди тех, кто в начале 1990-х годов стал активно внедрять использование поля значений, функции Грина и многочленов Фабера в исследование сходимости крыловских методов. Из «соратников» отметим М. Айерманна [97], О. Неванлинну [146] и JI. Н. Трефевена с соавторами [88] (список не претендует на полноту). Сейчас этими понятиями удивишь не очень многих вычислительных линейных алгебраистов: они (понятия) начали входить в учебники (см., например, [63, гл. 20]), а тогда их использование встречало заметное сопротивление.

Результаты диссертации докладывались на юбилейной лан-цошевской конференции [92, 128], конференции по вычислительной линейной алгебре [131], конференции 81АМ-САММ-2006 [134], на кафедре вычислительной математики Технического горного университета Фрайберга (Германия), в ВЦ РАН им. А. А. Дородницына, в ИПУ РАН им. В. А. Трапезникова, по нескольку раз обсуждались на семинарах в Институте вычислительной математики РАН и Институте прикладной математики РАН им. М. В. Келдыша (в том числе на семинаре им. К. И. Бабенко).

Часть I

Методы Ланцоша и спектрального разложения Ланцоша в точной арифметике: неадаптивные оценки

Глава 2

Метод спектрального разложения Ланцоша в точной арифметике

2.1 Введение

Пусть А — симметричная вещественная матрица размера п х п, / — функция, определённая на спектральном интервале А, <р £ Мп. Рассмотрим задачу вычисления вектора (1.7) и = /(А). Задачей такого типа является решение систем линейных уравнений (/(А) = А~1). В математической физике рассматриваемая задача возникает, например, при решении дифференциально-разностных аппроксимаций однородных уравнений в частных производных с коэффициентами, не зависящими от одной переменной (/(А) = ехр(—ЬА) — при решении параболических уравнений, /(А) = сов^Л1/2) — гиперболических уравнений, /(А) = ехр(—М1/2) — эллиптических уравнений1). Для вычисления и широко используются явные методы, в которых /(А) аппроксимируется многочленом (см., например, [13, 35, 38, 52, 143]). Рассмотрим общие свойства таких методов.

1 Связь матричных функций с дифференциальными уравнениями давно известна; см., например, [33].

Обозначим через А^, г = 1,2, . .,п, Лг+х > Л^, собственные значения А (которые в данном параграфе будем для простоты считать различными), а через — соответствующую ортонормированную систему собственных векторов. Если разложение <р имеет вид п v = фл,

2.1) то п

2—1

Возьмём в качестве приближённого значения и вектор ит = рт(А)(р^ где рт — многочлен степени не выше т — 1. Норма ошибки равна и - Um\\ — п

- Pm)(K)ViZi i=1

2.2) где г=1

6 — дельта-функция. Таким образом, задача сводится к полиномиальной аппроксимации / с обобщённым весом р (т. е. в узлах Лг- с весами <р\).

Основные вычислительные затраты в полиномиальных методах связаны с умножением А на векторы, поэтому главной характеристикой эффективности того или иного метода является число т, требуемое для получения заданной точности. Легко видеть, что при фиксированном т минимум в (2.2) достигается, когда рт — начальный кусок ряда Фурье / по многочленам, ортогональным с весом р. Процесс Ланцоша [138], [45, гл. 13], который первоначально предназначался для вычисления спектра А, позволяет в точной арифметике строить многочлены, ортогональные с весом рт, который в некотором смысле аппроксимирует р. Впервые в задачах типа (1.7) процесс Ланцоша был использован для решения линейных систем [154, 155, 171], затем в ряде работ он применялся для решения одномерных [147, 148] и многомерных [19] параболических и гиперболических уравнений. Общая схема применения процесса Ланцоша для решения задачи (1.7) была предложена в [18] ив другой форме — в [184].

Ниже получены оценки погрешности процесса Ланцоша при вычислении (1.7) в общем случае и для конкретных (наиболее употребительных) функций /. При доказательстве применяется разложение /(А) в матричный ряд Чебышёва, которое можно использовать как самостоятельный способ решения задачи (1.7). Применение рядов именно по многочленам Чебышёва обусловлено тем, что нужна оценка используемых многочленов не только на Эр (Л), но и в собственных значениях Н, а последние могут появляться всюду на спектральном интервале. Приведены также результаты численных экспериментов, показывающие сравнительную эффективность предлагаемых методов.

В этой главе изложение ведётся для точной арифметики. Возможность модификации утверждений из § 2-6 на случай машинной арифметики будет обоснована в гл. 4.

2.2 Метод операторных рядов Чебышёва

Будем считать, что матрица А не скалярная, т. е. Хп > Ах, и что = 1. В данном параграфе предполагается, что известны числа Ах и Ап, но результаты остаются справедливыми, если заменить Ах и Хп на их оценки снизу и сверху соответственно.

Положим

В = 5(ж) = ; лп — л\ Лп — Л1

Ап 4- Ах - (А„ - Ах)я где 1к — единичная матрица порядка к. Тогда ||В|| < 1 и функция д определена на отрезке [—1,1]. Рассмотрим ряд Чебышёва [46, гл. 3] функции оо д(х) = ^дкТк{х), (2.3) к=О где Тк — многочлены Чебышёва первого рода, ортогональные на интервале ] — 1,1[ с весом 1/\/1 — х2 и удовлетворяющие рекуррентному соотношению

То(я) = 1, Т1(х) = х, Тк+1(х) = 2хТк(х)-Тк-1(х), к> 1, (2.4) а дк — коэффициенты Чебышёва: j 1 -*-/ / а г ■'«г j ^ =- / -7===-ах. тг J \Д mm(2,k + l) j д(х)Тк{х) -1 ж 2

Поскольку и = /(А)(р = д(В)ср, то возьмём в качестве приближённого значения (1.7) вектор т—1 А;—О

Предложение 2.1 Пусть ряд (2.3) абсолютно сходится на отрезке [—1,1]. Тогда справедлива оценка погрешности оо и-Ут\\ < ]ГЫ <+00. (2.6) к=тп

Доказательство. Так как ТЦ1) = 1 для всех к и ряд (2.3) при х — 1 абсолютно сходится, то

00

22 ы < к—т

Учитывая неравенства ||1?|| < 1 и |ТЦж)| <1, — 1 < х < 1, получаем

00 оо п-ут\\<^Ы\\тк(в)\\ |М1<£Ы, к=т к=тп что и требовалось доказать. □

Предложенный метод вычисления (1.7), выражаемый формулой (2.5), назовём методом операторных рядов Чебышёва (МОРЧ). Несмотря на свою простоту, он даёт эффект, например, в эволюционных и некоторых других задачах, см. [179, 180]. Векторы Tk(B)ip могут быть вычислены рекуррентно, с помощью (2.4).

2.3 Метод спектрального разложения Ланцоша: оценка погрешности в терминах коэффициентов смещённого ряда Чебышёва вычисляемой функции

Напомним содержание т шагов процесса Ланцоша приближённого вычисления спектра оператора А. В подпространстве Крылова (1.1) /Ст(А, (р) строится базис ql,.,qm, получаемый в результате ортогонализации по Граму-Шмидту последовательности А(р,., Ат~1(р. Ортогонализацию можно провести с помощью трёхчленной рекурсии

Aqi = А-1дг-1 + ЗД + г = 1,2,., т - 1, (2.7) где poqo = 0, = у и Д > 0. Обозначим через Н трёхдиагональную матрицу

1 А \ А «2 02

Рт-1 ат через вг, вг = (^хг,., 5Шг)г, г = 1,2,.,т, — собственные значения и соответствующие нормированные собственные векторы Н\ е* есть г-й единичный вектор размерности т. Положим С} = ^ 1. Уг = ф^г

Тогда (9(,уг) — приближённые собственные пары оператора А, получаемые методом Ритца на /Ст(А, ф).

Предположим на время, что числа А; различны. Вследствие (2.1) тогда п и = У^гДАг)^. г=1

Ввиду ортогональности матрицы (5х. йт) ш т = 41 = = sliSi =

1 1=1 поэтому в качестве приближения ит к и естественно взять вектор т т г=1 г=1 что оправдывает определение (1.8) ит = Я/(Н)е1.

Положим ит = Я/(Н)е 1 вне зависимости от того, прост ли спектр А. Это определение корректно, поскольку спектр Н содержится в спектральном интервале А. Изложенный метод назовём методом спектрального разложения Ланцоша (МСРЛ).

Матричным выражением (2.7) является формула

АЯ-ЯН = РтЯт+А (2.8) частный случай (1.3) {АС} — (¿Н + Из неё следует, что если (Зт = 0 (это равенство должно стать справедливым по крайней мере на п-м шаге), то (9^ у{) — точные собственные пары А и ит = и.

Предложение 2.2 Пусть р £ ЩХ], с^р < т — 1. Тогда р(А)(р = Яр(Н)е 1.

Доказательство. Достаточно доказать с помощью конечной индукции, что

А'ч> = ЯН'е1, з<т-1. (2.9)

При ,7 = 0 равенство (2.9) принимает вид у? = и, очевидно, верно. Для перехода от у к ] + 1, используя (2.8) и (2.9) и учитывая, что, вследствие трёхдиагональности Н, е^Н^ех = 0 при 0 < ] < т — 2, получаем АА*<р = АЯ&ег = (ЯН + ртЯт+1еТт)Н3 ег = + (ЗтЧт+1еТгпН^1 = ЯН^е ь что и требовалось.2 □

Положим у 2 Ах Хп — Х\

2Отметим, что верен аналогичный результат (1.9) (/(А)<^ = Qf(H)e 1, / £ С[£], с^ / < тп — 1) для более общего метода — метода Арнольди. Фактически в доказательстве использована хессенберговость, а не трёхдиагональность Н. Отметим также, что этот простой результат был чуть позже опубликован Ю. Саадом в [164], но был известен последнему и раньше (частная переписка).

Поскольку, вследствие свойств аппроксимации Ритца,

Ai<6>¿<An, i = 1,2,., ш, (2.10) то \\V\\ < 1.

Теорема 2.1 Пусть ряд (2.3) абсолютно сходится на отрезке [—1,1]. Тогда справедливы равенство оо и - ит = ^ 9k[Tk(B)cp - QTk(V)ei} (2.11) k=m и оценка погрешности

00

11« - «mil < 2 Y; Ы < +оо. (2.12) k=m

Доказательство. Имеют место разложения в ряд оо u = J2gkTk(B)ip (2.13) k=О см. доказательство предложения 2.1) и

00 оо rn = Я^9кТк(У)ех = YJ9kQTk{V)el (2.14) к=0 к=О ряд сходится ввиду того, что ROOII < 1 и HQII = 1). Вычитая (2.14) из (2.13) и учитывая равенство Тк(В)ср = QTk(V)ei, к = 0,1,., m — 1 (предложение 2.2), получаем (2.11). Наконец, оо оо

11« - um\\ < Y, ы 01Т*(В)11 IMI + IIQII ||r*(V0||] < 2 Y, Ык=тп к=тп

Сравнивая (2.12) и (2.6), видим, что оценка погрешности метода спектрального разложения Ланцоша в два раза превышает оценку погрешности метода операторных рядов Чебышёва. Отметим, однако, следующее. На практике обычно погрешность метода операторных рядов

Чебышёва близка к правой части (2.6). Погрешность же метода спектрального разложения Ланцоша, как правило, существенно меньше правой части (2.12), что объясняется малостью величины в квадратной скобке выражения (2.11) при многих значениях к (при переходе от (2.11) и (2.12) квадратная скобка оценивалась тривиально). См. гл. 10 об адаптации к спектру.

12.1 Заключение

На наш взгляд, в диссертации систематически изложена теория сходимости методов Ланцоша и Арнольди и соответствующих методов вычисления произведения матричной функции и вектора. Доказаны многочисленные оценки погрешности решения частичной проблемы собственных значений и вычисления матричных функций, причём оценки для спектральных задач прямо или косвенно выведены из оценок для матричных функций — многочленов, выделяющих нужные собственные значения. По мере возможности освещено поведение методов как в точной, так и в машинной арифметике. Описана роль поля значений и операторного спектра; сформулирована концепция адаптации методов к (операторному) спектру; объяснено, что рассмотренные методы конкурентоспособны благодаря этой адаптации.

Не все приведённые результаты вполне удовлетворяют автора с эстетической точки зрения (см. список задач в § 12.2). Однако автор считает, что приведённых результатов достаточно для того, чтобы пользователи уверенно (не боясь неустойчивости) применяли методы Ланцоша и Арнольди.1

На начальном этапе работы по моделированию трёхмерных электромагнитных полей автор сам опасался применять метод спектрального разложения Ланцоша ввиду его неустойчивости.

12.2 Задачи

Нам видятся следующие нерешённые задачи.

Глава 2, § 2.3, и гл. 10, § 10.4. Связанные вопросы: сколько нужно «заплатить» за переход в теореме 2.1 от рядов по многочленам Че-бышёва к рядам по ортонормированным многочленам, соответствующим паре (А, <р), и за ослабление условия теоремы 10.1, говорящего, что функция аналитична внутри «критической изолинии» функции Грина? Результаты § 10.2 и 10.3 убеждают в том, что «бесплатно» это сделать нельзя. При каких ограничениях на вычисляемую функцию можно получить оценки с нижним пределом и пределом максимума ошибки на двух последовательных шагах, аналогичные (10.1) и (10.9)?

Глава 4, теорема 4.1. Вопрос, аналогичный вопросу к теореме 2.1, но осложнённый машинной арифметикой.

Глава 5, теорема 5.1. Что будет, если взять экстремальный многочлен /, построенный в стиле [34], [36, § 11]? При этом многочлен уже не обязан принимать наибольшее (в пределах спектрального интервала) значение в искомом собственном значении. В случае точной арифметики ответ положителен (см. теорему 3.1).

Глава 6, предложение 6.1, теорема 6.1 и следствие 6.1. Вопрос про квадратуру Гаусса-Ланцоша, аналогичный вопросу к теореме 4.1.

В перечисленных выше задачах механический переход к другой системе базисных многочленов невозможен, так как требуется знать оценку значений многочленов в числах Ритца, которые могут «гулять» по спектральному интервалу, а также оценку соответствующих весов. На рабочей встрече с участием Э. Гринбаум, В. Л. Друскина и автора в середине 1990-х годов была высказана идея итерационно делать совместное уточнение указанных величин, начиная с неадаптивных к спектру многочленов (Чебышёва и т. п.) и в пределе заканчивая «наилучшими» многочленами. Насколько известно автору, эту идею никто не пытался реализовать.

Глава 9, теорема 9.1. Получить оценки погрешности вычисления геометрически кратного изолированного собственного значения и соответствующей системы корневых векторов.

Глава 10. Получить какие-то аналоги приведённых адаптивных результатов для фиксированной матрицы. Глава 11.

1. Теорема 11.1: доказательство локальной равномерности сходимости аппроксимант по 2.

2. Нахождение априорного условия представимости функции марковского типа, порождённой комплекснозначной мерой, в виде, удобном для применения метода Арнольди с ограниченным оператором (см. замечание 11.2). После решения этой задачи результаты предложений 11.3 и 11.4 автоматически распространятся на случай комплекснозначной меры.

3. Выяснение того, что можно сделать в случае рационального возмущения с невещественным или неположительным суммарным вычетом. Очевидно, рассматриваемая в данной статье квадратура ограничение вещественности и положительности снять не позволяет.

4. Объяснение видимой периодичности на рис. 11.3.

5. Оптимизация выбора матрицы в § 11.4.

12.3 Другие подходы и родственные результаты других авторов

12.3.1 Подход Э. Гринбаум к теории простого процесса Лан-цоша

Альтернативный (элегантный) способ получения оценок погрешности метода Ланцоша в условиях машинной арифметики предложила Э. Грин- 231 баум в работе [112]. Она для каждого фиксированного номера шага процесса т представила реальный процесс Ланцоша как процесс Ланцоша в точной арифметике, применённый к матрице большей размерности со спектром, лежащим на «малом» расстоянии от спектра А. К сожалению, расстояние приходится делать порядка корня четвёртой степени из элементарной ошибки округления, что приводит к худшим результатам, чем в [18, 21]. Однако некоторые вспомогательные результаты из [112] оказалось возможным использовать для получения более точных оценок.

12.3.2 Методы Ланцоша и Арнольд и и теория ортогональных многочленов

Теорема 8.1.11 из первого тома двухтомника [169, 170] утверждает, что если некая точка является изолированной точкой меры /л на единичной окружности Т, то подходящие корни соответствующих ортогональных многочленов сходятся к изолированной точке меры со скоростью геометрической прогрессии. Доказательство неконструктивно, так что знаменатель прогрессии не указан.

На самом деле метод Арнольди, применённый к оператору умножения на независимую переменную в пространстве Ь2,ц(Т) и к начальному вектору 1 (постоянной функции «единица»), генерирует соответствующие ортонормированные многочлены как векторы Арнольди, причём корни ортонормированных многочленов совпадают с числами Ритца. Так как оператор унитарен (и, значит, нормален) и так как круг строго выпукл, предложение 8.1 даёт конструктивную экспоненциальную оценку скорости сходимости. Асимптотически более точную (адаптивную) оценку можно извлечь из предложения 11.4.

Аналогично, теорема 1.1 из статьи [87] родственна лемме 10.3.

Сказанное не следует воспринимать как упрёк. Это скорее констатация того факта, что математики, работающие в разных областях, иногда фактически делают одно и то же, но не видят междисциплинарных связей из-за того, что говорят на разных математических «диалектах». В частности, не только математический анализ может быть полезен в вычислительной линейной алгебре, но и результаты из вычислительной линейной алгебры могут быть полезны аналитикам.

12.3.3 Псевдоспектр (спектральный портрет матрицы)

Понятие псевдоспектра, или, что почти то же самое, спектрального портрета матрицы, описано в книгах [10, 11, 182] (см. также библиографию в них). Псевдоспектр — прекрасное средство объяснения того факта, что нельзя прогнозировать поведение крыловских процессов с сильно ненормальными матрицами, основываясь только на спектре. Однако само по себе рассмотрение псевдоспектра не позволяет получать априорные оценки погрешности в удобных терминах, поскольку обычно отсутствует априорная информация о величине на изолиниях псевдоспектра значений многочленов с требуемой нормировкой. Кроме того, для получения оценок нужно ещё рассматривать псевдоспектры матриц-проекций Н.

Характерным в этом плане является § 28 "Arnoldi and related eigenvalue iterations" из книги [182], где приводится некая оценка погрешности вычисления собственного значения в методе Арнольди, сходимость правой части которой к нулю при т —¥ оо представляется неясной, а потом за дальнейшими результатами о сходимости чисел Ритца в методе Арнольди читатель отсылается к нашей статье [132].

12.3.4 Условные минимизационные задачи теории потенциала и адаптация к спектру

Недавно появились статьи (см., например, [76, 117, 136]), касающиеся приложений условных (с ограничениями) минимизационных задач теории потенциала к теории методов Ланцоша и Арнольди (только с нормальными матрицами). Полученные этой техникой линейно-алгебраические утверждения относятся не к фиксированному процессу Ланцоша или

Арнольди, а к последовательности процессов в Сп с растущим п,2 точнее, к тому, что в пределе при п —> оо получается на шаге тп процесса в Сп при условии тп/п —> Ь Е]0,1[. Это не то, что хотелось бы, но это какое-то приближение (отличное от нашего) к разгадке явления адаптации методов к спектру.

12.3.5 Методы с рестартами

Известно, что при применении метода Арнольди часто возникают трудности, связанные с возрастанием вычислительной работы (из-за реор-тогонализации) и возрастанием требований к памяти (из-за хранения векторов Арнольди) по мере увеличения номера шага. В простом процессе Ланцоша реортогонализация не делается, но приходится хранить векторы Ланцоша, если нужно вычислить сразу несколько матричных функций во всех или многих точках евклидова пространства (в геофизических приложениях это обычно не так). Стандартным лекарством от таких трудностей является рестарт процесса. По поводу развивающейся теории см., например, работы [67, 74, 80, 98, 181].

12.3.6 Итерации подпространства

Вместо нахождения индивидуальных собственных пар иногда (если индивидуальные собственные пары плохо обусловлены) удобнее итерационно найти приближение к натянутому на них инвариантному подпространству с помощью крыловского или блочного крыловского алгоритма (возможно, с рестартами). См., например, [63, гл. 9], [73]. Существуют также итерационные методы вычисления инвариантного подпространства, основанные на дихотомии спектра (см., например, [6, 43]).

2 Такие последовательности были введены ещё в [183].

12.3.7 Крыловские процессы с преобразованным оператором

Если вычисление матрично-векторной функции /(А)<р с помощью метода спектрального разложения Ланцоша или Арнольди отнимает много времени из-за плохой обусловленности или большой нормы матрицы А, то иногда имеет смысл применить тот же метод к матрице В = (/ + тЛ)-1, где т — параметр, подлежащий оптимизации. Естественно, что при этом соответственно меняется вычисляемая функция и что эффективность сильно зависит от «цены» умножения матрицы В на векторы (т. е. от времени факторизации матрицы I + тА или от времени итерационного решения системы линейных уравнений с этой матрицей. Примеры см. в [100, 144].

12.4 Благодарности

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

Автор благодарит Э. Гринбаум за совместное написание нескольких статей по теории метода Ланцоша, а также за полезные обсуждения личных статей автора.

Автор благодарит за полезные обсуждения диссертации в целом или части отражённых в ней статей и за библиографическую поддержку М. Айерманна, С. К. Асвадурова, Б. Бекерманна, А. В. Богатырёва,

Дж. Голуба, С. А. Горейнова, С. Н. Давыдычеву, Н. Л. Замарашкина,

X. Д. Икрамова, В. П. Ильина, Дж. Каллэм, А. В. Князева, В. И. Лебедева

О. В. Локуциевского, К. Любиха, Ю. М. Нечепуренко, Б. Парлетта, Л. Райхеля, А. Руэ, В. С. Рябенького, А. Скороходова, А. В. Собяни-на, В. 3. Соколинского, С. П. Суетина, К. Торреса-Вердина, Е. Е. Тыр-тышникова, М. Хохбрук, О. Эрнста, участников семинаров в Институте вычислительной математики РАН и Институте прикладной математики

РАН, участников конференций [92, 134].

Автор благодарит Дэвида Бейли за публикацию пакета [72] в Интернете.

Автор благодарит Центральную геофизическую экспедицию и Schlu-mberger-Doll Research за организационную помощь.

Список литературы диссертационного исследования доктор физико-математических наук Книжнерман, Леонид Аронович, 2012 год

1. Абрамовиц М., Стиган И. М. Справочник по специальным функциям. М.: Наука, 1979. - 832 с.

2. Амосов А. А., Дубинский Ю. А., Копченова Н. В. Вычислительные методы для инженеров. М.: Высшая школа, 1994. 544 с.

3. Ахиезер Н. И. Классическая проблема моментов. М.: Физматлит, 1961. 311 с.

4. Бахвалов Н. С., Жидков Н. П., Кобельков Г. М. Численные методы. М.: Лаборатория базовых знаний, 2002. 630 с.

5. Бейтмен Г., Эрдейи А. Высшие трансцендентные функции. // Т. 2. Функции Бесселя, функции параболического цилиндра, ортогональные многочлены. М.: Наука, 1974. 296 с.

6. Булгаков А. Я., Годунов С. К. Круговая дихотомия матричного спектра // Сибирский матем. журнал. 1988. Т. 29. № 5. С. 59-70.

7. Воеводин В. В. Ошибки округления и устойчивость в прямых методах линейной алгебры. М.: Изд-во МГУ, 1969. 140 с.

8. Воеводин В. В., Кузнецов Ю. А. Матрицы и вычисления. М.: Наука, 1984. 319 с.

9. Гантмахер Ф. Р. Теория матриц. М.: Наука, 1988. 549 с.

10. Годунов С. К. Современные аспекты линейной алгебры. Новосибирск: Научная книга (ИДМИ), 1998. 389 с.

11. Годунов С. К. Лекции по современным аспектам линейной алгебры. Новосибирск: Научная книга (ИДМИ), 2002. 212 с.

12. Годунов С. К., Прокопов Г. П. Применение метода минимальных итераций для вычисления собственных значений эллиптических операторов // Ж. вычисл. матем. и матем. физ. 1970. Т. 10. № 5. С. 1180-1190.

13. Годунов С. К., Рябенький В. С. Разностные схемы. М.: Наука, 1973. 400 с.

14. Гончар А. А. О сходимости аппроксимаций Паде для некоторых классов мероморфных функций // Матем. сб. 1975. Т. 97 (139). № 4 (8). С. 607-629.

15. Гончар А. А., Суетин С. П. Об аппроксимациях Паде мероморфных функций марковского типа // Современные проблемы математики. 2004. Т. 5. С. 3-67.

16. Демидович Б. П., Марон И. А. Основы вычислительной математики. М.: Наука, 1970. 664 с.

17. Дзядык В. К. Введение в теорию равномерного приближения функций полиномами. М.: Наука, 1977. 512 с.

18. Друскин В. Л., Книжнерман Л. А. Использование операторных рядов по ортогональным многочленам при вычислении функций от самосопряжённых операторов и обоснование феномена Ланцоша. Деп. в ВИНИТИ. 1987. № 1535-В87. 47 с.

19. Друскин В. Л., Книжнерман Л. А. Спектральный дифференциально-разностный метод численного решения трёхмерных нестационарных задач электроразведки // Изв. АН СССР: Физика Земли. 1988. № 8. С. 63-74.

20. Друскин В. Л., Книжнерман Л. А. Два полиномиальных метода вычисления функций от симметричных матриц //Ж. вычисл. матем. и матем. физ. 1989. Т. 29. № 12. С. 1763-1775.

21. Друскин В. Л., Книжнерман Л. А. Оценки ошибок в простом процессе Ланцоша при вычислении функций от симметричных матриц и собственных значений // Ж. вычисл. матем. и матем. физ. 1991. Т. 31. № 7. С. 970-983.

22. Икрамов X. Д. Разрежённые матрицы // Итоги науки и техн.: Матем. анализ. Т. 20. М.: ВИНИТИ, 1982. С. 179-260.

23. Икрамов X. Д. Несимметричная проблема собственных значений. М.: Наука, 1991. 240 с.

24. Ильин В. П. Численный анализ. Часть 1. Новосибирск: Изд. ИВ-МиМГ, 2004. 335 с.

25. Книжнерман Л. А. Вычисление функций от несимметричных матриц с помощью метода Арнольди // Ж. вычисл. матем. и матем. физ. 1991. Т. 31. № 1. С. 5-16.

26. Книжнерман Л. А. Оценки погрешности метода Арнольди: случай нормальной матрицы // Ж. вычисл. матем. и матем. физ. 1992. Т. 32. № 9. С. 1347-1360.

27. Книжнерман Л. А. Качество аппроксимаций к хорошо отделённому собственному значению и расположение «чисел Ритца» в простом процессе Ланцоша // Ж. вычисл. матем. и матем. физ. 1995. Т. 35. № 10. С. 1459-1475.

28. Книжнерман Л. А. Простой процесс Ланцоша: оценки погрешности гауссовой квадратурной формулы и их приложения // Ж. вычисл. матем. и матем. физ. 1996. Т. 36. № 11. С. 5-19.

29. Книжнерман Л. А. Квадратура Гаусса-Арнольди для функции {(г1—А)~1<р, ср) и Паде-иодобная рациональная аппроксимация функций марковского типа // Матем. сб. 2008. Т. 199. № 2. С. 27-48.

30. Крейн С. Г. О классах корректности для некоторых граничных задач // Докл. АН СССР. 1957. Т. 114. № 6. С. 1162-1165.

31. Крылов А. Я. О численном решении уравнения, которым в технических вопросах определяются частоты малых колебаний материальных систем // Известия Академии наук СССР. VII серия. Отделение математических и естественных наук. 1931. № 4. С. 491-539.

32. Ланкастер П. Теория матриц. М.: Наука, 1978. 280 с.

33. Лаппо-Данилевский И. А. Применение функций от матриц к теории линейных систем обыкновенных дифференциальных уравнений. М.: Гос. изд-во технико-теор. л-ры, 1957. 454 с.

34. Лебедев В. И. Об итерационных методах решения операторных уравнений со спектром, лежащим на нескольких отрезках //Ж. вы-числ. матем. и матем. физ. 1969. Т. 9. № 6. С. 1247-1252.

35. Лебедев В. И. Явные разностные схемы с переменными шагами по времени для решения жёстких систем уравнений // Отдел вычислит. матем. АН СССР. 1987. Препринт № 177. 39 с.

36. Лебедев В. И. Функциональный анализ и вычислительная математика. М.: Физматлит, 2005. 296 с.

37. Ленг С. Алгебра. М.: Мир, 1968. 564 с.

38. Локуциевский В. О., Локуциевский О. В. Применение чебышёвских параметров для численного решения некоторых эволюционных задач // Ин-т прикл. матем. АН СССР. 1984. Препринт № 996. 30 с.

39. Марчу к Г. И. Методы вычислительной математики. М.: Наука, 1980. 536 с.40 4142