100318数值分析第二章2.ppt

对于简单迭代法需要讨论的基本问题是，迭代函数的构造，迭代序列的收敛性和收敛速度以及误差估计。 例　用简单迭代法求方程 f(x)=x3-x-1=0 在x=1.5附近的根 解：将方程改写为 x=(1+x)1/3 按上式建立迭代公式 xn+1=(1+xn)1/3 取x=1.5逐次迭代得x0=1.5,x1=1.35721, x2=1.33086,x3=1.32588,x4=1.32494, x5=1.32476,x6=1.32473,x7=1.32472,x8=1.32472 最后取稳定至小数后５位的迭代值x8 =1.32472为方程的根 但如果将方程改写为 x=x3-1，并建立迭代公式xn+1=xn3-1，则得到的结果是 x0=1.5,x1=2.375, x2=12.39,…… 迭代值愈来愈大，这时迭代序列的极限不存在，迭代法失效。 我们把迭代序列有极限存在的迭代过程称为收敛的迭代过程；否则就是发散的。 例： 求方程x3-x2-1=0在x0=1.5附近的根，设建立下列相应的迭代公式，分析收敛性，并求近似根 解： 例题 已知方程2x-7-lgx＝0，求方程的含根区间，考查用迭代法解此方程的收敛性。 在这里我们考查在区间[3.5,4]的迭代法的收敛性 很容易验证：f(3.5)0,f(4)0 将方程变形成等价形式：x＝(lgx+7)/2 例题 用一般迭代法求x3-x-1=0的正实根x* 例题 用一般迭代法求方程x-lnx＝2在区间（2，?）内的根，要求|xk-xk-1|/|xk|=10-8 将方程化为等价方程：x＝2＋lnx k xi 0 3.000000000 1 3.098612289 2 3.130954362 3 3.141337866 4 3.144648781 5 3.145702209 6 3.146037143 另一种迭代格式： 由此可见，对同一个非线性方程的迭代格式，在收敛的情形下，有的收敛快，有的收敛慢。 §4牛顿迭代法/* Newton - Raphson Method */  内容提纲（Outline) 牛顿法及其几何意义 收敛性及其收敛速度 计算实例及其程序演示 三、计算实例及其演示 辅助工具: VC程序设计语言 Matlab数学软件 计算步骤 例题1 用Newton法求方程 的根,要求 例题2 求函数 的正实根 精度要求： 初值x0＝8.0 时,计算的是单根, 迭代次数是 28,结果是7.600001481 初值x0＝1.0 ,计算的是重根,迭代次数是 1356,结果是1.198631981 例：分别用迭代法、牛顿法、双点弦截法（x0=2, x1=1.9）求方程x3-3x-1=0在x=2附近的根 解：（1）迭代法 （2）牛顿法 （3）双点弦截法x0=2, x1=1.9 * 基本上我们就是这么做的!很难想象这么简单！怎么了?有什么问题吗？ 对吗？谁告诉你这种方法一定收敛？ §3 简单迭代法 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 的根。 x y y = x x y y = x x y y = x x y y = x x* x* x* x* y=g(x) y=g(x) y=g(x) y=g(x) x0 p0 x1 p1 ? x0 p0 x1 p1 ? x0 p0 x1 p1 ? x0 p0 x1 p1 ? 定理 考虑方程 x = g(x), g(x)?C[a, 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]上的唯一不动点。 （证明略） 简单迭代法的计算步骤： 步一：准备 提供迭代初值x0; 步二：迭代 计算迭代值x1=?(x0); 步三：控制 检查 :若 ( 为预先指定的精度),则以 替换 转步二继续迭代;当 时终止计算,取 作为