PolynomialRootFinder

by KUO YOU-TING

JavaScript

//var coefficient = [8, 6, 5, 2, 1, 1, -12];
var coefficient = [3, -53.08, 309.72, -590.76, 66.96, -609.12, 233.28]; //(x-0.36)*(3*x*x+2*x+3)*(x-6)*(x-6)*(x-6)

function evaluator(coeff, x) {
    var a6=coeff[0],a5=coeff[1],a4=coeff[2],a3=coeff[3],
        a2=coeff[4],a1=coeff[5],a0=coeff[6];
	var fx = x*(x*(x*(x*(x*(a6*x+a5)+a4)+a3)+a2)+a1)+a0;
    var dfx = x*(x*(x*(x*(6*a6*x+5*a5)+4*a4)+3*a3)+2*a2)+a1;
    return [fx,dfx];
}

function bisection(func, epsilon, xLo, xHi) { 
    var count = 1, xMid, fMid;
	var fLo = func(coefficient, xLo);
    var fHi = func(coefficient, xHi);
    
    if(fLo[0]*fHi[0] > 0)
        return undefined;
    
    while(xHi-xLo > epsilon) {
        xMid = (xLo+xHi)/2;
        fMid = func(coefficient, xMid);
        
        if(Math.abs(fMid[0]) < epsilon)
            return [xMid, count];
        else if(fMid[0]*fLo[0] < 0) {
            xHi = xMid;
            fHi = fMid;
        }
        else {
            xLo = xMid;
            fLo = fMid;
        }
        count++;
    }
    return [(xLo+xHi)/2, count];
}

function Newton(func, epsilon, x0) {
    var imax = 20, x1;
    
    for (var i = 0; i < imax; i++) {
        var fdf = func(coefficient, x0);
        x1 = x0 - fdf[0]/fdf[1];
        console.log(x1);
        if (Math.abs(x1 - x0) < epsilon)
            break;
        x0 = x1;
    }
    return [x1, i+1];
}

var resultOfB = bisection(evaluator, 1e-4, 0, 1);
var resultOfN = Newton(evaluator, 1e-4, 1);

console.log('Bisection solver: ' + resultOfB[0] + ', interation: ' + resultOfB[1]);
console.log('Newton solver: ' + resultOfN[0] + ', interation: ' + resultOfN[1]);