《数值分析3迭代法》课件.ppt

《数值分析》3 不动点迭代法 不动点迭代的收敛性 迭代序列的收敛速度 收敛加速的方法 构造有效的迭代格式 选取合适的迭代初值 对迭代格式进行收敛性分析 一种圆周率计算方案: 初值: x0=1 ( n=1,2,3,······ ) 迭代格式: 2/16 将一个计算过程反复进行称为迭代,迭代法是一类常见常用的计算技术 当M=45o时,求解开普列方程: E= M + e sinE e = 0.1~0.2, 迭代公式: Ej+1 = M + e sinEj (取E0 = M) e 迭代次数k E 0.1 7 0.86126488447271 0.12 8 0.87771162159335 0.14 8 0.89459166643904 0.16 9 0.91190566740348 0.18 9 0.92965233106520 0.2 9 0.94782822306545 3/16 例2.2 方程 x3 + 4x2 – 10 = 0 在 [1, 2] 上有一个根, 将方程变换成另一形式 (1) ( n = 0,1,2,……) (2) ( n = 0,1,2,……) 4/16 fi=inline(0.5*sqrt(10-x^3)); x0=1.5;er=1;k=0; while er0.00001 x=fi(x0); er=abs(x-x0); x0=x;k=k+1; end fi=inline(sqrt(10/(4+x))); x0=1.5;er=1;k=0; while er0.00001 x=fi(x0); er=abs(x-x0); x0=x;k=k+1; end k=16 x0=1.3652 k=6 x0=1.3652 5/16 x2 x1 x0 y = x f(x) = 0 迭代格式: ( n = 0, 1, 2, ······ ) 迭代函数 若存在 x*,使得 ,则称x*为不动点 6/16 引理2.1 如果 ,满足条件: ; (2) 则 在 [a, b] 有唯一的不动点 x* 证 若 或 ,显然 有不动点 设 , 则有 , 记 则有 所以,存在x*,使得 即 , x*即为不动点. 7/16 定理2.4 如果 ,满足条件: ; (2) 则对任意的 x0∈ [a, b] , 迭代格式 产生的序列 { xn }收敛到不动点 x*,且有 证 8/16 ( 0L1 ) 所以, 故迭代格式收敛 9/16 不动点迭代产生序列的收敛速度 数列的 r 阶收敛概念 设 , 若存在 a0 , r0 使得 则称数列{xn} r 阶收敛. 特别: (1) 收敛阶r=1时,称为线性收敛; (2) 收敛阶r1时,称为超收敛; (3) 收敛阶r=2 时,称为平方收敛 序列的收敛阶数越高,收敛速度越快 10/16 例2.3 方程 x3+10x-20=0,取 x0 = 1.5, 证明迭代法 是线性收敛 证:令 f (x) = x3 + 10x –20, 绘出 y = f(x) 图形可知 方程的根 x*≈1.5, 令 求导数, 得 11/16 利用Lagrange中值定理, 有 其中, 介于xn和x*之间. 所以 由此可知,这一序列的收敛阶数为1,即迭代法是线性收敛. 显然,在x*附近 12/16 定理2.6 设x*是 的不动点,且 而 则 p阶收敛 由Taylor公式 其中, 介于xn和x*之间.所以 故迭代法p阶收敛. 13/16 1阶收敛的数列{xn}的加速收敛算法 s1=1;s2=s1-1/3;s3=s2+1/5; y0=s3; k=3;n=5;f=1;eor=1;