《数值线性代数简明教程—centre》由会员分享，可在线阅读，更多相关《数值线性代数简明教程—centre（5页珍藏版）》请在金锄头文库上搜索。
1、华中科技大学学习笔记系列 作者：centre -穷则投资自己，达则投资天下-1 1 三角方程组解法：前代法，回代法求解三角方程组解法：前代法，回代法求解 Ly=bLy=b 2 2 GaussGauss 变换法：变换法：A=LUA=LU L Lk k=I-l=I-lk ke ek k,L,Lk k-1-1=I+l=I+lk ke ek k, l lk k=(00=(00，l lk+1,kk+1,klln,kn,k),l),likik=a=aikik(K-1)(K-1)/a/akkkk(K-1)(K-1),(i=k+1n),(i=k+1n) A A(K-1)(K-1)=L=Lk-1k-1LL1 1
2、A,L=(LA,L=(LN-1N-1LL1 1) )-1-1,U=A,U=A(N-1)(N-1). . 存储：用存储：用 A A(K)(K)的元素冲掉的元素冲掉 A A(K-1)(K-1)相应位置的元素。运算量：相应位置的元素。运算量：2n2n3 3/3/3 主元主元 a aiiii(K-1)(K-1)均不为零均不为零 A A 的的 i i 阶顺序主子式阶顺序主子式|A|Ai i|0|0 A A 的顺序主子阵均非奇异的顺序主子阵均非奇异唯一单位下三角阵唯一单位下三角阵 LAC(A)=max|:(A);ACn*nn*n 矩阵范数矩阵范数|有有 (A)|A|(A)|A|0,0, 算子范数算子范数|
3、,st,|A|(A)+|,st,|A|(A)+ACACn*nn*n, ,则则A AK K=0=0 (A)nmn 超定超定( (矛盾矛盾) )方程组，方程组，mn),(mn)则则 A=Q(R,0),QA=Q(R,0),Q 是正交阵，是正交阵，R R 是具非负对角元是具非负对角元 的上三角，且的上三角，且 m=n ;求出求出 x x（以斜对角线的方式存在（以斜对角线的方式存在 A A 左左 下）下） 15 15 古典迭代法：古典迭代法：( (此后部分属于间接解法此后部分属于间接解法) ) JacobiJacobi 迭代：迭代：Ax=bAx=b (D-L-U)x=b(D-L-U)x=b x xk+1
4、k+1=D=D-1-1(L+U)x(L+U)xk k+D+D-1-1b=(I-Db=(I-D-1-1A)xA)xk k+D+D-1-1b bGauss-SeidelGauss-Seidel：Ax=bAx=b (D-L-U)x=b(D-L-U)x=b x xk+1k+1=(D-L)=(D-L)-1-1UxUxk k+(D-L)+(D-L)-1-1b(b(省存储量省存储量) ) 单步线性定常迭代，迭代矩阵，常数项，初始向量单步线性定常迭代，迭代矩阵，常数项，初始向量|G|0|G|0，STST，G(I-M)=A,Gg=b,(xG(I-M)=A,Gg=b,(xk+1k+1=Mx=Mxk k+g),+g
5、),则迭代法与线性方程组相容则迭代法与线性方程组相容迭代法收敛迭代法收敛 M MK K00(M)0,then,0,then, JacobiJacobi 收敛收敛 00A0 G-SG-S 迭代收敛迭代收敛 弱严格对角占优，严格对角占优，可约（可分）的，不可约（不可分）的弱严格对角占优，严格对角占优，可约（可分）的，不可约（不可分）的 IfIf A A 严格对角占优或不可约对角占优严格对角占优或不可约对角占优(=(=弱严格对角占优弱严格对角占优+ +不可约不可约) )， then,|A|0,Jacobir=0,0ijk;ri ir rj j=0,P=0,Pi iAPAPj j=0,ij,0i,jk
6、;=0,ij,0i,jk; KrylovKrylov 子空间：子空间：(A,r(A,r0 0,k+1)=spanr,k+1)=spanr0 0AAK Kr r0 0=spanrspanr0 0rrk k = =spanPspanP0 0PPk k 共轭梯度法得到的近似解是离方程组最近的共轭梯度法得到的近似解是离方程组最近的 19 19 实用共轭梯度法（误差使共轭梯度法实用共轭梯度法（误差使共轭梯度法 r rK K的正交性很快损失掉）的正交性很快损失掉） 原理：利用原理：利用|r|rK K|是否已经很小或是否已经很小或 K K 是否足够大来控制程序迭代次数是否足够大来控制程序迭代次数 收敛性：收
7、敛性：ifif A=I+B,rankB=r,thenA=I+B,rankB=r,then 共轭梯度法至多迭代共轭梯度法至多迭代 r+1r+1 步即可达到精步即可达到精 确解（证：由确解（证：由 KrylovKrylov 子空间的维数可知）子空间的维数可知） 。X XK K误差估计：误差估计：|x|xk k-x-x* *|A A2(2(-1)/(-1)/(+1)+1)k k|x|x0 0-x-x* *|A A,k=|A|,k=|A|2 2|A|A- -kk1 1|2 2 由上述条件可知：由上述条件可知：k1k1 时或系数矩阵十分良态时收敛很快。时或系数矩阵十分良态时收敛很快。 20 20 PCG
8、PCG 法法：（将：（将 A A 化为一系数矩阵仅有少数几个互不相同的特征值或非常化为一系数矩阵仅有少数几个互不相同的特征值或非常 良态的等价方程组，也就是解病态方程组的一种方法）良态的等价方程组，也就是解病态方程组的一种方法） AX=bAX=b(A=CAX=bAX=b(A=C-1-1ACAC-1-1,X=CX,b=C,X=CX,b=C-1-1b,Cb,C 为对称正定矩阵为对称正定矩阵) ) 令令 X XK K=CX=CXK K,r,rK K=Cr=CrK K,P,Pk k=CP=CPk k,M=C,M=C2 2. . 好的好的预优矩阵预优矩阵 M M：对称正定；稀疏；：对称正定；稀疏；M M
9、-1-1A A 仅有少数几个特征值；仅有少数几个特征值；Mz=rMz=r 易解。易解。选取：选取： IFIF A A 对角元相差很大，取对角元相差很大，取 M=diag(aM=diag(a1111aannnn) )推广推广 M=diag(AM=diag(A1111AAnnnn) )华中科技大学学习笔记系列 作者：centre -穷则投资自己，达则投资天下-不完全不完全 CholeskyCholesky 因子预优阵：因子预优阵：A=LL+R,A=LL+R,令令 M=LLM=LL 多项式预优阵：多项式预优阵：Mz=rMz=r 看作看作 Az=rAz=r 的近似，利用古典迭代法可取的近似，利用古典迭
10、代法可取 M M- -1 1=(I+G=(I+GP-1P-1)M)M1 1-1-1 21 21 非线性方程组的解法：非线性方程组的解法：F-F-导数导数( (强强) )，G-G-导数导数( (弱弱) )，F=d(fF=d(f1 1ffn n)/d(x)/d(x1 1xxn n) ) gradgrad F=(F)F=(F)T T. .性质：线性性，链式法则，中值公式，性质：线性性，链式法则，中值公式，Newton-LeibnizNewton-Leibniz 公式，公式， ，TaylorTaylor 定定 理理 BanachBanach 压缩映照原理压缩映照原理：闭集：闭集 D D0 0上的压缩映
11、射；上的压缩映射；F(DF(D0 0) ) D D0 0, ,则则 F F 在在 D D0 0有唯有唯 一不动点一不动点 PicardPicard 迭代法迭代法：(X),|(X)|(X),|(X)|2 21;detI-(X)1;detI-(X)T T(X)(X) =0,|(X)|=0,|(X)|2 2=sqrt(max=sqrt(maxi i)1)1 加速收敛技术加速收敛技术：X,(XX,(Xk k);P=(X);P=(Xk k);X);Xk+1k+1=(I-P)=(I-P)-1-1(X(Xk k)-PX)-PXk k AitkenAitken 加速迭代法加速迭代法：XXk+1k+1=(X=(
12、Xk k);X);Xk+1k+1=(X=(Xk+1k+1);X);Xk+1k+1=X=Xk+1k+1-(X-(Xk+1k+1-X-Xk+1k+1) )2 2 /(X/(Xk+1k+1-2X-2Xk+1k+1+X+Xk k) ) NewtonNewton 迭代法迭代法：X,F(X);XX,F(X);Xk+1k+1=X=Xk k-F(X-F(XK K)-1-1F(XF(XK K) )或或 X Xk k-F(X-F(X0 0)-1-1F(XF(XK K) ) NewtonNewton 下山法下山法：X Xk+1k+1=X=Xk k-F(X-F(XK K)-1-1F(XF(XK K) ) 【=(1/2)【=(1/2)k k】
