逆数の計算を計算の置換えで早くする

ー概要ー

逆数の計算は愚直に実装をすると遅くなってしまいます.そこでニュートン法を用いることで逆数の計算を引き算と2回掛け算の反復処理に変換することで高速に求めます.

プログラムの割り算処理を早くしたい

この章を学ぶ前に必要な知識
求根アルゴによる非線形方程式の解

効果

ニュートン法によって逆数の計算を引き算と掛け算2回の反復に置き換え

ポイント

反復計算のため精度は反復回数に依存します
f(x) = a - 1/x = 0のxをニュートン法によって求めます

解説

逆数の計算は愚直に実装をすると遅くなってしまいます.そこでニュートン法を用いることで逆数の計算を引き算と2回掛け算の反復処理に変換することで高速に求めます.

反復処理において何回計算するかで求まる逆数の値の精度が変わります.当然回数が多いほど精度は高まります.

逆数を計算の置換えで早くする

ニュートン法に関してはリンクを参照してください.

ニュートン法による求根

ααの逆数が求めたいとした場合、ニュートン法を以下の式に対して用いる.
f(x)=α−1xf(x)=α−1x
これが0となる点は、x=1αx=1αとなるはずである.
f(x)f(x)の微分は
f′(x)=1x2f′(x)=1x2
なので
ニュートン法によって導かれる式は、
xn+1=xn−f(xn)f′(xn)=xn−α−1xn1x2n=xn−αx2n+xn=2xn−αx2n=xn(2−αxn)xn+1=xn−f(xn)f′(xn)=xn−α−1xn1xn2=xn−αxn2+xn=2xn−αxn2=xn(2−αxn)
と求まる.
つまり、いかが更新式
xn+1=xn(2−αxn)xn+1=xn(2−αxn)

ニュートン法による逆数計算の反復計算への置き換え

xn+1=xn(2−αxn)xn+1=xn(2−αxn)
の計算を見ればわかるように
この計算は一回の引き算と二回の掛け算によって求められる.

これを必要な精度になるまで繰り返すことで逆数を求めることができる. 

ニュートン法による逆数計算の補足説明

C++
?
double value = 7; //taget value
double update(double x_n){
    double x_n1 = x_n * ( 2 - value * x_n );
    return x_n1;
}

逆数を求めたい対象をvalueとしています. update関数においては更新式に基づいてより良い値を求めています.

この章を学んで新たに学べる

なし

Comments

Reasons
>>隠す

知識: ニュートン法による求根

求根アルゴリズムとして有名である頻繁に使用されるニュートン法(1次元の場合)について紹介します.ニュートン法によって関数の値がゼロになる値等を算出します.探索する初期値に依存し、解は一つしか見つけられませんが、比較的高速です.導関数が適切に得られる必要があります.

続きを見る

逆数の計算を計算の置換えで早くする

ー 概要 ー

解 説

Reasons >>隠す

ー概要ー

解説

Reasons
>>隠す