📂数値解析

非線形システムを解くためのニュートン法

メソッド ¹

$\mathbf{f} ( \mathbf{x} ) := \begin{bmatrix} f_{1}( \mathbf{x} ) \\ \vdots \\ f_{N} ( \mathbf{x} ) \end{bmatrix}$のような多変数関数 $\mathbf{f} : \mathbb{R}^{N} \to \mathbb{R}^{N}$が $\mathbf{f} \in C^{2} \left( N ( \alpha ) \right)$であり、$\mathbf{f} ( \alpha ) = \mathbb{0}$、$\left[ D \mathbf{f} ( \alpha ) \right]^{-1}$が存在するとしよう。$\alpha$に十分近い初期値$\mathbf{x}_{0}$に対して、 $$ \mathbf{x}_{n+1} := \mathbf{x}_{n} - \left[ D \mathbf{f} ( \mathbf{x}_{n} ) \right]^{-1} f ( \mathbf{x}_{n} ) $$ のように定義された数列$\left\{ \mathbf{x}_{n} \right\}$は、$n \to \infty$の時、$\alpha$に対してクアドラティックに収束する。

---

• $\mathbf{f} \in C^{2} \left( N ( \alpha ) \right)$とは、$\alpha$の近傍で$\mathbf{f}$が2回微分可能で連続であることを意味する。
• $D \mathbf{f}$は$\mathbf{f}$のヤコビアンを示している。

説明

モチーフ

$$ \begin{cases} x + \cos ( x - y ) = 0 \\ - y + \sin (x + y) = 0 \end{cases} $$ 例えば、上のような問題があるとする。リニアシステムなら、線形代数のツールを使用して比較的簡単に解を出すことができるが、ノンリニアの場合はこのように二つの変数が混在していて解が難しい。しかし、ニュートンメソッドは数値的ではあるが、うまく解いてくれる。

ニュートン-ラフソンメソッドの一般化

ニュートン-ラフソンメソッドは、その速度が非常に速いだけではなく、ノンリニアシステム $$ \begin{cases} f_{1}( x_{1} , \cdots , x_{N} ) = 0 \\ \vdots \\ f_{N}( x_{1} , \cdots , x_{N} ) = 0 \end{cases} $$ を解くことができる汎用性も持っている。しかも、導出と証明も$1$次元からただ多次元に一般化するだけで、基本的な骨組みは同じだ。特に$f : \mathbb{R} \to \mathbb{R}$とすると$\displaystyle \left[ D f ( \mathbf{x}_{n} ) \right]^{-1} = {{1} \over { f ' ( x_{n} ) }}$になることを自然に理解できる。これは、ヤコビアンがベクトル関数の微分係数と同じ役割をするからだ。

要約すると、理解しやすくて速く、解くことのできる問題が多いので、非常に優れたメソッドだ。ニュートンメソッドを使いこなせば、ほとんどの分野で方程式を解く最良のツールを持っていると言ってもいい。

実装

以下は、Rコードでニュートンメソッドを実装したもので、ヤコビアンを求めるために numDerivパッケージを使用している。

library(numDeriv)
 
Newton<-function(f,x0,tol=10^(-8)){
  while(sqrt(sum(f(x0)^2))>tol){
    x0 <- x0 - solve(jacobian(f,x0)) %*% f(x0)
  }
  return(c(x0))
}
 
f<-function(v){c(
  v[1]+cos(v[1]-v[2]),
  -v[2]+sin(v[1]+v[2])
)}
 
Newton(f,c(1,1))
f(c(-0.9980201,-0.9350821))

初期値$(x_{0} , y_{0}) = (1,1)$でコードを実行すると、$\begin{cases} x + \cos ( x - y ) = 0 \\ - y + \sin (x + y) = 0 \end{cases}$の近似解である$(-0.9980201 \cdots , -0.9350821 \cdots )$を求めることができることがわかる。

参照

• 一次元でのニュートン-ラフソンメソッド