加载中…
常用算法之迭代法
(2006-10-31 13:39:22)| 分类： 数学工具 |
|
原文见数值分析课 一.不动点迭代法
据此建立迭代公式
迭代初值仍取x0 =1.5 则有x1 =2.375,x2 =12.39继续迭代下去没有必要。 由连续函数性质可知存在x*∈(a,b)使f(x*)=0即x* =ψ(x*), x*即为的不动点 再证唯一性。设http://sxyd.sdut.edu.cn/shuzhifenxi/images/pic8.2/8_208.gif ∈[a,b]都是ψ(x)的不动点,则由(2.4)得: 引出矛盾，故ψ(x)的不动点只能是唯一的。 在ψ(x)的不动点存在唯一的情况下,可得到迭代法(2.2)收敛的一个充分条件。 证明：设x∈[a,b]是ψ(x)在[a,b]上的唯一不动点，由条件1 可知xk∈[a,b],再有(2.4)得 因0<L<1,故当k→∞时序列{xk}收敛到x* 下面再证估计式(2.5),由(2.4)有 据此反复递推得 于是对任意正整数p有 在上式令p→∞,注意到 http://sxyd.sdut.edu.cn/shuzhifenxi/images/pic8.2/8_215.gif即得式(2.5),证毕. 定义1 设ψ(x)有不动点x* ,如果存在x* 的某个邻域R:|x -x* |≤δ对任意x0∈R，迭代(2.2)产生的序列{xk}∈R,且收敛到x*,则称迭代法(2.2)局部收敛. 定理3 设x* 为ψ(x)的不动点，ψ′(x)在x* 的某个邻域连续，且|ψ′(x*)|＜1,则迭代法(2.2)局部收敛. 证明： 由连续函数的性质，存在x* 的某个邻域R:|x-x* |≤δ, 使对于任意x∈R成立: 故对于任意x,y∈R有： 此外，对于任意x∈R，总有ψ(x)∈R成立，这是因为 于是依照定理2可以判定迭代过程xk+1=ψ(x k), 对于任意初值x0 ∈R均收敛。证毕. 下面讨论迭代序列的收敛速度问题。先看例. 例4 用不同方法求方程x2 -3=0的根http://sxyd.sdut.edu.cn/shuzhifenxi/images/pic8.2/8_217.gif 解：这里f(x)=x2 -3=0,可改写为各种不同的等价形式x=ψ(x)，
从图中看出迭代过程在根的两边摆动。
从图中看出迭代法收敛.
从图中看出迭代法收敛. 取x0=2，对上述4种迭代法，计算三步所得的结果如下表。 注意http://sxyd.sdut.edu.cn/shuzhifenxi/images/pic8.2/8_227.gif= 1.7320508…，从计算结果看到迭代法(1)及(2)均不收敛，且它们均不满足定理3中的局部收敛条件，迭代法(3)和(4)均满足局部收敛条件，且迭代法(4)比(3)收敛快。 因为迭代法(4)中ψ′(x*)=0。为了衡量迭代法(2.2)收敛速度的快慢可给出以下定义。 定义2 设迭代过程xk+1 =ψ(xk)收敛于方程x=ψ(x)的根 x* ,如果迭代误差ek =xk -x*当k→∞时成立下列渐进关系式 则称该迭代过程是P阶收敛的。特别P=1时称线性收敛，P=2时称平方收敛，P>1时称超线性收敛。 定理4 对于迭代过程xk+1=ψ(xk)，如果ψ(p)(x)在所求根x* 的邻域连续，并且 则该迭代过程在点x* 邻近是p阶收敛的。 对于收敛的迭代过程，只要迭代足够多次,就可以使结果达到任意精度，但有时迭代收敛过程收敛缓慢，从而使计算量变的很大,因此迭代过程的加速是个重要课题。 设x0是根x*的某个近似值，用迭代公式校正一次得x1=ψ(x0)，而由微分中值定理，有 其中ξ介于x* 与x0之间 假定ψ′(x)改变不大，近似的取某个近似值L，则有 若将校正值x1=ψ(x0)，再校正一次，又得 x2=ψ(x1)，由于 将它与(2.9)式联立，消去未知的L，有 由此推知 在计算了x1及x2 之后，可用上式右端作为x*的新近似，记作http://sxyd.sdut.edu.cn/shuzhifenxi/images/pic8.2/8_233.gif，一般情况是由xk计算xk+1 ,xk+2 ，记 (2.10)称为埃特金(AitKen)Δ2加速法。 可以证明 它表明序列 http://sxyd.sdut.edu.cn/shuzhifenxi/images/pic8.2/8_2351.gif的收敛速度比{xk}的收敛快。 埃特金方法不管原序列{xk}是怎样产生的，对{xk}进行加速计算， 得到序列http://sxyd.sdut.edu.cn/shuzhifenxi/images/pic8.2/8_2351.gif。如果把埃特金加速技巧与不动点迭代结合,则可得到如下的迭代方法： 称为斯蒂芬森(steffensen)迭代法. 它可以这样理解，我们要求x=ψ(x)的根值x* ，令ε(x)=ψ(x)-x,ε(x* )=ψ(x* )-x* =0,已知x*的近似值xk 及yk , 其误差分别为 把误差ε(x)“外推到零”，即过(xk ,ε(xk ))及(yk ,ε(yk ))两点做线性插值函数，它与x轴交点就是(2.11)中xk+1 , 即方程: 的解 实际上(2.11)是将不动点迭代法(2.2)计算两步合并成一步得到的，可将他写成另一不动点迭代 其中 对不动点迭代(2.13)有以下局部收敛性定理。 定理5 若x* 为(2.13)定义的迭代函数φ(x)的不动点, 则x* 为ψ(x)的不动点。反之，若x* 为ψ(x)的不动点，设ψ″(x)存在,ψ′(x*)≠1，则x*是φ(x)的不动点，且斯蒂芬森迭代法(2.11)是2阶收敛的。
计算表明它是收敛的，这说明即使迭代法(2.2)不收敛，用斯蒂芬森迭代法(2.11)仍可能收敛。 例6 求方程3x2-ex =0在[3,4]中的解. 解：由方程得 ex=3x2 , 取对数得 若构造迭代法 且当x∈[3,4]时,ψ(x)∈[3,4]，根据定理2此迭代法是收敛的。若取x0=3.5, 迭代16次得x16=3.73307,六位有效数字。
这里计算2步(相当于(2.2)迭代4步)结果与x16相同, 说明用迭代法 (2.11)的收敛速度比迭代法(2.2)快得多。 |
喜欢
0
赠金笔