数值分析二分法迭代法及收敛性.pptx

《数值分析二分法迭代法及收敛性.pptx》由会员分享，可在线阅读，更多相关《数值分析二分法迭代法及收敛性.pptx（31页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、n=1,2时方程的根是大家熟悉的，时方程的根是大家熟悉的，n=3,4时虽有求时虽有求根公式但比较复杂，可在数学手册中查到，但已不适根公式但比较复杂，可在数学手册中查到，但已不适合数值计算，而合数值计算，而n5时就不能用公式表示方程的根时就不能用公式表示方程的根.因因此，通常对此，通常对n3的多项式方程求根与一般连续函数方的多项式方程求根与一般连续函数方程程(1.1)一样都可采用迭代法求根一样都可采用迭代法求根.第1页/共31页方程方程f(x)=0的的根根 x*，又称为函数又称为函数f(x)的的零点零点，它使得，它使得f(x*)=0，若，若f(x)可分解为可分解为f(x)=(x-x*)mg(x)

2、，其中其中m为正整数，且为正整数，且g(x*)0.当当m=1时，则称时，则称x*为为单根单根，若若m1称称x*为为(1.1)的的m重根重根，或，或x*为函数为函数f(x)的的m重零重零点点.若若x*是是f(x)的的m重零点重零点，则，则注：第2页/共31页3.1.2 3.1.2 二分法二分法如果如果 f(x)在区间在区间a,b上连续上连续,f(a)f(b)0,则在则在a,b 内有方程的根内有方程的根.（Bisection Method）二分法原理第3页/共31页二分法的实施过程二分法的实施过程取取a,b的中点的中点 将区间一分为二将区间一分为二.若若 f(x0)=0,则则x0就是方程的根就是方

3、程的根,否则判别根否则判别根 x*在在 x0 的的左侧左侧还是还是右侧右侧.若若f(a)f(x0)0,则则x*(a,x0),令令 a1=a,b1=x0;若若f(x0)f(b)0,则则x*(x0,b),令令 a1=x0,b1=b.不论出现哪种情况不论出现哪种情况,(a1,b1)均为新的有根区间均为新的有根区间,它它的的长度只有原有根区间长度的一半长度只有原有根区间长度的一半,达到了达到了压缩有根压缩有根区间的目的区间的目的.第4页/共31页如此反复进行如此反复进行,即可的一系列即可的一系列有根区间套有根区间套 由于每一区间都是前一区间的一半，因此区间由于每一区间都是前一区间的一半，因此区间an,

4、bn的长度为的长度为若每次二分时所取区间中点都不是根，则上述过程将若每次二分时所取区间中点都不是根，则上述过程将无限进行下去无限进行下去.当当 n 时，区间必将最终收缩为一时，区间必将最终收缩为一点点x*，显然，显然 x*就是所求的就是所求的根根.第5页/共31页 若取区间an,bn的中点作为x*的近似值，则有下述误差估计式误差估计式只要只要 n 足够大足够大,(即区间二分次数足够多即区间二分次数足够多)，误差就可，误差就可足够小足够小.二分法的误差估计二分法的误差估计第6页/共31页例例1 用二分法求方程用二分法求方程 f(x)=x3-x-1=0在在(1,1.5)的实根的实根,要要求误差不超

5、过求误差不超过0.005.解解 由题设条件，即：由题设条件，即：则要|x*-xn|0.005由此解得由此解得 取取 n=6,按二分法计算过程见下按二分法计算过程见下表表,x6=1.3242 为所求之近似根为所求之近似根.第7页/共31页n an bn xn f(xn)说明说明01234561.01.251.251.31251.31251.31251.32031.51.51.3751.3751.34381.32811.32811.251.3751.31251.34381.32811.32031.3242-+-+-(1)f(a)0(2)根据精根据精 度要求，度要求，取到小数取到小数点后四位点后四位

6、 即可即可.二分法的优点是算法简单，且总是收敛的，缺点是收敛的太慢，故一般不单独将其用于求根，只是用其为根求得一个较好的近似值.第8页/共31页二分法的计算步骤:步骤1 准备 计算函数f(x)在区间a,b端点处的值f(a),f(b).若若f(a)f(a+b)/2)0,则以则以(a+b)/2代替代替b，否则以，否则以(a+b)/2代替代替a.步骤2 二分 计算函数f(x)在区间中点(a+b)/2处的值f(a+b)/2).步骤3 判断 若f(a+b)/2)=0，则(a+b)/2即是根，计算过程结束，否则检验.反复执行步骤反复执行步骤2和步骤和步骤3，直到区间，直到区间a,b长度小于长度小于允许误差

7、允许误差，此时中点，此时中点(a+b)/2即为所求近似根即为所求近似根.第9页/共31页3.2 迭代法及其收敛性迭代法及其收敛性3.2.1 不动点迭代法 将方程 f(x)=0 改写为等价方程形式 x=(x).(2.1)若要求 x*满足 f(x*)=0，则 x*=(x*)；反之亦然，称 x*为函数(x)的一个不动点不动点.求 f(x)的零点零点就等于求(x)的不动点不动点，选择一个初始近似值 x0，将它代入(2.1)右端，即可求得 x1=(x0).第10页/共31页可以如此反复迭代计算 xk+1=(xk)(k=0,1,2,).(2.2)(x)称为迭代函数称为迭代函数.如果对任何如果对任何x0a,

8、b，由，由(2.2)得得到的序列到的序列xk有极限有极限则称迭代方程则称迭代方程(2.2)收敛收敛.且且x*=(x*)为为(x)的的不动点不动点，故称故称(2.2)为为不动点迭代法不动点迭代法.第11页/共31页当(x)连续时，显然x*就是方程 x=(x)之根(不动点).于是可以从数列xk中求得满足精度要求的近似根.这种求根方法称为不动点迭代法,称为迭代格式,(x)称为迭代函数,x0 称为迭代初值,数列xk称为迭代序列.如果迭代序列收敛,则称迭代格式收敛,否则称为发散.第12页/共31页分别按以上三种形式建立迭代公式，并取分别按以上三种形式建立迭代公式，并取x0=1进行进行迭代计算，结果如下：

9、迭代计算，结果如下：解 对方程进行如下三种变形：例例2 用迭代法求方程用迭代法求方程x4+2x2-x-3=0 在区间在区间1,1.2内内的实根的实根.第13页/共31页准确根准确根 x*=1.124123029,可见可见迭代公式不同迭代公式不同,收敛情收敛情况也不同况也不同.第二种公式比第一种公式收敛快得多第二种公式比第一种公式收敛快得多,而而第三种公式第三种公式不收敛不收敛.第14页/共31页xyoy=(x)y=x解x=(x)求 y=x 与y=(x)的交点的横坐标x*x0(x0,x1)(x1,x2)(x1,x1)x1x2迭代法的几何意义第15页/共31页xyy=xxyy=xxyy=xxyy=

10、xx*x*x*x*y=(x)y=(x)y=(x)y=(x)x0p0 x1p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p1第16页/共31页注：迭代法的研究涉及四个问题：注：迭代法的研究涉及四个问题：(1)(1)迭代公式的选取；迭代公式的选取；(2)(2)迭代公式收敛性的判定；迭代公式收敛性的判定；(3)(3)在收敛情况下，如何比较收敛速度；在收敛情况下，如何比较收敛速度；(4)(4)迭代停止的条件。迭代停止的条件。第17页/共31页3.2.2 3.2.2 不动点的存在性与迭代法的收敛性不动点的存在性与迭代法的收敛性 首先考察(x)在a,b上不动点的存在唯一性.定理定理1 1 设(

11、x)Ca,b满足以下两个条件：1 对任意对任意xa,b有有a(x)b.2 存在正数存在正数La及(b)0,f(b)=(b)-b0,由连续函数性质可知存在由连续函数性质可知存在 x*(a,b)使使 f(x*)=0，即即x*=(x*)，x*即为即为(x)的不动点的不动点.再证不动点的唯一性唯一性.设x1*,x2*a,b都是(x)的不动点，则由(2.4)得引出矛盾，故(x)的不动点只能是唯一的.证毕证毕.第19页/共31页 定理定理2 2 设(x)Ca,b满足定理1中的两个条件，则对任意x0a,b，由(2.2)得到的迭代序列xk收敛到不动点x*，并有误差估计式误差估计式 证明证明 设设x*a,b是是

12、(x)在在a,b上的唯一不动点上的唯一不动点,由条件由条件1，可知，可知xka,b，再由，再由(2.4)得得因因0L1时称时称超线性收敛超线性收敛，p=2 时称时称平方收敛平方收敛.第29页/共31页 定理定理4 4 对于迭代过程 xk+1=(xk)，如果(p)(x)在所求根 x*的邻近连续（p 1），并且则该迭代过程在则该迭代过程在 x*的邻近是的邻近是 p 阶收敛的阶收敛的.证明证明 由于(x*)=0，根据定理3立即可以断定迭代过程xk+1=(xk)具有局部收敛性.再将再将(xk)在根在根x*处做泰勒展开处做泰勒展开,利用条件利用条件(2.8),则有则有注意到注意到(xk)=xk+1，(x*)=x*，由上式得，由上式得第30页/共31页感谢您的观看。第31页/共31页