简单迭代法.ppt

1、学习和了解科学计算的桥梁,Numerical Calculations,数值计算,迭代法是求解非线性方程近似根最常用的一种方法。简单迭代法又是其它迭代法的基础。 迭代法的关键是确定迭代函数(x)，即 用直接的方法将原方程f(x)=0变为等价的方程x= (x ) (即隐含的求出x), 从而确定迭代函数(x)，然后进行迭代，求出方程的近似根。 简单迭代法收敛速度较慢，迭代次数多，因此常用于理论研究中，实际用于求根的迭代法是另一种迭代法Newton迭代法，它采用另一种迭代格式, 具有较快的收敛速度，由牛顿迭代法还可以得到其他的迭代格式。,2.3 简单迭代法,一、简单迭代法原理,简单迭代法又称逐次逼近

2、法. 基本思想：是构造不动点方程，以求得近似根。 即由方程f(x)=0变换为等价方程 x=(x) （#）,这样原方程的根必满足：x*= (x*) ，即(x) 作用在x*上，其值不发生变化，因此我们也称x*为(x) 的不动点， (#)也称为不动点方程。要求方程f(x)=0的根就转化为求(x) 的不动点了。具体作法如下：,先取一个估计值x0来试探,若(x0) =x0,则x*=x0(可能性很小)一般(x0) x0, 记 x1=(x0) ，若x1=(x1) , 则x*=x1 若x1(x1),记 x2=(x1),再用x2继续试探如此反复计算,即形成一迭代公式 xk+1=(xk)(k=0,1,2,),定义

3、：如果xk收敛，则称迭代公式xk+1=(xk)是收敛的；否则称迭代公式是发散的。,当xk收敛于a，而(x)是连续函数时，那么a就是所求方程的根x* 。这是因为,a即是(x)的不动点。 即：x*=a,一般地，我们称(x)为方程f(x)=0的迭代函数，上述求根的方法，称为简单迭代法。,迭代函数(x)的构造方法是多种多样的。,例1 用迭代法求方程x3-x-1=0在x=1. 5附近的根。,解：先将原方程改写为如下两种等价形式：,x=1(x),x=2(x)=x3-1,相应地可得到两个迭代公式：,xk+1=1(xk),xk+1=2(xk)=xk3-1,如果取初始值x0=1. 5，分别用上面两公式迭代(用6

4、位有效数字计算），可得下表：,x*=1.32472,收敛,由方程f(x)=0变换为等价方程 x=(x) （#）,先取一个估计值x0（初始值），若(x0) =x0，则x*=x0(可能性很小)一般(x0) x0， 记 x1=(x0) ， 若x1(x1) ， 记 x2=(x1) ，再用x2继续试探 记 x3=(x2) 如此反复计算 即形成一迭代公式 xk+1=(xk) ，(k=0,1,2,),简单迭代法的思想,x*是方程f(x)=0的根,x*是方程x=(x)的根,x*为(x) 的不动点,即：x*= (x*),定义：如果xk收敛，则称迭代公式xk+1=(xk)是收敛的；否则称迭代公式是发散的。,当xk

5、收敛于a，而(x)是连续函数时，那么a就是所求方程的根x* 。这是因为,a即是(x)的不动点。 即：x*=a,一般地，我们称(x)为方程f(x)=0的迭代函数，上述求根的方法，称为简单迭代法。,迭代函数(x)的构造方法是多种多样的。,二、简单迭代法的几何解释,求方程x=(x) 的根在几何上就是求y=(x) 与y=x的交点P*的横坐标。,y=x,y=(x),x0,(x0)=x1,x1,x2,P0,P1,给出一个估计值x0，在曲线y=(x) 上得到以x0为横坐标的点P0，P0的纵坐标为(x0) =x1，过P0引x轴的平行线与直线y=x交于一点Q1，过Q1再作y轴的平行线与曲线y=(x) 相交于一点

6、P1，x1即为P1点的横坐标，按图中箭头所示继续做下去，在曲线y=(x) 上得到点列P1,P2,其横坐标分别为x1,x2,，,恰好为按公式xk+1=(xk) 所确定的迭代值。若迭代收敛，则点列P1,P2,将越来越逼近所求交点P*.,Q1,(x1)=x2,迭代格式有多种，如何选择迭代函数才能保证迭代法的数列收敛？有如下定理：,三、迭代公式的收敛性与误差估计,迭代公式可能收敛，也可能发散，那么 (1)当迭代函数(x)满足什么条件时，相应的迭代公式 xk+1=(xk)才收敛？ (2)当迭代收敛时，迭代值的误差如何估计？ 我们也不能无穷迭代下去，只能迭代有限次，所以需要估计迭代值的误差，以便适时终止迭

7、代。,定理2.1：假定迭代函数(x) 满足下列条件： 1、对任意xa,b ，有 (x) a,b 2、存在正数 L1，使对任意x，ya,b 有 |(x) - (y)|L|x-y| 则(x)在a,b上存在唯一的不动点x*,且对于任意初值x0a,b,由迭代公式 xk+1= (xk) 产生的数列xk都收敛于x*,并有如下的误差估计式：,证明：1)先证不动点的存在性,返回,作f(x)=x- (x),则条件2知f(x)在a,b上连续,由条件1知 : f(a)=a- (a)0, f(b)=b- (b)0 f(a) f(b)0,由零点定理知，至少存在一点x* a,b，使得,f(x*)=0，即x*= (x*)，

8、 x*即为(x)的不动点 。,再证不动点的唯一性：设有两个不同的不动点x1*, x2*,由条件2得： |x1*- x2*|=| (x1*) - (x2*) |L |x1*- x2*|, |x1*- x2*| 矛盾,x1*=x2*.,2)数列xk收敛到x*： 由1)知，存在一点x* a,b， 使得：x*= (x*) ， 再由xk+1= (xk) ，得 |xk+1-x*|=| (xk) - (x*) |L|xk-x*| 故 |xk+1-x*|L|xk-x*| 据此反复递推有：| xk-x*|Lk|x0-x*| 故当 k 时，迭代值xkx*(0L1),3)误差估计式,|xk+1-xk|=| xk+1

9、-x* +x*- xk | |x*- xk|- | xk+1-x*|= |x*- xk|- | (xk) - ( x*)| |x*- xk|-L | xk-x*|= (1-L )| x*-xk|,0L1，有：,由(*)反复递推得： |xk+1-xk|Lk|x1-x0| 代入上述误差估计式，得：,再由条件2得: |xk+1-xk|=| (xk) - (xk-1) |L|xk-xk-1| (*) 代入上式得：,即：只要前后两次迭代值的差值足够小，就可使近似值xk达到任意的精度要求。,注1：定理2.1给出了一个收敛的迭代数列xk的误差估计式。利用它，在给定精度0后，只要计算到,就有：|x*-xk|,

10、特别地,当L1/2时，有不等式|x*-xk|xk-xk-1|,此时，只要|xk-xk-1| ，就可以终止迭代，求出满足精度要求的近似根xk。,注2：定理2.1的条件（2）不好验证，故不易使用，,|(x) - (y)|L|x-y| (0L1),一般用,由中值定理可以证明上述结论:,|(x) - (y)|=| ()| |x-y|,只要,就有： |(x) - (y)|L|x-y| (0L1),故只要,迭代公式xk+1=(xk) 就收敛,上面给出的迭代数列xk在整个区间a,b上收敛,通常称为全局收敛性。有时在整个区间上检验定理的条件很困难，实际应用时通常在不动点x*的邻近考察其收敛性局部收敛性。,定义

11、 如果存在不动点x*的某个邻域U(x*,)，使得对于任意初值x0 U(x*,)，迭代公式xk+1= (xk) （k=0,1,2.)产生的数列xk均收敛于x*，则称迭代公式xk+1= (xk)是局部收敛的。,定理2.2(局部收敛定理) 设(x)在x= (x)的根x*邻近有连续的一阶导数, 且| (x*)|1， 则迭代公式xk+1=(xk)具有局部收敛性。（证明略）,注：根据(x)的连续性条件| (x*)|1可用| (x0)|1来近似代替。 (x*不知道，验证| (x*)|1很困难),例 求方程x=e-x在0. 5附近的一个根，要求精度=10-5,解:过x=0.5以h=0.1为步长搜索一次,可发现

12、所求根在区间0.5,0.6内,由上述公式知，迭代公式 对于初值x0=0.5是收敛的。迭代18次后，得x*=0.56714。,(e - 0. 6)=0.5488,(e - 0. 5)= 0.6065,0.5- 0.60650,0.6-0.54880,且有 | (0.5)|= |(e-0.5)|1,四、迭代法的计算步骤,1）准备：确定迭代函数(x) 及初始值x0，为保证迭代收敛，(x)须满足： |(x)|1，或 (x0)1;,2）迭代：按迭代公式xk+1=(xk)计算出xk(k=1,2,);,3）判断：若|xk-xk-1| ，则终止迭代，取x*xk；否则，转2)继续迭代。,注：迭代法的优点： 1、

13、算法逻辑结构简单； 2、在计算中，初始值的误差或中间值的误差都不影响最终计算结果。(迭代时可以自动修正),作业： P34 4、5,五、收敛速度与迭代公式的加速,（1）收敛速度,一种迭代法具有实用价值，不但要肯定它是收敛的，还要求它收敛的比较快。所谓迭代过程的收敛速度，是指在接近收敛时迭代误差的下降速度。,定义 如果迭代误差 ek=(x*-xk),当k时，有,（C0,且为常数）,则称迭代过程是p阶收敛的。 特别地，当p=1，称为线性收敛；p1时称为超线性收敛；p=2时称为平方收敛。,定理：对于迭代过程xk+1= (xk) ，如果(p)(x) 在所求根x*的邻近连续，并且(x*)= (x*) =.

14、= (p-1)(x*) =0，(#) (p)(x*)0，则该迭代过程在点x* 邻近是P阶收敛的。,证明：由于(x*)=01,据定理2.2，立即可以断定迭 代过程xk+1= (xk) 具有局部收敛性。,利用条件(#)，则有,再将(xk) 在根x*处展开，,介于xk与x*之间,上述定理告诉我们，迭代过程的收敛速度依赖于迭代函数. 如果选取当xa,b 时(x)0，则该迭代过程只能是线性收敛。,因此对迭代误差有: 这表明迭代过程xk+1= (xk)确实为P阶收敛，证毕。,注意到 (xk)= xk+1 ， (x*)= x*由上式得,C,例: x*= 是方程x2-3=0的一个正根，构造两个迭代公式:,是线

15、性收敛的,是平方收敛的,（2） 迭代过程的加速方法,a、加速方法的构造：,假设(x)在x*的附近变化不大，估计其值大约为L，则由微分中值定理，得：,整理得：,即:,记,称此公式为迭代加速公式。,即,迭代加速公式,用此加速公式时，需要知道两个量：迭代函数(x)和L,L(x0),例：用迭代加速公式求方程x=e-x在0. 5附近的根.,解：,迭代函数为(x)= e-x ,初始值为x0=0.5,而(x)= -e-x ,在x0=0.5附近的估计值为 (x)- 0.6 x0.5，0.6,由加速迭代公式,得：,经过3次迭代得近似根x3=0.56714(加速明显）,作业：P34 4、5,由方程f(x)=0变换

16、为等价方程 x=(x) （#）,先取一个估计值x0（初始值），若(x0) =x0，则x*=x0(可能性很小)一般(x0) x0， 记 x1=(x0) ， 若x1(x1) ， 记 x2=(x1) ，再用x2继续试探 记 x3=(x2) 如此反复计算 即形成一迭代公式 xk+1=(xk) ，(k=0,1,2,),简单迭代法的思想,复习：,x*是方程f(x)=0的根,x*是方程x=(x)的根,x*为(x) 的不动点,即：x*= (x*),当xk收敛于x*， x*即是(x)的不动点，也就是原方程的根。,(x)是连续函数，称为迭代函数,1、迭代公式 xk+1=(xk)收敛 xk收敛于x*,2、若,则迭代

17、公式xk+1=(xk) 收敛,全局收敛性,3、若(x)在x*邻近有连续的一阶导数，且| (x*)|1,则迭代公式xk+1=(xk)具有局部收敛性。,注：有局部收敛性的条件| (x*)|1可用| (x0)|1来近似代替。,迭代公式收敛性的判断,误差估计式,当迭代公式xk+1=(xk) 收敛时，有误差估计式：,即：只要前后两次迭代值的差值足够小，就可使近似值xk达到任意的精度。,| (x*)|L1 或| (x0)|L1,特别地,当L1/2时，有不等式|x*-xk|xk-xk-1|,此时，只要|xk-xk-1| ，就可以终止迭代，求出满足精度要求的近似根xk。,b、艾特肯(Aitken)加速方法,上

18、述加速公式在使用时，有时估计(x)的值很难，为了避免对导数(x)的估计，可采用下列方法：,仍记,对 再进行一次迭代，,得：,消去L，得：,整理得近似值 的事后估计式：,由前面讨论知:,由此得下列艾特肯迭加公式：,校正,再校正,改进,例：用艾特肯方法求解方程：x3-x-1=0在x=1.5附近的根,解：,用公式xk+1=x3k -1,校正,再校正,改进,仍取x0=1.5，经过5次迭代，得：x5=1. 32472(收敛),由上例可看到，艾特肯方法，将一个原本发散的过程改造成了一个迭代收敛的过程。,作业：P34 4、5,求方程x3+x=2x2+3在x0=4附近的根。 解：函数(x)=x3-2x2+x-3写成嵌套形式 (x)=x3-2x2+x-3=(x-2)x+1)x-3 (x)=3x2-4x+1=(3x-4)