1

好奇心から、非線形方程式を解くために Newton が (収束に成功した場合に) 二分法より実際に高速であることを確認したいと思います。

の両方を実装しましたtextbook algorithms。テストされた関数は次のとおりです。

 f(x) = 5*(x-0.4)*(x^2 - 5x + 10), with a simple real root 0.4

収束精度は 1e-4 に設定されています。ニュートンは から始まりx0 = 0.5ますconverges in 2 iterations。二分は で始まり、interval [0,1]に収束し14 iterationsます。

私performance.now()は両方の方法の経過時間を測定するために使用します。驚くべきことに、何度も試行しても、ニュートンは常に二分法よりも遅くなります。

Newton time: 0.265 msec: [0.39999999988110857,2]
bisection time: 0.145 msec: [0.399993896484375,14]

プログラムを C (ビジュアル C) に移植しました。ニュートンは、二分法よりもはるかに高速です。

これらの数値コードは非常に単純なので、奇妙なことが起こっていることはわかりません。誰でも助けることができますか？

http://jsfiddle.net/jmchen/8wvhzjmn/

// Horner method for degree-n polynomial
function eval (a, t) {

    // f(x) = a0+ a1x + ... + anxn
    var n = a.length - 1;// degree (n)
    var b = [];
    var c = [];
    var i, k;
    for (i = 0; i <= n; i++)
        b.push(0), c.push(0);

    b[n] = a[n];
    c[n] = b[n];
    for (k = n-1; k >= 1; k--) {
        b[k] = a[k] + t*b[k+1];
        c[k] = b[k] + t*c[k+1];
    }
    b[0] = a[0] + t*b[1];

    return [b[0],c[1]];
}

// simple Newton
function Newton (eval, x0, epsilon) {
    var eps = epsilon || 1e-4;
    var imax = 20;
    for (var i = 0; i < imax; i++) {
        var fdf = eval (coeff, x0);
        x1 = x0 - fdf[0]/fdf[1];
        if (Math.abs(x1 - x0) < eps)
            break;
        x0 = x1;
    }
    return [x1, i];  // return [approx. root, iterations]
}

// simple bisection
function bisection (func, interval, eps) {
    var xLo = interval[0];
    var xHi = interval[1];

    fHi = func(coeff,xHi)[0];   // fb
    fLo = func(coeff,xLo)[0];   // fa
    if (fLo * fHi > 0)
        return undefined;

    var xMid, fHi, fLo, fMid;
    var iter = 0;
    while (xHi - xLo > eps) {
        ++iter;
        xMid = (xLo+xHi)/2;
        fMid = func(coeff,xMid)[0];  // fc

        if (Math.abs(fMid) < eps)
            return [xMid, iter];

        else if (fMid*fLo < 0) { // fa*fc < 0 --> [a,c]
            xHi = xMid;
            fHi = fMid;
        } else {  // fc*fb < 0 --> [c,b]
            xLo = xMid;
            fLo = fMid;
        }
    }

    return [(xLo+xHi)/2, iter];
}

// f(x) = 5x^3 - 27x^2 + 60x - 20
//      = 5*(x-0.4)*(x^2 - 5x + 10)
var coeff = [-20,60,-27,5];  

var t0 = performance.now();
var sol1 = Newton (eval, 0.5, 1e-4);
var t1 = performance.now();
var sol0 = bisection (eval, [0,1], 1e-4);
var t2 = performance.now();

console.log ('Newton time: '+ (t1-t0).toFixed(3) +  ': ' + sol1);
console.log ('bisection time: '+ (t2-t1).toFixed(3) + ': ' + sol0);
4

1 に答える 1

2

コードが JIT コンパイルされる順序やキャッシュなど、そのテストに影響を与える可能性のある多くの外的要因があります。このような少数の反復で時間を測定することはあまり意味がありません。これらの外的要因は、測定しようとしているものよりも大きくなる可能性があるためです。

たとえば、ニュートンを計算する前に二分法を計算するように順序を逆にすると、反対の結果が得られます。

もっとうまくやりたい場合は、おそらく両方を一度実行してから、ループを実行して両方をN回実行し、そのループを実行するのにかかる時間を測定します。

于 2015-10-27T12:01:58.493 に答える