1Lecture-15Homework, Rate of Convergence of CG, preconditioning, FR-GC, PR-GCHomework (Due March 25)•5.1•5.9• Proof for Theorem 5.5 (see the slides)2Theorem 5.4If A has only r distinct eigenvalues, then the CG iterationwill terminate at the solution in at most r iterations.Theorem 5.52*02112*1||||||||AknknAkxxxx −+−≤−−−+λλλλIf A has eigenvalues we havenknknλλλλ,,,,,11KK+−−3Proof))(())(()1()(12112111 ++++−−−−−=kkkkkkQτλτλτλτλττττλKK1)0(,,1for 0)(11=+−==++kikQnkniQ Kλ1)(1−+λkQIs polynomial of degree k+1 with root at0=λλλ)1)((1−=+kkQPDegree k2max1min)](1[ikiniPPkλλ+≤≤2112max12max1min)](1[)](1[0+−=+≤+≤−−≤≤≤≤λλλλλλλλknknikiniikiniPPPk(B)Define polynomial:Assume eigenvalues take k distinct values: and nknλλ,,,1K+−kτττ<< ,,21K211λλτ+=−+knk2*02112*1||||||||AknknAkxxxx −+−≤−−−+λλλλHomework: show thisExample},,}{,,,{11 nmnmnλλλλKK+−−Clustered around 1AAmxxxx ||||||||*0*1−≈−+ε2*02112*1||||||||AknknAkxxxx −+−≤−−−+λλλλm largest eigenvaluesFor small value of CG will converge in only m+1 steps.ε4ExampleThe matrix has five large eigenvalues with all smaller eigenvalues clustered around .95 and 1.05N=14, has four clusters of eigenvalues: single eigenvalues at 140, 120, a cluster of 10 eigenvalues very close to 10 with the remaining eigenvalues clustered between .95 and 1.05.5Convergence using Condition number2*022*1||||1)(1)(||||AAkxxAAxx −+−≤−+κκnAAAλλκ1212||||||||)( ==−nλλ>1Convergence Rate of Steepest Descent: Quadratic Function2*2112*1||||||||QknnQkxxxx −+−≤−+λλλλTheorem 3.3nλλ<16What is desirable?•Matrix A should have either:– Few distinct eigenvalues– Few distinct eigenvalues, and few clusters of eigenvalues– Smaller condition numberPreconditioning• If the matrix A dose not have favorable eigenvalues, we can transform the problem such that eigenvalue distribution of a matrix in the transformed problem improves.7Preconditioning Cxx =ˆxCbxACxCxTTˆˆ)ˆ(21)ˆ(ˆ111 −−−−=φxxC =−ˆ1)(ˆ)(1bCxACCTT −−−=Original problem:xbAxxxTT−=21)(φbAx=orTransformation:Transformed problem:xbCxACCxxTTTTˆ)(ˆ)(ˆ21)ˆ(ˆ1 −−−−=φPreconditioningSelect C such that:condition number of is much smaller than the original matrix A.1−−ACCTThe eigenvalues of are clustered1−−ACCTTTLLALC == such that ,One possible preconditioner is ILLLLALLACCTTTT===−−−−−− 111)(ˆ)(1bCxACCTT −−−=8Algorithm 5.3 (Preconditioned CG))(;1 ; ; ; ; ; 0 0 , ;for , , ;oner preconditi ,Given 111111111100000000whileendkkpypyryrrMyAprrpxxAppyrrWhilekrpyrMysolvebAxrsetMxkkkkkTkkTkkkkkkkkkkkkkTkkTkkk+←+−←←=+←+←−←≠←−←=−←++++++++++ββαααCCMT=Homework:convert 5.2 to5.3 using preconditioning)(;1 ; ; ; ; ; 0 0 , , ;Given 1111111100000whileendkkprprrrrAprrpxxApprrrWhilekrpbAxrsetxkkkkkTkkTkkkkkkkkkkkTkkTkkk+←+−←←+←+←−←≠←−←−←++++++++ββααα5.35.2Non-linear CG• Two changes in linear GC– Perform line search for step length – Replace residual r by the gradient of the function• Two algorithms:– FR (Fletcher-Reves) (1964)– PR (Polak-Rebiere) (1969)• The difference is only in β9Algorithm 5.4 (FR-CG))(;1 ; ; ; ; ; compute 0 0 , )( , ;Given 111111110000000whileendkkpfpfffffevaluatepxxfWhilekfpsetxff)f(xfevaluatexkFRkkkkTkkTkFRkkkkkkkk+←+−∇←∇∇∇∇←∇+←≠∇←−∇←∇=∇=++++++++ββαα5.25.4)(;1 ; ; ; ; ; 0 0 , , ;Given 1111111100000whileendkkprprrrrAprrpxxApprrrWhilekrpbAxrsetxkkkkkTkkTkkkkkkkkkkkTkkTkkk+←+−←←+←+←−←≠←−←−←++++++++ββαααQuestion• How do we guarantee that the search direction is a descent direction for any arbitrary non-linear function?10Choice of step length 1211|||| −−−∇+∇−=∇∇+∇−∇=∇+−∇=kTkFRkkkTkkTkFRkkTkkTkkFRkkkpffpfpfffpfpfpβββThe search direction pkmay fail to be a descent direction, unless step length satisfies certain conditions.kFRkkkpfp111 ++++−∇←βIf , then , therefore pkis a descent direction (Theorem 5.2 for quadratic functions).01=∇−kTkpf0<∇kTkpfIf ,then the second term may dominate, and 01≠∇−kTkpf0>∇kTkpfChoice of step length 0 <∇kTkpf)1,0( ,) ()(11∈∇+≤+ cpfcxfpxfkTkkkkαα210 |,) (||)(|212<<<∇≤+∇ cc pxfcppxfkkTkkTkkαTo solve this problem, we will require step length satisfies thefollowing Strong Wolf’s conditions:We will show in Lemma 5.6 that the Wolf’s conditions guarantee:11Polak-RibierekTkkkTkPRkfffff∇∇∇−∇∇←+++)(111βkTkkTkFRkffff∇∇∇∇←+++111βThey are the same if the f is quadratic function, and line search is exact, since gradients (residuals) are mutually orthogonal by Theorem 5.3For general non-linear functions, numerical experience indicates PR-CG tends to be more robust and efficient.For PR-CG strong wolf conditions do not guarantee that pkis always a descent direction.Other Choices)0,max(11PRkk +++=ββkTkkkkTkHSkpfffff)()(1111∇−∇∇−∇∇←++++βThis can satisfy descent propertyYet another choice12Quadratic Termination & RestartsNon-linear CG methods preserves their connections to linear CG. Quadratic interpolation along pkguarantees that for a quadratic function, the step length is exact, that is non-linear CG reduces to linear GC.Restart non-linear GC after every n steps:kFRkkkpfp111 ++++−∇←β11 ++−∇←kkfpIt is steepest descent. It erases the old memory,which may not be beneficial.Quadratic Termination & RestartsN-step Quadratic convergence can be proved with restartsIf the function is strongly quadratic in a neighborhood of a solutionAssume the algorithm is converging to solution, the iterations will enter the quadratic region, at some point algorithm will be restarted, that point onward thebehavior will be similar to linear GC.convergence will occur within n stepsRestart is important, because finite termination is subject to p0 equal to the negative gradient.Even if the function is not strongly quadratic,it can be approximated by Taylor series, if it is smooth.Therefore substantial progress can be made toward the