吉林大学：《计算方法》课程电子教案（PPT课件）第五章 解线性代数方程组的迭代法 5.1 Jacobi迭代法

第一节Jacobi 迭代法 一、引言 二、 迭代格式的构造 三、Jacobi迭代法的收敛性 四、小结

第一节 Jacobi 迭代法 三 、 Jacobi 迭代法的收敛性 一、引言 二、 迭代格式的构造 四、小结

一、引言 迭代法是解线性代数方程组的另二类重要方法，特别 适于求解系数矩阵为稀疏阵的大型线性代数方程组。它的 基本思想是，从任一初始向量X,出发，按某一规则，逐 次构造一个向量序列{X},当X收敛于X时，使X 是所给方程组的解。于是，就有下列问题需要计论： (1)构造迭代格式； (2)收敛性及误差估计

  ( ) k X 迭代法是解线性代数方程组的另一类重要方法，特别 适于求解系数矩阵为稀疏阵的大型线性代数方程组。它的 基本思想是，从任一初始向量 出发，按某一规则，逐 次构造一个向量序列 ，当 收敛于 时，使 是所给方程组的解。于是，就有下列问题需要计论： (0) X ( ) k X * X * X (1) 构造迭代格式； (2) 收敛性及误差估计。 一、引言

二、迭代格式的构造 设所给方程组为 X=BX+F (1.1) 其中，B是n阶方阵，F是已知身量，X是未知向量。 任取X0∈R”代入(1.1)的右端，算得的结果记为 X0,再以XD代入(1.1)的右端，算得的结果记为x2, 如此进行下去，便得到迭代格式

任取 代入（1.1）的右端，算得的结果记为 ，再以 代入（1.1）的右端，算得的结果记为 ， 如此进行下去，便得到迭代格式 (0) n X R  (1) X (1) X (2) X 其中， B 是 n 阶方阵， F 是已知身量, X 是未知向量。 二、 迭代格式的构造 X BX F = + 设所给方程组为 （1.1）

Xk+=BX)+F,k=0,I…, (1.2) 此格式称为Jacobi迭代格式，称B为迭代矩阵。 由此迭代格式可构造出一个向量序列： Xo,X1,X2,…,Xk, 显然，若mX=X”存在，则有 X'=BX'+F (1.3) 即X为(1.1)的解

( 1) ( ) , 0,1 , k k X BX F k + = + = (1.2) 显然，若 存在，则有 ( ) * lim k k X X − = * * X BX F = + (1.3) 此格式称为 Jacobi 迭代格式，称 B 为迭代矩阵。 由此迭代格式可构造出一个向量序列： 0 1 2 , , , , , X X X Xk 即 X * 为（1.1）的解

注：若方程组由下面形式给出 AX =b (1.4) 则需要把它改写成便于迭代的形式(1.1)， 其方法是多种多样的，最一般的方法是将A分 解为两个矩阵之差 A=M-N (15) 其中矩阵M可逆，于是(1.4)成为 X=MNX+Mb (1.6 令B=MN,F=Mb,即得(1.1)

1 1 B M N F M b , − − 令 = = ，即得（1.1）. 注：若方程组由下面形式给出 AX b = (1.4) 则需要把它改写成便于迭代的形式（1.1）， 其 方 法是多种多样的，最一般的方法是将 分 解为两个矩阵之差 A A M N = − (1.5) 其中矩阵M可逆，于是(1.4)成为 1 1 X M NX M b − − = + (1.6)

必须指出，(1.5)中的M应是便于求逆的，M 的最简单选择是把它选为对角阵，通常，当A的 对角线元素全不为零时，就把M选为A的对角 线，于是 A=D-E 其中D是具有A的对角线元素的对角阵，而 E在对角线上的元素为零。此时关系式(1.6成为 X=DEX+Db 式中，D是简单的对角阵，它的对角线元 素是D的元素的倒数

必须指出，(1.5)中的 应是便于求逆的， 的最简单选择是把它选为对角阵，通常，当 的 对角线元素全不为零时，就把 选为 的对角 线，于是 M M A A M A D E = −1 1 X D EX D b − − = + 其中 是具有 的对角线元素的对角阵，而 在对角线上的元素为零。此时关系式(1.6)成为 D A E 式中， 是简单的对角阵， 它的对角线元 素是 的元素的倒数。 1 D − D

例1、将方程组： 20x1+2x2+3x3=24, AX=b: x+8x2+x3=12 2x1-3x2+15x3=30 化成便于迭代的形式X=BX+F 最直观的方法是，将方程组改写为： 2 3 24 x=0x1- X一 20 x3+ 3 20 20 0 10 20 1 12 X X2= 1+0x2 d 1 1 → 0 8 8 5-43-22 3 30 X3=一 X,十 x2+0x3 X: 15 15 15 25

例1、将方程组： 1 2 3 1 2 3 1 2 3 20 2 3 24, 8 12, 2 3 15 30 x x x x x x x x x  + + =   + + =   − + = AX b = : 化成便于迭代的形式 X BX F = + . 最直观的方法是，将方程组改写为： 1 1 2 3 2 1 2 3 3 1 2 3 2 3 24 0 , 20 20 20 1 1 12 0 , 8 8 8 2 3 30 0 15 15 15 x x x x x x x x x x x x  =  − − +     = − +  − +   = − + +  +   1 1 2 2 3 3 1 3 5 0 10 20 4 1 1 3 0 8 8 2 2 1 2 0 15 5 x x x x x x     − −              = − − +                           −        

三、Jacobi迭代法的收敛性 若由迭代格式 X(k+D)=BX(k)+Fk=0,1.., (1.2 所构成的向量序列{X}收敛，则称迭代格式 (1.2)收敛，或称Jacobi迭代法收敛。 由关系式： (X(k+)=BX(k)+F, X'=BX'+F 可得 X+)-X=B(X)-X) =B2(X-)-X =Bk+(X0-X)

三 、 Jacobi 迭代法的收敛性 若由迭代格式 所构成的向量序列 收敛，则称迭代格式 (1.2)收敛，或称 迭代法收敛。   ( ) k X Jacobi ( 1) ( ) , 0,1 , k k X BX F k + = + = (1.2) 由关系式： ( 1) ( ) * * , k k X BX F X BX F +  = +   = + 可得 ( 1) * ( ) 2 ( 1) * ( 1) (0) * ( ) ( ) ( ) k k k k X X B X X B X X B X X +  − + − = − = − = −

所以，为使Jacobii迭代法收敛，即要使 X)→X 必要且只要B→0(k→o)。而B→0的 充要条件是矩阵B的谱半径P(B)<1, 故有 定理对任意右端向量F和初始向量X, 迭代格式(1.2)收敛于(1.1)的解X的充要条 件是p(B)<1 由定理1可以看出，迭代是否收敛只与迭代矩阵 的谱半径有关，而迭代矩阵B是由系数矩阵A演变过 来的，所以迭代是否收敛是与系数矩阵4以及演变的 方式有关，与右端向量和初始迭代向量的选择无关

(0) 定理 对任意右端向量F和初始向量 X ， 迭代格式(1.2)收敛于（1.1）的解 的充要条 件是 * X ( ) 1 B  所以，为使Jacobi迭代法收敛，即要使 ( ) * k X X → k →  0( ) k 必要且只要 B k → →  0 k 。而 B → 的 充要条件是矩阵B的谱半径 ( ) 1 B  ，故有 . 由定理1可以看出，迭代是否收敛只与迭代矩阵 的谱半径有关，而迭代矩阵 是由系数矩阵 演变过 来的，所以迭代是否收敛是与系数矩阵 以及演变的 方式有关，与 右 端向量和初始迭代向量的选择无关。 B A A

在具体问题中，谱半径是很难计算的， 但由于有p(B)≤B刷，所以可以用B例来作为 (B)的一种估计。当B<1时迭代格式一定收 敛，不过这只是收敛的充分条件。 定理2若<1则迭代格式(1.2)收敛于 (1.1)的解X*,且有误差估计 -x (1.7) 或 -x=K- (1.8)

在具 体问 题 中 ， 谱 半 径 是 很 难计算的， 但由于有 ，所 以可以 用 来 作 为 的 一种估计。 当 时迭代格式一定收 敛，不 过这 只是 收敛 的充分条件。 ( ) B B  B ( ) B B 1 定理 2 若 则迭代格式（1.2）收敛于 （1.1）的解 , 且有误差估计 B 1 X * ( ) * ( ) ( 1) , 1 k k k B X X X X B − −  − − （1.7） 或 ( ) * (1) (0) , 1 k k B X X X X B −  − − (1.8)