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

《非线性方程迭代法省公共课一等奖全国赛课获奖课件.pptx》由会员分享，可在线阅读，更多相关《非线性方程迭代法省公共课一等奖全国赛课获奖课件.pptx（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、非线性方程迭代法非线性方程迭代法邹昌文邹昌文 第1页迭代法迭代法 /Fixed-Point Iteration/f(x)=0 x=g(x)等价变换等价变换f(x)根根g(x)不动点不动点思思绪绪从一个初值从一个初值 x0 出发，计算出发，计算 x1=g(x0),x2=g(x1),xk+1=g(xk),若若 收敛，即存在收敛，即存在 x*使得使得 ，且，且 g 连续，则由连续，则由 可可知知 x*=g(x*)，即，即x*是是 g 不动点，也就是不动点，也就是f 根。根。迭代法几何意义以下迭代法几何意义以下第2页xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=g(x)y=g(x)y=g

2、(x)y=g(x)x0p0 x1p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p1第3页定理定理（充分条件）考虑方程（充分条件）考虑方程 x=g(x),g(x)Ca,b,若若(I)当当 x a,b 时，时，g(x)a,b；(II)0 L 1 使得使得|g(x)|L 1 对对 x a,b 成立。成立。则任取则任取 x0 a,b，由，由 xk+1=g(xk)得到序列得到序列 收敛于收敛于g(x)在在a,b上唯一不动点。而且有误差预计式：上唯一不动点。而且有误差预计式：(k=1,2,)且存在极限且存在极限第4页证实：证实：g(x)在在a,b上存在不动点？上存在不动点？令令有根有根 不动点

3、唯一？不动点唯一？反证：若不然，设还有反证：若不然，设还有 ，则，则在在和和之间。之间。而而 当当k 时，时，xk 收敛到收敛到 x*？第5页 可用可用 来控来控制收敛精度制收敛精度L 越越 收敛越快收敛越快小小注注注注：定理条件非必要条件，可将定理条件非必要条件，可将a,b缩小，定义缩小，定义局部收局部收敛性敛性：若在：若在 x*某某 领域领域 B =x|x x*|有有 g C1a,b 且且|g(x*)|1，则由则由 x0 B 开始迭代收开始迭代收敛。即敛。即调整初值可得到收敛结果。调整初值可得到收敛结果。第6页 设在区间设在区间 a a,b b 上方程上方程 x=x=(x x)有根有根x

4、x*,且对一且对一切切x xa a,b b 都有都有|(x(x)|1)|1，则对于该区间上任意，则对于该区间上任意x x0 0(x x*),),迭代公式迭代公式x xk k+1+1=(x xk k)一定发散。一定发散。证实证实:不可能收敛于不可能收敛于0 0。定理定理第7页改进、加速收敛改进、加速收敛 /accelerating convergence/待定参数法：待定参数法：若若|g(x)|1，则将则将 x=g(x)等价地改造为等价地改造为求求K，使得，使得例：例：求求 在在(1,2)实根。实根。假如用假如用 进行迭代，则在进行迭代，则在(1,2)中有中有现令现令希望希望，即，即在在 (1,

5、2)上可取任意上可取任意 ，比如，比如K=0.5，则则对应对应 即产生收敛序列。即产生收敛序列。第8页 Aitken 加速：加速：xyy=xy=g(x)x*x0P(x0,x1)x1x2P(x1,x2)普通地，有：普通地，有：比比 收敛得略快。收敛得略快。Steffensen 加速：加速：详见详见P273P273第9页定理定理 （牛顿法收敛充分条件牛顿法收敛充分条件）设）设 f C2a,b，若，若(1)f(a)f(b)0；则则Newtons Method产生序列产生序列 xk 收敛到收敛到f(x)在在 a,b 唯唯一根。一根。有根有根根唯一根唯一产生序列单调有界，产生序列单调有界，确保收敛。确保

6、收敛。定理定理 （局部收敛性局部收敛性）设）设 f C2a,b，若，若 x*为为 f(x)在在a,b上根，且上根，且 f(x*)0，则存在，则存在 x*邻域邻域 使得任取初值使得任取初值 ，Newtons Method产生序列产生序列 xk 收敛到收敛到x*，且满足，且满足第10页证实：证实：Newtons Method 实际上是一个特殊不动点迭代实际上是一个特殊不动点迭代 其中其中 ，则，则收敛收敛由由 Taylor 展开：展开：只要只要 f(x*)0，则令，则令 可得结论。可得结论。在在单根单根/simple root/附近收敛快附近收敛快 第11页牛顿迭代法改进与推广牛顿迭代法改进与推广

7、 重根重根 /multiple root/加速收敛法：加速收敛法：Q1:若若 ，Newtons Method 是否仍收敛？是否仍收敛？设设 x*是是 f n 重根，则：重根，则：且且 。因为因为 Newtons Method 实际上是一个特殊不动点迭代，实际上是一个特殊不动点迭代，其中其中 ，则，则A1:有局部收敛性，但重数有局部收敛性，但重数 n 越高，收敛越慢。越高，收敛越慢。Q2:怎样加速重根收敛？怎样加速重根收敛？A2:将求将求 f 重根转化为求另一函数单根。重根转化为求另一函数单根。令，则令，则 f 重根重根=单根。单根。第12页 正割法正割法 /Secant Method/：New

8、tons Method 一步要计算一步要计算 f 和和 f，相当于，相当于2个函数值，个函数值，比较费时。现用比较费时。现用 f 值近似值近似 f，可少算一个函数值。，可少算一个函数值。x0 x1切线切线/tangent line/割线割线/secant line/切线斜率切线斜率 割线斜率割线斜率需要需要2个初值个初值 x0 和和 x1。收敛比收敛比Newtons Method 慢，慢，且对初值要求一样高。且对初值要求一样高。第13页 下山法下山法 /Descent Method/Newtons Method 局部微调：局部微调：原理：原理：若由若由 xk 得到得到 xk+1 不能使不能使|

9、f|减小，则在减小，则在 xk 和和 xk+1 之之间找一个更加好点间找一个更加好点 ，使得，使得 。xkxk+1注：注：注：注：=1 时就是时就是Newtons Method 公式。公式。当当 =1 代入效果不好时，将代入效果不好时，将 减半计算。减半计算。第14页 求复根求复根 /Finding Complex Roots/Newton 公式中自变量能够是复数公式中自变量能够是复数记记 z=x+i y,z0 为初值，一样有为初值，一样有设设代入公式，令实、虚部对应相等代入公式，令实、虚部对应相等，可得，可得第15页迭代法收敛阶迭代法收敛阶 /Order of Convergence/设迭代

10、设迭代 xk+1=g(xk)收敛到收敛到g(x)不动点不动点 x*。设设 ek=xk x*，若，则称该迭代为若，则称该迭代为p 阶收敛阶收敛，其中其中 C 称为称为渐进误差常数渐进误差常数。/xk converges to x*of order p,with asymptotic error constant C 0/普通普通 Fixed-Point Iteration 有有 ，称为，称为线线 性收敛性收敛/linear convergence/，这时，这时 p=1，0 C 1。比如比如 xn=1/nn 超线性收敛到超线性收敛到0，但对任何，但对任何 p 1 都没有都没有 p 阶收敛。阶收敛。

11、Aitken 加速有加速有 。称为称为超线性收敛超线性收敛 /superlinear convergence/。第16页 Steffensen 加速加速有有 p=2，条件是，条件是 ，称为，称为平方收敛平方收敛 /quadratic convergence/。Newtons Method 有有 ，只要，只要 ，就有就有 p 2。重根是线性收敛。重根是线性收敛。Q:怎样实际确定收敛阶和怎样实际确定收敛阶和渐进误差常数渐进误差常数？定理定理 设设 x*为为x=g(x)不动点不动点，若，若 ，p 2；，且，且 ，则，则 xk+1=g(xk)在在 内内 p 阶收敛。阶收敛。证实：证实：x*k C详见详

12、见P271第17页第18页第19页第20页 一个迭代法含有实用价值，首先要求它是收敛，一个迭代法含有实用价值，首先要求它是收敛，其次还要求它收敛得比较快。其次还要求它收敛得比较快。设迭代过程设迭代过程 收敛于收敛于 根根 ,记记迭代误差迭代误差若存在常数若存在常数p p（p p11）和）和c c（c c00），使），使 则称序列则称序列 是是p p 阶收敛阶收敛,c c称渐近误差常数。尤其地称渐近误差常数。尤其地,p p=1=1时称为线性收敛时称为线性收敛,p p=2=2时称为平方收敛。时称为平方收敛。11p p22时称时称为超线性收敛。为超线性收敛。迭代法收敛阶迭代法收敛阶/Order of Convergence/第21页 数数p p大小反应了迭代法收敛速度快慢，大小反应了迭代法收敛速度快慢，p p愈大，则收愈大，则收敛速度愈快，故迭代法收敛阶是对迭代法收敛速度敛速度愈快，故迭代法收敛阶是对迭代法收敛速度一个度量。一个度量。第22页