ニュートン法
ニュートン法は、微分可能な関数の零点を反復的に近似する数値計算法である。接線近似に基づくため、解近傍で二次収束を示し、高速に高精度へ到達できるのが特長である。単変数の非線形方程式だけでなく、連立非線形方程式や最適化問題における勾配ゼロ点探索にも拡張される。歴史的には Newton–Raphson と呼ばれ、Taylor 展開から導かれる理論的に明快な手法である。
定義と導出
スカラー関数 f(x) の零点を求めるとき、点 x_k での Taylor 一次近似 f(x) ≈ f(x_k) + f'(x_k)(x − x_k) を用い、f(x)=0 の解を接線の根で近似する。これにより更新式 x_{k+1} = x_k − f(x_k)/f'(x_k) を得る。多変量関数 F(x) に対しては Jacobian J_F(x_k) を用い、線形方程式 J_F(x_k) s_k = −F(x_k) を解いて x_{k+1} = x_k + s_k とする。最適化では目的関数 φ(x) の停留点を狙い、Hessian H(x_k) と勾配 ∇φ(x_k) から H(x_k)s_k = −∇φ(x_k) を解いて同様に更新する。
アルゴリズム手順
- 初期値 x_0 を与える（解に十分近いほど良い）。
- 導関数 f'(x_k)（または J_F, H）を評価する。
- 線形方程式を解いてステップ s_k を求め、x_{k+1} = x_k + s_k とする。
- 収束判定（|f(x_{k+1})| や ||F(x_{k+1})||、||s_k|| の閾値）を満たせば終了。
- 必要に応じて減衰（ダンピング）や line search を行い安定化する。
幾何学的解釈
単変数では、x_k における接線が x 軸と交わる点を次の近似解 x_{k+1} とする。解の近傍では接線が曲線をよく近似するため、誤差はほぼ二乗で減少する。多変量では、Jacobian による線形化超平面と原点との交点を求める操作に等価である。
多変量への拡張
連立方程式 F(x)=0 では J_F(x_k) の因数分解（LU など）により s_k を効率的に求める。最適化では Hessian が正定値であれば s_k は降下方向となり収束性が高い。大規模問題では明示逆行列を作らず、直線解法や前処理付き反復解法（Newton–CG など）を用いる。疎構造を活用した分解（Cholesky, QR）が計算量削減に有効である。
収束性と初期値依存
ニュートン法は単純根に対し二次収束する。一方で多重根では収束次数が一次に劣化する。初期値が遠い場合や f'(x_k) が小さい場合、または曲率が不適切な場合には発散や振動を起こしうる。非線形方程式は「吸引域」が複雑な形を持つことがあり、初期値選定は実務上の重要課題である。
大域化の実務手法
実問題ではステップ長を調整する line search（Wolfe 条件など）や、信頼領域法（trust region）でステップを制限するのが標準である。最小二乗構造では Gauss–Newton が有効で、非線形性が強い場合は Levenberg–Marquardt により安定性を高める。これらの大域化は、ニュートン法の局所的な高速性と実務上の堅牢性を両立させる枠組みである。
数値例
方程式 x^2−2=0 の根 √2 を求める例を示す。x_0=1 とすると、f(x)=x^2−2, f'(x)=2x であり、更新は x_{k+1}=x_k−(x_k^2−2)/(2x_k) である。反復は次の通りで急速に収束する。
- x_0=1 → x_1=1.5
- x_1=1.5 → x_2=1.41666…
- x_2≈1.41666 → x_3≈1.4142157
- x_3≈1.4142157 → x_4≈1.41421356
実装の注意
- 導関数・Jacobian・Hessian は自動微分や厳密微分が望ましい。差分近似はステップ幅選択を誤ると桁落ちやノイズを招く。
- スケーリングと前処理で条件数を改善し、線形ソルバの安定性を確保する。
- 停止判定は残差・ステップ・目的関数の相対/絶対基準を併用し、最大反復回数と組み合わせる。
- 特異に近い Jacobian/Hessian では正則化（例: λI の付加）で安定化する。
バリエーション
導関数の再計算頻度を下げる改良型、逆行列近似を更新する準 Newton（BFGS, L-BFGS）、導関数不要の secant や割線近似などがある。最小二乗では残差構造を利用する Gauss–Newton、非凸最適化では trust region や damping を組み合わせた safeguarded Newton が広く用いられる。
多重根への対応
多重度 m の根に対しては更新 x_{k+1}=x_k−m f(x_k)/f'(x_k) とする修正で収束性を改善できる。あるいは f, f', f'' を用い x_{k+1}=x_k−f f'/{(f')^2−f f''} の形式も知られる。
制約付き最適化での利用
不等式制約を含む問題では interior-point により障壁関数を導入し、KKT 条件の Newton ステップを解く。行列ブロックの構造（対称・疎）を活かすことで大規模でも実用的な計算が可能である。
停止判定の設計
実務では tol_res（残差）, tol_step（ステップ）, tol_obj（目的関数変化）の3基準を用意し、相対値 max(1,||x_k||) で正規化する。さらに安全策として最大反復 k_max と時間上限を設定する。
計算コストとスパース性
大規模疎問題では因数分解の fill-in を抑える並べ替えと、疎直接法や前処理付き CG による近似解法が有効である。メモリ帯域やキャッシュ効率も性能を左右するため、ブロック化や再利用（factorization reuse）を設計に組み込むと良い。なお、ニュートン法は線形代数の選択が支配的な計算要素である。