二分法

牛顿切线法

设函数 $f(x)$ 在 $[a,b]$ 上连续可导，且 $f^{\prime }(x)\ne 0$，又 $f(a)f(b)<0$，则方程 $f(x)=0$ 在 $(a,b)$ 内有且仅有一个实根 $x^{\ast }$ 取 $[a,b]$ 内的点 $x_0=b$ 为初始值，过点 $(x_0,f(x_0))$ 作切线，方程为

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

因为 $f^{\prime }(x_0)\ne 0$，切线与 $x$ 轴交点横坐标为

$$x_1=x_0-{\displaystyle \frac{f(x_0)}{f^{\prime }(x_0)}}$$

把 $x_1$ 作为根的第一次近似值，重复上面步骤，得到第 $n$ 次近似值

$$x_n=x_{n-1}-{\displaystyle \frac{f(x_{n-1})}{f^{\prime }(x_{n-1})}},n=1,2,\cdots$$

牛顿迭代法

若记 $\phi (x)=x-{\displaystyle \frac{f(x)}{f^{\prime }(x)}}$，则有牛顿切线法迭代公式

$$x_n=\phi (x_{n-1}),n=1,2,\cdots$$

当数列 $\{x_n\}$ 收敛时，记 $\underset{n\to \mathrm{\infty }}{lim}{x}_n=\xi$，由 $\phi (x)$ 连续性得

$$\xi =\phi (\xi )=\xi -{\displaystyle \frac{f(\xi )}{f^{\prime }(\xi )}}⟹f(\xi )=0$$

故 $n$ 充分大后，$x_n$ 是 $x^{\ast }$ 的近似值

若 $\phi (x^{\ast })=x^{\ast }$，则称 $x^{\ast }$ 为函数 $\phi$ 的不动点