N

Newton法 (にゅーとんほう)

Newton法は、非線形方程式 \begin{eqnarray} \boldsymbol{f}(\boldsymbol{x})&=&\boldsymbol{0},\\ && \boldsymbol{x}\in\mathbb{K}^N, \boldsymbol{f}(\boldsymbol{x})\in\mathbb{K}'^N \end{eqnarray} を適当な初期値 $\boldsymbol{x}_0$ から出発して \begin{eqnarray} \boldsymbol{x}_{k+1} &=& \boldsymbol{x}_k - \boldsymbol{J}^{-1}(\boldsymbol{x}_k) \boldsymbol{f}(\boldsymbol{x}_k),\label{update} \\[0.5em] && \boldsymbol{J}(\boldsymbol{x}) = \left( \begin{array}{cccc} \frac{\partial \boldsymbol{f}_0(\boldsymbol{x})}{\partial x_0} & \frac{\partial \boldsymbol{f}_0(\boldsymbol{x})}{\partial x_1} & \cdots & \frac{\partial \boldsymbol{f}_0(\boldsymbol{x})}{\partial x_{N-1}} \\ \frac{\partial \boldsymbol{f}_1(\boldsymbol{x})}{\partial x_0} & \frac{\partial \boldsymbol{f}_1(\boldsymbol{x})}{\partial x_1} & \cdots & \frac{\partial \boldsymbol{f}_1(\boldsymbol{x})}{\partial x_{N-1}} \\ \vdots & & \ddots & \vdots\\ \frac{\partial \boldsymbol{f}_{N-1}(\boldsymbol{x})}{\partial x_0} & \frac{\partial \boldsymbol{f}_{N-1}(\boldsymbol{x})}{\partial x_1} & \cdots & \frac{\partial \boldsymbol{f}_{N-1}(\boldsymbol{x})}{\partial x_{N-1}} \end{array} \right) \end{eqnarray} で更新してゆく解法。

式(\ref{update})の $\boldsymbol{x}_k$ を左辺に移項して \begin{eqnarray} \boldsymbol{d}_{k} &=& \boldsymbol{x}_{k+1}-\boldsymbol{x}_k &=& - \boldsymbol{J}^{-1}(\boldsymbol{x}_k) \boldsymbol{f}(\boldsymbol{x}_k),\\[0.5em] \end{eqnarray} とし、両辺に $\boldsymbol{J}(\boldsymbol{x}_k)$ を掛けて \begin{eqnarray} \boldsymbol{J}(\boldsymbol{x}_k) \boldsymbol{d}_{k} &=& -\boldsymbol{f}(\boldsymbol{x}_k),\\[0.5em] \end{eqnarray} を解いて $\boldsymbol{d}_{k}$ を求め、 \begin{eqnarray} \boldsymbol{x}_{k+1} &=& \boldsymbol{x}_k + \boldsymbol{d}_k \end{eqnarray} で更新すれば、逆行列を計算しなくてすむ。