计算方法与误差理论-2.ppt

方程求根——牛顿迭代法 牛顿迭代法—牛顿下山法 牛顿法是局部收敛的，对初值要求苛刻。为了防止迭代发散，对迭代过程附加一项要求，即具有单调性：|f(xk+1)||f(xk)|，满足这项要求的算法称下山法。 牛顿下山法：把牛顿法与下山法结合 迭代公式： 下山因子λ：0λ≤1，λ=1,1/2,1/22,…(λ≥ελ下山因子的下界)，满足单调性 方程求根——割线法 割线法 牛顿法的收敛速度快，但每迭代一次，除计算f(x)外，还要计算f’(x) f(x)复杂，f’(x)的计算工作量大 f’(x)不好计算 割线法：用差商来代替导数 经过k次迭代后，用f(x)在xk,xk-1两点的差商来代替牛顿迭代公式中的导数值f’(xk) Newton’s Method 一步要计算 f 和 f ’，相当于2个函数值，比较费时。现用 f 的值近似 f ’，可少算一个函数值。 x0 x1 切线 /* tangent line */ 割线 /* secant line */ 切线斜率　?　割线斜率 需要2个初值 x0 和 x1。 收敛比Newton’s Method 慢，且对初值要求同样高 割线法 方程求根——根的精确化 割线法 迭代公式： 几何意义 经过A(xk,f(xk))及B(xk-1,f(xk-1))两点作割线AB，其点斜式方程为： 割线与x轴交点的横坐标即为xk+1 收敛速度比牛顿法略慢 计算量比牛顿法少 y=f(x) B(xk-1, f(xk-1)) y x x* xk-1 0 xk+1 A(xk, f(xk)) xk 例：用迭代法、牛顿法、割线法（x0=2, x1=1.9）求方程x3-3x-1=0在x=2附近的根 因为x3 = 3x+1 |?‘(x)|= | 3 1 3 | = =0.27 1 x0=2 =1.91293 =1.88883 =1.88203 x4=1.88014 x5=1.87960 x6=1.87945 x7=1.87940 x8=1.87939 x9=1.87939 解：（1）迭代法 第一步：形成迭代函数 （2）牛顿法 f(x0)= 23-3*2-1 =1 f’’(x0)= (f’(x0))’ =(3(x2 -1))’ =6x =6*2 =12 ff’’| x0=20 ?取初值x0=2 =1.88889 x2=1.87945 x3=1.87938 x4= 1.87938 第二步：确定初值 第三步：迭代计算 例：用迭代法、牛顿法、割线法（x0=2, x1=1.9）求方程x3-3x-1=0在x=2附近的根 （3）割线法x0=2, x1=1.9 x0=2 f(x0)= 23-3*2-1 =1 x1=1.9 f(x1)= 1.93-3*1.9-1 =0.159 = 2*0.159 - 1.9*1 0.159-1 =1.8811 f(x2)=0.0130 x3= 1.9*0.0130 - 1.8811*0.159 0.0130-0.159 =1.8794 f(x3)=0.0001 x4= 1.8811*0.0001 - 1.8794*0.0130 0.0001-0.0130 =1.8794 例：用迭代法、牛顿法、割线法（x0=2, x1=1.9）求方程x3-3x-1=0在x=2附近的根 x2= 方程求根——根的精确化 总结 方程求根，首先要求出有根区间 对于局部收敛的迭代格式，这个区间要尽可能的小 讨论各方法的有效性时，主要考察它的收敛速度和计算的工作量 二分法：只能求实根；简单直观，适于提供初值 其它方法均可用于求复根 牛顿法：有较快的收敛速度，对初值要求高 割线法：收敛比牛顿法略慢，计算量少 y=?(x) ????x???? y=x p0(x0,x1) x y o x0 p1 x1 x* p* ????x???? x y o x0 x1 x* p* y=?(x) x0? 方程求根——迭代法 方程求根——迭代法 迭代法—迭代法的收敛速度1 定义：设序列{xk}收敛于x*，并记ek=xk-x* (k=0,1,2,…)。如果存在非零常数c和正常数p使得： 则称序列{xk}是p阶收敛的 p：反映{xk}的收敛速度的快慢。p越大，则收敛越快 线性收敛：p=1且0|c|1 超线性收敛：p1；平方收敛：p=2 c：渐进误差常数 方程求根——迭代法 迭代法—迭代法的收敛速度2 推论1：若定理3中还有 φ’(x*) ≠ 0，即φ’(x*) 满足0|φ’(x*)|1，则迭代是线性收敛的。 方程求根——迭代法 迭代法—迭代法的收敛速度3 定理4：若φ(x)在x*附近的某个邻域内有p (p≥1)阶连续导数，且φ(x*)=x*, φ’(x*)= φ’’(x*)=…=φ(p-1)(x*)=0, φ(p)(x*) ≠0，则对任意靠近x*的初