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

$\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)$

$F(x_1,x_2)=\begin{bmatrix} x_1\\ \frac{10x_1}{x_1+0.1}+2x_2^2 \end{bmatrix}=\mathbf{0}$

$J(x_1,x_2)=\begin{bmatrix} 1&0\\ \frac{1}{(x_1+0.1)^2}&4x_2 \end{bmatrix}$

$x_2=0$，則 $J(x_1,x_2)$ 是不可逆的。若 $\mathbf{x}_k=(0,y)^T$，則

$\mathbf{x}_{k+1}=\begin{bmatrix} 0\\ y \end{bmatrix}-\begin{bmatrix} 1&0\\ 100&4y \end{bmatrix}^{-1}\begin{bmatrix} 0\\ 2y^2 \end{bmatrix}=\begin{bmatrix} 0\\ \frac{y}{2} \end{bmatrix}$

[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$ 的一個不動點。

[2] 取自 M.J.D. Powell, A Hybrid Method for Non-Linear Equations, in P. Rabinowitz (ed): Numerical Methods for Non-Linear Algebraic Equations, 1970, pp 87.

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

1. yufenglyu 說道：

周老师，正文最后一行“使用高斯消去法解出线性方程 $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-軸的交點。

3. 查理 說道：

請教一下:為何牛頓法n個聯立方程式時，會碰到無解的請況呢?是跟Jacobian有關?

• ccjou 說道：

你說的無解是指 Jacobian J 是不可逆矩陣嗎？這是可能的，譬如在機器手臂的運動學的某些姿態會失去一個自由度，我們稱之為退化(degeneracy)。

• Ju-Hsien Lai 說道：

老師好，想請教一下，若F(x) 屬於N維空間 但 x屬於M維空間，如此一來Jacobian不會是方陣，也沒辦法有可逆矩陣，此時在牛頓法裡改代Jacobian的偽逆矩陣是合理的做法嗎?

• ccjou 說道：
4. 吳昱良 說道：

老師您好：
您提到
“任意挑選正數 \rho<1，根據連續性，必存在區間 I=[p-\delta,p+\delta] 使得 \vert g'(x)\vert\le\rho，x\in I。"
然而從上面的假設粗略的看來g'(x)的連續性應該由f''(x)決定，因此如果使用連續性，是否應該考慮f''(x)連續呢？