Какова сложность конъюгатного градиента в худшем случае?

9

Позволять ARn×n, симметричный и положительно определенный. Предположим, это займетm единицы работы, чтобы умножить вектор на A, Хорошо известно, что выполнение алгоритма CG наA с номером условия κ требует O(mκ), ед.

Теперь, конечно, будучи OУтверждение, что это верхняя граница. А алгоритм CG всегда может завершиться нулевым шагом с удачным начальным предположением.

Знаем ли мы, что существует RHS и первоначальное (неудачное) предположение, которое потребует Θ(κ)шаги? Другими словами, сложность работы CG в худшем случае действительноΘ(mκ)?

Этот вопрос возникает, когда я пытался определить, является ли преимущество предварительного кондиционера (ниже κ) перевесил его стоимость (выше m). Прямо сейчас я работаю с игрушечными проблемами и хотел бы иметь лучшую идею, прежде чем реализовывать что-либо на скомпилированном языке.

Фред
источник
5
Вы могли бы предположительно построить пессимальное начальное предположение, запустив алгоритм CG «назад» и поместив подходящую энергию в каждый из A-ортогональный поиск направлений, что алгоритм требует всех шагов.
origimbo

Ответы:

9

Ответ оглушительный да. Граница скорости сходимости(κ1)/(κ+1) точен на множестве симметричных положительно определенных матриц с условным числом κ, Другими словами, ничего не зная оA чем номер условия, CG действительно может принять κитерации, чтобы сходиться. Грубо говоря, верхняя граница достигается, если собственные значенияA равномерно распределены (то есть «поперчены») в пределах интервала номера условия κ,

Вот более строгое утверждение. Детерминированные версии более сложны, но работают по тем же принципам.

Теорема (Выбор в худшем случаеA). Выберите любую случайную ортогональную матрицуU, позволять λ1,,λn быть n реальные числа, равномерно выбранные из реального интервала [1,κ], и разреши b=[b1;;bn] быть nреальные цифры взяты из стандартного гауссова. определять

A=Udiag(λ1,,λn)UT.
Тогда в пределе nсопряженные градиенты будут сходиться с вероятностью один к ϵ точное решение Ax=b не менее чем Ω(κlogϵ1) итераций.

Доказательство. Стандартное доказательство основано на оптимальных полиномиальных аппроксимациях Чебышева с использованием методов, найденных в ряде мест, таких как книга Гринбаума или книга Саада .

Ричард Чжан
источник
1
Граница не является точной, как объясняется в ответе позже. Если собственные значения не распределены равномерно, cg сходится быстрее, поскольку это не стационарная итерация. Таким образом, нам нужно больше узнать о матрице.
Гвидо Каншат
@GuidoKanschat: Хороший вопрос, и я исправил заявление, чтобы прояснить, что резкость достигается по всем A с условием κ,
Ричард Чжан
Доказательство сводится к минимизации p(A)в пространстве полиномов порядка удовлетворяющих условию . Эквивалентно это, В указанном пределе и решением минимаксной задачи является полином Чебышева, ошибка которого сходится кkp(0)=1minpmaxλΛ(A)|p(λ)|Λ(A)[1,κ]κ
Ричард Чжан
0

Принимая это как мой первоначальный вопрос: знаем ли мы, что существует RHS и первоначальное (неудачное) предположение, для которого потребуются шаги?Θ(κ)

Ответ на вопрос «нет». Идея этого ответа исходит из комментария Гвидо Каншата.

Утверждение: для любого заданного номера условия существует матрица с тем номером условия, для которого алгоритм CG завершится не более чем за два шага (для любого заданного RHS и начального предположения).kA

Consider ARn×n where A=diag(1,κ,κ,,κ). Then the condition number of A is κ. Let bRn be the RHS, and denote the eigenvalues of A as λi where

λi={1i=1κi1.

Сначала рассмотрим случай, когда , первоначальное предположение, равно нулю. Обозначим в качестве второй оценки из алгоритма CG. Мы показываем, что , показывая . Действительно, у нас естьx(0)Rnx(2)RnA1bx(2)=A1bx(2)A1b,A(x(2)A1b)=0

x(2)A1b,A(x(2)A1b)=x(2)A1bA2=minppoly1(p(A)A1)bA2=minppoly1i=1n(p(λi)λi1)2λibi2i=1n(p^(λi)λi1)2λibi2=0

Где мы используем многочлен первого порядка определенный как . Таким образом, мы доказали случай для .p^p^(x)=(1+κx)/κx(0)=0

Если , то где - это вторая оценка алгоритма CG с заменой на . Таким образом, мы сократили этот случай до предыдущего. x(0)0x(2)=x(2)¯+x(0)x(2)¯bb¯=bAx(0)

Фред
источник
Насколько это верно для арифметики с конечной точностью?
origimbo
@origimbo Если ваш вопрос был адресован мне, ответ: «Я не знаю».
Фред