數值線性代數簡明教程—centre

1、華中科技大學學習筆記系列 作者：centre 1 三角方程組解法：前代法，回代法求解Ly=b2 Gauss變換法：A=LULk=I-lkek,Lk-1=I+lkek,lk=(00，lk+1,kln,k),lik=aik(K-1)/akk(K-1),(i=k+1n)A(K-1)=Lk-1L1A,L=(LN-1L1)-1,U=A(N-1).存儲：用A(K)的元素沖掉A(K-1)相應位置的元素。運算量：2n3/3主元aii(K-1)均不為零 A的i階順序主子式|Ai|0A的順序主子陣均非奇異唯一單位下三角陣L&上三角陣U,ST,A=LU3 Cholesky分解法：（對正定線性方程組）Cholesky

2、分解定理：A對稱正定 一對角元均為正數的下三角陣L，ST,A=LLlik=(aik-liPlkP)/lkK.lkK=sqrt(akK-lKPlKP).4 LDL分解法：（改進的平方根法，避免開方運算）vk=dkljk.dj=ajj-ljkvk=ajj-ljkljkdk.lij=(aij-likvk)/dj.5 向量范數：定義：RnR,正定性(|x|0,|x|=0當且僅當x=0),齊次性(|x|=|*|x|),三角不等式(|x+y|x|+|y|)性質：連續(xù)實函數P范數：|x|p=(|x1|p+|xn|p)1/p,p1.p=1,2，時最重要的范數(證：|xy|x|p|y|q (1/p+1/q=1)

3、定理：|&|C1,C2,STxRn,C1|x|x|C2|x|。定理：xkRn,|xk-x|=0 |xi(K)-xi|=06 矩陣范數：定義：Rn*nR,正定性,齊次性,三角不等式,+相容性(|AB|A|B|)。矩陣范數和向量范數滿足|Ax|v|A|m|x|v,則|m與|v相容。|是Rn的一向量范數，if|A|=|A|,ARn*n，then|是Rn*n的一矩陣范數。7 向量范數誘導出的算子范數：行和范數：|A|=|aij|列和范數：|A|1=|aij|8 譜范數：|A|2=SQRT(max(AA)=MAX|yAx|:x,yCn,|x|2= |y|2= 1=|A|2=SQRT(|AA|2)=|A|

4、2=|VA|2=|AU|2(正交陣U,V)9 Frobenius范數：|A|F=(|aij|2)1/2. 譜半徑：(A)=max|:(A);ACn*n 矩陣范數|有(A)|A| 0,算子范數|,st,|A|(A)+ ACn*n,則AK=0 (A)1 AK收斂 ACn*n,則AK收斂時，有AK=(I-A)-1且算子范數St,|(I-A)-1 -AK|A|m+1/(1-|A|) |是Cn*n的一矩陣范數，|I|=1,設ACn*n有|A|1,則I-A可逆且|(I-A)-1 |1/(1-|A|)10 敏度分析：(A+A)(x+x)=b+b(b=Ax)得(A+A)x=b-Ax得x=(I+A-1A)-1A

5、-1(b-Ax)得|x|A-1|(|b|+|A| |x|)/(1-|A-1|A|)得|x|/|x|A-1|A|(|A|/|A|+|b|/|b|)/(1-|A-1|A|) K(A)=|A-1|A|為Ax=b的條件數 推論：|是Rn*n的一矩陣范數，|I|=1,設ARn*n非奇異，A滿足|A-1|A|n超定(矛盾)方程組，mn)則A=Q(R,0),Q是正交陣，R是具非負對角元的上三角，且m=n&A0時上述分解唯一。 |Ax-b|22=|Q(Ax-b)|22=|Q(Q(R,0)x-b)|22=|Rx-C1|22+|C2|22 QR分解法：QR分解；c1=Q1b；Rx=c1;求出x（以斜對角線的方式存

6、在A左下）15 古典迭代法：(此后部分屬于間接解法) Jacobi迭代：Ax=b (D-L-U)x=b xk+1=D-1(L+U)xk+D-1b=(I-D-1A)xk+D-1b Gauss-Seidel：Ax=b (D-L-U)x=b xk+1=(D-L)-1Uxk+(D-L)-1b(省存儲量) 單步線性定常迭代，迭代矩陣，常數項，初始向量 |G|0，ST，G(I-M)=A,Gg=b,(xk+1=Mxk+g),則迭代法與線性方程組相容 迭代法收斂 MK0(M)1 IF 迭代法M有|M|=q1,|I|=1,則|xk-x*|x1-x0|qk/(1-q) IF 迭代法M有|M|=q1,|I|=1,則

7、|xk-x*|xk+1-xk|q/(1-q) B是Jacobi迭代陣： If|B|1,then,G-S迭代收斂|xk-x*|x1-x0|k/(1-) If|B|11,then,G-S迭代收斂|xk-x*|1|x1-x0|1k/(1-)(1-s)【s=|bij|,=|bij|/(1-|bij|)|B|11,=|bij|/(1-|bij|)|B|0,then, Jacobi收斂 0A0 G-S迭代收斂 弱嚴格對角占優(yōu)，嚴格對角占優(yōu)，可約（可分）的，不可約（不可分）的 If A嚴格對角占優(yōu)或不可約對角占優(yōu)(=弱嚴格對角占優(yōu)+不可約)，then,|A|0,Jacobi&G-S迭代均收斂。 If A嚴格

8、對角占優(yōu)或不可約對角占優(yōu)，A=A,aii0，then,A016 SOR法：（要求A有較好的性質，計算opt非常困難）xk+1=xk+x=(1-)xk+(D-1Lxk+1+D-1Uxk+D-1b)得xik+1=(1-)xik+(xjk+1+xjk+gi)1為超松馳迭代；1為低松弛迭代；=1為G-S迭代xk+1=Lxk+(D-L)-1b （其中L=(D-L)-1(1-)D+U）收斂性質：A嚴格對角占優(yōu)OR不可約對角占優(yōu)，（0，1）A實對稱正定，（0，2）SOR收斂 （L）1（0，2）最佳松弛因子：+-1=u*sqrt() =(u/2)2,得opt=2/(1+)時（L）=(1-)/(1+)17 最速

9、下降法：（對稱正定矩陣局部下山最佳方向）Min(x)=xTAx-2bTx grad(x)=2(Ax-b)=-2r (其中rk=b-Axk)(x*+y)=(x*)+yTAy(x*)令xk+1=xk+kPk。 F()=(xk+kPk)=2PkTAPk-2rkTPk+(xk)F()=0得k=rkTPk/PkTAPk.此時(xk+1)-(xk)=-(rkTPk)2/PkTAPk.收斂性質：設A的特征值01n,|x|A=sqrt(xTAx)|xk-x*|A(n-1)/(n+1)k|x0-x*|A|P(A)x|Amaxp(i)|x|A.其中P(t)是實系數多項式 18 CG法：（對稱正定矩陣整體下山最佳方

10、向）給定初始向量X0,第一步仍選負梯度方向為下山方向，P0=r0,0=r0r0/P0AP0,X1=X0+0P0,r0=b-AX1.對k+1步，下山方向為過XK由RK,PK-1張成的二維平面，X=XK+K+PK-1.(,)=XAX-2bX X=XK+0rK+0PK-1.令k-1=0/0,XK+1=XK+KPK.得K=rkPk/PkAPk,k=-rk+1APk/PkAPk,PK=rK+kPK-1,rK+1=rK-KAPK.性質：Pirj=0,0ijk;rirj=0,PiAPj=0,ij,0i,jk;Krylov子空間：(A,r0,k+1)=spanr0AKr0=spanr0rk正交基=spanP0

11、Pk共軛正交基共軛梯度法得到的近似解是離方程組最近的19 實用共軛梯度法（誤差使共軛梯度法rK的正交性很快損失掉） 原理：利用|rK|是否已經很小或K是否足夠大來控制程序迭代次數 收斂性：if A=I+B,rankB=r,then 共軛梯度法至多迭代r+1步即可達到精確解（證：由Krylov子空間的維數可知）。 XK誤差估計：|xk-x*|A2(-1)/(+1)k|x0-x*|A,k=|A|2|A-1|2由上述條件可知：k1時或系數矩陣十分良態(tài)時收斂很快。20 PCG法：（將A化為一系數矩陣僅有少數幾個互不相同的特征值或非常良態(tài)的等價方程組，也就是解病態(tài)方程組的一種方法） AX=bAX=b(A

12、=C-1AC-1,X=CX,b=C-1b,C為對稱正定矩陣) 令XK=CXK,rK=CrK,Pk=CPk,M=C2. 好的預優(yōu)矩陣M：對稱正定；稀疏；M-1A僅有少數幾個特征值；Mz=r易解。 選?。?IF A對角元相差很大，取M=diag(a11ann)推廣M=diag(A11Ann) 不完全Cholesky因子預優(yōu)陣：A=LL+R,令M=LL 多項式預優(yōu)陣：Mz=r看作Az=r的近似，利用古典迭代法可取M-1=(I+GP-1)M1-121 非線性方程組的解法：l F-導數(強)，G-導數(弱)，F=d(f1fn)/d(x1xn)grad F=(F)T.l 性質：線性性，鏈式法則，中值公式，Newton-Leibniz公式，Taylor定理l Banach壓縮映照原理：閉集D0上的壓縮映射；F(D0) D0,則F在D0有唯一不動點l Picard迭代法：(X),|(X)|21;detI-(X)T(X)=0,|(X)|2=sqrt(maxi)1l 加速收斂技術：X,(Xk);P=(Xk);Xk+1=(I-P)