[prev] 73 [next]

Approximation for Numerical Problems (cont)

A simple approximation algorithm for finding a root in a given interval: 

bisection(f,x1,x2):
|  Input  function f, interval [x1,x2]
|  Output x∈[x1,x2] with f(x)≅0
|
|  repeat
|  |  mid=(x1+x2)/2
|  |  if f(x1)*f(mid)<0 then
|  |     x2=mid      // root to the left of mid
|  |  else
|  |     x1=mid      // root to the right of mid
|  |  end if
|  until f(mid)=0 or x2-x1<ε   // ε: accuracy
|  end while
|  return mid

bisection guaranteed to converge to a root if f continuous on [x1,x2] and f(x1) and f(x2) have opposite signs