3数值分析.ppt

2.4.5割线法（弦截法，弦切法） 2.5代数方程求根的劈因子法 3.2 消去法3.2.1三角方程组解法 * * 思路：构造新的迭代函数，提高收敛阶. 寻找新的迭代公式 由前面性质（定理2.1）知： 当k很大时，有 2.3.4埃特金加速法（Aitken） 原来迭代函数 解出 该式可作为一个迭代公式.令 ,则 可以证明： 具体可利用洛必塔法则（ 型）得到： （然后将 代入得） 还可以证明：若原来 是线性收敛，则 是平方收敛； 若 是p阶( )收敛 ，则新的迭代函数 是（ 2p-1） 阶收敛。 （证明略） 2.4 牛顿法与割线法2.4.1 牛顿法 特点： ①.将非线性方程转为线性方程处理； ②.可计算重根； ③.可推广到n维空间求根。 思路：设 是 的近似根, 将 在 点作一阶泰勒展开 （转为线性方程） ① 可得迭代公式: 几何意义：迭代公式可看成 与 轴 ( )的交点.（令左式中 ，即得①式） 两个公式联合，可得几何意义： 表示曲线过 的切线方程与x轴 的交点作为下一个迭代点。 牛顿法也称为切线法。 只要初值点足够靠近 ，牛顿法局部收敛。 初值可通过别的方法求出。 2.4.3 收敛速度 利用前面定理判断，需计算 各阶导数及在 点处的值。 对 ，先计算各阶导数： 2.4.2 收敛性 对单根情况，设 为 的单根，可写成 ∴ (其中 ) ∴ 且： (一般地， ) ∴由前面定理知：p=2，即2阶局部收敛， 且有： 对m重根（m≥2），可类似知收敛阶为1： 设 为 的m重根，即有 ∴ 利用 及导数定义 ，得 ∴由前面定理知，对重根（m ≥2）是一阶局部收敛 总结：牛顿法特点：局部收敛，收敛速度快，可处理重根。 例：使用牛顿法求 在x=0.4附近根， ∴ 迭代 具体可通过 判断迭代是否结束。 要求达到4位有效数字。 2.4.4 大范围收敛性 牛顿法对初值 要求比较苛刻，要充分靠近 （可与别的方法结合）。要对初值在较大范围内收敛， 需对 附加的一些条件（充分条件）。 定理：设 在区间[a,b]上存在二阶连续导数，且满足 ① ② ③ ④ 则牛顿法二阶收敛。 简要说明：①和②保证[a,b]内有唯一根， 因为在[a,b]内 切线不再同一侧，有可能不收敛于 ，如图所示， 具体证明可见参考文献。 另外，若保证 在区间内收敛， 也可改用牛顿下山法。 ③保证 在[a,b]上是凹或凸曲线， ④保证当 时, . 牛顿下山法介绍： 为防止迭代发散，可对迭代附加条件: （1） 这样可保证收敛，称为下山法。 具体的，可将前后两次迭代计算作加权平均， 构造新的迭代公式，即 设 为迭代x+1次的结果 新迭代公式 为权因子（下山因子） 对于权因子迭取，可采用类似二分法，先取 =1， 若不能保证(1),对 减半迭取，如果仍不能保证(1) ， 则需要更换初值。 牛顿法每迭代一次需计算 , 计算量大。 可使用差商代替 ，用 表示 即 所以迭代公式： 几何意义：可看成直线 （该直线斜率）与x轴（y=0）交点。 当 较复杂时， 特点：迭代需2个初值 （可取有根区间端点）； ( 可求出，不必重新计算). 不需计算导数； 计算中，每迭代1次只需求1次 收敛速度与牛顿法相比稍慢，但还是较快. 该方法也称为抛物线法（Muller法） 该方法还可推广，利用三个点构成迭代公式， 三个点可构造二次抛物线方程， 例：使用割线法求 在x=0.4附近的根， 要求达到4位有效数字（上机作业） 以上方法可计算单根、重根，都为实数根； 该方法可用来求复根。 思路：设方程 从 中分离出一个二次多项式， ( 二次方程有求根公式，可求重根和复根) 为 n-2次多项式 这样可转为对 求根，关键问题是如何找 , 可使用迭代法。 即 , 可事先构造初始函数