非线性方程迭代法优秀PPT.ppt
非线性方程迭代法第一页，本课件共有22页迭代法迭代法 /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 的根。的根。迭代法几何意义如下迭代法几何意义如下第二页，本课件共有22页xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)x0p0 x1p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p1第三页，本课件共有22页定理定理（充分条件）考虑方程（充分条件）考虑方程 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,)且存在极限且存在极限第四页，本课件共有22页证明：证明：g(x)在在a,b上存在不动点？上存在不动点？令令有根有根 不动点唯一？不动点唯一？反证：若不然，设还有反证：若不然，设还有 ，则，则在在和和之间。之间。而而 当当k 时，时，xk 收敛到收敛到 x*？第五页，本课件共有22页 可用可用 来控来控制收敛精度制收敛精度L 越越 收敛越快收敛越快小小注注注注：定理条件非必要条件，可将定理条件非必要条件，可将a,b缩小，定义缩小，定义局部收敛局部收敛性性：若在：若在 x*的某的某 领域领域 B =x|x x*|有有 g C1a,b 且且|g(x*)|1，则由则由 x0 B 开始的迭代收开始的迭代收敛。即敛。即调整初值可得到收敛的结果。调整初值可得到收敛的结果。第六页，本课件共有22页 设在区间设在区间 a a,b b 上方程上方程 x=x=(x x)有根有根x 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。定理定理第七页，本课件共有22页改进、加速收敛改进、加速收敛 /accelerating convergence/待定参数法：待定参数法：若若|g(x)|1，则将则将 x=g(x)等价地改造为等价地改造为求求K，使得，使得例：例：求求 在在(1,2)的实根。的实根。如果用如果用 进行迭代，则在进行迭代，则在(1,2)中有中有现令现令希望希望，即，即在在 (1,2)上可取任意上可取任意 ，例如，例如K=0.5，则对则对应应 即产生收敛序列。即产生收敛序列。第八页，本课件共有22页 Aitken 加速：加速：xyy=xy=g(x)x*x0P(x0,x1)x1x2P(x1,x2)一般地，有：一般地，有：比比 收敛得略快。收敛得略快。Steffensen 加速：加速：详见详见P273P273第九页，本课件共有22页定理定理 （牛顿法收敛的充分条件牛顿法收敛的充分条件）设）设 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*，且满足，且满足第十页，本课件共有22页证明：证明：Newtons Method 事实上是一种特殊的不动点迭代事实上是一种特殊的不动点迭代 其中其中 ，则，则收敛收敛由由 Taylor 展开：展开：只要只要 f(x*)0，则令，则令 可得结论。可得结论。在在单根单根/simple root/附附近收敛快近收敛快 第十一页，本课件共有22页牛顿迭代法的改进与推广牛顿迭代法的改进与推广 重根重根 /multiple root/加速收敛法：加速收敛法：Q1:若若 ，Newtons Method 是否仍收敛？是否仍收敛？设设 x*是是 f 的的 n 重根，则：重根，则：且且 。因为因为 Newtons Method 事实上是一种特殊的不动点迭代，事实上是一种特殊的不动点迭代，其中其中 ，则，则A1:有局部收敛性，但重数有局部收敛性，但重数 n 越高，收敛越慢。越高，收敛越慢。Q2:如何加速重根的收敛？如何加速重根的收敛？A2:将求将求 f 的重根转化为求另一函数的单根。的重根转化为求另一函数的单根。令，则令，则 f 的重根的重根 =的单根。的单根。第十二页，本课件共有22页 正割法正割法 /Secant Method/：Newtons Method 一步要计算一步要计算 f 和和 f，相当于，相当于2个函数值，比个函数值，比较费时。现用较费时。现用 f 的值近似的值近似 f，可少算一个函数值。，可少算一个函数值。x0 x1切线切线/tangent line/割线割线/secant line/切线斜率切线斜率 割线斜率割线斜率需要需要2个初值个初值 x0 和和 x1。收敛比收敛比Newtons Method 慢，慢，且对初值要求同样高。且对初值要求同样高。第十三页，本课件共有22页 下山法下山法 /Descent Method/Newtons Method 局部微调：局部微调：原理：原理：若由若由 xk 得到的得到的 xk+1 不能使不能使|f|减小，则在减小，则在 xk 和和 xk+1 之间找一个更好的点之间找一个更好的点 ，使得，使得 。xkxk+1注：注：注：注：=1 时就是时就是Newtons Method 公式。公式。当当 =1 代入效果不好时，将代入效果不好时，将 减半计算。减半计算。第十四页，本课件共有22页 求复根求复根 /Finding Complex Roots/Newton 公式中的自变量可以是复数公式中的自变量可以是复数记记 z=x+i y,z0 为初值，同样有为初值，同样有设设代入公式，令实、虚部对应相等代入公式，令实、虚部对应相等，可得，可得第十五页，本课件共有22页迭代法的收敛阶迭代法的收敛阶 /Order of Convergence/设迭代设迭代 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 阶收敛。阶收敛。Aitken 加速有加速有 。称为称为超线性收敛超线性收敛 /superlinear convergence/。第十六页，本课件共有22页 Steffensen 加速加速有有 p=2，条件是，条件是 ，称为，称为平方收敛平方收敛 /quadratic convergence/。Newtons Method 有有 ，只要，只要 ，就有就有 p 2。重根是线性收敛的。重根是线性收敛的。Q:如何实际确定收敛阶和如何实际确定收敛阶和渐进误差常数渐进误差常数？定理定理 设设 x*为为x=g(x)的不动点的不动点，若，若 ，p 2；，且，且 ，则，则 xk+1=g(xk)在在 内内 p 阶收敛。阶收敛。证明：证明：x*k C详见详见P271第十七页，本课件共有22页第十八页，本课件共有22页第十九页，本课件共有22页第二十页，本课件共有22页 一种迭代法具有实用价值，首先要求它是收敛的，其一种迭代法具有实用价值，首先要求它是收敛的，其次还要求它收敛得比较快。次还要求它收敛得比较快。设迭代过程设迭代过程 收敛于收敛于 的根的根 ,记迭记迭代误差代误差若存在常数若存在常数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/第二十一页，本课件共有22页 数数p p的大小反映了迭代法收敛的速度的快慢，的大小反映了迭代法收敛的速度的快慢，p p愈大，愈大，则收敛的速度愈快，故迭代法的收敛阶是对迭代法则收敛的速度愈快，故迭代法的收敛阶是对迭代法收敛速度的一种度量。收敛速度的一种度量。第二十二页，本课件共有22页
