数值分析与4 Newton迭代法 .ppt

* 《数值分析》4 Newton迭代格式 Newton迭代法的收敛性 Newton迭代法的变形 数值实验练习题 设 x*是方程 f(x)=0 的根, x0是x*的近似值.在 x0 附近,有 x1比x0更接近于x* x0 x1 x* f(x) = 0 ? 2/18 (n = 0, 1, 2, ·····) 牛顿迭代格式 给定初值 x0 , 迭代产生数列 x0, x1, x2,·········, xn, ······· 应用——求正数平方根算法 设C 0, x2 – C = 0 令 f(x) = x2 – C , 则 思考:用牛顿迭代法求C的倒数(不用除法) 3/18 例1 平方根算法 (n =0, 1, ·····) 的收敛性证明及收敛阶估计. 牛顿迭代法计算格式 化简,得 解: 对n≥0, 当 xn 0时 4/18 (n =0, 1, ·····) ( n 0) 数列 { xn }单减有下界, 故必有极限. 设为x*, 对递推式 取极限, 有 5/18 由此可知, 平方根迭代 是 2 阶收敛. 6/18 Newton迭代法的局部收敛性 定理2.7 设 f(x) 在点x*的某邻域内具有二阶连续导数,且设 f(x*)=0, f ’(x*) ≠ 0, 则对充分靠近点x*的初值x0, Newton迭代法至少平方收敛. 所以, Newton迭代法至少平方收敛 ? 7/18 例2.求 f(x)=xex – 1= 0 在 x0=0.5 附近的根 解: 迭代格式为 (n = 0, 1, ·····) f=inline(x*exp(x)-1); f1=inline((x+1)*exp(x)); x0=1.5;er=1;k=0; while er0.00001 x=x0-f(x0)/f1(x0); er=abs(x-x0) x0=x;k=k+1 end x = 0.5671 k=6 er=4.3596e-009 8/18 缺陷 1.被零除错误 2.程序死循环 y = arctan x 方程: f(x)=x3 –3x + 2 = 0 在重根x*=1附近,f’(x)近似为零 对 f(x) = arctan x 存在 x0,Newton迭代法陷入死循环 9/18 Newton迭代法陷入死循环的另一个例子 取 x0=0, (n = 0, 1, ·····) 10/18 f’0, f”0 f’0, f”0 f’0, f”0 f’0, f”0 11/18 定理: 若函数f(x) 在[a，b] 上满足条件 则方程 f(x) = 0 在[a，b] 上有唯一根 x*，且由初值x0按牛顿迭代公式求得的序列{ xn} 二阶收敛于x*。 （1）f(a) f(b) 0； （2）f ’(x)，f ”(x) 在[a，b]上连续且不变号（恒为正或恒为负）； （3）取x0∈[a，b] 使得 f(x0)f ”(x0) 0。 12/18 13/18 *