Newton's Method

ニュートン法

概要

多変数（$n$ 変数）ニュートン法は、複数の未知数を含む連立非線形方程式系 $\boldsymbol{f}(\boldsymbol{x}) = \boldsymbol{0}$ の解を反復的に求めるためのアルゴリズムです。 1変数における「導関数（接線の傾き）」の概念を、多次元における「ヤコビ行列」へと拡張することで、複雑な非線形問題に対処します。

更新式：

\[ \boldsymbol{x}_{k+1} = \boldsymbol{x}_k - \boldsymbol{J}(\boldsymbol{x}_k)^{-1} \boldsymbol{f}(\boldsymbol{x}_k) \]

※実際には逆行列を計算せず、連立一次方程式 $\boldsymbol{J}(\boldsymbol{x}_k) \Delta \boldsymbol{x} = -\boldsymbol{f}(\boldsymbol{x}_k)$ を解いて修正量を求めます。

ヤコビ行列（Jacobian Matrix）

$n$ 変数ニュートン法において最も重要な役割を果たすのがヤコビ行列 $\boldsymbol{J}$ です。各関数を各変数で偏微分した要素で構成され、現在の地点における多次元的な勾配（傾き）を表します。

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

アルゴリズムのステップ

初期値ベクトル $\boldsymbol{x}_0$ を設定する。
現在の点 $\boldsymbol{x}_k$ において、関数ベクトル $\boldsymbol{f}(\boldsymbol{x}_k)$ とヤコビ行列 $\boldsymbol{J}(\boldsymbol{x}_k)$ を計算する。
連立一次方程式 $\boldsymbol{J}(\boldsymbol{x}_k) \Delta \boldsymbol{x} = -\boldsymbol{f}(\boldsymbol{x}_k)$ を解き、修正量 $\Delta \boldsymbol{x}$ を求める。
$\boldsymbol{x}_{k+1} = \boldsymbol{x}_k + \Delta \boldsymbol{x}$ により値を更新する。
$\|\Delta \boldsymbol{x}\|$ が許容誤差以下に収束するまで繰り返す。

SPICEとの繋がり

SPICE指向型解析法において、このヤコビ行列の各要素は回路の「等価コンダクタンス」に対応します。 SPICEシミュレーターは内部でこの収束計算を高速に行うことで、複雑な非線形回路の動作点を導き出しています。

具体的な計算例（2変数）

以下の簡単な2元連立非線形方程式を解く過程を考えます。

\[ \begin{cases} f_1(x_1, x_2) = x_1^2 + x_2^2 - 1 = 0 \\ f_2(x_1, x_2) = x_1 - x_2 = 0 \end{cases} \]

（単位円と直線 $x_1 = x_2$ の交点を求める問題です）

1. ヤコビ行列の導出

各関数を各変数で偏微分します。

\[ \boldsymbol{J}(x_1, x_2) = \begin{bmatrix} \frac{\partial f_1}{\partial x_1} & \frac{\partial f_1}{\partial x_2} \\ \frac{\partial f_2}{\partial x_1} & \frac{\partial f_2}{\partial x_2} \end{bmatrix} = \begin{bmatrix} 2x_1 & 2x_2 \\ 1 & -1 \end{bmatrix} \]

2. 反復計算（第1ステップ）

初期値を $\boldsymbol{x}_0 = [1, 0]^T$ と仮定して計算を開始します。

Step A: 関数値とヤコビ行列の計算
$\boldsymbol{f}(1, 0) = [1^2 + 0^2 - 1, 1 - 0]^T = [0, 1]^T$
$\boldsymbol{J}(1, 0) = \begin{bmatrix} 2(1) & 2(0) \\ 1 & -1 \end{bmatrix} = \begin{bmatrix} 2 & 0 \\ 1 & -1 \end{bmatrix}$
Step B: 修正量 $\Delta \boldsymbol{x}$ の算出
連立一次方程式 $\begin{bmatrix} 2 & 0 \\ 1 & -1 \end{bmatrix} \begin{bmatrix} \Delta x_1 \\ \Delta x_2 \end{bmatrix} = - \begin{bmatrix} 0 \\ 1 \end{bmatrix}$ を解くと：
$2\Delta x_1 = 0 \Rightarrow \Delta x_1 = 0$
$1(0) - \Delta x_2 = -1 \Rightarrow \Delta x_2 = 1$
Step C: 値の更新
$\boldsymbol{x}_1 = \boldsymbol{x}_0 + \Delta \boldsymbol{x} = \begin{bmatrix} 1 \\ 0 \end{bmatrix} + \begin{bmatrix} 0 \\ 1 \end{bmatrix} = \begin{bmatrix} 1 \\ 1 \end{bmatrix}$

このように、多次元空間上での修正ベクトル $\Delta \boldsymbol{x}$ を積み重ねることで、真の解（この場合は $[1/\sqrt{2}, 1/\sqrt{2}]^T$ など）へと収束させていきます。

注意点

多変数問題では、ヤコビ行列が正則でない（逆行列を持たない）地点に陥ると計算が破綻します。また、変数の数が増えるほど計算コストが増大するため、初期値の選択や行列のスパース性（疎行列性）の活用が重要になります。