第三章迭代法.pptVIP

Jacobi迭代(直接证||G||?1) G = -D-1(L+U) 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（特征值的性质：特征值之和等于对角线元素的和） 4 逐次超松弛（SOR）法 Gauss-Seidel迭代格式的加速 收敛的必要条件0?2 低松弛法 0?1 ?=1, Gauss-Seidel迭代 超松弛法 1?2 P66 例3.9 P70习题 ex1 ex2,ex3 ex5,ex6 ex9,ex10,ex11(2) ex13 第三章迭代法 §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 证明x3?3x?1 = 0 有且仅有3个实根，并确定根的大致位置使误差不超过? =0.5。 解: 单调性分析和解的位置 选步长h=2?, 扫描节点函数值 异号区间内有根 f(x)= x3?3x?1 二分法(更快的扫描法) 条件: 设f(x)在[a,b]上连续，f(x)=0在[a,b]上存在唯一解，且f(a)f(b)0。记 Step 1: If 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 x3?3x?1 = 0, [1,2], 精度0.5e-1 二分法 优点 算法简单 收敛有保证 只要f(x)连续 缺点 对区间两端点选取条件苛刻 收敛速度慢 难以推广至多维情形 §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* 。进一步，有误差估计式 后验估计 先验估计 算法设计中迭代结束条件: 近似使用|xk-xk-1|? 不动点原理 例3.3 x3?x?1 = 0 ，[1,2], x0=1.5, 不动点原理 证明步骤 解的存在性; 解的唯一性; 解的收敛性; 误差估计式。 局部收敛性(格式收敛) 定理3.2 （局部收敛性）设g’(x)连续, 则存在充分靠近x*的初值，使迭代收敛于x*。 证明：利用定理3.1,取L= 具有局部收敛性的迭代计算上不一定收敛，它是否收敛还要看初值是否取的恰当； 而不具有局部收敛性的迭代对任何初值都不可能收敛。 应用中: 近似使用|g(x0)|1判断 收敛性的阶(局部收敛速度) 定义3.1 当xk?x*，记ek= x* - xk ，若存在实数p，使 ek+1/epk ? c?0， 则称{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}平方收敛。