560 Appendix A
found by interpolatingflinearly betweenx 1 andx 2 , resulting in a location
x 3 =
x 2 f 1 −x 1 f 2
f 1 −f 2. (A.6)
Iff 3 =f(x 3 )andf 1 have opposite signs, we can be sure that the root lies between
x 1 andx 3 and the procedure is repeated for the interval[x 1 ,x 3 ], else the root lies
in the interval[x 3 ,x 2 ]and this is used in the next step. The procedure stops when
either the size of the interval lies below a prescribed value, or the absolute value of
the function is small enough.
Instead of checking which of the intervals,[x 1 ,x 3 ]or[x 3 ,x 2 ]contains the root,
we might simply use the twox-values calculated most recently to predict the next
one. In that case we use an equation similar to(A. 6 ):
xn+ 1 =
xnfn− 1 −xn− 1 fn
fn− 1 −fn. (A.7)
Here,xnis the value ofxobtained at thenth step, so the pointsxnandxn− 1 do not
necessarily enclose the root. This method, called thesecant method, is slightly more
efficient than the regula falsi;regula falsi methodit has a convergence exponent
equal to the golden mean 1.618.... If the function has a very irregular behaviour,
these methods become less efficient and it is more favourable in that case to take
at each step the middle of the current bracket interval as the new point, and then
check whether the root lies in the left or in the right half of the current interval.
This method is called the bisection method. As the size of the intervals is halved at
each step, the exponentytakes on the value 1. For more elaborate and fault-proof
methods,seeRef.[1].
For the Newton–Raphson method, the derivative of the function must be cal-
culated, which is not always possible. Again, a prediction based on a linear
approximation of the functionfis made. Starting with a pointx 0 lying close to
the root, the values off(x 0 )≡f 0 and of its derivativef′(x 0 )≡f 0 ′suffice to make a
linear interpolation forf, resulting in a guessx 1 for the location of the root:
x 1 =x 0 −f 0
f 0 ′. (A.8)
Just as in the secant method or the regula falsi, this procedure is repeated until the
convergence criterion is satisfied. Notice that for a successful guess of the root,
the sign of the derivative of the functionf must not change in the region where
the pointsxiare located. The convergence of this method is quadratic, that is, the
scaling exponentyis equal to 2.
A4 Finding the optimum of a function
Suppose we want to locate the point where a functionfassumes its minimum (for
a maximum, we consider the function−f and apply a minimisation procedure).