javascript实现牛顿与平分

出于好奇，我想验证牛顿确实比求解非线性方程的二等分（对于成功收敛的情况）更快。javascript实现牛顿与平分

我实施了两个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（visual 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);

来源

2015-10-27 Jyun-Ming Chen

有可能影响该测试的许多外部因素，包括在你的代码变得JIT编译，缓存的顺序。在如此少量的迭代中测量时间并不是很有意义，因为这些外部因素最终可能比您要测量的要大。

例如，如果您反转订单，以便在计算牛顿之前计算平分，则会得到相反的结果。

如果你想做得更好，也许可以运行一次，然后做一个循环再次运行N次，并测量运行该循环需要多长时间。

来源

2015-10-27 12:01:58 Gio

javascript实现牛顿与平分

回答

相关问题