ホーム ] 多倍長語 MegaLong ] 基数変換 ] 数値変換 ] 定数システム ] 演算時間予測システム ]

上へ
収束予測
階乗予測
級数予測
時間予測
限界値自動決定

演算時間予測システム

収束予測

最終更新日:2007/04/26  修正

●概要

 級数やニュートン法では、時間を予測するには収束を予測しなければならない。

●原理

 収束を予測することは、ある演算値が一定の値以下になることを判別することになる。一定の値は通常、演算精度(桁) とする。例えば、演算精度が32000桁とは、ある演算値が10-32000 以下になることと同じである。

○級数の収束

 (演算可能な)一般的な級数は、杷(X,k)/g(k) なる無限級数になる。少なくともこれが収束するには、f(X,k) < g(k)  が必要で、現実には、f(X,k) ≪ g(k) が必要である。級数の場合の収束判定は、k 番目の項の値を用いる。P を目標精度とすれば、

f(X,k) / g(k) ≦ 10-P

が、判定条件となる。これ以上、k を増やしても意味のある値は得られないので終了する。

○ニュートン法の収束

 ニュートンの場合は、漸化式なので、直前の値と同じになれば終了となる。しかし、これだと原理的には無限回必要となるので、差を判定に使用する。一般には、

 δk = 1 - f(Xk)

なるδ を導入し、このδ がいかに 0 に近づくかを判定する。但し、0 では元の木阿弥となる。f(Xk) が1 に近づくことと同じであるが、一般に、いかに1に近いかは判定できないので差を用いる。しかし、この、 1 - f(Xk) の演算は、

 1 - (1に限りなく近い値)

であり、危険な演算となる。つまり、打ち切り誤差が大きくなる。誤差が大きくて、結果が0 になれば、幸いで判定できるが、適度に大きいと、δ は、量子化され、漸化式を繰り返しても、もはやδ は不変となってしまう。このドツボにはまると、ニュートンは無限ループに陥る。通常、ニュートンのループは考えられない有限のループ数にし、無限ループを避けるが、これが起こると、無駄なループが起こり、演算時間が異常に長くなってしまう。不幸にも、値は正しい。これを原理的に避けるには、演算精度に余計な精度を付加し、収束判定を、演算精度+余計な精度 未満にするなどすれば良い。これにより、打ち切り誤差が、適度に小さくなり、δ は量子化しなくなる。MegaPrecision では、内部演算は、公称精度+拡張桁とし、収束判定は、公称精度+拡張桁/2 としている。