Zeroes of a real function: bracketing methods

Directly to the input form

• Bracketing methods for zeroes have the advantage of safe convergence. They may be somewhat slower than other zero codes, but are not necessarily so. Their general structure is as follows: Given an initial interval
  [a(0),b(0)] with f(a(0))*f(b(0)) <= 0
  they proceed iteratively: compute x(k) with a(k) < x(k) < b(k) , the new test point. Evaluate f(x(k)). Then
  a(k+1) = x(k) and b(k+1)=b(k) if f(a(k))*f(x(k)) > = 0
  b(k+1) = x(k) and a(k+1)=a(k) if f(b(k))*f(x(k)) > = 0
  such that again f(a(k+1))*f(b(k+1)) <= 0 and b(k+1)-a(k+1) < b(k)-a(k). The differences are in the computation of the testpoint.
• Here we present four different methods for computing the testpoint for comparison:
  1. The bisection method: x(k)=a(k)+(b(k)-a(k))/2 .
     This is linearly convergent, halving the error approximately at each step, and this independent of the properties of f.
  2. The method of false position (regula falsi)
     x(k)=a(k)-f(a(k))*(b(k)-a(k))/(f(b(k))-f(a(k))) .
     This has the disadvantage that finally one endpoint remains fixed, provided the second derivative of f at the zero is nonzero. This is a method producing linear convergence and can be slower than bisection.
  3. The Illinois method, a modification of the method of false position: this one avoids that one of the endpoints remains fixed: if
     f(x(k-1))*f(x(k-2)) > = 0 and f(x(k-1))*f(x(k-3)) >= 0 then
     x(k)=x(k-1) - f(x(k-1))*(x(k-1)-x(k-2))/(f(x(k-1))-f(x(k-2))/2) otherwise we apply the formula of false position (observe that a(k)=x(k-1) or b(k)=x(k-1) and similar for the index k-1.) This produces a three step cubic convergence.
  4. The method of Brent and Decker: this is a hybrid method, which mixes inverse quadratic interpolation, method of false position and bisection. Inverse interpolation is based on the idea that, provided f' is nonzero in a neighborhood of the zero x^* then it is locally invertible there and hence we can write
     x^* = f^-1(0)
     The inverse function is then approximated by a polynomial which interpolates the data (y(j),x(j)=f^-1(y(j)). Let P be the polynomial which takes the value x(j) at the point y(j), j=k-1,k-2,k-3. Then we let
     x(k) = P(0) .
     However, if this would fail or seem unsafe due to roundoff effects then one switches to the method of false position or even bisection. Normally this is convergent with an order of 1.618 (the secant method) or 1.839 (continued inverse quadratic interpolation). Details can be found in the original work of Brent (1973).
• These methods have the advantage of needing function values only.
• We present the results of the four methods side by side for comparison.
• However, since a function may have more than one zero in the input interval and only one of these is found, different solutions might be obtained which makes a direct comparison senseless, for example for
  exp(x)*sin(pi*x)-0.01*x, x in [0.1,11.5]
  

Input

• You either choose a predefined case or define a function yourself by writing a piece of code following the rules of FORTRAN.
• The interval [a,b] in which the zero should be found. Necessary is : a < b and f(a)*f(b) < 0, otherwise we terminate directly !
• eps : The required reduction of the interval length. b-a will be reduced to (b-a)*eps.
  For numerical reasons we limit this to 1.e-14 < eps < 1.e-2 ! For the method of false position we replace this by
  min(x(k)-a(k),b(k)-x(k)) <= eps*(b(0)-a(0))
  since here the interval length will not go to zero in general.

Output

• The number of function evaluations used.
• The best approximation found for the zero and the corresponding function value.
• A graphical representation of the iteration. The bars represent the position of the test points x(k).
  This is produced in the following way: the center of the plot is the zero. The length of the interval around it is reduced by the factor of ten in each picture. Hence for the superlinear convergent methods there finally no bars may appear (since we always produce the same number of pictures).

Questions ?

• Compare the methods with respect to their effort, measured in function evaluations!
• Compare the methods with respect to the final precision in the best solution found!
• Why one must use a different termination criterion for the method of false position?

To the input form