Numerical Computation Solving Equations

Multiplicity

若函数 $f(x)$ 在 $x=r$ 处满足：

$$f(r)=f^{\prime }(r)=\cdots =f^{(m-1)}(r)=0,f^{(m)}(r)\ne 0,$$

则称 $r$ 是 $f(x)$ 的重根（multiple root），重数为 $m$。

当 $m=1$ 时，称为单根（simple root）。

三重根示例

方程：

$$f(x)=\sin x+x^2\cos x-x^2-x$$

在 $x=0$ 附近：

$$f(0)=f^{\prime }(0)=f^{″}(0)=0,f^{‴}(0)=-1$$

说明 $r=0$ 是三重根（m=3）。

Newton 法此时满足：

$$e_{i+1}\approx \frac{2}{3}{e}_i$$

即线性收敛，约需 36 步 才能达到 6 位有效数字。

---

Bisection Method

思想：不断缩小区间 $[a,b]$，保证 $f(a)f(b)<0$。 公式：

$$c_n=\frac{a_n+b_n}{2}$$

误差估计：

$$|x_n-r|<\frac{b-a}{2^{n+1}}$$

收敛性：线性收敛，速率约为 1/2。 优点是绝对收敛，但速度较慢。

---

Fixed-Point Iteration

思想：将 $f(x)=0$ 改写为 $x=g(x)$，并不断迭代。

公式：

$$x_{i+1}=g(x_i)$$

收敛条件：

若 $|g^{\prime }(r)|<1$，则局部线性收敛。

误差关系：

$$e_{i+1}\approx g^{\prime }(r)e_i$$

Newton’s Method

Idea: Newton 法利用函数的切线近似（linearization）来迭代逼近方程 $f(x)=0$ 的根。

在当前点 $x_i$ 处，用切线方程：

$$y=f(x_i)+f^{\prime }(x_i)(x-x_i)$$

近似代替 $f(x)$。令 $y=0$ 得到切线与 $x$-轴的交点，即下一个迭代点：

$$x_{i+1}=x_i-\frac{f(x_i)}{f^{\prime }(x_i)}$$

Newton 法只需一次函数值与一次导数值，即可得到新的近似解。

几何解释（Geometric Meaning） 在图形上，Newton 法通过不断作切线并取其与 $x$-轴交点来逐步逼近根。

若初值 $x_0$ 足够接近真根 $r$，切线逼近精度高，收敛速度极快。

收敛性（Convergence）

• 对于单根（Simple Root, $m=1$） 若 $f(x)$ 在 $r$ 附近连续可导且 $f^{\prime }(r)\ne 0$，则 Newton 法具有局部二次收敛（Quadratic Convergence）。 设误差 $e_i=x_i-r$，则有：

$$e_{i+1}\approx M{e}_i^2,M=\frac{f^{″}(r)}{2f^{\prime }(r)}$$

这意味着：

$$|e_{i+1}|\approx M|e_i{|}^2$$

若当前误差为 ${10}^{-3}$，则下一次迭代误差约为 ${10}^{-6}$ —— 收敛速度极快。

• 对于重根（Multiple Root, $m>1$） 若根 $r$ 的重数为 $m$，即：

$$f(r)=f^{\prime }(r)=\cdots =f^{(m-1)}(r)=0,f^{(m)}(r)\ne 0,$$

则 Newton 法的收敛性会退化为线性收敛。

定理（Theorem）：

若 $f(x)$ 为 $m+1$ 次连续可导，且 $r$ 是 $f(x)$ 的重数为 $m$ 的根，则：

$$\underset{i\to \mathrm{\infty }}{lim}\frac{e_{i+1}}{e_i}=S,S=\frac{m-1}{m}.$$

因此：

• 当 $m=1$：$S=0$，为二次收敛；

• 当 $m=2$：$S=1/2$，为线性收敛；

• 当 $m\to \mathrm{\infty }$：收敛速度进一步减慢。

---

Example

单根示例

设 $f(x)=x^3+x-1$，则 $f^{\prime }(x)=3x^2+1$。

Newton 迭代式为：

$$x_{i+1}=x_i-\frac{x_i^3+x_i-1}{3x_i^2+1}=\frac{2x_i^3+1}{3x_i^2+1}.$$

从初值 $x_0=-0.7$ 出发，6 步即可收敛至 $x\approx 0.6823$，表现出典型的二次收敛。

重根示例

若 $f(x)=x^2$，则根 $r=0$，重数 $m=2$：

$$x_{i+1}=x_i-\frac{x_i^2}{2x_i}=\frac{1}{2}{x}_i,$$

误差递推式为：

$$e_{i+1}=\frac{1}{2}{e}_i,$$

仅线性收敛，收敛率为 $S=1/2$。

---

情况	收敛阶	误差关系	收敛速率
单根 ($m=1$)	二次	$e_{i+1}\approx M{e}_i^2$	快
重根 ($m>1$)	线性	$e_{i+1}\approx \frac{m-1}{m}{e}_i$	慢，随 $m$ 增大而变慢

Secant Method

思想：用割线代替切线，避免计算导数。 公式：

$$x_{i+1}=x_i-f(x_i)\frac{x_i-x_{i-1}}{f(x_i)-f(x_{i-1})}$$

特征：

• 无需导数；
• 需要两个初始值；
• 收敛阶 $\alpha \approx 1.62$（超线性收敛）。

误差关系：

$$e_{i+1}\approx M{e}_i^{\alpha },M=|\frac{f^{″}(r)}{2f^{\prime }(r)}{|}^{\alpha -1}$$

---

各方法综合比较

方法	迭代公式	收敛阶	是否需导数	收敛速度	优点	缺点
二分法	$c_n=(a_n+b_n)/2$	线性	否	慢	保证收敛	慢、需符号变化
不动点迭代	$x_{n+1}=g(x_n)$	线性	否	依赖 $g^{\prime }(r)$	简单易实现	收敛条件苛刻
牛顿法	$x_{n+1}=x_n-\frac{f(x_n)}{f^{\prime }(x_n)}$	二次	是	快	收敛快	需导数、易发散
割线法	$x_{n+1}=x_n-f(x_n)\frac{x_n-x_{n-1}}{f(x_n)-f(x_{n-1})}$	超线性	否	中等	无需导数	需两初值

---

• 二分法最稳但最慢；
• Fixed-Point方法简单但依赖函数形式；
• 牛顿法最快，但要求精确导数；
• 割线法是折中方案：不需导数且速度较快。

Convergence

Linear Convergence

以 Fixed-Point Iteration（不动点迭代法） 为例：

$$x_{i+1}=g(x_i)$$

若 $g^{\prime }(r)$ 连续且满足 $|g^{\prime }(r)|<1$，则误差满足：

$$e_{i+1}\approx g^{\prime }(r)e_i$$

因此方法局部线性收敛（locally linearly convergent），收敛速率约为 $|g^{\prime }(r)|$。

示例： 方程 $x^3+x-1=0$

• $g(x)=1-x^3$：$|g^{\prime }(r)|>1$，发散
• $g(x)=\sqrt[3]{1-x}$：$|g^{\prime }(r)|=0.716<1$，线性收敛
• $g(x)=\frac{1+2x^3}{2+3x^2}$：$|g^{\prime }(r)|=0$，极快收敛（近似二次）

---

Quadratic Convergence

若

$$M=\underset{i\to \mathrm{\infty }}{lim}\frac{e_{i+1}}{e_i^2}<\mathrm{\infty },$$

则称该方法具有二次收敛性。Newton 法满足此条件，当 $f^{\prime }(r)\ne 0$ 时有：

$$e_{i+1}\approx \frac{f^{″}(r)}{2f^{\prime }(r)}{e}_i^2$$

即误差在每次迭代中近似平方级减小。

例如：若上次误差为 ${10}^{-3}$，下一次约为 ${10}^{-6}$，收敛极快。

---

Superlinear Convergence

割线法的收敛阶介于 1 与 2 之间：

$$e_{i+1}=M{e}_i^{\alpha },\alpha \approx 1.62$$

因此称为超线性收敛（superlinear convergence）。

---

Local Convergence

若算法仅在初始猜测点足够接近真根 $r$ 时收敛，则称为局部收敛（locally convergent）。

在 Newton 或 FPI 中：

• 初值若离真根过远 → 可能震荡或发散；
• 可能收敛到其他根或非根点。

例如 FPI 的不同 $g(x)$ 形式会导致完全不同的收敛表现。

---