## 牛頓法──非線性方程的求根方法

$\displaystyle f(x)=0=f(x_0)+f'(x_0)(x-x_0)+O((x-x_0)^2)$

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

$\displaystyle x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}$

$\displaystyle x^3-x+\frac{\sqrt{2}}{2}=0$

$\displaystyle x_{k+1}=x_k-\frac{x_k^3-x_k+\sqrt{2}/2}{3x_k^2-1}$

$x_0=0$，則 $x_1=\sqrt{2}/2$$x_2=0$$\{x_k\}$ 數列將來回震盪，無法收斂。若 $x_0=-1$，經過7次迭代便收斂至 $-1.25107862158365$

Newton Iteration
Image source: Wikipedia, by Ralf Pfeifer

$\displaystyle g(x)=x-\frac{f(x)}{f'(x)}$

$\displaystyle g'(x)=1-\frac{f'(x)f'(x)-f(x)f''(x)}{(f'(x))^2}=\frac{f(x)f''(x)}{(f'(x))^2}$

$\displaystyle \vert g'(c)\vert=\frac{\vert g(p)-g(x)\vert}{\vert p-x\vert}$

$\displaystyle \vert p-g(x)\vert=\vert g(p)-g(x)\vert=\vert p-x\vert \vert g'(c)\vert\le\delta\rho<\delta$

$\displaystyle f(p)=f(x_k)+f'(x_k)(p-x_k)+\frac{1}{2}f''(\xi_k)(p-x_k)^2$

$\displaystyle 0=\frac{f(x_k)}{f'(x_k)}+(p-x_k)+\frac{f''(\xi_k)}{2f'(x_k)}(p-x_k)^2$

$\displaystyle p-x_{k+1}=-\frac{f''(\xi_k)}{2f'(x_k)}(p-x_k)^2$

$e_k=p-x_k$。代入上式，等號兩邊取絕對值即有

$\displaystyle \vert e_{k+1}\vert =\frac{\vert f''(\xi_k)\vert}{2\vert f'(x_k)\vert}e_k^2$

$\displaystyle F(\mathbf{x})=\begin{bmatrix} f_1(x_1,\ldots,x_n)\\ \vdots\\ f_n(x_1,\ldots,x_n) \end{bmatrix}$

$\mathbf{x}_k=(x_{k1},\ldots,x_{kn})^T$$F(\mathbf{x})=\mathbf{0}$ 的一根的估計值。考慮 $f_i(\mathbf{x})$$\mathbf{x}_k$ 的泰勒級數：

$\displaystyle f_i(\mathbf{x})=0=f_i(\mathbf{x}_k)+\sum_{j=1}^n\frac{\partial f_i}{\partial x_j}(\mathbf{x}_k)(x_j-x_{kj})+\cdots,~~~i=1,\ldots,n$

$\displaystyle J(\mathbf{x}_k)(\mathbf{x}-\mathbf{x}_k)=-F(\mathbf{x}_k)$

$J(\mathbf{x}_k)=\begin{bmatrix} \frac{\partial f_1}{\partial x_1}(\mathbf{x}_k)&\frac{\partial f_1}{\partial x_2}(\mathbf{x}_k)&\cdots&\frac{\partial f_1}{\partial x_n}(\mathbf{x}_k)\\[0.5em] \frac{\partial f_2}{\partial x_1}(\mathbf{x}_k)&\frac{\partial f_2}{\partial x_2}(\mathbf{x}_k)&\cdots&\frac{\partial f_2}{\partial x_n}(\mathbf{x}_k)\\ \vdots&\vdots&\ddots&\vdots\\ \frac{\partial f_n}{\partial x_1}(\mathbf{x}_k)&\frac{\partial f_n}{\partial x_2}(\mathbf{x}_k)&\cdots&\frac{\partial f_n}{\partial x_n}(\mathbf{x}_k) \end{bmatrix}$

$J(\mathbf{x}_k)$ 可逆，牛頓法迭代公式為

$\displaystyle \mathbf{x}_{k+1}=\mathbf{x}_k-(J(\mathbf{x}_k))^{-1}F(\mathbf{x}_k)$

[1] 不動點定理 (fixed point theorem)：設 $g$ 是定義於 $[a,b]$ 的一次可導函數。若對於任一 $x\in[a,b]$$g(x)\in[a,b]$$\vert g'(x)\vert<1$，則 $x_{k+1}=g(x_k)$ 收斂至 $p$，其中 $p\in[a,b]$$g$ 的一個不動點。

This entry was posted in 特別主題 and tagged , , , . Bookmark the permalink.

### 4 則回應給 牛頓法──非線性方程的求根方法

1. 周老师，正文最后一行“使用高斯消去法解出线性方程 $J(\mathbf{x}_{k+1})\mathbf{z}_k=-F(\mathbf{x}_k)$”，是不是应该是 $J(\mathbf{x}_{k})\mathbf{z}_k=-F(\mathbf{x}_k)$

• ccjou 說：

感謝指正，已修訂。

2. 董瀚林 說：

周老师您好，很荣幸拜读您的文章。但有一处希望与您探讨：您在本文收敛性证明处，对于迭代公式的表述写到g(x)=x-f(x)/f'(x)，此处g为f的反函数，那么表述成g（y）是否更加妥当？不对之处恳请您批评指正。

• ccjou 說：

$g(x)=x-\frac{f(x)}{f'(x)}$ 並不是 $f(x)$ 的反函數，例如，若 $f(x)=x-1$，則 $g(x)=x-\frac{x-1}{1}=1$$(g(x),0)$$f$ 於點 $(x,f(x))$ 的切線與x-軸的交點。