第三章__迭代法s1s2_二分法及迭代法原理

1、3.1 二分法二分法3.2 迭代法原理迭代法原理3.3 Newton迭代法和迭代加速迭代法和迭代加速3.4 解线性方程组的迭代法解线性方程组的迭代法 根的估计根的估计 二分法二分法求求 f (x) = 0 的根的根q 代数方程：代数方程： f (x) = a0 + a1x + . . . + anxn超越方程：超越方程： f (x) 含超越函数，如含超越函数，如 sin(x), ex, lnx 等等q 实根与复根实根与复根q 根的重数根的重数 f (x) = ( x x*)m g(x) 且且 g(x*) 0, 则称则称 x* 为为 f (x) 的的 m 重根重根q 有根区间：有根区间：a, b

2、 上存在上存在 f (x) = 0 的一个实根的一个实根在在有根的前提下求出方程的的前提下求出方程的近似根。研究研究 内容内容:*(1)*( )*1,()().()0,()0,.kkkf xfxfxfxxk 如如果果有有则则为为 重重根根引理引理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。解解: : 单调性分析和解的位置单调性分析

3、和解的位置选步长选步长h=2 , 扫描节点函数值扫描节点函数值异号区间内有根异号区间内有根若若 f Ca, b，且，且 f (a) f (b) 0，则，则 f 在在 (a, b) 上必有一根。上必有一根。p 基本原理：基本原理：p 具体方法：具体方法：通过二等分不断缩小有根区间的长度，直到满足精度为止。通过二等分不断缩小有根区间的长度，直到满足精度为止。abx0 x1x*何时终止何时终止?1kkxx()kf x或或不能保证不能保证 x 的精的精度度算法 3.1 (二分法二分法)给定有根区间给定有根区间 a, b ( f(a) f(b) 0) 和和 精度要求精度要求 1. 令令 x = (a+b

4、)/22. 如果如果 b a = 2 , 停止计算，输出停止计算，输出 x ,否则执行第否则执行第3步步3. 如果如果 f (a) f (x) 0 , 则令则令 b = x，否则令，否则令 a = x, 返回第返回第1步步P50. Matlab源程序：源程序：nabisect.m用二分法求根，通常先给出用二分法求根，通常先给出 f (x) 草图以确定根的大概位置。草图以确定根的大概位置。 记记 a0 = a, b0 = b, 第第 k 步的有根区间为步的有根区间为 ak, bk112222kkkkkkkbababaxxx 0012kba 对于给定的精度对于给定的精度 ,可估计二分法所需的步数可

5、估计二分法所需的步数 k ：12kba 2log1,bak 取取2log1bak 简单易用简单易用 无法求复根及偶重根无法求复根及偶重根 对对 f (x) 要求不高，只要连续即可要求不高，只要连续即可 收敛速度慢收敛速度慢 12kba 两位有效数字两位有效数字 =0.5*10-1 , k (ln 20/ ln 2)-1, 取取k=4迭代法的思想迭代法的思想 不动点原理不动点原理 局部收敛性局部收敛性收敛性的阶收敛性的阶 (x) 的不动点的不动点x*f (x) = 0 x = (x) 称为迭代函数称为迭代函数等价变换等价变换p 基本思想基本思想从一个给定的初值从一个给定的初值 x0 出发，计算出

6、发，计算 x1 = (x0), x2 = (x1), 若若 收敛，即存在收敛，即存在 x* 使得使得 ，则由，则由 的连续的连续性和性和 可得可得 x* = (x*)，即，即 x* 是是 的不的不动点，也就是动点，也就是 f (x) 的零点。的零点。 0kkx*limxxkk 1limlimkkkkxxp 具体做法：具体做法：不动点迭代f (x) 的零点的零点x*p 几何含义：几何含义： 求曲线求曲线 y = (x) 与直线与直线 y = x 的交点的交点xk+1 = (xk)xyy = xxyy = xxyy = xxyy = xx*x*x*x*y= (x)y= (x)y= (x)y= (x

7、)x0p0 x1p1x0p0 x1p1 x0p0 x1p1x0p0 x1p1x2 迭代公式迭代公式1：迭代公式迭代公式2：计算结果：计算结果：311kkxx 131(1)kkxx 2.3701.512512.341904kkx公式公式1 1：01.511.3572121.3308631.3258841.3249451.324761.324731.376724 2kkx公式公式2 2：怎么判断迭代公式收敛或发散呢？怎么判断迭代公式收敛或发散呢？精确解精确解x* =1.3247179. 定理定理3.1设设 (x)在在a, b上连续，上连续， 且一阶导数连续，若且一阶导数连续，若(2) 0 L 1，

8、使得，使得 | (x) | L 对对 x a, b 成立成立则函数则函数 f (x) = x - (x) 在在 a, b 中有中有唯一唯一的零点的零点 x*。(压缩映像定理，不动点原理压缩映像定理，不动点原理)x* 称为称为 (x) 的的不动点不动点 (x*) = x*(1) a (x) b 对一切对一切 x a, b 都成立都成立简证：简证：f(a) = a - (a) 0 , f(b) = b - (b) 0f(x) 在在a, b 上有零点。上有零点。唯一性：反证法，假设存在唯一性：反证法，假设存在 x*, y* a, b 使得使得( *)( *)( )*xyL xxyyxy x* = (

9、x*) y* = (y*)矛盾！矛盾！封闭性封闭性 压缩性压缩性 定理定理3.1设设 (x)在在a, b上连续，上连续，且一阶导数连续，若且一阶导数连续，若(2) 0 L 1，使得，使得 | (x) | L 对对 x a, b 成立成立,(1) a (x) b 对一切对一切 x a, b 都成立都成立,则有则有(a) 对任意对任意 x0 a, b，由，由 xk+1 = (xk) 产生的迭代序列产生的迭代序列 均收敛到均收敛到 (x) 在在 a, b 中的唯一不动点中的唯一不动点 x*。 0kkx(b) 有如下的误差估计有如下的误差估计:1|*|1kkkLxxxxL 10|*|1kkLxxxxL

10、 可用可用| x k-xk-1 | 来控制收敛精度来控制收敛精度 L 越小收敛越快越小收敛越快 后验估计后验估计: :先验估计先验估计: :证：证：(a) 由压缩映像定理可知，不动点由压缩映像定理可知，不动点 x* 存在且唯一。存在且唯一。(b)1|*|*|kkxxL xx111|(*) (*)|*kkkkkkxxxxxxxxxx(1)*kL xx11*1kkkxxxxL1111|()()|( )| |kkkkkkkkxxxxxxL xx 又又11101*111kkkkkkLLxxxxxxxxLLL111()( *)|( )| |*|*|*|kkkkxxxxxxxLx 2120|*|*|*|*

11、|kkkkxxL xxLxxLxxlim|*|0kkxxlim*.kkxx即p 定理的条件保证了不动点迭代的定理的条件保证了不动点迭代的全局收敛性全局收敛性。即迭代的收敛性与初始点的选取无关。即迭代的收敛性与初始点的选取无关。p 这种在这种在 x* 的邻域内具有的收敛性称为的邻域内具有的收敛性称为局部收敛性局部收敛性。定理中的条件定理中的条件 | (x) | L 1 可以适当放宽可以适当放宽(2) (x) 在在 x* 的某个邻域内连续，且的某个邻域内连续，且 | (x*) | 1由由 (x) 的连续性及的连续性及 | (x*) | 1 即可推出：即可推出：定理定理3.23.2若若 (x)的一阶

12、导数连续的一阶导数连续, 且满足条件且满足条件(2), 则一定存在则一定存在 x* 的的某个某个 邻域邻域 N(x*) =x*- , x* + , 使得对使得对 x N(x*)都有都有| (x) | L 1, 则由则由 x0 N(x*) 开始开始的迭代都收敛。的迭代都收敛。 具有局部收敛性的迭代计算上不一定收敛，它是否收敛还具有局部收敛性的迭代计算上不一定收敛，它是否收敛还要看初值是否取的恰当；要看初值是否取的恰当； 而不具有局部收敛性的迭代对任何初值都不可能收敛。而不具有局部收敛性的迭代对任何初值都不可能收敛。迭代公式迭代公式1：迭代公式迭代公式2：迭代公式迭代公式3：迭代公式迭代公式4：计

13、算结果：计算结果：213kkkxxx 13/kkxx 怎么判断收敛的迭代公式的速度快慢呢？怎么判断收敛的迭代公式的速度快慢呢？321(3)/ 4kkkxxx 13)/ 2(/kkkxxx 0123123402222131.51.751.752921.7343751.7321433871.51.7323611.732051kkxxxxx方方法法方方法法方方法法方方法法31.7320508.精确值：精确值：1,21,2上迭代收敛性上迭代收敛性? ?1,21,2上迭代收敛性上迭代收敛性? ?设迭代设迭代 xk+1 = (xk) 收敛到收敛到 (x) 的不动点的不动点 x*。记记 绝对误差绝对误差ek

14、 = xk x*，若若1lim0kpkkeCe 定义定义则称该迭代为则称该迭代为 p 阶收敛。(1) 当当 p =1 时称为时称为线性收敛，此时，此时 |C| 1 时称为时称为超线性收敛。 p 不动点迭代中，若不动点迭代中，若 迭代数列迭代数列xk收敛，且收敛，且 (x*) 0，则则 11*()( *)( )kkkkexxxxe取极限得取极限得1lim( *)0kkkexe(C为常数为常数)线性收敛线性收敛.设迭代设迭代 xk+1 = (xk) ，若，若 (p)(x) 在在 x* 的某邻域内连续，的某邻域内连续，则该迭代法具有则该迭代法具有 p 阶收敛的充分必要条件是阶收敛的充分必要条件是定理定理3.3(1)()( *)*,( *)( *)( *)0,( *)0ppxxxxxx()11lim( *)!pkpkkexep并且有并且有( )(1)11()( *)()( *)( *)(*).(*)(*)(1)!ppppkkkkkkxxxxxxxxxxxpp 证明：充分性充分性. 根据泰勒展开有根据泰勒展开有( )1()*(*)!ppkkkxxxxp()11lim( *)!pkpkkexep必要性必要性. 设迭代设迭代 xk+1 = (xk) 是是