В чем заключается принцип сходимости подпространственных методов Крылова для решения линейных систем уравнений?

24

Насколько я понимаю, существует две основные категории итерационных методов решения линейных систем уравнений:

  1. Стационарные методы (Якоби, Гаусс-Зайдель, СОР, Мультисетка)
  2. Методы подпространства Крылова (Conjugate Gradient, GMRES и др.)

Я понимаю, что большинство стационарных методов работают путем итеративного ослабления (сглаживания) мод Фурье ошибки. Насколько я понимаю, метод сопряженных градиентов (метод подпространств Крылова) работает, «шагая» через оптимальный набор направлений поиска по степеням матрицы, примененной к му остатку. Является ли этот принцип общим для всех методов подпространства Крылова? Если нет, то как в целом охарактеризовать принцип сходимости подпространственных методов Крылова?n

Пол
источник
2
Ваш анализ стационарных методов смещен простыми модельными проблемами, потому что они могут быть проанализированы с точки зрения мод Фурье. Он также игнорирует неявное переменное направление (ADI) и многие другие методы. Смысл большинства «стационарных методов» состоит в том, чтобы объединить множество простых «приближенных частичных» решателей в один итерационный решатель. Смысл методов Крылова состоит в том, чтобы ускорить (или даже навязать) сходимость данной стационарной линейной итерации.
Томас Климпел
4
Я думаю, что статья, написанная для ответа на ваши вопросы, - это Ипсен и Мейер. Идея методов Крылова, амер. Математика Ежемесячно 105 (1998), стр. 889-899. Это чудесно хорошо написанная и разъясняющая статья, доступная здесь .
Эндрю Т. Баркер
@ AndrewT.Barker: Круто! Спасибо Андрей! :)
Павел

Ответы:

21

В общем, все методы Крылова, по сути, ищут многочлен, который мал при оценке по спектру матрицы. В частности, й остаток метода Крылова (с нулевым начальным предположением) можно записать в видеn

rn=Pn(A)b

где - некоторый монический многочлен степени . нPnn

Если диагонализуем, с , мы имеемA = V Λ V - 1AA=VΛV1

rnVPn(Λ)V1b=κ(V)Pn(Λ)b.

В том случае, если нормально (например, симметричный или унитарный) мы знаем , что GMRes конструктов такой многочлена через Арнольди итерацию, в то время как CG строит многочлен с использованием другого внутреннего продукта (см этого ответа для подробностей ). Точно так же BiCG строит свой полином через несимметричный процесс Ланцоша, в то время как чебышевская итерация использует предварительную информацию о спектре (обычно оценки наибольшего и наименьшего собственных значений для симметричных определенных матриц).κ ( V ) = 1.Aκ(V)=1.

В качестве классного примера (мотивированного Trefethen + Bau) рассмотрим матрицу, спектр которой таков:

Спектр матрицы

В MATLAB я построил это с помощью:

A = rand(200,200);
[Q R] = qr(A);
A = (1/2)*Q + eye(200,200);

Если мы рассмотрим GMRES, который строит многочлены, которые фактически минимизируют остаток по всем моническим многочленам степени , мы можем легко предсказать историю остатков, посмотрев на многочлен-кандидатn

Pn(z)=(1z)n

который в нашем случае дает

|Pn(z)|=12n

для в спектре .AzA

Теперь, если мы запустим GMRES на случайной RHS и сравним остаточную историю с этим полиномом, они должны быть очень похожими (возможные значения полинома меньше, чем остаточный GMRES, потому что ):b2>1

Остаточная история

Reid.Atcheson
источник
Не могли бы вы уточнить, что вы подразумеваете под «малым по спектру матрицы»?
Павел
2
Взятый как комплексный многочлен, многочлен имеет малый модуль в области комплексной плоскости , которая включает в себя спектр . Представьте контурную диаграмму, наложенную на точечную диаграмму собственных значений. Насколько маленький маленький? Это зависит от проблемы, является ли нормальным, и правая частьОсновная идея заключается в том, что последовательности полиномов стремятся постепенно уменьшаться и уменьшаться в спектре, так что остаточная оценка в моем ответе стремится к . A A b . ( П н ) 0PnAAb.(Pn)0
Reid.Atcheson
@ Reid.Atcheson: Очень хорошо. Могу ли я порекомендовать написатькак и упомянуть, что это один для нормальных матриц? κ ( V )VV1κ(V)
Джек Поулсон
Лапласиан, обусловленный оптимальным SOR, имеет спектр, очень похожий на матрицу этого примера. Подробности здесь: scicomp.stackexchange.com/a/852/119
Джед Браун
Строго говоря, CGNE не зависит от спектра, поскольку зависит только от сингулярных значений.
Джед Браун
17

По нормам

В качестве дополнения к ответу Reid.Atcheson, я хотел бы прояснить некоторые вопросы, касающиеся норм. На итерации GMRES находит многочлен который минимизирует норму невязки п н 2nthPn2

rn=Axnb=(Pn(A)1)bb=Pn(A)b.

Предположим, что является SPD, поэтому индуцирует норму и . затемAAA1

rnA1=rnTA1rn=(Aen)TA1Aen=enTAen=enA

где мы использовали ошибку

en=xnx=xnA1b=A1rn

Таким образом, норма ошибки эквивалентна норме невязки. Сопряженные градиенты сводят к минимуму норму ошибки, что делает ее относительно более точной при разрешении низкоэнергетических мод. -норм остаточных, который минимизирует GMRES, подобно -норме ошибки, и , следовательно , слабее в том смысле , что режимы с низким потреблением энергии менее хорошо решены. Обратите внимание, что норма остатка по существу бесполезна, потому что она еще слабее на модах с низкой энергией.A - 1 A 2 A T A AAA1A2ATAA

Резкость границ сходимости

Наконец, есть интересная литература о различных методах Крылова и тонкостях сходимости GMRES, особенно для ненормальных операторов.

Джед браун
источник
Вы остановились на превосходной книге Олави Неванлинны: books.google.com/…
Мэтт Кнепли
11

Итерационные методы в двух словах:

  1. Ax=bC

    x=x+CbCAx
    ICA<1CC=D1Dявляется диагональной матрицей, содержащей диагональные элементы ).A
  2. Крылов метода методы подпространственная в сущности проекционных методов : Вы выбираете подпространства и искать такие , что остаточный ортогонален . Для методов Крылова конечно, является пространством, охватываемым степенями примененными к начальному остатку. Различные методы соответствуют конкретному выбору (например, для CG и для GMRES).˜ xU b - A ˜ x V U A V V = U V = A UU,VCnx~UbAx~VUAVV=UV=AU

    Свойства сходимости этих методов (и проекционные методы в целом) следует из того , что благодаря соответствующему выбору , то являются оптимальным над (например, они минимизируют ошибку в энергетической норме для CG или остаточного для GMRES). Если вы увеличиваете размерность на каждой итерации, вы гарантированно (в точной арифметике) найдете решение после конечного числа шагов.˜ x U UVx~UU

    Как отметил Reid Atcheson, используя крыловские пространства для позволяет доказать скорости сходимости в терминах собственных (и , следовательно , число обусловленности) от . Кроме того, они имеют решающее значение для выведения эффективных алгоритмов для вычисления проекции .A ˜ xUAx~

    Это хорошо объясняется в книге Юсефа Саада об итерационных методах .

Кристиан Клэйсон
источник