第二章、解线性方程组的迭代法 直接法:经过有限次运算后可求得方程组精确解的方 法(不计舍入误差!) 迭代法:从解的某个近似值出发,通过构造一个无穷序 列去逼近精确解的方法。(一般有限步内得不到精确解) 直接法比较适用于中小型方程组。对高阶方程组, 既使系数矩阵是稀疏的,但在运算中很难保持稀疏性, 因而有存储量大,程序复杂等不足 迭代法则能保持矩阵的稀疏性,具有计算简单,编 制程序容易的优点,并在许多情况下收敛较快。故能有 效地解一些高阶方程组
第二章、解线性方程组的迭代法 直接法: 经过有限次运算后可求得方程组精确解的方 法(不计舍入误差!) 迭代法：从解的某个近似值出发，通过构造一个无穷序 列去逼近精确解的方法。（一般有限步内得不到精确解） 直接法比较适用于中小型方程组。对高阶方程组， 既使系数矩阵是稀疏的，但在运算中很难保持稀疏性， 因而有存储量大，程序复杂等不足。 迭代法则能保持矩阵的稀疏性，具有计算简单，编 制程序容易的优点，并在许多情况下收敛较快。故能有 效地解一些高阶方程组
§1.迭代法概述 迭代法的基本思想是构造一串收敛到解的序列,即建立一种 从已有近似解计算新的近似解的规则。由不同的计算规则得到不 同的迭代法,本章介绍单步定常线性迭代法 对线性方程组Ax=b 其中A=(an)nx非奇异矩阵,b=(b1,…,bn) 构造其形如x=Mx+g 的同解方程组,其中M为n阶方阵 R 任取初始向量x()∈R",代入迭代公式 (k+1) M (k) +g(k=0,1,2, 生向量序列{x()},当k充分大时,以x()作为 方程组Ax=b的近似解,这就是求解线性方程组 的单步定常线性迭代法。M称为迭代矩阵
§1.迭代法概述 迭代法的基本思想是构造一串收敛到解的序列，即建立一种 从已有近似解计算新的近似解的规则。由不同的计算规则得到不 同的迭代法，本章介绍单步定常线性迭代法。 1 ( 0 ) ( 1 ) ( ) ( ) ( ) ( ) ( , , ) , (k = 0 ,1 ,2 , ) { } T ij n n n n n k k k k A x b A a b b b x M x g M n g R x R x M x g x k x A x b 对 线 性 方 程 组 其 中 非 奇 异 矩 阵 ， 构 造 其 形 如 的 同 解 方 程 组 ， 其 中 为 阶 方 阵 ， 。 任 取 初 始 向 量 代 入 迭 代 公 式 产 生 向 量 序 列 ， 当 充 分 大 时 ， 以 作 为 方 程 组 的 近 似 解 ， 这 就 是 求 解 线 M 性 方 程 组 的 单 步 定 常 线 性 迭 代 法 。 称 为 迭 代 矩 阵
定义:设{x)}为R中的向量序列,x∈R",如果 mIx k→∞ 其中‖·为向量范数,则称序列{x)收敛于x,记为 m x k→∞ 定理:R中的向量序列{x6)收敛于R中的向量x当且仅当 Im (k 其中x()=( 证:由定义x收敛于难即1im1)-x1=0 而对任意1≤1≤m,有05x)-x5max1x0)-x=1x)-x 由极限存在准则得 lim xg-x=0 m x
( ) ( ) ( ) ( ) ( ) ( { } 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 ( ) ( 1, 2, , ) ( , , , ) , ( , , , ) { } lim 0 1 0 max lim =0 ( 1, 2, , ) k i k k k k T T n n k k k k k k i i j j j n k i i k x i n x x x x x x x x x x x x i n x x x x x x x x i n 其中 。 证：由定义， 收敛于 即 而对任意 ，有 由极限存在准则得 即 ( ) lim ( 1, 2, , ) k i i k x x i n
定义:设{A(}为n阶方阵序列,A为n阶方阵,如果 lim a 0 k→)∞ 其中|·为矩阵范数,则称序列{4}收敛于矩阵A,记为 lim A(k)=a k→∞ 定理:设{A)}=(a()(k=1,2,…),A=(an)均为n阶方阵, 则矩阵序列{4(}收敛于矩阵A的充要条件为 k) (i,j=1,2,…,n) k→∞ 证明略。 定理表明,向量序列和矩阵序列的收敛可以归结为对应 分量或对应元素序列的收敛 若按x)=Mx+g产生的向量序列{x}收敛于向量x, 则有x=1imx+)=lim[Mx)+g]=Mx+g k→)∝ 即x是方程组Ax=b的解
( ) ( ) ( ) ( ) ( ) ( ) ( ) { } 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 定 义 ： 设 为 阶 方 阵 序 列 ， 为 阶 方 阵 ， 如 果 其 中 为 矩 阵 范 数 ， 则 称 序 列 收 敛 于 矩 阵 ， 记 为 定 理 ： 设 )均 为 阶 方 阵 ， 则 矩 阵 序 列 收 敛 于 矩 阵 的 充 ( ) ( 1) ( ) ( ) ( 1) ( ) lim ( , 1, 2, , ) { } , lim lim[ ] k ij ij k k k k k k k k a a i j n x M x g x x x x M x g M x g x A 要 条 件 为 证 明 略 。 定 理 表 明 ， 向 量 序 列 和 矩 阵 序 列 的 收 敛 可 以 归 结 为 对 应 分 量 或 对 应 元 素 序 列 的 收 敛 。 若 按 产 生 的 向 量 序 列 收 敛 于 向 量 则 有 即 是 方 程 组 x b的 解
§2.雅可比( Jacobi)迭代法 aux1taux ain b a2x1+a2X2+…+a2nxn=b x2+…+amxn=b 若系数矩阵非奇异即a≠0(=1,2,…,n),则有 62x2+b13x3++bmxn+g baix b b t o bx,+b.,+ bax 其中b (i≠j,i,j=1,2,…,n) b
§2.雅可比(Jacobi)迭代法 11 1 12 2 1n 1 21 1 22 2 2n 2 n1 1 n1 2 nn 0 ( 1, 2, , ), n n n n ii i n a x a x a x b a x a x a x b a x a x a x b a 若 系 数 矩 阵 非 奇 异 即 则 有 1 12 2 13 3 1 1 2 21 1 23 3 2 2 n 1 1 2 2 3 3 n n n n n n n n x b x b x b x g x b x b x b x g x b x b x b x ,( , , 1, 2, , ), ( 1, 2, , ). ij i ij i ii ii a b b i j i j n g i n a a g 其中
0 b 6 b g1 bo b b 若记B g2 g 66 b nn 方程组可简记为x=Bx+g 选初值向量x代入→x0),x1)=Bx0+g,代入x →x2)…,如此继续下去,就产生一个向量序列{x} 满足x+)=Bx6)+g(k=0,1,2,…) 此过程所给出的迭代法称为 Jacobi迭代法,又称简单 迭代法
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 此过程所给出的迭代法称为 迭代法，又称简单 迭代法
矩阵简化记法 0b2…b 0 0)(1-b2 b1 b20 b,0 0|-b21 b B (bm, b 6-6 C11 C1112 aIn a22 C21a22 a2n 1-DA am八 anl an2 同样 8=(8128 g =(b1/a1,b2/a22,…,bn/an)=Db
矩阵简化记法 1 1 1 0 0 1 0 1 0 1 0 0 0 0 0 1 2 21 2 12 1 1 2 21 2 12 1 b b b b b b b b b b b b n n n n n n n n B I- D A a a a a a a a a a a a a I nn 1 n1 n2 nn 21 22 2n 11 12 1n 1 1 22 1 11 1 1 2 1 1 1 2 2 2 ( , , , ) ( , , , ) T T n n n n g g g g b a b a b a D b 同 样
收敛与解 Jacobi迭代x (n+1) Bx+gn=O,1,2,… 若收敛 Ck x}->x 则 Br+ 即(-B)x=g,B=Ⅰ-DA,g=Db →DAx=Db →Ax=b 故如果序列收敛,则收敛到解.B称迭代矩阵
收敛与解 1 * * * n 0 1 2 { } B g n n k Jacobi x Bx g x x x x （ ） （ ） （ ） 迭代 ，，， 若收敛 ，则 * 1 1 1 * 1 * (I B)x g, B I D A, g D b D Ax D b Ax b 即 故如果序列收敛, 则收敛到解.B 称迭代矩阵
10 2x2=72 例:用lcob迭代法求解{-x+10x2-2x=83 5x3=42 解:B=Ⅰ-DA 00 100 10 10-1-200.102 010-0 01-110-2|=0.1002 1-1 0.20.20 00 g=Db=(72,8.3,8 取x0)=(0,0,0,代入选代式,得x=Bx0+g=(72,8384) x2)=Bx+g=(9,710.70,115)2…x)=(10.99941199912.999) 精确解为x=(111,13)3
1 2 3 1 2 3 1 2 3 1 10 2 72 10 2 83 5 42 1 0 0 10 1 0 0 10 1 2 0 0.1 0.2 1 0 1 0 0 0 1 10 2 0.1 0 0.2 10 0 0 1 1 1 5 0.2 0.2 0 1 0 0 5 x x x Jacobi x x x x x x B I D A 例：用 迭代法求解 解： 1 (0) (0) (2) (1) (9) (7.2,8.3,8.4) (0,0,0) , (7.2,8.3,8.4) (9.71,10.70,11.5) (10.9994,11.9994,12.9992) (11,12,13) . T T T T T g D b x Bx g x Bx g x x 取 代入迭代式，得 (1) x 精确解为
Jacobi迭代法的计算过程如下: 1输入4=(an)b=(;…,b),维数n,x0=(x0),x),…,) E,最大容许迭代次数N 2置k=1 3对=12…nx=(b∑anx0)/ J≠ 4若x-x0<E,输出x,停机;否则转5 5若k<N,置k+1→k,x→x(i=1,2…,m),转3; 否则,输出失败信息,停机。 评价:公式简单,每迭代一次只需计算一次矩阵和向量 的乘法,不改变M的稀疏性,需两组工作单元,存x),x+1
Jacobi迭代法的计算过程如下： (0) (0) (0) (0) 1 1 2 (0) 1 (0) (0) 1. ( ), ( , , ), , ( , , , ), , . 2. 1. 3. 1,2, , ( )/ 4. , , 5 5. , 1 , ( 1,2, , ), 3 ij n n n i i ij j ii j j i i i A a b b b n x x x x N k i n x b a x a x x x k N k k x x i n 输入 维数 最大容许迭代次数 置 对 若 输出 停机；否则转 。 若 置 转 ； 否则，输出失败信息，停机。 ( ) ( 1 , k k M x x ） 评价：公式简单，每迭代一次只需计算一次矩阵和向量 的乘法，不改变 的稀疏性，需两组工作单元，存