比较A=LDL的两边, function [L, D= cholesky(a 记z 得到关系 for i=2. n (i1)=a(i1)d(1); end 2:n,i=j+1:n forj=2:n 12.d for k=1:1-1 t=t+a(j,k)^2*a(k,k); end a(2j)=a(,j)-t for +1 MATLAB命令:L=chol( t=0 说明:A=LL,L为上三角矩阵 for k=1: j-1 t+a(k, k)a(ik)a(, k) 运算量:乘除_(m3+9n2+2n) a(ij=(a(1j-t/aG,j; 当n很大时,相当于-n,是 end 6 高斯消去法的一半
= − = − = = + = = = = − = − = j j k i j i j k i k j k j k j j j j k k i i T l a d l l d d a l d d a l a d i n A LDL ( )/ j 2 : n, i j 1: n , / , 2 : 1 1 1 1 2 1 11 1 1 1 得到关系： 比较 的两边， end end a(i, j) (a(i, j) - t)/a(j, j); end t t a(k, k)*a(i, k)*a(j, k); for k 1: j-1 t 0; for i j 1: n a(j, j) a(j, j) - t; end t t ( , )^2* ( , ); for k 1: j-1 t 0; for j 2 : n end a(i,1) a(i,1)/d(1 ); for i 2 : n [m, n] size(a); [L, D] cholesky(a ) = = + = = = + = = + = = = = = = = a j k a k k function 高斯消去法的一半。 当 很大时，相当于 ，是 运算量：乘除 说明： 为上三角矩阵 命令： 3 3 2 6 1 ( 9 2 ) 6 1 ,L ( ) n n n n n A L L MATLAB L chol A T + + = =
三、线性代数方程组的迭代法 线性代数方程组的迭代法并不适用于所有问题,但它对 些特定类型的问题非常有效。当问题是大型稀疏矩阵方程 时,高斯消去法的效率会变得非常低,而且有时还会超出内 存要求。对于这样的问题就需要使用迭代法。 大系统问题的求解最终归结为大型稀疏矩阵方程。比如, 电网络、场方程的数值计算、运筹问题等 尽管迭代法的种类很多,这里只介绍其中的三种: 1、 Jacobi迭代; 2、 Gauss-Seidel迭代; 3、超松弛迭代法(SOR)
三、线性代数方程组的迭代法 线性代数方程组的迭代法并不适用于所有问题，但它对 一些特定类型的问题非常有效。当问题是大型稀疏矩阵方程 时，高斯消去法的效率会变得非常低，而且有时还会超出内 存要求。对于这样的问题就需要使用迭代法。 大系统问题的求解最终归结为大型稀疏矩阵方程。比如， 电网络、场方程的数值计算、运筹问题等。 尽管迭代法的种类很多，这里只介绍其中的三种： 1、Jacobi迭代； 2、Gauss-Seidel迭代; 3、超松弛迭代法（SOR)
1、线性代数方程组的迭代法的一般理论 Ax=b冷x=Bx+d 算法: 1、选定初始值:x0)∈Rn 2、迭代:x(k+1)=Bx()+d,k=012,… 3、收敛条件x()-x≤E 其中ⅹ*为方程组的真解,ε为近似解xk)的精度. 迭代算法简单,但问题是: 能否保证算法收敛? 2、能否充分利用矩阵的稀疏性,使运算量和存贮 量尽量少
x . 3 , 2 , 0,1,2, ; 1 ; * ( ) ( ) * ( 1) ( ) (0) 其中 为方程组的真解， 为近似解 的精度 、收敛条件： 、迭代： 、选定初始值： 算法： k k k k n x x x x Bx d k x R Ax b x Bx d − = + = = = + + 1、线性代数方程组的迭代法的一般理论 迭代算法简单，但问题是： 1、能否保证算法收敛？ 2、能否充分利用矩阵的稀疏性，使运算量和存贮 量尽量少
收敛性定理 对于任意的初值x(0)∈Rn 定理一]迭代法收敛的充分必要条件是mB=0 [定理一]迭代法收敛的充分必要条件是P(B)<1 [定理三]迭代法收敛的充分条件是 k B<1,且|×)-x<,一‖ x(0) G G 和 X(-x‖< x(k)-x(k-1) B=max∑b列和范数:|B=max∑行和范数 |B2=√m(B)谱范数
[定理一] 迭代法收敛的充分必要条件是 lim 0 1 = = k k B [定理二] 迭代法收敛的充分必要条件是 (B) 1 [定理三] 迭代法收敛的充分条件是 (k) * ( ) ( 1) (k) * (0) 1 x * 1 1, x − − − − − − − k k k x x G G x x x G G B x 和 且 谱范数 列和范数 行和范数 B ( ) max ; max 2 1 1 1 1 1 T n j i j i n n i i j j n BB B b B b = = = = = 收敛性定理 对于任意的初值 Rn x (0)
迭代矩阵B的构造 充分利用矩阵的稀疏性,使运算量和存贮量尽量少的办 法就是要求迭代矩阵B与原矩阵A有相同的稀疏结构。具体就 是: A=D-L-U,D=diag(a ll,a22,,,,, an) 0a12 a a 21 a n-1,n a 0 Ax=b(D-L-u)x=b
迭代矩阵B的构造 充分利用矩阵的稀疏性，使运算量和存贮量尽量少的办 法就是要求迭代矩阵B与原矩阵A有相同的稀疏结构。具体就 是： = − = − = − − = 0 a 0 0 a a , U a a 0 a 0 0 L A D L U, D diag(a ,a , ,a ); n-1 ,n 1 2 1 n n 1 n n-1 2 1 1 1 2 2 n n Ax = b (D − L −U)x = b