《6[1]2不动点迭代法及其收敛定理教学教案》由会员分享，可在线阅读，更多相关《6[1]2不动点迭代法及其收敛定理教学教案（54页珍藏版）》请在金锄头文库上搜索。
1、 6.2 不动点迭代法及其收敛定理,第6章 方程与方程组的迭代解法,一、迭代法原理,-(2),将非线性方程 f (x) = 0 化为一个同解方程,继续,-(3),称(3)式为求解非线性方程(2)的简单迭代法,则称迭代法(3)收敛,否则称为发散,-(4),例1.,解:,(1) 将原方程化为等价方程,仍取初值,x2 = 0.9644 x3 = 0.9940 x4 = 0.9990 x5 = 0.9998 x6 = 1.0000 x7 = 1.0000,依此类推,得,已经收敛,故原方程的解为,同样的方程 不同的迭代格式 有不同的结果,什么形式的迭代法 能够收敛呢?,迭代函数的构造有关,如果将(2)式
2、表示为,与方程(2)同解,收敛,发散,定理1.,-(5),-(6),-(7),(局部收敛性),迭代过程的收敛性,证:,由条件(1),由根的存在定理,证:,由,由微分中值定理,证毕.,定理1指出,只要构造的迭代函数满足,由(6)式,只要,因此,当,迭代就可以终止,-(8),定义1：如果存在 的某个邻域 ，使迭代过程 对于任意初值 均收敛，则称迭代过程 在根 邻近具有局部收敛性。,例2.,用迭代法求方程的近似解,精确到小数点后6位,解:,本题迭代函数有两种构造形式,因此采用迭代函数,d1 = 0.1000000 d2 = -0.0105171 d3 = 0.1156e-002 d4 = -0.12
3、65e-003 d5 = 0.1390e-004 d6 = -0.1500e-005 d7 = 0.1000e-006,由于|d7| =0.1000e-0061e-6,因此原方程的解为,x7 = 0.090525,x1 = 0.1000000 x2 = 0.0894829 x3 = 0.0906391 x4 = 0.0905126 x5 = 0.0905265 x6 = 0.0905250 x7 = 0.0905251,由定理1的(7)式出,迭代法收敛就越快,定义1.,-(9),迭代法收敛速度,定理3.,例,解:本题迭代函数有两种构造形式,迭代法发散.,(2),迭代法收敛.,(1),Newto
4、n 迭代法,将f(x)在点xn作Taylor展开:,Taylor展开线性化,f(x)=0 近似于 f(xn)+ f(xn)(x-xn)=0 (1),从(1)解出x, 记为xn+1 ,则,1. Newton迭代公式建立,它对应的迭代方程为 显然是f(x)=0的同解方程，故其迭代函数为 在 f(x)=0的根 x* 的某个邻域 内, 在 x* 的邻域R 内，对任意初值 ，应用公式（2）来解方程的方法就称为牛顿迭代法。它是解代数方程和超越方程的有效方法之一.,2. Newton迭代法的几何意义,与x轴(y=0)的交点x,作为下一个迭代点xn+1 ,即,用f(x)在 xn 处的切线,Newton迭代法又
5、称切线法.,例 用Newton迭代法求下面方程的一个正根,计算结果精确到7位小数.,解:,由Newton迭代法,由Newton迭代法,x1 = 1.4666667 , x4 = 1.3688081 x5 = 1.3688081,迭代5次精度达10-7 x* 1.368808,4. Newton迭代法收敛定理,（1）Newton迭代公式在单根情况下至少2阶收敛; （2）,定理 设 f(x*)=0, ,且在 x* 的邻域 上 存在, 连续, 则可得,证：将f(x)在 xn 处作2阶Taylor展开,并将解x*代入,注意到n 在xn 及x*之间,及 , 故,所以，Newton法至少二阶收敛.,注意到
6、n 在xn 及x*之间,及 ,故,例3.,为线性收敛,证明:,所以,例4.,至少是平方收敛的,由定义1,注意例4与例3的迭代法是相同的,两例有何区别?,证明:,令,则,所以,由定理2,该迭代法至少是平方收敛的,Newton迭代公式是一种特殊的不动点迭代,其迭代矩阵为: Newton迭代是局部线性化方法,它在单根附近具有较高的收敛速度. 方法有效前提:,Newton迭代法的特征,5. Newton迭代法的应用-开方公式,对于给定正数 应用牛顿迭代法解二次方程 可导出求开方值 的计算公式 设 是 的某个近似值，则 自然也是一个近似值，上式表明，它们两者的算术平均值将是更好的近似值。 定理 开方公式
7、对于任意给定的初值 均为平方收敛。,牛顿迭代法的优缺点,优点： 在单根附近, 牛顿迭代法具有平方收敛的速 度，所以在迭代过程中只要迭代几次就会得到很精 确解。 缺点:1. 重根情形下为局部线性收敛; 2. 牛顿迭代法计算量比较大:因每次迭代除 计算函数值外还要计算微商值; 3. 选定的初值要接近方程的解，否则有可能得 不到收敛的结果;,牛顿迭代法的改进,缺点克服: 1. 局部线性收敛-改进公式或加速 2.每步都要计算微商值-简化Newton迭代法 或弦截法 3. 初值近似问题-二分法求初值或”下山算法”,方法一. 若已知重数m(m1),则利用m构造新的迭代公式: 此时, , 至少2阶收敛. 不
8、实用: m往往不确定. 方法二. 取 ,再对函数F(x)用Newton迭代: 此时,X*为F(x)的单根,所以是2阶收敛. 但要用到二阶导数.,6. Newton法的改进(I)-重根情形,Newton迭代法,需要求每个迭代点处的导数 f (xk),复杂！,这种格式称为简化Newton迭代法,精度稍低,6. Newton法的改进(II),则Newton迭代法变为,这种格式称为弦截法,收敛阶约为1.618,例4 用简化Newton法和弦截法解下面方程的根，并和Newton 迭代法比较,解:,由简化Newton法,由弦截法,由Newton迭代法,x0= 0.5 x1= 0.3333333333 x2
9、 = 0.3497942387 x3 = 0.3468683325 x4 = 0.3473702799 x5 = 0.3472836048 x6 = 0.3472985550 x7 = 0.3472959759 x8 = 0.3472964208 x9 = 0.3472963440 x10 = 0.3472963572 x11 = 0.3472963553,x0=0.5; x1=0.4; x2 = 0.3430962343 x3 = 0.3473897274 x4 = 0.3472965093 x5 = 0.3472963553 x6 = 0.3472963553,简化Newton法,由弦截法
10、,要达到精度10-8,简化Newton法迭代11次,弦截法迭代5次,Newton迭代法迭代4次,x0 =0.5; x1 =0.3333333333 x2 =0.3472222222 x3 =0.3472963532 x4 =0.3472963553,由Newton迭代法,无论哪种迭代法：,Newton迭代法,简化Newton法,弦截法,用Newton迭代法求解:,x0 = 2 x1 = -3.54 x2 = 13.95 x3 = -279.34 x4 = 122017,是否收敛均与初值的位置有关.,例:,x0 =1 x1 = -0.5708 x2 = 0.1169 x3 = -0.0011 x
11、4 = 7.963110-10 x5 = 0,收敛,发散,迭代法的局部收敛性,6. Newton法的改进(III) : 牛顿下山法,一般地说，牛顿法的收敛性依赖于初值 的选取，如果 偏离 较远，则牛顿法可能发散。 为了防止发散，通常对迭代过程再附加一项要求，即保证函数值单调下降： 满足这项要求的算法称为下山法。 牛顿下山法采用以下迭代公式： 其中 称为下山因子。,牛顿下山法只有线性收敛.,例7.,解:,1.先用Newton迭代法,x4 = 9.70724 x5 = 6.54091 x6 = 4.46497 x7 = 3.13384 x8 = 2.32607 x9 = 1.90230 x10=
12、1.75248 x11= 1.73240 x12= 1.73205 x13= 1.73205,迭代13 次才达 到精度 要求,2.用Newton下山法,结果如下,故有,且,由例3.,对于Newton迭代法,趋于零,Newton迭代法也只是线性收敛,此时Newton迭代法可能不收敛,由定理2，迭代法,至少是二阶收敛,Numerical Value Analysis,Steffensen方法,第6章 方程与方程组的迭代解法,简单迭代公式的加速,设 是根 的某个近似值，用迭代公式校正一次得 假设 ， 则有 据此可导出如下加速公式： 其一步分为两个环节： 迭代: 改进:,埃特金迭代法求方程的实根,定理 设序列 线性收敛于x*, 则 的Aitken序列 存在,且 即 比 更快收敛于x*.,Steffensen迭代,在Aitken加速法中,只要有三个相邻的点就可以进行 家速,即对任意线性收敛序列 构建的. 现将其与不 动点迭代 方法结合起来: 迭代函数 迭代初始值 迭代序列,或写成不动点迭代形式,
