Roots of Nonlinear Functions

Amsterdam Method

Amsterdam Method: Mueller's method, van Wijngaarden,Dekker, Brent method

Mueller created a method of finding roots of a nonlinear equation by a method of successive bisection and inverse quadratic interpolation. His technique has undergone refinements by van Wijngaarden, Dekker and later Brent. The numerical method programmed below requires initial estimates which bracket a root in which the function evaluated at the two initial estimates has opposite signs. Initially, the midpoint is chosen as a third estimation point. The procedure then iterates by trying to fit a quadratic in the ordinate values and interpolate for the zero of the quadratic. If the zero is within the bounds of the bounding estimates, that value is used to reduce the length of the bracketing interval, if the zero is exterior to the bounding estimates, the bisection method is employed and the interval is halved. If the new estimate is too near one of the endpoints, the next estimate is either the midpoint or the process is terminated because the root has been determined within a preassigned tolerance. The inverse quadratic interpolation - bisection method should be the method of choice when trying to find a root of a real-valued function of a real-value. Some tests I have made, shows that it requires upto 1/3 of the number of function calls of the Illinois Algorithm, about the same number of function calls as the secant method which depends different initial conditions, and fewer than the Newton-Raphson which required two function calls per iterative step. Moreover, this method is not susceptible to poor estimates due to local minima and maxima as the secant method or the Newton-Raphson method can be.

Function List

  • double Amsterdam_Method( double (*f)(double), double a, double c, double tolerance, int max_iterations, int *err )

    Find a root of f(x) in the interval ( min(a,c), max(a,c) ) where f(a)·f(c) < 0. The procedure terminates when the absolute difference of the return value and the actual root is less than tolerance, where tolerance is a user specified number specifying the desired accuracy of the result. The method returns an err of 0 if the iteration was successful, -1 if the initial estimates fail to satify the requirement that the function evaluated at the two values must have opposite signs, and -2 if the number of iterations exceed the number max_iterations specified by the user.

C Source Code