はエルミート多項式

Question

のための強引なルーツしようとしている私は、ニュートン法を使って、**番目のエルミート多項式のための根を見つけることになっているプログラムを持っているが、プログラムを実行するのに長い時間を取っています。私はC言語ではかなり新しいので、私のバグがどこにあるのか、これがブルートゥースの本性に過ぎないのか分からない。私はまた、正確な根を得るの問題を抱えているが、これまでのところ、それは私が唯一のテストケースごとに5〜10分

CODE私は

Answer 1

REMOVED 100％を実行することができますので、そのバグを見つけるのは難しいですニュートン・ラフソンが長い時間を取る良い理由はないと確信しています。この方法が収束することが保証されていないため、場合によっては問題がある可能性があります。しかし、あなたの特定のケースでは、問題はありません。

明白なことの1つは、モンスター過度の再帰です。ちょうどあなたのhermiteのn = 37の計算はややについて40百万人で37のフィボナッチ数を、合計するなど複雑で再帰です。

さて、10^-12まで収束するまでの中まで、あなたのnewton方法は（再帰の同程度の大きさである）を繰り返しhermiteを呼び出すだけでなく、h_derivべきだと思います。何十回もの干渉のように聞こえる。

そして、すべてではないこれは十分では、あなたもnewton再帰的を実装するために管理します！このように、世界には本当に理由はありません。 （lispの/スキームあなたの最初のプログラミング言語でしたか？）

これにより、パフォーマンスを向上させるために何をすべきかです：

1. はあなたhermiteを修正。 37 係数を計算する必要があります。これは再帰的に行うことができます。これが完了したら、通常の時間に多項式の値を計算するためにそれらを使用する必要があります。

2. 派生物に関しては同じ。ちょうど36係数を計算してください。

3. は、必要に応じて、あなたのnewtonを修正します。私が見る限りでは、あなたはパフォーマンスの多くを得ることはありません。あなたの "再帰"はそれにもかかわらず、厄介なループです。しかし、それはよりよく見え、より少ないスタックを消費します。

編集：

私は時間がかかったと&実行これを構築しようとしたコメントを読んだ後。そして、私は認めなければならない、私は問題の複雑さを過小評価した。結局のところ

は、再帰的な関係によって計算された係数は急速に成長し、丸め誤差が支配するようです。したがって、ブルートフォースでこの問題を解決するには、避けられない影響があります。また、事前に計算された係数を使用して（そしてそれらをまっすぐな順序で合計すると）同じ結果が得られることは明らかではありません。

それでも計算ロジックを変更することなく、とんでもない再帰を取り除くための方法があります：

const int N = 37; 

double g_pHermiteValues[N+1]; 

void CalcHermiteAt(double x) 
{ 
    double x2 = x*2; 

    g_pHermiteValues[0] = 1.; 
    g_pHermiteValues[1] = x2; 

    for (int n = 2; n <= N; n++) 
     g_pHermiteValues[n] = 
      g_pHermiteValues[n - 1] * x2 - 
      g_pHermiteValues[n - 2] * 2*(n - 1); 
} 

double CalcHermiteDerivAt() 
{ 
    return g_pHermiteValues[N - 1] * 2*N; 
} 

double newton(double x_0) 
{ 
    const double tolerance = 1E-12; 

    while (true) 
    { 
     CalcHermiteAt(x_0); 

     if (abs(g_pHermiteValues[N]) < tolerance) 
      return x_0; 

     x_0 -= g_pHermiteValues[N]/CalcHermiteDerivAt(); 
    } 
} 

我々は同じ再帰的な関係を使用し、です。与えられた点でエルミート多項式の値を計算するためには、n = 37 反復的にまでのすべての多項式についてそれを計算し、結果をグローバル配列に格納します。その上の要素は必要な結果を保持し、導関数は最後から2番目の配列要素からも導かれます。

各ステップのNewton-Raphsonアルゴリズムでは、値と派生値の両方が同じポイントで必要になるため、これは効果的に行われます。

P.S.しかし、これまで私は解決策には出くわしていませんでした。ニュートン・ラフソンは、私が始めようとした点については収束していません。

私は、このような質問のために、中央値検索などのより堅牢な方法を使用することができます。