1
出於好奇，我想驗證牛頓確實比求解非線性方程的 二等分（對於成功收斂的情況）更快。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);