2

ニュートン法を使用して**番目のエルミート多項式の根を見つけることになっているプログラムがありますが、プログラムの実行には長い時間がかかります。私はCにかなり慣れていないので、自分のバグがどこにあるのか、またはこれがこの問題を強制するブルートの性質であるのかどうかを理解できません。正確なルートを取得する際にも問題が発生しますが、テストケースは5〜10分ごとにしか実行できないため、これまでのところ、そのバグを見つけるのは困難です。

コードが削除されました

4

1 に答える 1

1

Newton-Raphson がそれほど時間をかける正当な理由はないと 100% 確信しています。この方法は収束することが保証されていないため、場合によっては問題が生じることがあります。しかし、あなたの特定のケースでは、問題はないはずです。

明らかなことの 1 つは、再帰をとてつもなく使いすぎていることです。n=37 でyour を計算するだけで、37 個のフィボナッチ数 (約4,000 万hermite) を合計するような複雑さを伴う再帰になります。

ここで、メソッドが を繰り返しnewton呼び出す必要があると考えてください(これは、再帰と同じ程度の大きさです) まで、 in が まで収束します。数十回のインターレーションのように聞こえます。hermiteh_deriv10^-12

そして、これだけでは不十分ですが、newton 再帰的に実装することもできます! 世の中にそうする理由はありません。(lisp/scheme はあなたの最初のプログラミング言語でしたか?)

パフォーマンスを改善するには、次のことを行う必要があります。

  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 アルゴリズムでは、各ステップで値と導関数の両方が同じポイントで必要になるため、これは効果的に行われます。

PSしかし、これまでのところ、私は解決策にたどり着くことができませんでした。Newton-Raphson は、私が開始しようとしたポイントに収束しません。

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

于 2012-04-22T17:10:36.067 に答える