非线性方程迭代解法yjs省公共课一等奖全国赛课获奖课件.pptx

第第7 7章章 非线性方程迭代解法非线性方程迭代解法1根存在性。方程有没有根？假如有根，有几个根？根存在性。方程有没有根？假如有根，有几个根？2这些根大致在哪里？怎样把根隔离开来？这些根大致在哪里？怎样把根隔离开来？3根准确化根准确化本章介绍求解非线性方程本章介绍求解非线性方程 f(x)=0 几个常见和有效数几个常见和有效数值方法值方法.其中其中(x x)是高次多项式函数或超越函数是高次多项式函数或超越函数.如如 (x)=3)=3x5 5-2-2x4 4+8+8x2 2-7-7x+1+1 (x)=e)=e2 2x+1+1-xln(sinln(sinx)-2)-2等等等等.1科大硕士学位课程 数值分析第1页7.1 7.1 根搜索与二分法根搜索与二分法求非线性方程求非线性方程 确定方程有根区间确定方程有根区间 计算根近似值计算根近似值f(x)=0根方法根方法分为两步：分为两步：2科大硕士学位课程 数值分析第2页首先确定有限区间：依据零点定理。首先确定有限区间：依据零点定理。设设 ，且，且 ，则方，则方程程 在区间在区间 上最少有一个根。假上最少有一个根。假如如 在在 上恒正或恒负，则此根唯上恒正或恒负，则此根唯一。一。3科大硕士学位课程 数值分析第3页等步长扫描法求有根区间 用计算机求有根区间：等步长扫描法。设h0是给定步长，取x0=a,x1=a+h，若f(x0)*f(x1)b 则扫描失败。再将h 缩小，继续以上步骤。4科大硕士学位课程 数值分析第4页等步长扫描算法等步长扫描算法 算法：（求方程算法：（求方程 f(x)=0 有根区间）有根区间）(1)输入输入 a,b,h；(2)f0=f(a)；(3)x=a+h,f1=f(x),若若xb 输出失败信息，停机。输出失败信息，停机。(4)若若 f1=0 ,输出输出 x，已算出方程一个根，停机。，已算出方程一个根，停机。(5)若若 f0 f1 0 .输出输出 a,x,a,x 为有根区间，停机为有根区间，停机(6)a=x，转，转 3）注：假如对足够小步长注：假如对足够小步长h扫描失败。说明：扫描失败。说明：在在 a,b 内无根内无根在在 a,b 内有偶重根内有偶重根详细看书上详细看书上Matlab程序程序P148看例看例7.15科大硕士学位课程 数值分析第5页用二分法用二分法(将区间对平分将区间对平分)求解。求解。令令a1=a,b1=b,c1=(a1+b1)/2 若若 f(a1)f(c1)0，则，则 a1,c1 为有根区间，为有根区间，不然不然 c1,b1 为有根区间为有根区间 记新有根区间为记新有根区间为 a2,b2，则则a1,b1 包含包含a2,b2，且，且 b2-a2=(a1+b1)/2 二二二二 分分分分 法法法法对对 a2,b2 重复上述做法得重复上述做法得 6科大硕士学位课程 数值分析第6页 设设 所求根为所求根为 x*，则，则 即即 取取 为为 x*近似解近似解 二二二二 分分分分 法法法法7科大硕士学位课程 数值分析第7页求方程求方程f(x)=0根二分法算法根二分法算法(2)置置x:=(a+b)/2,(3)若若f(x)=0，输出，输出x，停算；不然，转步，停算；不然，转步(4);(4)若若f(a)f(b)0，则置，则置b:=x；不然，置；不然，置a:=x;(5)置置x:=(a+b)/2,若若|b-a|,输出输出x，停算，不然，转，停算，不然，转步步(3).参看教材程序参看教材程序P1508科大硕士学位课程 数值分析第8页误差误差 分析：分析：第第1步产生步产生有误差有误差第第 k 步产生步产生 xk 有误差有误差对于给定精度对于给定精度 ,可预计二分法所需步数可预计二分法所需步数 k：简单简单;对对f(x)要求不高要求不高(只要连续即可只要连续即可).无法求复根及偶重根无法求复根及偶重根 收敛慢收敛慢 注：注：注：注：用二分法求根，最好先给出用二分法求根，最好先给出 f(x)草图以确定根大约位草图以确定根大约位置。或用搜索程序，将置。或用搜索程序，将a,b分为若干小区间，对每一个满分为若干小区间，对每一个满足足 f(ak)f(bk)0 区间调用二分法程序，可找出区间区间调用二分法程序，可找出区间a,b内多个根，且无须要求内多个根，且无须要求 f(a)f(b)0。9科大硕士学位课程 数值分析第9页7.2 简单迭代法及其加速简单迭代法及其加速f(x)=0 x=(x)等价变换等价变换f(x)根根(x)不动点不动点思思绪绪从一个初值从一个初值 x0 出发，计算出发，计算 x1=(x0),x2=(x1),xk+1=(xk),若若 收敛，即存在收敛，即存在 x*使使得得 ，且，且 连续，则由连续，则由 可可知知 x*=(x*)，即，即x*是是 不动点，也就是不动点，也就是f 根。根。10科大硕士学位课程 数值分析第10页迭代法需处理三个问题迭代法需处理三个问题迭代函数结构迭代函数结构由迭代函数产生解序列收敛性由迭代函数产生解序列收敛性序列收敛速度和误差预计序列收敛速度和误差预计11科大硕士学位课程 数值分析第11页迭代法几何意义 交点横坐标 y=xy=(x)12科大硕士学位课程 数值分析第12页 例1 试用迭代法求方程 在区间(1，2)内实根。解：由 建立迭代关系 k=0,1,2,3.计算结果以下:准确到小数点后五位13科大硕士学位课程 数值分析第13页但假如由 建立迭代公式 仍取 ，则有 ，显然结果越来越大，是发散序列.14科大硕士学位课程 数值分析第14页xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=(x)y=(x)y=(x)y=(x)x0p0 x1p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p115科大硕士学位课程 数值分析第15页定理定理考虑方程考虑方程 x=(x),(x)C1a,b,若若(I)当当 x a,b 时，时，(x)a,b；(II)0 L 1 使得使得|(x)|L 1 对对 x a,b 成成立。立。则任取则任取 x0 a,b，由，由 xk+1=(xk)得到序列得到序列 收收敛于敛于(x)在在a,b上唯一不动点。而且有误差预计式：上唯一不动点。而且有误差预计式：(k=1,2,)且存在极限且存在极限k16科大硕士学位课程 数值分析第16页证实：证实：(x)在在a,b上存在不动点？上存在不动点？令令有根有根 不动点唯一？不动点唯一？反证：若不然，设还有反证：若不然，设还有 ，则则在在和和之间。之间。而而 当当k 时，时，xk 收敛到收敛到 x*？17科大硕士学位课程 数值分析第17页 可用可用 来来控制收敛精度控制收敛精度L 越越 收敛越快收敛越快小小注注注注：定理条件非必要条件，可将定理条件非必要条件，可将a,b缩小，定义缩小，定义局部收局部收敛性敛性：若在：若在 x*某某 领域领域 B =x|x x*|有有(x)C1a,b 且且|(x*)|1，则由则由 x0 B 开始开始迭代收敛。即迭代收敛。即调整初值可得到收敛结果。（局部收敛调整初值可得到收敛结果。（局部收敛性）性）18科大硕士学位课程 数值分析第18页迭代过程收敛速度迭代过程收敛速度 设由某方法确定序列设由某方法确定序列xk收敛于方程根收敛于方程根x*，假如存在正实数假如存在正实数p，使得，使得（C C为非零常数）为非零常数）定义：定义：则称序列则称序列xk收敛于收敛于x*收敛速度是收敛速度是p阶阶，或称该方法，或称该方法含有含有p 阶敛速。称阶敛速。称C C为为渐进常数渐进常数。当。当p=1时，称该方法为时，称该方法为线性（一次）收敛；当线性（一次）收敛；当p=2时，称方法为平方（二次）收敛；时，称方法为平方（二次）收敛；当当1 p 2时，称方法为超线性收敛。时，称方法为超线性收敛。19科大硕士学位课程 数值分析第19页Q:怎样实际确定收敛阶和怎样实际确定收敛阶和渐进误差常数渐进误差常数？定理定理 设设 x*为为x=(x)不动点不动点，若，若 ，p 2；，且，且 ，则，则 xk+1=(xk)在在 内内 p 阶收敛。阶收敛。证实：证实：x*k C20科大硕士学位课程 数值分析第20页改进、加速收敛改进、加速收敛 待定参数法：待定参数法：若若|(x)|1，则将则将 x=(x)等价地改造等价地改造为为求求K，使得，使得例：例：求求 在在(1,2)实根。实根。假如用假如用 进行迭代，则在进行迭代，则在(1,2)中有中有现令现令希望希望，即，即在在 (1,2)上可取任意上可取任意 ，比如，比如K=0.5，则则对应对应 即产生收敛序列。即产生收敛序列。21科大硕士学位课程 数值分析第21页 松弛松弛加速：加速：dwww+=-+=+-)()(,)()1(*21*1*1*kkkkkkkkkkkxfxfxxxxxxxxx条件下成立条件下成立确保以下不等式在一定确保以下不等式在一定以这类推。引入松弛因子以这类推。引入松弛因子修正计算修正计算再对再对修正，并计算修正，并计算作为作为把把，令，令选取适当松弛因子选取适当松弛因子22科大硕士学位课程 数值分析第22页 Aitken 加速：加速：xyy=xy=(x)x*x0P(x0,x1)x1x2P(x1,x2)普通地，有：普通地，有：比比 收敛得略快。收敛得略快。23科大硕士学位课程 数值分析第23页 Steffensen（斯蒂芬森）（斯蒂芬森）加速：加速：其实是将原不动点迭代计算两次合并成一步得到，其实是将原不动点迭代计算两次合并成一步得到，可改为另一个不动点迭代法可改为另一个不动点迭代法:将将Aitken（埃特金）加速与不动点迭代结合（埃特金）加速与不动点迭代结合.可得到可得到以下迭代法以下迭代法:24科大硕士学位课程 数值分析第24页定理定理 若若x*为上式定义函数为上式定义函数g(x)不动点，则不动点，则x*为为(x)不不动点动点.反之，若反之，若x*是是(x)不动点，设不动点，设(x)存在存在,(x*)0，则，则x*是是(x)不动点且不动点且斯蒂芬森斯蒂芬森迭代法是迭代法是二阶收敛二阶收敛.(.(证实略）证实略）25科大硕士学位课程 数值分析第25页例2 试用Steffensen算法求解方程解法一、取 ，由 n=0，1，2，取初值x0=1.5，计算结果以下：nxnynzn01.51.3572088081.33086095911.3248991811.3247523791.32472449621.3247179571.3247179571.32471795726科大硕士学位课程 数值分析第26页解法二、取解法二、取 ，对于该迭代函数在普通迭代法中是发散，而对于该迭代函数在普通迭代法中是发散，而Steffensen格格式却是收敛。式却是收敛。n=0，1，2，取初值取初值x0=1.5，计算结果以下：，计算结果以下：nxnynzn01.52.3751.23964843711.4162929751.8409219155.23887276921.3556504421.4913982792.31727069931.3289487771.3470628831.44435122441.3248044891.3251735441.32711728151.3247179441.3247181521.32471898061.32471795727科大硕士学位课程 数值分析第27页Steffensen迭代格式几何解释 28科大硕士学位课程 数值分析第28页Steffensen迭代算法 程序见p159。29科大硕士学位课程 数值分析第29页7.3 惯用迭代法惯用迭代法牛顿法牛顿法原理：原理：将非线性方程线性化将非线性方程线性化 Taylor 展开展开取取 x0 x*，将将 f(x)在在 x0 做一阶做一阶Taylor展开展开:，在在 x0 和和 x 之间。之间。将将(x*x0)2 看成高阶小量，则有：看成高阶小量，则有：线性线性/*linear*/xyx*x0只要只要 f C1，每一步迭代都有，每一步迭代都有f(xk)0，而且而且 ，则，则 x*就是就是 f 根。根。30科大硕士学位课程 数值分析第30页定理定理 （收敛充分条件收敛充分条件）设）设 f C2a,b，若，若(1)f(a)f(b)0；则则Newtons Method产生序列产生序列 xk 收敛到收敛到f(x)在在 a,b 唯唯一根。一根。有根有根根唯一根唯一产生序列单调有界，产生序列单调有界，确保收敛。确保收敛。定理定理 （局部收敛性局部收敛性）设）设 f C2a,b，若，若 x*为为 f(x)在在a,b上根，且上根，且 f(x*)0，则存在，则存在 x*邻域邻域 使得任取初使得任取初值值 ，Newtons Method产生序列产生序列 xk 收敛到收敛到x*，且满足，且满足31科大硕士学位课程 数值分析第31页证实：证实：Newtons Method 实际上是一个特殊不动点迭代实际上是一个特殊不动点迭代 其中其中 ，则，则收敛收敛由由 Taylor 展开：展开：只要只要 f(x*)0，则令，则令 可得结论。可得结论。在在单根单根/*simple root*/附近收敛快附近收敛快 32科大硕士学位课程 数值分析第32页Newtons Method 有有 ，只要，只要 就有就有 p 2。最少是二阶收敛。最少是二阶收敛。算法算法7.5（牛顿法牛顿法）(1)取初始点x0，最大迭代次数N和精度要求eps，置k:=0；(2)计算xk+1=xk-f(xk)/f(xk)(3)若|xk+1-xk|eps,则停算；(4)若k=N,则停算；不然，置k:=k+1,转步2.程序见程序见P161。33科大硕士学位课程 数值分析第33页例 用Newton法计算 。解：34科大硕士学位课程 数值分析第34页注：注：注：注：Newtons Method 收敛性依赖于收敛性依赖于x0 选取。选取。x*x0 x0 x035科大硕士学位课程 数值分析第35页牛顿牛顿法迭代公式法迭代公式q 牛顿法优点q 牛顿法是当前求解非线性方程(组)主要方法最少二阶最少二阶局部局部收敛，收敛速度较快，尤其是当迭收敛，收敛速度较快，尤其是当迭代点充分靠近准确解时。代点充分靠近准确解时。q 牛顿缺点l 对重根收敛速度较慢（线性收敛）对重根收敛速度较慢（线性收敛）l 对初值选取很敏感，要求初值相当靠近真解对初值选取很敏感，要求初值相当靠近真解在实际计算中，能够先用其它方法取得真解一个粗糙在实际计算中，能够先用其它方法取得真解一个粗糙近似，然后再用牛顿法求解。近似，然后再用牛顿法求解。36科大硕士学位课程 数值分析第36页改进与推广改进与推广 重根加速收敛法：重根加速收敛法：Q1:若若 ，Newtons Method 是否仍收敛？是否仍收敛？设设 x*是是 f n 重根，则：重根，则：且且 。因为因为 Newtons Method 实际上是一个特殊不动点迭代，实际上是一个特殊不动点迭代，其中其中 ，则，则A1:有局部收敛性，但重数有局部收敛性，但重数 n 越高，收敛越慢。越高，收敛越慢。Q2:怎样加速重根收敛？怎样加速重根收敛？A2:将求将求 f 重根转化为求另一函数单根。重根转化为求另一函数单根。令，则令，则 f 重根重根=单根。单根。37科大硕士学位课程 数值分析第37页改进与推广改进与推广Q3:怎样加速重根收敛？怎样加速重根收敛？A3:修改迭代函数，令修改迭代函数，令有，则改进后迭代法有，则改进后迭代法最少含有最少含有二阶收敛性二阶收敛性。38科大硕士学位课程 数值分析第38页 下山法（阻尼牛顿法）下山法（阻尼牛顿法）Newtons Method 局部微调：局部微调：原理：原理：若由若由 xk 得到得到 xk+1 不能使不能使|f|减小，则在减小，则在 xk 和和 xk+1 之之间找一个更加好点间找一个更加好点 ，使得，使得 。xkxk+1注：注：注：注：=1 时就是时就是Newtons Method 公式。公式。当当 =1 代入效果不好时，将代入效果不好时，将 减半计算。减半计算。改进与推广改进与推广39科大硕士学位课程 数值分析第39页 割线法：（割线法：（弦截法）弦截法）Newtons Method 一步要计算一步要计算 f 和和 f，相当于，相当于2个函数值，个函数值，比较费时。现用比较费时。现用 f 值近似值近似 f，可少算一个函数值。，可少算一个函数值。x0 x1切线切线/*tangent line*/割线割线/*secant line*/切线斜率切线斜率 割线斜率割线斜率需要需要2个初值个初值 x0 和和 x1。收敛比收敛比Newtons Method 慢，且对初值要求一样高。慢，且对初值要求一样高。40科大硕士学位课程 数值分析第40页 能够证实，弦截法含有超线性收敛，收敛阶约为能够证实，弦截法含有超线性收敛，收敛阶约为1.618，它与前面介绍普通迭代法一样都是线性化方，它与前面介绍普通迭代法一样都是线性化方法，但也有区分。即普通迭代法在计算法，但也有区分。即普通迭代法在计算xk+1+1时只用到前时只用到前一步值一步值xk，故称之为，故称之为单点单点迭代法；而弦截法在求迭代法；而弦截法在求xk+1时时要用到前两步结果要用到前两步结果xk-1-1和和xk，使用这种方法必须给出两，使用这种方法必须给出两个初始近似根个初始近似根x0 0,x1 1,这种方法称为这种方法称为多点多点迭代法迭代法。41科大硕士学位课程 数值分析第41页算法算法7.7（割线法割线法）(1)取初始点x0，最大迭代次数N和精度要求eps，置k:=0；(2)计算f(xk)及f(xk)xk+1:=xk-f(xk)(xk-xk-1)/(f(xk)-f(xk-1)(4)若|xk+1-xk|eps,则停算；(5)若k=N,则停算；不然，置xk-1:=xk,xk=xk+1,k:=k+1,转步2.程序见程序见P166。(3)置例例 用割线法解方程用割线法解方程 f(x)=xex-1=0.42科大硕士学位课程 数值分析第42页