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

9

Soit ARn×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 κ nécessite O(mκ), unités de travail.

Maintenant, bien sûr, étant une instruction 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 Θ(κ)étapes? Autrement dit, la complexité du travail dans le pire des cas de CG est vraimentΘ(mκ)?

Cette question se pose lorsque j'ai essayé de déterminer si les avantages d'un préconditionneur ( inférieur κ) 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é.

Fred
la source
5
Vous pourriez probablement construire une estimation initiale pessimale en exécutant l'algorithme CG "en arrière" et en mettant l'énergie appropriée dans chacune des directions de recherche orthogonales A que l'algorithme nécessite toutes les étapes.
origimbo

Réponses:

9

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(κ1)/(κ+1)κ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κ.κAκ

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 ,AUλ1,,λnn[1,κ]b=[b1;;bn]nEnsuite, 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=Udiag(λ1,,λn)UT.
nϵAx=bitérations.Ω(κlogϵ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 .

Richard Zhang
la source
1
La limite n'est pas nette, comme l'explique la réponse plus loin, si les valeurs propres ne sont pas uniformément distribuées, cg converge plus rapidement, car il ne s'agit pas d'une itération stational. Ainsi, nous devons en savoir plus sur la matrice.
Guido Kanschat
@GuidoKanschat: Bon point, et j'ai corrigé la déclaration pour clarifier que la netteté est atteinte sur tout avec la condition κ . Aκ
Richard Zhang
La preuve se résume à minimiser dans l'espace des polynômes d'ordre satisfaisant . De manière équivalente, il s'agit de. Dans la limite indiquée, , et la solution pour le problème minimax est alors le polynôme de Chebyshev, dont l'erreur converge commep(A)kp(0)=1Λ ( A ) [ 1 , κ ] minpmaxλΛ(A)|p(λ)|Λ(A)[1,κ]κ
Richard Zhang
0

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 ?Θ(κ)

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).AkA

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 .ARn×nA=diag(1,κ,κ,,κ)AκbRnAλi

λi={1i=1κi1.

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 avonsx(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

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)=0p^p^(x)=(1+κx)/κ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)0x(2)=x(2)¯+x(0)x(2)¯bb¯=bAx(0)

Fred
la source
Dans quelle mesure l'arithmétique est-elle robuste à précision finie?
origimbo
@origimbo Si votre question s'adressait à moi, la réponse est "je ne sais pas".
Fred