% 
% Bisection for nonlinear equation
%
clear all; 
close all;

f = @(x) x.^3 - x - 1;
a = 1; 
b = 2;
tol   = 1e-3;       % tolerance 
maxit = 100;      % maximum iteration number

xt = 1.324717957244745; % 近似精确解, 用于计算收敛速度

fa = f(a); 
fb = f(b); 
for k = 1 : maxit
    x  = (a + b) / 2;
    fx = f(x);
    % fprintf('k=%d, a/fa=%.4f/%.4e, b/fb=%.4f/%.4e, x/fx=%.4f/%.4e\n', ...
    %     k, a, fa, b, fb, x, fx);
    error = x - xt;
    fprintf('k = %d\n', k)
    fprintf('  a = %.4f, f(a) = %.4e, b = %.4f, f(b) = %.4e\n', a, fa, b, fb)
    fprintf('  x = %.4f, f(x) = %.4e, |x - xt| = %.4e\n', x, fx, error)
    if (k > 1) 
        fprintf('  收敛速度: %.2f\n', abs(error/error_old) )
    end
    if ( abs(fx) < tol || b - a < tol )
        break;
    end
    if ( fx*fa < 0 )
        b = x; fb = fx;
    else
        a = x; fa = fx;
    end
    error_old = error;
end

fprintf('*** x = %.4f, f(x) = %.4e\n', x, fx);

