/* Solutions of Nonlinear Equations */ 第三章 非线性方程求根 /* Solutions of Nonlinear Equations */ 求 f (x) = 0 的根 §1 多项式基础 /* Polynomials */ （自习） §2 二分法 /* Bisection Method */ 原理：若 f C[a, b]，且 f (a) · f (b) < 0，则 f 在 (a, b) 上必有一根。

When to stop? b x1 x* a a b x2 或 不能保证 x 的精度 2 x x*

误差 分析： 第1步产生的 有误差 第 k 步产生的 xk 有误差 对于给定的精度  ,可估计二分法所需的步数 k ： ①简单; ② 对f (x) 要求不高(只要连续即可) . ①无法求复根及偶重根 ② 收敛慢 注：用二分法求根，最好先给出 f (x) 草图以确定根的大概位置。或用搜索程序，将[a, b]分为若干小区间，对每一个满足 f (ak)·f (bk) < 0 的区间调用二分法程序，可找出区间[a, b]内的多个根，且不必要求 f (a)·f (b) < 0 。

Is it really better than  试位法 /* Regula Falsi Method */ Is it really better than Bisection Method? (b, f (b)) b a x* (a+b)/2 (a, f (a)) 注：试位法每次迭代比二分法多算一次乘法，而且不保证收敛。

§3 迭代法 /* Fixed-Point Iteration */ 等价变换 f (x) = 0 x = g (x) g (x) 的不动点 f (x) 的根 从一个初值 x0 出发，计算 x1 = g(x0), x2 = g(x1), …, xk+1 = g(xk), … 若 收敛，即存在 x* 使得 ，且 g 连续，则由 可知 x* = g(x* )，即x* 是 g 的不动点，也就是f 的根。 思路 So basically we are done! I can’t believe it’s so simple! What’s the problem? Oh yeah? Who tells you that the method is convergent?

    x y y = x x y y = x x0 p0 p1 y=g(x) y=g(x) x* x1 x0 p0 x1 x*

      定理 考虑方程 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]上的唯一不动点。并且有误差估计式：   ( k = 1, 2, … ) 且存在极限     k  

   证明：① g(x) 在[a, b]上存在不动点？ 令 有根 ② 不动点唯一？ 反证：若不然，设还有 ，则 在 和 之间。 而 ② 不动点唯一？ 反证：若不然，设还有 ，则 在 和 之间。  而 ③ 当k   时， xk 收敛到 x* ？ 

   小 ④ 可用 来控制收敛精度 ⑤ L 越 收敛越快 ⑥ 可用 来控制收敛精度 ⑤ L 越 收敛越快  小 ⑥  注：定理条件非必要条件，可将[a, b]缩小，定义局部收敛性：若在 x* 的某 领域 B = { x | | x  x* |   } 有 gC1[a, b] 且 | g’(x*) | < 1，则由x0B 开始的迭代收敛。即调整初值可得到收敛的结果。

改进、加速收敛 /* accelerating convergence */  待定参数法： 若 | g’(x) |  1，则将 x = g(x) 等价地改造为 求K，使得 例：求 在 (1, 2) 的实根。 如果用 进行迭代，则在(1, 2)中有 现令 希望 ，即 在 (1, 2) 上可取任意 ，例如K = 0.5，则对应 即产生收敛序列。

一般地，有：  Aitken 加速： 比 收敛得略快。  Steffensen 加速： x y y = x y = g(x) x* 比 收敛得略快。 x y y = x y = g(x) x* P(x1, x2) x2  Steffensen 加速： P(x0, x1) x1 x0

§4 牛顿法 /* Newton - Raphson Method */ 原理：将非线性方程线性化 —— Taylor 展开 /* Taylor’s expansion */ 取 x0  x*，将 f (x)在 x0 做一阶Taylor展开: ， 在 x0 和 x 之间。 将 (x*  x0)2 看成高阶小量，则有： x y x* x0 线性 /* linear */ 只要 f C1，每一步迭代都有f ’( xk )  0， 而且 ，则 x*就是 f 的根。

定理 定理 （收敛的充分条件）设 f C2[a, b]，若 (1) f (a) f (b) < 0；(2) 在整个[a, b]上 f ”不变号且 f ’(x)  0； (3) 选取 x0  [a, b] 使得 f (x0) f ”(x0) > 0； 则Newton’s Method产生的序列{ xk } 收敛到f (x) 在 [a, b] 的唯一根。 产生的序列单调有界，保证收敛。 有根 根唯一 定理 （局部收敛性）设 f C2[a, b]，若 x* 为 f (x) 在[a, b]上的根，且 f ’(x*)  0，则存在 x* 的邻域 使得任取初值 ，Newton’s Method产生的序列{ xk } 收敛到x*，且满足

在单根 /*simple root */ 附近收敛快 证明：Newton’s Method 事实上是一种特殊的不动点迭代 其中 ，则 收敛  在单根 /*simple root */ 附近收敛快 由 Taylor 展开： 只要 f ’(x*)  0，则令 可得结论。

I have the proof, but there 注：Newton’s Method 收敛性依赖于x0 的选取。 Excuses for not doing homework I have the proof, but there isn't room to write it in this margin.   x0 x0 x0 x*

 改进与推广 /* improvement and generalization */  重根 /* multiple root */ 加速收敛法： Q1: 若　　　 ，Newton’s Method 是否仍收敛？ 设 x* 是 f 的 n 重根，则： 且 。 因为 Newton’s Method 事实上是一种特殊的不动点迭代， 其中 ，则 A1: 有局部收敛性，但重数 n 越高，收敛越慢。 Q2: 如何加速重根的收敛？  A2: 将求 f 的重根转化为求另一函数的单根。 令　　　　　，则 f 的重根 =  的单根。

收敛比Newton’s Method 慢，且对初值要求同样高。  正割法 /* Secant Method */ ： Newton’s Method 一步要计算 f 和 f ’，相当于2个函数值，比较费时。现用 f 的值近似 f ’，可少算一个函数值。 割线 /* secant line */ x0 切线 /* tangent line */ 收敛比Newton’s Method 慢，且对初值要求同样高。 x1 切线斜率　　割线斜率 需要2个初值 x0 和 x1。

 下山法 /* Descent Method */ ——Newton’s Method 局部微调： 原理：若由 xk 得到的 xk+1 不能使 | f | 减小，则在 xk 和 xk+1 之间找一个更好的点 ，使得 。 xk xk+1 注： = 1 时就是Newton’s Method 公式。 当  = 1 代入效果不好时，将  减半计算。

 求复根 /* Finding Complex Roots */ —— Newton 公式中的自变量可以是复数 记 z = x + i y, z0 为初值，同样有 设 代入公式，令实、虚部对应相等，可得

§5 迭代法的收敛阶 /* Order of Convergence */ 定义 　　　设迭代 xk+1 = g(xk) 收敛到g(x) 的不动点 x*。 设 ek = xk  x*，若　　　　　　　，则称该迭代为p 阶收敛，其中 C 称为渐进误差常数。/* { xk } converges to x* of order p, with asymptotic error constant C > 0 */  一般 Fixed-Point Iteration 有　　　　　　　 ，称为线 性收敛 /* linear convergence */，这时 p = 1，0 < C < 1。  Aitken 加速有　　　　　 。 称为超线性收敛 /* superlinear convergence */。 注：超线性收敛不一定有 p > 1。 例如 xn = 1/nn 超线性收敛到0，但对任何 p > 1 都没有 p 阶收敛。

This is a one line proof...if we start sufficiently far to the left.  Steffensen 加速有 p = 2，条件是 ，称为平方收敛 /* quadratic convergence */。  Newton’s Method 有 ，只要 ， 就有 p  2。重根是线性收敛的。 Q: 如何实际确定收敛阶和渐进误差常数？ 定理 设 x* 为x = g(x) 的不动点，若 ，p  2； ，且 ，则 xk+1 = g(xk) 在 内 p 阶收敛。 This is a one line proof...if we start sufficiently far to the left. k   C 证明： x*