JavaScriptで数値計算---二分法とニュートン法

要するに

前回の記事のJavaScriptを実行できるWebサイトを使って
汎用的な方程式の数値的開放である二分法とニュートン法について解説する。
これらはあらゆる$f(x)=0$を解ける、つまり汎用的な数値的解放として代表的な２つである。
JSでのコーディングの例として数値計算の例として代表的な$\sqrt(2)$を求める問題を取り上げる。

Github

これらはgithub,ioのページとして公開している。それらへのリンクは解説のあとにつけておく
github自体へのリンクはここである

二分法

ある２つの値、$x_0,x_1$、としそれらの関数の値がそれぞれ正と負であるとする。
その時、必ず$x_0$と$x_1$の間に答え(解)がある。
なので、その平均$x_{center}=\frac{x_0+x_1}{2}$を新たな値として範囲を狭めていく方法である。
解が求まったという条件は$x_0$と$x_1$のが十分小さいとする。
JSの数値型は倍精度浮動点少数でありその最小の差は$1$で大体$10^{-16}$程度とされている。
しかしあまりに小さく取ると収束しないという問題があるので大体、半分の乗数の$10^{-8}$が用いられる。

これをコーディングするとこのようになる。

byselection.js

const n=2;
const func=x=>{ return x*x-2; };
let x0=0, x1=n;
let y0=func(x0), y1=func(x1);
let counter=0;

while( Math.abs(x0-x1)>1.0e-8 ){
    counter++;
    if( y0*y1>0 ) throw new Error('!!! Byselection same sign !!!');
    const x_c=0.5*(x0+x1);
    const y_c=func(x_c);
    if( y_c*y0<0 ) x1=x_c;
    else x0=x_c;
    output.log('Iteration =', counter, ' f(', x_c, ') =', y_c);
}

解く方程式はfunc=x=>{ return x*x-n; };であり、これは$x^2-2=0$を解いている
この方法では誤差$|x_0-x_1|$は1ステップで半分にしかならないので収束は遅いが必ず小さくなるので安定的と言われる。

これはJavaScript実行テストページ---二分法グラフ付で実行できる。

ニュートン法

ニュートン法はある、値$x_0$で$f(x)$を一次近似してその解を$x_1$を次の値として更新していく方法である。
一次近似なので微分を使い傾きを求める、これは微分を発明したニュートンが発明したためこの名前になった

JSの関数は第一級オブジェクトなので他の関数に引数として渡すことが出来る。
そのため、微分は以下のようにモジュール化出来る。

diff.js

export default {
    forward: (f, x, dx=1.0e-8)=>{ return (f(x+dx)-f(x))/dx; },
    central: (f, x, dx=1.0e-8)=>{ return (f(x+0.5*dx)-f(x-0.5*dx))/dx; },
    backward: (f, x, dx=1.0e-8)=>{ return (f(x), f(x-dx))/dx; }
}

これらを数式で表すと
$f'(x_0)_{forward} \sim \frac{f(x+dx)-f(x)}{dx}$

$f'(x_0)_{central} \sim \frac{f(x+0.5dx)-f(x-0.5dx)}{dx}$

$f'(x_0)_{backward} \sim \frac{f(x)-f(x-dx)}{dx}$
となる上から前方、中心、後方差分法と言われるもので微分の定義式の$dx \rightarrow 0$を微小量で近似したものである。
前方、後方差分の誤差はdxの一次のオーダーで中心差分では$dx$の二次のオーダーになる。

この微分をdiffモジュールとするとニュートン法は以下のように実装される。

newton.js

const n=2;
const func=(x)=>{ return x*x-n; };
let x0=n;
let x1=x0-func(x0)/diff.central(func, x0);

let counter=0;
while( Math.abs(x0-x1)>1.0e-8 ){
    counter++;
    x0=x1;
    x1=x0-func(x0)/diff.central(func, x0);
    output.log('Iteration =', counter, ' x=', x1, 'dx =', Math.abs(x0-x1));
}
output.log('x =', x1, '  calc =', Math.sqrt(n));

これにビジュアライゼーションを追加したものを実行すると次の絵のようになる

これはJavaScript実行テストページ---ニュートン法グラフ付で実行することが出来る。