计算方法迭代法

1、第三章迭代法,3.1 二分法 3.2 迭代法原理 3.3 Newton迭代法和迭代加速 3.4 解线性方程组的迭代法,3.1 二分法,根的估计 二分法,根的估计,引理3.1（连续函数的介值定理） 设f(x)在a,b上连续，且f(a)f(b)0，则存在x*(a,b)使f(x*)=0。 例3.1 证明x33x1 = 0 有且仅有3个实根，并确定根的大致位置使误差不超过 =0.5。 解: 单调性分析和解的位置 选步长h=2, 扫描节点函数值 异号区间内有根,f(x)= x33x1,二分法,条件: 设f(x)在a,b上连续，f(x)=0在a,b上存在唯一解，且f(a)f(b)0。记,Step 1: I

2、f f(a0)f(x0)0, then x*(a0,x0) let a1=a0, b1=x0; Else x*(x0,b0) let a1=x0, b1=b0; Let x1=(a1+b1)/2.,Step k: If f(ak-1)f(xk-1)0, then x*(ak-1,xk-1) let ak=ak-1, bk=xk-1; Else x*(xk-1,bk-1) let ak=xk-1, bk=bk-1; Let xk=(ak+bk)/2.,收敛性及截断误差分析:,例3.2 x33x1 = 0, 1,2, 精度0.5e-1,二分法,优点 算法简单 收敛有保证 只要f(x)连续 缺点 对

3、区间两端点选取条件苛刻 收敛速度慢,3.2 迭代法原理,迭代法的思想 不动点原理 局部收敛性 收敛性的阶,迭代法的思想,条件: f(x)=0 在x0附近有且仅有一个根 设计同解变形 x=g(x) 迭代式 xk=g(xk-1), k=1,2, 如果收敛 xk x*, 则x*是f(x)=0 的根,不动点原理(迭代过程收敛),定理3.1 (不动点原理) 设映射g(x)在a,b上有连续的一阶导数且满足 1o 封闭性：x a,b, g(x) a,b , 2o 压缩性： L (0,1)使对x a,b, |g(x)|L, 则在a,b上存在唯一的不动点x*，且对x0 a,b, xk=g(xk-1)收敛于x*

4、。进一步，有误差估计式,算法设计中迭代结束条件: 近似使用|xk-xk-1|,不动点原理,证明步骤 解的存在性; 解的唯一性; 解的收敛性; 误差估计式。 例3.3,局部收敛性(格式收敛),定理3.2 （局部收敛性）设g(x)连续, 则存在充分靠近x*的初值，使迭代收敛于x*。 证明：利用定理3.1,取L= 具有局部收敛性的迭代计算上不一定收敛，它是否收敛还要看初值是否取的恰当； 而不具有局部收敛性的迭代对任何初值都不可能收敛。,应用中: 近似使用|g(x0)|1判断,收敛性的阶(局部收敛速度),定义3.1 当xkx*，记ek= x* - xk ，若存在实数p，使 ek+1/epk c0， 则

5、称xk有p阶收敛速度。 线性收敛 p=1 平方收敛 p=2,定理3.3 设xk=g(xk-1) x*，则 (1) 当g(x*)0时，xk线性收敛； (2) 当g(x*)=0,而g(x*) 0时，xk平方收敛。,3.3 Newton迭代法和迭代加速,牛顿(Newton)迭代法 “迭代加速”技术,牛顿(Newton)迭代法,原理(1次近似, 直线代替曲线) 牛顿格式,Newton法几何意义：切线法,切线代替曲线,Newton法局部收敛性,单根：平方收敛 m重根：线性收敛 例3.5 （P56) Newton迭代法，计算3次达到4位有效数字 计算4次达到4位有效数字 越是精度要求高, Newton迭代

6、法优势越明显,“迭代加速”技术,加快迭代过程的收敛速度 将发散的迭代格式加工成收敛的 若g(x)在x*附近大约为D, 改进xk = g(xk-1) 为 例3.6 （P57),4 解线性方程组的迭代法,1 迭代思想 2 Jacobi迭代和Gauss-Seidel迭代 3 迭代的收敛性 4 迭代加速逐次超松弛（SOR）法,1 迭代思想,解大型稀疏型方程组比直接法存储量小 条件: Ax=b 解存在唯一 设计同解变形 x=Gx+f 迭代式 x(k)=Gx (k-1)+f, k=1,2, 取初值x(0) ，如果收敛 x(k) x*, 则x*是Ax=b的解 x(k) x*,2 Jacobi迭代和Gauss

7、-Seidel迭代,例3.7 解：变形,Jacobi迭代,Jacobi迭代 初值取 ，精度要求 =10-3。 计算得 |x(6) x(5)|10-3.,Gauss-Seidel迭代,Gauss-Seidel迭代 初值取 ，精度要求 =10-3。 计算得 |x(5) x(4)|10-3.,编程计算公式,Jacobi迭代 Gauss-Seidel迭代 迭代结束条件一般用 |x(k) x(k-1)| 问题(1)收敛性条件? (2) |x(k) x(k-1)| 作为结束条件是否可靠?,计算公式矩阵形式,和分解： A=L(下三角)+D (对角) +U (上三角) 迭代 x(k)= Gx (k-1) +

8、f, k=1,2, Jacobi迭代 G = -D-1(L+U) = I-D-1A f = D-1 b Gauss-Seidel迭代 G = - (L+D)-1 U f = (L+D)-1 b,3 迭代的收敛性,定理3.4 设G的某种范数|G|1，则x=Gx+f存在唯一解，且对任意初值，迭代序列 x(k)= Gx (k-1) + f 收敛于x*，进一步有误差估计式 证明思路：(1)解的存在唯一性; (2)解的收敛性;(3)误差估计式(习题)。,直接从Ax=b判断,推论 若A按行严格对角占优（ ），则解Ax=b的Jacobi迭代和Gauss-Seidel迭代均收敛。 证明思路：用定理3.4. A

9、严格对角占优， 则无穷大范数 |G|1 Jacobi迭代(直接证|G|1) Gauss-Seidel迭代, 令y=Gx，则y= -D-1(Ly+Ux) 先证存在某x, |x| =1, 使|G| =|y| 再证当|x| =1, 有|y| 1,Gauss-Seidel迭代收敛性证明,记迭代矩阵 存在m, 令 那么 且,Gauss-Seidel迭代收敛性证明,记 ，其中迭代矩阵 那么 存在k使得 所以,充分必要条件,谱半径(G)：G的特征值模的最大值 定理3. 5 迭代x(k)= Gx (k-1) + f对任意初值收敛(G)1. （证明较深，略）,三种方法比较,方法一(推论): 从A判断, A严格对角占优，则Jacobi迭代和Gauss-Seidel迭代收敛, 充分条件, 最方便 方法二(定理3.4): 从G判断, 有一种范数|G|1, 充分条件 方法三(定理3.5): 从G判断,谱半径(G) 1, 充要条件, 最宽 P63, 例3.8（特征值的性质：特征值