1、 2.1 二分法二分法二分法又称区间对分法，是最直观、最简单的一种方法。二分法又称区间对分法，是最直观、最简单的一种方法。2.1.1 二分法原理二分法原理 若若 f(x)在在a,b内单调连续，且内单调连续，且f(a)f(b)0，则，则f(x)在在(a,b)内必有惟一的实根。内必有惟一的实根。实现：实现：区间对分，去同存异区间对分，去同存异2.1.2 二分法计算步骤二分法计算步骤2.1.3 二分法的收敛性二分法的收敛性2.1.4 二分法的优缺点二分法的优缺点n 算法简单直观，易编程计算；算法简单直观，易编程计算；n 只需连续即可；只需连续即可；n 区间收缩速率相同，收敛速度慢；区间收缩速率相同，
2、收敛速度慢；n 无法求复根和偶重根。无法求复根和偶重根。例例2-1 p15二分法的二分法的本质本质是：是：缩小含根区间，使之缩小含根区间，使之达到精度要求达到精度要求2.2 不动点迭代法不动点迭代法 2.2.1 不动点迭代不动点迭代 .).()(limlim)()()()(),2,1,0()()(0)(*1*1*1称其为不动点此时有散。，否则，称迭代公式发收敛，称迭代公式收敛若迭代数列为迭代公式。为迭代函数，称的不动点的根xxxxxxxxxxxxfkxxxxxfkkkkkkkkkkk同解变换对收敛性很重要例例2/)1()(1)(11)(1)(01)(2423212xxxxxxxxxxxxxxx
3、xf哪个哪个 公式好？公式好？2.2 不动点迭代法不动点迭代法2.2.1 不动点迭代不动点迭代 不动点迭代示意图（不动点迭代示意图（P16）不动点迭代法步骤（不动点迭代法步骤（P17）不动点迭代算法流程图（不动点迭代算法流程图（P17）例例2-2 P172.2 不动点迭代法不动点迭代法2.2.2 不动点迭代法的几何意义及收敛性不动点迭代法的几何意义及收敛性 迭代法的几何意义是求迭代函数和y=x的交点的横坐标。xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=y=y=y=x0p0 x1p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p1 可以看出：可以看出：若的变化幅度小若的
4、变化幅度小于的变化幅度时，于的变化幅度时，迭代公式收敛，迭代公式收敛，否则，迭代公式否则，迭代公式不收敛。不收敛。)(xyxy2.2 不动点迭代法不动点迭代法2.2.2 不动点迭代法的几何意义及收敛性不动点迭代法的几何意义及收敛性 关于关于全局收敛性的判定全局收敛性的判定)(lim)4(,2,1(1,2,1(11)3(lim,)2(,)()1()12()(-)(,10;,)(,),(,)(*1*01*k1k*0*xxxxxkxxLLxxkxxLxxxxxbaxxbaxyxLyxbayxLbaxbaxbabaxkkkkkkkkk）有如下误差估计：收敛，且，迭代序列；内有唯一不动点在函数则使得，压
5、缩性：时，有映内性：当内可导，且满足：内连续，在在区间设迭代函数说明：说明：式（式（2-1）的）的Lipschitz条件太强，条件太强，不好验证。通常采用更强的条件不好验证。通常采用更强的条件)22(,1)(baxLx全局收敛性定理全局收敛性定理2-12.2 不动点迭代法不动点迭代法2.2.2 不动点迭代法的几何意义及收敛性不动点迭代法的几何意义及收敛性例例2-3 P20 局部收敛性判定局部收敛性判定 局部收敛性定理局部收敛性定理2-2 收敛的阶收敛的阶 p阶阶收敛的定理收敛的定理2-3例例2-4 P220,0 xa证明证明 迭代法的特点迭代法的特点n算法逻辑结构简单，便于机器实现；算法逻辑结
6、构简单，便于机器实现；n在计算时在计算时,中间结果若有扰动中间结果若有扰动,仍不会影响计算结果；仍不会影响计算结果；n不同的迭代公式在收敛性、收敛速度上有差别。不同的迭代公式在收敛性、收敛速度上有差别。.)4(4lim432421*21kkkkkkxxxxxx邻近平方收敛，并求是在证明迭代公式312210)(lim33)3(0,kkkkkkkxaxaaaxaxxxxa阶方法，并计算的是计算，证明迭代公式设2.2 不动点迭代法不动点迭代法2.2.2 不动点迭代法的几何意义及收敛性不动点迭代法的几何意义及收敛性例例例例例例2.3 牛顿法与割线法牛顿法与割线法 2.3.1 牛顿法原理与几何意义牛顿法
7、原理与几何意义 牛顿法原理牛顿法原理 牛顿法几何意义牛顿法几何意义2.3 牛顿法与割线法牛顿法与割线法2.3.1 牛顿法原理与几何意义牛顿法原理与几何意义 牛顿法步骤及流程图牛顿法步骤及流程图 P242.3 牛顿法与割线法牛顿法与割线法2.3.1 牛顿法原理与几何意义牛顿法原理与几何意义例例2-5 例例 用牛顿迭代法推导求用牛顿迭代法推导求 的迭代公式，并求收敛的阶的迭代公式，并求收敛的阶。a2.3 牛顿法与割线法牛顿法与割线法 2.3.2 牛顿迭代法的收敛性牛顿迭代法的收敛性例例2-6 P25证明证明yx0aby=f(x)x00)(,0)(xfxf(a)x x0 0取靠近取靠近b b一侧一侧
8、yx0aby=f(x)x00)(,0)(xfxf(b)x x0 0取靠近取靠近a a一侧一侧yx0aby=f(x)x00)(,0)(xfxf(c)x x0 0取靠近取靠近a a一侧一侧yx0aby=f(x)x00)(,0)(xfxf(d)x x0 0取靠近取靠近b b一侧一侧牛顿法局部收敛的牛顿法局部收敛的4种情形种情形 1,0)()()1()()(kkkkkkkxfxfxxxfxfx2.3 牛顿法与割线法牛顿法与割线法 牛顿法的特点与改进牛顿法的特点与改进预测预测校正型牛顿公式校正型牛顿公式构造高阶迭代公式构造高阶迭代公式证明证明2.3 牛顿法与割线法牛顿法与割线法2.3.3 割线法割线法
9、割线法的几何意义割线法的几何意义 割线割线法的计算步骤法的计算步骤 割线法的收敛性割线法的收敛性例例2-7 P27 割线法的特点割线法的特点收敛速度比较快，但比牛顿法慢；收敛速度比较快，但比牛顿法慢；超线性收敛，收敛阶为超线性收敛，收敛阶为1.618；无需计算导数无需计算导数，每步只需计算一次函数值；，每步只需计算一次函数值；属于属于多点迭代多点迭代，而牛顿法和一般迭代法属于，而牛顿法和一般迭代法属于单点迭代。单点迭代。2.3 牛顿法与割线法牛顿法与割线法2.3.3 割线法割线法2.3 牛顿法与割线法牛顿法与割线法2.3.4 牛顿法求解代数方程牛顿法求解代数方程2.4 迭代法的改善与加速迭代法的改善与加速 一般的加速算法一般的加速算法2.5.2 埃特金（埃特金（Aithen）加速算法）加速算法 2.4 迭代法的改善与加速迭代法的改善与加速 2.4.1 埃特金加速算法埃特金加速算法求解求解22)()(axxf 2.4 迭代法的改善与加速迭代法的改善与加速 2.4.2 牛顿法求重根时的改善牛顿法求重根时的改善
