§4、解线性方程组的迭代法 ·迭代法概述 雅可比( Jacobi)迭代法 高斯一塞德尔( Gauss- Seidel)迭代法 ·松弛法 迭代法的收敛条件 误差估计
§4 、解线性方程组的迭代法 • 迭代法概述 • 雅可比(Jacobi)迭代法 • 高斯—塞德尔（Gauss-Seidel)迭代法 • 松弛法 • 迭代法的收敛条件 • 误差估计
迭代法概述 迭代法的基本思想是构造一串收敛到解的 序列,即建立一种从已有近似解计算新的近似 解的规则。由不同的计算规则得到不同的迭代 法,本章介绍单步定常线性迭代法 直接法比较适用于中小型方程组。对高阶方 程组,既使系数矩阵是稀疏的,但在运算中很难 保持稀疏性,因而有存储量大,程序复杂等不足. 迭代法则能保持矩阵的稀疏性,具有计算简 单,编制程序容易的优点,并在许多情况下收敛 较快。故能有效地解一些高阶方程组
一.迭代法概述 迭代法的基本思想是构造一串收敛到解的 序列，即建立一种从已有近似解计算新的近似 解的规则。由不同的计算规则得到不同的迭代 法，本章介绍单步定常线性迭代法。 直接法比较适用于中小型方程组。对高阶方 程组，既使系数矩阵是稀疏的，但在运算中很难 保持稀疏性，因而有存储量大，程序复杂等不足. 迭代法则能保持矩阵的稀疏性，具有计算简 单，编制程序容易的优点，并在许多情况下收敛 较快。故能有效地解一些高阶方程组
对线性方程组Ax=b 其中A=(an)非奇异矩阵,b=(b1…,bn) 构造其形如x=Mx+g 的同解方程组,其中M为n阶价方阵,g∈R"。 任取初始向量x∈R",代入迭代公式 (k+1) Mx6)+g(k=0,1,2,…) 生向量序列{x()},当k充分大时,以x)作为 方程组Ax=b的近似解,这就是求解线性方程组 的单步定常线性迭代法。M称为迭代矩阵
1 (0) ( 1) ( ) ( ) ( ) ( ) ( , , ) , (k=0,1,2, ) { } T ij n n n n n k k k k Ax b A a b b b x Mx g M n g R x R x Mx g x k x Ax b 对线性方程组 其中 非奇异矩阵， 构造其形如 的同解方程组，其中 为 阶方阵， 。 任取初始向量 代入迭代公式 产生向量序列 ，当 充分大时，以 作为 方程组 的近似解，这就是求解线 M 性方程组 的单步定常线性迭代法。 称为迭代矩阵
定义:设{x)}为R中的向量序列,x∈R,如果 m =0 k 其中·‖为向量范数,则称序列x收敛于x,记为 (k) mx X 定理:R中的向量序列x收敛于R中的向量x当且仅当 imx3=x(i=1,2,…,m) k->oo 其中x6)=(x18,x2)…x6),x=(x12x2…,xn)
( ) ( ) ( ) ( ) ( ) ( { } lim 0 { } lim { } lim k n n k k k k k n k n i k x R x R x x x x x x R x R x x ：设 为 中的向量序列， ，如果 其中 为向量范数，则称序列 收敛于 ，记为 ： 中的向量序列 收敛于 中的向量 当且仅当 定义 定理 ) ( ) ( ) ( ) ( ) 1 2 1 2 ( 1,2, , ) ( , , , ) , ( , , , ) k i k k k k T T n n x i n x x x x x x x x 其中
证:由定义x收敛于想m-=0 而对任意≤i≤n,有 (k (k) x:≤max 1≤j≤n 由极限存在准则得 imx=x|=0(=12…;n) →0 imx3=x(i=1,2;…,m)
( ) ( ) ( ) ( ) ( ) 1 ( ) { } lim 0 1 0 max lim =0 ( 1,2, , ) lim k k k k k k i i j j j n k i i k k x x x x i n x x x x x x x x i n x 证：由定义， 收敛于 即 而对任意 ，有 由极限存在准则得 即 ( ) ( 1,2, , ) k i i x i n
定义:设{A4为阶介方阵序列,A为阶方阵,如果 limn‖4)-A‖=0 其中·为矩阵范数,则称序列4收敛于矩阵4,记为 lim ak)=a k →0 定理:设{4)}=(a6)(k=1,2,…,A=(an)均为阶方阵 则矩阵序列A收敛于矩阵拍充要条件为 k) (i,=1,2,…,n) 证明略
( ) ( ) ( ) ( ) ( ) ( ) ( ) { } lim 0 { } lim { } ( )( 1,2, ), ( { } k k k k k k k k ij ij k A n A n A A A A A A A a k A a n A A 定义：设 为 阶方阵序列， 为 阶方阵，如果 其中 为矩阵范数，则称序列 收敛于矩阵 ，记为 定理：设 )均为 阶方阵， 则矩阵序列 收敛于矩阵 的充 ( ) lim ( , 1,2, , ) k ij ij k a a i j n 要条件为 证明略
定理表明,向量序列和矩阵序列的收敛可以归结为 对应分量或对应元素序列的收敛。 若按x)=Mx)+g产生的向量序列{x)}收敛于向 量x,则有 x=limx(k+D=lim[Mx()+8]=Mx+g k→>∞ →0 即x是方程组Ax=b的解
( 1) ( ) ( ) ( 1) ( ) { } , lim lim[ ] k k k k k k k x Mx g x x x x Mx g Mx g x Ax b 定理表明，向量序列和矩阵序列的收敛可以归结为 对应分量或对应元素序列的收敛。 若按 产生的向量序列 收敛于向 量 则有 即 是方程组 的解
二.雅可比( Jacobi)迭代法 aux tax,+.+ax=b C2.X1+a2X2 b anx+anx2+…+amxn=b 若系数矩阵非奇异即a。≠0(1=1.2,…,n)则有
二.雅可比(Jacobi)迭代法 11 1 12 2 1n 1 21 1 22 2 2n 2 n1 1 n1 2 nn n n n n a x a x a x b a x a x a x b a x a x a x b 0 ( 1,2, , ), ii 若系数矩阵非奇异即 a i n 则有
0 12 b X a a a 21 0 b X X 22 a 2 a a a X 0+ b nn nn X1 bux,+b b b,ix b +b x=6x+6mn2x2+5m3x3+.+ g 其中b (i≠j,ij=1
12 13 1 1 1 2 3 11 11 11 11 21 23 2 2 2 1 3 22 22 22 22 1 2 n 1 2 0 - 0 n n n n n n nn nn a a a b x x x x a a a a a a a b x x x x a a a a a a x x x a a 3 3 1 12 2 13 3 1 1 2 21 1 23 3 2 2 n 1 0 n n nn nn n n n n n a b x a a x b x b x b x g x b x b x b x g x 1 2 2 3 3 , ( , , 1, 2, , ), ( 1, 2, , ). n n n ij i ij i ii ii a b b i j i j n g i n a a b x b x b x g 其 中
0 6 6 b.,b, 12 13 b 0 6 b 若记B n 6. 6 b 2 nn 则方程组可简记为x=Bx+g 选初值向量x0代入→x),x)=Bx0+g,代入x0) → 如此继续下去,就产生一个向量序列{x6)} 满足x6+1)=Bx6)+g(k=0,1,2,… 此过程所给出的迭代法称为lcbi迭代法,又称简单 迭代法
12 13 1 1 1 1 21 23 2 1 2 2 1 2 3 1 (0) (1) 1 0 (1) (2) ( ) ( 1) 0 0 0 , { } n n n n n n n nn n k k b b b b g b b b b g B g b b b b g x Bx g x x x Bx g x x x x Bx （ ） （ ） 若记 则方程组可简记为 选初值向量 代入 ，代入 ，如此继续下去，就产生一个向量序列 满足 ( ) ( 0,1,2, ) k g k Jacobi 此过程所给出的迭代法称为 迭代法，又称简单 迭代法