This yields (4:11)and (4:13).I'sing (4:16)with In view of theorem 4:6.it is seen that at each step p=y and g=r we find that of the cd-routine the dimensionality of the spacer in which we seek the solution h is reduced by unity. fx)=(y1y）=y,r）≤ylrl. Beginning with ro.we seleet an arbitrary chord Co of Hence f(r)=f(ro)through ro and find its center.The plane fr)=4)y2≤yr, through r conjugate to (a contains the centers of all chords parallel to C.In the next step we re- so that the second inquality in (4:14)holds. The strict ourselves to r and select an arbitrary chord first inequality is obtained from the relations C:of f(r)=f(n)through r and find its midpoint r:and the plane r:in conjugate to C:(and hence 2 u(r)) to Co).This process when repeated will yield the answer in at most n steps.In the cg-method the chord Cr of f(r)=f()is chosen to be the normal As is to be expected,any ed-method has within at Je its routine a determination of the inverse 1-1 of 4. We have,in fact,the following: 5.Basic Relations in the cg-Method Theorem 4:5.Let po, .,Pn-be n mutually con- jugate nonzero vectors and let p be the i-th component Recall that in the cg-method the following formulas The element in the j-th rou and k-th column of are used 海ieen b the sum po=ro=k-ro (5:1n pupis re (5:1h (p:Ap) a(puAp This result follows from the formula r1-1=1+0P: (5:1 h=罗p:利 11=一04月g (5:1) (pip)P 6,= (5:1e) for the solution h of r=k,obtained by selecting irg? 10=0. We conclude this section with the following: Pitt=ri1-bipt. (5:1f) Theorem 4:6.Let w:be the (n-i)-limensional plane through r;conjugate to the rectors po.P...., One should verify that eg.(5:1e)and (5:1f)hold for p:-..The plane contains the points i=0.1.2....if.and only if. and intersects the (n-1)-dimensional ellipsoid f(r)= f()in an ellipsoid E:of dimension (n-i-1). The center of E:is the solution h of Ar=k.The point h=空 k=0,1,2.,… (5:2) x是the midpoint of the chord C:ofthrough为 which is parallel to pi.In the cg-method the chord C is normal to E at ri and hence is in the direction of The present section is devoted to consequences of the gradient of f(r)at x:in w. these formulas.As a first result,we have The last statement will be established at the end Theorem 5:1.The residuals ro.ri. and the of section 6.The equations of the plane is given direction rectors po.p....generated by (5:1)satisfy by the system the relations (Ap.r-r)=0 (i=0.1...i1). (,r)=0 (位≠) (5:3a Since pp..are conjugate to po...pi-,so also (p,1p)=0 (≠) (5:3b i Ct-I=0p:T。·.-Qk-1Pk-1 (k>i). (p,r=0(i<), (p,,）=r2(i≥j)(5:3c The points r,d+i… ..rm=h are accordingly in i and h is the center of E;.The chord C.is defined by (r1p)=(p,1pd,(.1)=0(i≠j,i≠j÷1)(5:3d the equation z=r:-tapi,where t is a parameter.As is easily seen. The residuals ro....are mutually orthogonal and the direction rectcrs po,p,···are mutually conju- fx十taP:=fx)一(2t-t护)a(p1p) gate The proof of this result will be made by induction. The second endpoint of the chord C:is the point The vectors ro.Po =ro and ri satisfy these relations x+2a.p at which t=2.The midpoint corresponds since to t=1,and hence is the pointr as was to be proved. (ro.r)=(po.r1)=ro-ao(ro:Apo)=0 414
by(5:1b).Suppose that(5:3)holds for the vectors we accordingly suppose that the routine terminates .P-1.To show that pr can eadjoiadsstifsnecCoaoToat: at the n-th step.Since the r:is orthogonal to ritt we haver:and hence a:40.It follows that (p:r)0by (4:1a).We may accordingly suppose the (rupt)=r (≤) (5:4a) vectors p:have been normalized so that (par)=r:2. In view of (4:3b)and (4:3c)eq (5:3c)holds.Select (pAps)=0 (i<) (5:4b) numbers a such that (rk.1p》=(pk.1D, (i≤k.i≠k-1)(5:4c) P1= Equation (5:4a)follows at once from (5:2)and (5:3a).To prove (5:4b)we use (5:1d)and find that Taking the inner product of p:with r,it is seen by (5:3c)that (r1+1,P）=(px)-a(1p:Pe. By(5:4a)this becomes a)= ≥， a,=0(<. r2=r-a(Apip)(i<k). Consequently,(5:2)holds and the theorem is estab- Since a>0,eq (5:4b)holds.In order to establish lished. Theorem 5:3.The residual rectors ro.n. and (5:4c),we use (5:1f)to obtain the direction rectors po.p,...satisfy the further relations (p:.Ap)=(rx.Api)+bx-1(p:-1.Ap=(rAp) (≠k-1) p,p=2 r (i≤) (5:6a) It.follows that (5:4c)holds and hence that (5:3) holds for the vectors ro.n·..rg and po,p1,··y p2=r2+b1p4-12=r∑ 1 ir (>0) Pt (5:6b) It remains to show that re can be adjoined to this set.This will be done by showing that (r1）=0 i->1 (5:6c) (r,rk+i)=0 (i≤k) (5:5a) (r1Ar)=(pAp)+b-(p-1,1p-) (1>0). (4AP,rk-)=0 (i<k) (5:5b) (5:6d) (P,7+1)=0 (i≤k) (5:5c) The rector r,is shorter than ps. The rector pi makes an acute angle with p The relations (5:6a)and (5:6b)follow readily from By (5:Id)we have (5:1e),(⑤：1f),(⑤：2)，and(5:3).Using(5:1f)and (5:3d).we see that (r,Tk÷1）=(r,re)一Q(r,1pk. (,Ar)=(r,Ap)-b-1(r,Ap-)=0 (<j-1). If i<k,the terms on the right are zero and (5:5a) holds.If i=k,the right member is zero by (5:1b) Hence (5:6c)holds.Equation (5:6d)is a conse- and(i:3d).'sing(⑤：ld)again we have with i< quence of (5:1f)and (5:3b).The final statements are interpretations of formula(5:6b)and (5:6a). 0=(r)=(k)-ai(r1Api)=-a(rAp). Theorem5:4.The direction vectors po,p,·· satisfy the relations Hence (5:5b)holds.The equation (5:5c)follows from (5:5a)and the formula (5:2)for p:. As a consequence of (5:3b)we have the first two p1=(1÷bu)Po-ao1o (5:7a) sentences of the following: (i>0.(5:7l) Theorem 5:2.The cg-method is a ed-mcthod.It is 141=(1+b,)p:-a1,-b1-P-i the special case of the cd-method in which the p:are obtained by A-orthogonalization of the residual vecturs Similarly,tlt.residuals ro,ri,···satisfy the relations ri.On the other hand,a cd-methond in which the rexid- ri=To-avAro (5:8a) uals ro.ri....arc mutually orthogonal is essentially a cg-mcthod. r+1=(1+b-i)r,-a1r-b-1r-1 (5:8h) The term "essentially"is used to designate that we disregard iterations that terminate in fewer than arht re n steps,unless one adds the natural assumption that the formula for p,in the routine depends continu- ously on the initial estimate ro.To prove this result bb (5:9) 415
Equation (5:7b)is obtained by climinating r Theorem6:L.The extimates ro,I,···,Imfh1re and r:from the equations distinet.The point 1:minimizes the error funetion f(r)=(h-r,1(h-r))on the i-dimensional plane P P1+1=r:+1+b: passing through the points ro,,.·,·, In the ith step of the cg-method.f(r)is diminished by the amount r=r-ap: fr-)-fx=n-1r-2=u(p-)r-1-r2(6:1 4=r:+b:--1 where u(z)is the Rayleigh quotient (4:12).Hence. Equation (5:7a)follows similarly.In order to prove (5:8b),eliminate .Ip,and .ip:-from the equations fr-fr）=r2+···+n-ir-(i<. (6:23 +1=r-l1p The point r,is giren by the formulas 1p:=1r:÷b:-1p-1 1-1 r=rn十∑aP,=ro十 只f》-, (6:3) T=r-1-0:-t1p1-1 This result is essentially a restatement of theorem Equation (5:8a)holds since po=ro. 4:3.The formula (6:3)follows from (5:2)and Theorem 5:5.The scalars a:and b;are gicen by the (6:2).The second equation in (6:1)is readily seteral formulas verified. Theorem 6:2.Let S:be the conver closure of the r (pir)(pi.ro) a=(p,lpp.dp）p1p） (5:10) estimales xo.n,...,I1.The point zi is the point in S:.whose error rector h-r is the shortest. For a point r in S:is expressible in the form b,=_dp。-dr】 r2✉ (p,1p) (5:11) (p..1p) r=a0la+··+十axd The senlur a;satisfies the relution where a1≥0，十a1十··-a=1. ⊥=ro, ap<2<ar)心0， (5:12) We have accordingly d i where u(z)is the Rayleigh quotient (4:12).The recip- r:-1=a(x,-rn)÷···十x-1(1-了-1)=oD rocal of a:lies between the smallest and largest char- acteristic roots of A. ÷、,,-3-P-1 The formula (5:10)follows from (5:1b)and (5:3c), while (5:11)follows from (5:le),(5:1f).(5:3b),and where the B's are nonnegative.Inasmuch as all (5:3d).Since (PPe)>0 it follows that r<Pi (reAr>(p.Apo (,-r,11->0(i<. by (5:6b)and (5:6d),we have Using the relation p,dp）p.dp）r.dr) r)-2=一5,2+2(5)-51-+x-1(6:4 p r ire we find that The inequalities (5:12)accordingly hold.The last statement is immediate,since u(z)lies between the -5,<5,-f(i<j smallest and largest characteristic roots of 4. Setting j=m,we obtain theorem 6:2. 6.Properties of the Estimates x;of h in the Incidentally.we have established the cg-Method Corollary.The point ri is the point in S,nearest to the point rs (j>i. Let now ro,n,...,rm=k be the estimates of h Theorem 6:3.At each step of the cg-algorithm the obtained by applying the cg-method.Let ro.ri, error roctor yi=h-ri is reduced in length.In fact. ...rm=0 be the corresponding residuals and po p,...,pm-1 the direction vectors used.The pres- -:-y2=f+f- (6:5) ent section will be devoted to the study of the prop- 4P:-i erties of the points ro.i....,rm.As a first result we have where u(z)is the Rayleigh quotient (4:12). 416
In order to establish (6:5)observe that,by (5:6a),is the point in P;whose distance from the solution h is the least.It lies on the line ri-r;beyond r.Mforeorer, (y1.r-t-=(tm-x1,p-1）a1-1 1 =[a(p,p:-)十.，.+am-(pm-pt-i]a-i J(25)-f(r)f) (6.9) =a+.+am-17m-3a4-242 and 「-2 h-x2=h-r2+)-f .(6.10) 4(P-1 In view of (6:2)and (5:1b)this becomes In order to establish (6:9)and 6:10)we use the ,54--)=) (6:6) formula 4(p-1) f(r-api-1)=f(ril-a(p:-1.Ap-1). Setting r=r-and j=m in (6:4),we obtain (6:5) by the use of (6:6)and (6:1). which holds for all values of a in view of the fact that This result establishes the cg-method as a method r:minimizes f(x)on P.Setting a=f(r)-1 of successive approximations and justifies the pro- we have cedure of stopping the algorithm before the final- step is reached.If this is done,the estimate ob- tained can be improved by using the results given )=f+a=f0r+, f(r f()2 in the next two theorems. Theorem,6:4..Ltr4.··,r be the projec- An algebraic reduction yields (6:9).Inasmuch as tions o时the points r+,···,tm=h in the i- dimensional plane P:passing through the points ro. ··· .The points r-,了x·,，81ie h-2-h-02=,）12-1 r- on a straight line in the order giren by their enumeration. The point rg (k>i)is giren by the formulas f(r)2a1-1卫-12 =1-4+-=u,-1-,67a =f5--f04-3 f(1)-f(ri) we obtain (6:10)from (6:9)and (5:1b). =-1+fU-f As a further result we have 1-2 P1-1 (G:7b） Theorem6:6.Iett,··: be the projections of the points n..,on the line joining the initial point ro to the solution m=h.The points ro..... In order to prove this result,it is sufficient to establish (6:7).To this end observe first that the atroete vector tion withoui oscillation.To prove this fact we need 1-1 (1≥) only observe that (rm-了r1-了1-）=(m-了00-P-） is orthogonal to each of the vectors po,p,. p.This can be seen by forming the inner product 二1 with p(<i),and using (5:6a).The result is =0-12a(pp1->0 10 -,9=0 (P)-M-= by(5:6a). A similar result holds for the line joining rt0,(i<i) The projcetion of the point Let x:be the (n-i)-dimensional plane tbrough r conjugate to po.p,....p:1.It consists of the set Ix=J:-1十01-1-10，P十.··十0k-1-1 of points r satisfying the equation in P,is accordingly (.1P-了=0 Gj=0.1.··-1 5=1-1+0-1-:十-14= 12 …1-1 This plane contains the points r....and hence the solution h. I'sing (6:2).we obtain (6:7).The points lie in the Theorem 6:7.The gradient of the function f(r)at r designated order,since fr:>+). in the plane x:is a scalar multiple of the rector p. Since f)=0,we have the first part of The gradient of f(r）at了：is the vector-rTle gradient g:of f(r)at r:in r,is the orthogonal projec- Thcorom 6:5.The point tion of -r in the plane i.Hence g:is of the form =+ 51-121 (6:8) 417
where ao,··,a-t are chosen s0thtq:is orthogonal = (7:3l1 t0.lp,,·,lp-1:Sie C:0r: p=r o72 -,=公会 1。 (7:31 r+1=r-0·1P, g=0.1.…..i-1)、 The sum of the cotfficients of ro,r.....sin (7:3b) (and hence of ror....,r;in (7:3c))is unity it is seen upon elimination of ro... .…"i-1s1l'res- sively that p is also a linear combination of r:.po. The relation (7:1)can be established by induction It holds for i=0.If it holds for i,then ...Ap1.Inasmuch as p:is conjugate to pa. p-1,it is orthogonal to ipo,. Ap:-1.The vector p accordingly is a scalar multiple of the gradient q P+1=r-1十bP=(1+b,C)k-1(r+1+bcE,） of f(r)at r:in r,as was to be proved. =（+(k一1F-) In view of the result obtained in theorem 6:7 it is seen that the name "method of conjugate gradients" The formula (7:3a)follows from (7:2a),(5:le)and is an appropriate name for the method given in sec- 5:6b). Formula (7:3b)is an easy consequence of tion 3.In the first step the relaxation is made in the (7:2b. To prove (7:3c)one can use (5:2)or (7:3b). direction po of the gradient of f(r)at ro,obtaining as one wishes.The final statement is a consequence a minimum value of f()at r.Since the solution k of(7:3a). lies in m,it is sufficient to restrict r to the plane ri Theorem 7:2.The point r;gicen by (7:2)lies in Accordingly,in the next step,we relax in the direc- the conrer closure Si of the points ro.r, tion p of the gradient of f(r)in at ri,obtaining the the point r in the i-dimensional plane P:through ro. point r2 at which f(r)is least.The problem is then n,.,r:at which the squared residual k-Ar2 has reduced to relaxing f(r)in the plane 2,conjugate to its minimum ralue. This minimum ralue is giren by po and pi.At the next step the gradient in r2 in ra the formula is used.and so on.The dimensionality of the space in which the relaxation is to take place is reduced bv unity at each step.Accordingly,after at most n ✉2_ steps,the desired solution is attained. ctp (7:4) The squared residuals ro,T,.···diminish mone- 7.Properties of the Estimates x;of h in the tonically during the cg-method.At the ith step the cg-Method squared residual is reduced by the amount In the cg-method there is a second set of estimates F-12-r2= .Tol, (7:5) To=ro,.of h that can be computed,and Ci that are of significance in application to linear systems arising from difference equations approxi- The first statement follows from (7:3b),since the mating boundary-valve problems.In these applica- coefficients of Jo,r,. ··,r are positive and have tions,the function defined by is smoother than unity as their sum.In order to show that the that of r,and from this point of view is a better squared residual has a minimum on P:at F:,observe approximation of the solution h.The point 7:has that a point r in P:differs from 7,by a vector z:of its residual proportional to the conjugate gradient p.. the form The points To,Ti,2: can be computed by the iteration(7:2)given in the following: Theorem 7:1.The conjugate gradientp:iserpressible r-E:=1=D0十···十a-P-1 in the form The residual r=k-Ar is accordingly given by P=C(k-A7:, (7:1) r=r:-12 where c:and Ts are defined by the recursion formulas 1z=an1p0十··-a-11i-1 co=1,c1-1=1÷b:: (7:2a) Inasmuch as.by (7:3c),F=Pc:,we have 0=r0.7441=41+b:c7 (7:2b) C:+1 G,1p,}=1(p.dp）=0 (j<i). We have the relations Consequently,(FiHz)=0 and =r1 (7:3) 712=7:2+A>79 (山≠i) 418