ここからは数学ネタ注意
間違ってたらすみません。
数値計算は詳しくないのでさらに注意。
多項式の根の近似値を求めるのはどうやるんだろなとちょっと考えてみた。
多項式のとかの近似値を求めるときニュートン法と呼ばれる方法で求められる。
ニュートン法
関数fは区間[a,b]で常にf''(x)>0でありfが区間(a,b)内に1つの根αを持つものとする。
f(c)>0なるc∈[a,b]をとり、数列a(n)を次のように定義する。
a(0)=c
a(n+1)=a(n)-f(a(n))/f'(a(n))
このときa(n)はαに単調に収束する。
この定理を利用して、関数fに対して適当な区間を取ることで根を近似できる。
図
まぁ例としては3^(1/2)なんかはx^2-3の根になってるけど区間[0,2]をとることで上の定理が使える。
a(n+1)=a(n)-(a(n)^2-3)/(2*a(n))
と漸化式が求められるので、これを初期値をa(0)=2で与えて、プログラムで十分な大きさのNまで計算すればいい。
n乗根でも同様に求められるし、一般的に代数的解法が存在しない5次方程式でも解が大体どのあたりにあるかがわかれば
細かい近似値を求めることができる。
ちなみに5次方程式の一般的な代数的解法は見つかっていないんじゃなくて存在しないことが証明されている。
つまり冪根や冪、四則演算で表すことができない場合がある。
で、話を戻すとニュートン法以外になんかないかなと思って、考えてみたんだけど、
ニュートン法と同じ条件(関数fは区間[a,b]で常にf''(x)>0でありfが(a,b)内に1つの根αを持つものとする。)のとき
区間をn等分に分割して、分割された区間で根αを含むものを取り出す。(端点のfの値の符号が違う区間)
さらにそれをn等分して、分割された区間で根αを含むものを取り出す。
もし途中でfの値が0となる端点があれば、それが根となる。
この操作を繰り返していくことで近似値を求めることができそう。
あと誤差の範囲が大体わかって、m回繰り返したとするとαからプラスマイナス1/n^m以内の範囲で収まる。
で、S=mnのとしてプログラムが処理する量はSに大体比例しそう。
そういうわけでSを一定値としたとき、もっとも誤差の範囲が小さくなるようなnの値(つまり何等分するか)を考えてみる。
そのためにn^mが最も大きくなる時を求める。つまりn^(S/n)の最大値をもとめればいい。
g(x)=x^(S/x)を考えて、微分してみるとg'(x)=S*g(x)*(1-log n)/n^2
となりg'(e)=0 (eは自然対数の底)であり、またx
g(x)はx=eで最大となる。(ちなみにx→0で1、x→∞で0となる)
つまりn^(S/n)はe (2.71828…)の周りにある2または3で最大となる。
そこで実際に代入してみてそれぞれ6乗してみると8^Sと9^Sとなる。
なので3等分を繰り返すのが一番効率よさそう。
まぁ2等分を繰り返しても結構速く収束しそうだけどね。
