Page 194 - Applied Numerical Methods Using MATLAB

BISECTION METHOD 183
√
(Q) How do we make the iteration converge to another solution x =− 2of
2
x − 2 = 0?

4.2 BISECTION METHOD

The bisection method can be applied for solving nonlinear equations like f(x) =
0, only in the case where we know some interval [a, b]onwhich f(x) is contin-
uous and the solution uniquely exists and, most importantly, f(a) and f(b) have
the opposite signs. The procedure toward the solution of f(x) = 0 is described
as follows and is cast into the MATLAB routine “bisct()”.
Step 0. Initialize the iteration number k = 0.
1
1
Step 1. Letm = (a + b).Iff(m) ≈ 0or (b − a) ≈ 0,thenstopthe iteration.
2 2
Step 2. If f(a)f (m) > 0, then let a ← m; otherwise, let b ← m.Gobackto
step 1.

function [x,err,xx] = bisct(f,a,b,TolX,MaxIter)
%bisct.m to solve f(x) = 0 by using the bisection method.
%input : f = ftn to be given as a string ’f’ if defined in an M-file
% a/b = initial left/right point of the solution interval
% TolX = upperbound of error |x(k) - xo|
% MaxIter = maximum # of iterations
%output: x = point which the algorithm has reached
% err = (b - a)/2(half the last interval width)
% xx = history of x
TolFun=eps; fa = feval(f,a); fb = feval(f,b);
if fa*fb > 0, error(’We must have f(a)f(b)<0!’); end
fork=1: MaxIter
xx(k) = (a + b)/2;
fx = feval(f,xx(k)); err = (b-a)/2;
if abs(fx) < TolFun | abs(err)<TolX, break;
elseif fx*fa > 0, a = xx(k); fa = fx;
else b = xx(k);
end
end
x = xx(k);
if k == MaxIter, fprintf(’The best in %d iterations\n’,MaxIter), end

Remark 4.2. Bisection Method Versus Fixed-Point Iteration

1. Only if the solution exists on some interval [a, b], the distance from the
midpoint (a + b)/2 of the interval as an approximate solution to the true
solution is at most one-half of the interval width—that is, (b − a)/2, which
we take as a measure of error. Therefore, for every iteration of the bisection
method, the upper bound of the error in the approximate solution decreases
by half.