牛顿与二分的javascript实现(javascript implementation of newton vs. bisection)

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

我实现了两种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);

Out of curiosity, I want to verify that Newton is indeed faster than bisection (for the cases it successfully converges) for solving nonlinear equations.

I implemented both out of textbook algorithms. The function tested is:

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

The convergence accuracy is set to 1e-4. Newton starts at x0 = 0.5, converges in 2 iterations. bisection starts with an interval [0,1], converges in 14 iterations.

I use performance.now() to measure the elapsed time of both methods. SURPRISINGLY, with many tries, Newton is always slower than bisection.

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

I ported the program to C (visual C): Newton is a lot faster than bisection.

These numerical codes are so simple that I cannot spot any weird thing going on. Can anyone help?

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);

最满意答案

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

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

如果你想做得更好，也许只运行一次，然后做一个循环再次运行N次，并测量运行该循环所需的时间。

There are many external factors that can influence that test, including the order in which your code gets JIT compiled, and caching. Measuring time on such a small number of iterations isn't very meaningful, as those external factors may end up being bigger than what you're trying to measure.

For example, if you invert the order so it calculates bisection before it calculates Newton, you get the opposite result.

If you want to do it better, perhaps run both once, then do a loop to run both again N times, and measure how long it takes to run that loop.

更多推荐