Hw3 Reference

bisection, Newton, Horner

by yi hom

JavaScript

// Horner method
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]];
}

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]
}

function hybridSolver (func, interval, epsilon) {
    var eps = epsilon || 1e-4;
 	var imax = 50;
    var a = interval[0],  b = interval[1];
    var fa = func(coeff,a)[0], fb = func(coeff,b)[0];
    var x0, x1, fdf;
    var i;
    
    x0 = (b+a)/2;
    for (i = 0; i < imax; i++) {
		// bisection break
        if (b - a <= eps) break;
        
        fdf = func (coeff,x0);
        x1 = x0 - fdf[0]/fdf[1];
        if (Math.abs(x1 - x0) < eps)  // Newton break
            break;
        
        if (x1 > b || x1 < a) { // bisection step
            if (fdf[0]*fa < 0) // [a,x0]
                b = x0, fb = fdf[0];
        	else // [x0,b]
                a = x0, fa = fdf[0];
            console.log ('[bisection]: ' + a + ':' + b);
			x0 = (a+b)/2;
            continue;
        }
        
        //console.log ('[newton]: ' + x1); 
        x0 = x1;
    }
    return [x1, i];  // return [approx. root, iterations]
}


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 =...