电子科技大学：《数值分析 Numerical Analysis》课程教学资源（课件讲稿）迭代法初步

迭代法初步 Jacob i迭代法 Seidel迭代法 迭代法的矩阵表示 1/15

1/15 Jacobi迭代法 Seidel迭代法 迭代法的矩阵表示

迭代法的基本概念 设方程组A比=有唯一解x*,将Ax=f变形为等价 的方程组 x=Bx+f 由此建立迭代公式 xk+0=Bx)+f(k=0,1,2,…） 给定初始向量x,按此公式计算的近似解向量序列 {x},称此方法为迭代法 若Iimx)=x,显然有x*=Bx*+f k→00 则称迭代法是收敛的，否则称为发散的。迭代格式中 的矩阵B称为迭代矩阵。 2/15

2/15 显然有x* = B x* + f 则称迭代法是收敛的，否则称为发散的。迭代格式中 的矩阵B称为迭代矩阵。 ( ) * lim , k k x x  若  设方程组Ax = f有唯一解x* ，将Ax = f 变形为等价 的方程组 x = B x + f 由此建立迭代公式 给定初始向量 ，按此公式计算的近似解向量序列 { }，称此方法为迭代法 ( 1) ( ) ( 0,1, 2, ) k k x Bx f k      (0) x (k ) x 迭代法的基本概念

例4.1 9x1-x2-x3=7 -x1+10x2-x3=8 特点：系数矩阵主 对角元均不为零 -x1-x2+15x3=13 x1=(7+x2+x3)/9 0 x2=(8+x1+x3)/10 取X0) 0 x3=(13+x1+x2)/15 0 计算格式X)=BX0)+f 1/9 1/9 719 1/10 1/10 8/10 1/151/15 13/15 3/15

3/15                15 13 10 8 9 7 1 2 3 1 2 3 1 2 3 x x x x x x x x x 例4.1 特点:系数矩阵主 对角元均不为零                           13 /15 8 /10 7 / 9 1/15 1/15 0 1/10 0 1/10 0 1/ 9 1/ 9 (0) 3 (0) 2 (0) 1 (1) 3 (1) 2 (1) 1 x x x x x x 计算格式 X(1)=B X(0) + f               (13 )/ 15 (8 )/ 10 (7 )/ 9 3 1 2 2 1 3 1 2 3 x x x x x x x x x 取 X(0) =       0 0 0

计算格式：X+)=BX+f X0) X1) X2) X3) X4) 0 0.7778 0.9630 0.9929 0.9987 0 0.8000 0.9644 0.99350.9988 0 0.8667 0.9778 0.9952 0.9991 X 1.0000 准确解 1.0000 1.0000 4/15

4/15 X* 1.0000 1.0000 1.0000 X(0) 0 0 0 X(1) 0.7778 0.8000 0.8667 X(2) 0.9630 0.9644 0.9778 X(3) 0.9929 0.9935 0.9952 计算格式: X(k+1)=BX(k)+f 准确解  X(4) ······ 0.9987 0.9988 0.9991

雅可比迭代法 41ux1+412X2++41mxn=b1 2X1+022X2++2mXm=b2 ∑a,x,=b amx1+an2X2++amnxn bn =12m =4-之，9-4,1 i=i+1 (i=1,2,…n;k=1,2,…） 取初始向量X0=x,0x20)·xn7,迭代计算 5/15

5/15                  n n nn n n 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     1 1 2 2 21 1 22 2 2 2 11 1 12 2 1 1 雅可比迭代法 (i = 1,2,…n; k=1,2,……) 取初始向量X(0)=[x1 (0) x2 (0) ··· xn (0)]T , 迭代计算           n j i k ij j i j k i ij j ii k i b a x a x a x 1 ( ) 1 1 ( 1) ( ) [ ] 1 i n j ij j a x  b 1 (i = 1,2,…,n)

迭代法适用于解大型稀疏方程组 (万阶以上的方程组，系数矩阵中零元素占很大比例 而非零元按某种模式分布) 背景：电路分析、边值问题的数值解和数学物理方 程 0 问题：(1)如何构造迭代格式？ (2)迭代格式是否收敛？ 10 (3)收敛速度如何？ 12 14 (4)如何进行误差估计？ 16 18 0 5 10 15 6/15

6/15 迭代法适用于解大型稀疏方程组 (万阶以上的方程组,系数矩阵中零元素占很大比例, 而非零元按某种模式分布) 背景: 电路分析、边值问题的数值解和数学物理方 程 问题: (1)如何构造迭代格式？ (2)迭代格式是否收敛？ (3)收敛速度如何？ (4)如何进行误差估计？

高斯一赛德尔迭代法 ∑agx)=6=12m i=1 -.4-ay-立，1 i=i+1 (i=1,2,.n;k=1,2,…) 取初始向量x0=x10)x20)…xn7,迭代计算 7/15

7/15 i n j ij j a x  b 1 (i = 1,2,…,n) 高斯-赛德尔迭代法            n j i k ij j i j k i ij j ii k i b a x a x a x 1 ( ) 1 1 ( 1) ( 1) [ ] 1 (i = 1,2,…n; k =1,2,……) 取初始向量x(0)=[x1 (0) x2 (0) ··· xn (0)]T , 迭代计算

例 9x1-X2-X3=7 x1=(7+x2+x3)/9 -x1+10x2-x3=8 x2=(8+x+x3)/10 -x1-x2+15x3=13 x3=(13+x1+x2)/15 x+”=(7++x)/9 0 x+D=(8+x+”+xg)/10 二 0 xg+”=(13+x+)+x+)/15 0 0 0 k+1) 1/9 1/9 7/9 -1/10 1 0 1/10 + 8/10 -1/15-1/151 0 13/15 8/15

8/15 例                15 13 10 8 9 7 1 2 3 1 2 3 1 2 3 x x x x x x x x x (13 )/ 15 ( 1) 2 ( 1) 1 ( 1) 3       k k k x x x                                      13 / 15 8 / 10 7 / 9 0 0 0 0 0 1/ 10 0 1/ 9 1/ 9 1/ 15 1/ 15 1 1/ 10 1 0 1 0 0 ( ) 3 ( ) 2 ( ) 1 ( 1) 3 ( 1) 2 ( 1) 1 k k k k k k x x x x x x (7 )/ 9 ( ) 3 ( ) 2 ( 1) 1 k k k x   x  x  (8 )/ 10 ( ) 3 ( 1) 1 ( 1) 2 k k k x   x  x                 (13 )/ 15 (8 )/ 10 (7 )/ 9 3 1 2 2 1 3 1 2 3 x x x x x x x x x              0 0 0 (0) 3 (0) 2 (0) 1 x x x

import numpy as np 雅可比迭代算法 A=np.array(l9,-1,-1],-1,10,-1], -1,-1,15]) B=np.array([7,8,13]) 9x1-x2-x3=7 x0=np.array(0.0,0,0]） x np.array([0.0,0,0]) -x1+10x2-x3=8 k=0 while True: -x1-x2+15x3=13 for i in range(③)： temp 0 0.7778 0.8000 0.8667 tempx =x0.copy( 0.9630 0.9644 0.9719 for j in range(3): ifil=j: 0.9929 0.9935 0.9952 temp +xo[j]A[illjl x[i]=(B[i]-temp/Al时 0.9987 0.9988 0.9991 er max(abs(x -x0)) k+=1 0.9998 0.9998 0.9998 ifer <le-4: break 1.0000 1.0000 1.0000 else: 1.0000 1.0000 1.0000 x0=x.copy() print(k,x) 9/15

9/15                15 13 10 8 9 7 1 2 3 1 2 3 1 2 3 x x x x x x x x x import numpy as np A = np.array([[9, -1, -1], [-1, 10, -1], [-1, -1, 15]]) B = np.array([7, 8, 13]) x0 = np.array([0.0, 0, 0]) x = np.array([0.0, 0, 0]) k = 0 while True: for i in range(3): temp = 0 tempx = x0.copy() for j in range(3): if i != j: temp += x0[j] * A[i][j] x[i] = (B[i] - temp) / A[i][i] er = max(abs(x - x0)) k += 1 if er < 1e-4: break else: x0 = x.copy() print(k,x) 雅可比迭代算法 0.7778 0.8000 0.8667 0.9630 0.9644 0.9719 0.9929 0.9935 0.9952 0.9987 0.9988 0.9991 0.9998 0.9998 0.9998 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000

import numpy as np 高斯一赛德尔迭代算法 A=np.array(l9,-1,-1],-1,10,-1], -1,-1,15]) B np.array([7,8,13]) 9x1-x2-X3=7 x0=np.array(0.0,0,0) x np.array([0.0,0,0]) -x1+10x2-x3=8 k=0 while True: -x1-x2+15x3=13 for i in range(③)： temp 0 0.7778 0.8778 0.9770 tempx =x0.copy() for j in range(3): 0.9839 0.9961 0.9987 ifil=j: temp +x[jl A[illj] 0.9994 0.9998 0.9999 x[i](B[i]temp)/A[i]li] er max(abs(x -x0)) 1.0000 1.0000 1.0000 k+=1 ifer le-4: 1.0000 1.0000 1.0000 break else: x0=x.copy() print(k,x) 10/15

10/15 高斯-赛德尔迭代算法                15 13 10 8 9 7 1 2 3 1 2 3 1 2 3 x x x x x x x x x import numpy as np A = np.array([[9, -1, -1], [-1, 10, -1], [-1, -1, 15]]) B = np.array([7, 8, 13]) x0 = np.array([0.0, 0, 0]) x = np.array([0.0, 0, 0]) k = 0 while True: for i in range(3): temp = 0 tempx = x0.copy() for j in range(3): if i != j: temp += x[j] * A[i][j] x[i] = (B[i] - temp) / A[i][i] er = max(abs(x - x0)) k += 1 if er < 1e-4: break else: x0 = x.copy() print(k,x) 0.7778 0.8778 0.9770 0.9839 0.9961 0.9987 0.9994 0.9998 0.9999 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000