Quelle est la complexité la plus défavorable du gradient conjugué?

Soit $A\in \mathbb{R}^{n\times n}$ , symétrique et positif défini. Supposons qu'il faut $m$ unités de travail pour multiplier un vecteur par $A$ . Il est bien connu que l'exécution de l'algorithme CG sur $A$ avec le numéro de condition $\kappa$ nécessite $\mathcal{O} (m\sqrt{\kappa})$, unités de travail.

Maintenant, bien sûr, étant une instruction $\mathcal{O}$ , c'est une limite supérieure. Et l'algorithme CG peut toujours se terminer en zéro étapes avec une supposition initiale chanceuse.

Savons-nous s'il existe un RHS et une supposition initiale (malchanceuse) qui nécessitera $\mathcal{\Theta}(\sqrt{\kappa})$étapes? Autrement dit, la complexité du travail dans le pire des cas de CG est vraiment$\Theta( m \sqrt{\kappa})$?

Cette question se pose lorsque j'ai essayé de déterminer si les avantages d'un préconditionneur ( inférieur $\kappa$) l'emportaient sur son coût ( supérieur $m$). En ce moment, je travaille avec des problèmes de jouets et j'aimerais avoir une meilleure idée avant d'implémenter quoi que ce soit dans un langage compilé.

La réponse est un oui retentissant. Le taux de convergence lié à est nette sur l'ensemble des matrices définies positives symétriques avec le numéro de conditionκ. En d'autres termes, sachant rien de plus surAque son numéro de condition, CG peut vraiment prendre∼$(\sqrt{\kappa}-1) / (\sqrt{\kappa}+1)$$\kappa$$A$ itérations pour converger. En gros, la limite supérieure est atteinte si les valeurs propres deAsont uniformément réparties (c'est-à-dire "poivrées") dans un intervalle de nombre de conditionsκ.$\sim\sqrt{\kappa}$$A$$\kappa$

Voici une déclaration plus rigoureuse. Les versions déterministes sont plus impliquées mais fonctionnent en utilisant les mêmes principes.

Théorème (choix du pire cas de ). Choisir une quelconque matrice orthogonale aléatoire U , laisser λ 1 , ... , λ n soit n nombres réels uniformément échantillonnés à partir de l'intervalle réel [ 1 , κ ] , et que b = [ b 1 ; … ; b n ] être n nombres réels échantillonnés iid à partir du gaussien standard. Définissez A = U d i a g ( λ 1$A$$U$$\lambda_1,\ldots,\lambda_n$$n$$[1,\kappa]$$b=[b_1;\ldots;b_n]$$n$Ensuite, dans la limite n → ∞ , les gradients conjugués convergeront avec la probabilité un vers une ϵ solution précise de A x = b en pas moins de Ω (

$$A=U\mathrm{diag}(\lambda_1,\ldots,\lambda_n)U^T.$$ $n\to\infty$$\epsilon$$Ax=b$itérations.$\Omega(\sqrt{\kappa}\log\epsilon^{-1})$

Preuve. La preuve standard est basée sur des approximations polynomiales optimales de Chebyshev, en utilisant des techniques trouvées dans un certain nombre d'endroits, comme le livre de Greenbaum ou le livre de Saad .

En prenant cela comme ma question d'origine: savons-nous s'il existe un RHS et une supposition initiale (malchanceuse) qui nécessitera des étapes ?$\Theta(\sqrt{\kappa})$

La réponse à la question est "non". L'idée de cette réponse vient du commentaire de Guido Kanschat.

Revendication: Pour tout numéro de condition , il existe une matrice , avec ce numéro de condition pour lequel l'algorithme CG se terminera en au plus deux étapes (pour tout RHS donné et estimation initiale).$k$$A$

Considérons où . Alors le numéro de condition de est . Soit le RHS et notons les valeurs propres de comme où A = d i a g ( 1 , κ , κ , … , κ ) A κ b ∈ R n A λ i λ i = { 1 i = 1 κ i ≠ 1$A\in \mathbb{R}^{n\times n}$$A=\mathrm{diag}(1,\kappa,\kappa,\ldots, \kappa)$$A$$\kappa$$b\in \mathbb{R}^n$$A$$\lambda_i$

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

Nous considérons d'abord le cas où , la supposition initiale, est zéro. Notons comme la deuxième estimation de partir de l'algorithme CG. Nous montrons que en montrant . En effet, nous avons$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*}$$

Où nous utilisons le polynôme de premier ordre défini comme . Nous avons donc prouvé le cas pour . p (x)=(1+κ-x)/κx(0)=$\widehat{p}$$\widehat{p}(x)= (1+\kappa-x)/\kappa$$x^{(0)}= 0$

Si , alors où est la deuxième estimation de l'algorithme CG avec remplacé par . Nous avons donc réduit ce cas au précédent. x ( 2 ) = ¯ x ( 2 ) + x ( 0 ) ¯ x ( 2 ) b ¯ b = b - A x ( 0 $x^{(0)} \not = 0$$x^{(2)}= \overline{x^{(2)}}+ x^{(0)}$$\overline{x^{(2)} }$$b$$\overline{b} = b-A x^{(0)}$