不动点迭代法及其加速技术.ppt

华长生制作 5. Newton迭代法的应用----------开方公式 对于给定正数 应用牛顿迭代法解二次方程 可导出求开方值 的计算公式 设 是 的某个近似值，则 自然也是一个近似值，上式表明，它们两者的算术平均值将是更好的近似值。 定理 开方公式对于任意给定的初值 均为平方收敛。 方法一. 若已知重数m(m1),则利用m构造新的迭代公式: 此时, , 至少2阶收敛. 不实用: m往往不确定. 方法二. 取 ,再对函数F(x)用Newton迭代: 此时,X*为F(x)的单根,所以是2阶收敛. 但要用到二阶导数. 6. Newton法的改进(III) : 牛顿下山法 一般地说，牛顿法的收敛性依赖于初值 的选取，如果 偏离 较远，则牛顿法可能发散。 为了防止发散，通常对迭代过程再附加一项要求，即保证函数值单调下降： 满足这项要求的算法称为下山法。 牛顿下山法采用以下迭代公式： 其中 称为下山因子。 迭代法的加速 二、Aitken加速法 一、待定参数法 /* accelerating convergence */ 若 | g’(x) | ? 1，则将 x = g(x) 等价地改造为 求K，使得 一、待定参数法 例：求 在 (1, 2) 的实根。 如果用 进行迭代，则在(1, 2)中有 现令 希望 ，即 在 (1, 2) 上可取任意 ，例如K = ?0.5，则对应 即产生收敛序列。 设 xk 是根 x* 的某个预测值，用迭代公式校正一次得： 假设 在所考虑范围内改变不大，其估计值为L，则有 二、Aitken加速法 相除 将 再校正一次， 所以 ? Aitken 加速： x y y = x y = g(x) x* x0 P(x0, x1) x1 x2 P(x1, x2) 一般地，有： 比 收敛得略快。 　Newton 迭代法 将f(x)在点xn作Taylor展开: ——Taylor展开线性化 f(x)=0 近似于 f(xn)+ f′(xn)(x-xn)=0 (1) 从(1)解出x, 记为xn+1 ,则 1. Newton迭代公式建立 4 它对应的迭代方程为 显然是f(x)=0的同解方程，故其迭代函数为 在 f(x)=0的根 x* 的某个邻域 内, 在 x* 的邻域R 内，对任意初值 ，应用公式（2）来解方程的方法就称为牛顿迭代法。它是解代数方程和超越方程的有效方法之一. 2. Newton迭代法的几何意义 与x轴(y=0)的交点x,作为下一个迭代点xn+1 ,即 用f(x)在 xn 处的切线 Newton迭代法又称切线法. 例 用Newton迭代法求下面方程的一个正根,计算结果精确到7位小数. 解: 由Newton迭代法 由Newton迭代法 x1 = 1.4666667 ,…, x4 = 1.3688081 x5 = 1.3688081 迭代5次精度达10-7 x* ≈ 1.368808 4. Newton迭代法收敛定理 （1）Newton迭代公式在单根情况下至少2阶收敛; （2） 定理 设 f(x*)=0, ,且在 x* 的邻域 上 存在, 连续, 则可得 证：将f(x)在 xn 处作2阶Taylor展开,并将解x*代入 注意到ξn 在xn 及x*之间,及 , 故 所以，Newton法至少二阶收敛. 注意到ξn 在xn 及x*之间,及 ,故 例3. 为线性收敛 证明: 所以 例4. 至少是平方收敛的 由定义1 注意例4与例3的迭代法是相同的,两例有何区别? 证明: 令 则