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

Позволять $A\in \mathbb{R}^{n\times n}$, симметричный и положительно определенный. Предположим, это займет$m$ единицы работы, чтобы умножить вектор на $A$, Хорошо известно, что выполнение алгоритма CG на$A$ с номером условия $\kappa$ требует $\mathcal{O} (m\sqrt{\kappa})$, ед.

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

Знаем ли мы, что существует RHS и первоначальное (неудачное) предположение, которое потребует $\mathcal{\Theta}(\sqrt{\kappa})$шаги? Другими словами, сложность работы CG в худшем случае действительно$\Theta( m \sqrt{\kappa})$?

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

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

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

Теорема (Выбор в худшем случае$A$). Выберите любую случайную ортогональную матрицу$U$, позволять $\lambda_1,\ldots,\lambda_n$ быть $n$ реальные числа, равномерно выбранные из реального интервала $[1,\kappa]$, и разреши $b=[b_1;\ldots;b_n]$ быть $n$реальные цифры взяты из стандартного гауссова. определять

$$A=U\mathrm{diag}(\lambda_1,\ldots,\lambda_n)U^T.$$ Тогда в пределе $n\to\infty$сопряженные градиенты будут сходиться с вероятностью один к $\epsilon$ точное решение $Ax=b$ не менее чем $\Omega(\sqrt{\kappa}\log\epsilon^{-1})$ итераций.

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

Принимая это как мой первоначальный вопрос: знаем ли мы, что существует RHS и первоначальное (неудачное) предположение, для которого потребуются шаги?$\Theta(\sqrt{\kappa})$

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

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

Consider $A\in \mathbb{R}^{n\times n}$ where $A=\mathrm{diag}(1,\kappa,\kappa,\ldots, \kappa)$. Then the condition number of $A$ is $\kappa$. Let $b\in \mathbb{R}^n$ be the RHS, and denote the eigenvalues of $A$ as $\lambda_i$ where

$$\lambda_i = \left\{\begin{array}{ll}1 & i=1\\ \kappa & i\not= 1 \end{array} \right. .$$

Сначала рассмотрим случай, когда , первоначальное предположение, равно нулю. Обозначим в качестве второй оценки из алгоритма CG. Мы показываем, что , показывая . Действительно, у нас есть$x^{(0)} \in \mathbb{R}^n$$x^{(2)}\in \mathbb{R}^n$$A^{-1}b$$x^{(2)} =A^{-1}b$$\langle x^{(2)}-A^{-1}b, A(x^{(2)}-A^{-1}b)\rangle =0$

$$\begin{align*} \langle x^{(2)}-A^{-1}b, A(x^{(2)}-A^{-1}b)\rangle &= \left\| x^{(2)}-A^{-1}b \right\|_A^2 \\ &=\min_{p\in \mathrm{poly}_{1} } \left\| (p(A)-A^{-1}) b \right\|_A^2\\ &=\min_{p\in \mathrm{poly}_{1} } \sum_{i=1}^n (p(\lambda_i) - \lambda_i^{-1})^2 \lambda_i b_i^2 \\ &\le \sum_{i=1}^n (\widehat{p}(\lambda_i) - \lambda_i^{-1})^2 \lambda_i b_i^2 = 0 \end{align*}$$

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

Если , то где - это вторая оценка алгоритма CG с заменой на . Таким образом, мы сократили этот случай до предыдущего. $x^{(0)} \not = 0$$x^{(2)}= \overline{x^{(2)}}+ x^{(0)}$$\overline{x^{(2)} }$$b$$\overline{b} = b-A x^{(0)}$