Brent process

The Brent method is a numerical mathematics method for iterative determination of a zero, which combines bisection , secant method (or linear interpolation ) and inverse quadratic interpolation . The method was developed by Richard P. Brent in 1973 and is a modification of the earlier algorithm by Theodorus Dekker (1969).

Basic idea

Problem: We are looking for the zero of a continuous function. There are two starting values a and b , whose function values f ( a ) and f ( b ) have different signs , so that according to the intermediate value theorem, there is a zero in the interval . ${\ displaystyle f (x) = 0}$ ${\ displaystyle f \ colon [a, b] \ to \ mathbb {R}}$
${\ displaystyle [a, b]}$

Different approaches can now be used to solve this problem. In general, you will always come to an approximation with the bisection . But there are also methods that can converge faster for smooth functions, such as the secant method with superlinear convergence. However, there are examples where the secant method does not converge at all, since this method only converges locally, that is, it depends on how the starting values are chosen.

The Dekker method now combines the two advantages of the two methods.

Dekker's method

Three points belong to each iteration step:

${\ displaystyle b_ {k}}$ is the current iteration value
${\ displaystyle a_ {k}}$ is the opposite point, i.e. H. a point so that and have different signs so that the interval contains the zero. In addition, the following should also apply: so that is a better approximation than . ${\ displaystyle f (a_ {k})}$ ${\ displaystyle f (b_ {k})}$ ${\ displaystyle \ left [a_ {k}, b_ {k} \ right]}$ ${\ displaystyle | f (b_ {k}) | \ leq | f (a_ {k}) |}$ ${\ displaystyle b_ {k}}$ ${\ displaystyle a_ {k}}$
${\ displaystyle b_ {k-1}}$ is the previous iteration value (we set in the first iteration step ). ${\ displaystyle b_ {k-1} = a_ {0}}$

Two preliminary values are determined for each iteration step. The first by the secant method:

{\ displaystyle s = b_ {k} - {\ frac {b_ {k} -b_ {k-1}} {f (b_ {k}) - f (b_ {k-1})}} f (b_ { k}),}

and the second by the bisection:

{\ displaystyle m = {\ frac {a_ {k} + b_ {k}} {2}}.}

If the value of the secant method is between and , then this becomes the new iteration value , otherwise the midpoint after bisection ( ). ${\ displaystyle s}$ ${\ displaystyle b_ {k}}$ ${\ displaystyle m}$ ${\ displaystyle b_ {k + 1} = s}$ ${\ displaystyle b_ {k + 1} = m}$

The new point is chosen so that and have different signs, this happens as follows: if and have different signs, then will . Otherwise, and must have different signs so that . ${\ displaystyle a_ {k + 1}}$ ${\ displaystyle f (a_ {k + 1})}$ ${\ displaystyle f (b_ {k + 1})}$ ${\ displaystyle f (a_ {k})}$ ${\ displaystyle f (b_ {k + 1})}$ ${\ displaystyle a_ {k + 1} = a_ {k}}$ ${\ displaystyle f (b_ {k + 1})}$ ${\ displaystyle f (b_ {k})}$ ${\ displaystyle a_ {k + 1} = b_ {k}}$

Ultimately, the better approximation must be, so it must apply , if not, both variables are simply exchanged. ${\ displaystyle b_ {k + 1}}$ ${\ displaystyle | f (b_ {k + 1}) | \ leq | f (a_ {k + 1}) |}$

An iteration step has now been carried out.

Proceedings of Brent

The Dekker method converges quickly when the function is benign. However, there are examples in which the secant method is used in every iteration step, but which converge only very slowly. In particular, it can be arbitrarily small, i. H. is very close . In this case, Dekker's method requires far more iteration steps than bisection . ${\ displaystyle b_ {k}}$ ${\ displaystyle | b_ {k} -b_ {k-1} |}$ ${\ displaystyle b_ {k-1}}$ ${\ displaystyle b_ {k}}$

In order to avoid this, Brent modified the method slightly by using three points and to calculate the new approximation , the three points include the approximation of the last iteration step and the corresponding opposite point, the function value of which has a different sign, and a " older “approximation from a previous step. In addition, even more prerequisites are required before an interpolation is carried out at all, so that converging that is too slow can be excluded and the method does not converge much more slowly than the bisection. In addition, Brent uses not only linear interpolation but also inverse quadratic interpolation when the three points and have different function values and . This promises a somewhat better efficiency when approaching the zero point. ${\ displaystyle a, b}$ ${\ displaystyle c}$ ${\ displaystyle a, b}$ ${\ displaystyle c}$ ${\ displaystyle f (a), f (b)}$ ${\ displaystyle f (c)}$

The interpolation is carried out when the newly calculated point s lies in the interval , otherwise a bisection step is carried out. In addition, the change in the point should be greater than a certain tolerance value, which is calculated from the desired accuracy and the machine accuracy . If the step is smaller, you change point b by this tolerance step in order to at least ensure that you calculate . After such a small step by a bisection is carried out at the latest in the next but one iteration step so that the process does not converge much more slowly than the bisection itself. ${\ displaystyle \ left [{\ tfrac {3} {4}} (cb) (cb), b \ right]}$ ${\ displaystyle b_ {k + 1} = b_ {k} + d}$ ${\ displaystyle tol}$ ${\ displaystyle t}$ ${\ displaystyle \ varepsilon}$ ${\ displaystyle | b_ {k} -b_ {k-1} | \ geq tol}$ ${\ displaystyle b_ {k + 1} = b_ {k} \ pm tol}$ ${\ displaystyle tol}$

Brent shows that his method required at most iteration steps, where the number of iterations is for the bisection. If the function is benign, then the Brent method will usually use inverse quadratic or linear interpolation and thus converge superlinearly. ${\ displaystyle N ^ {2}}$ ${\ displaystyle N}$ ${\ displaystyle f}$

Brent's algorithm for Matlab

The Brent method is based on the following algorithm:

fa=f(a); fb=f(b);

if fa*fb>0
    error('f(a) und f(b) sollten unterschiedliche Vorzeichen haben');
end

c=a; fc=fa;   %Zu Beginn ist c = a

c=a; fc=fa; d=b-a; e=d;

iter=0;
maxiter=1000

while iter<maxiter
    iter=iter+1

    if fb*fc>0
        c=a; fc=fa; d=b-a; e=d;
    end

    if abs(fc)<abs(fb)
        a=b; b=c; c=a;
        fa=fb; fb=fc; fc=fa;
    end

    tol=2*eps*abs(b)+t; m=(c-b)/2; %Toleranz

    if (abs(m)>tol) && (abs(fb)>0) %Verfahren muss noch durchgeführt werden

        if (abs(e)<tol) || (abs(fa)<=abs(fb))
            d=m; e=m;
        else
            s=fb/fa;
            if a==c
                p=2*m*s; q=1-s;
            else
                q=fa/fc; r=fb/fc;
                p=s*(2*m*q*(q-r)-(b-a)*(r-1));
                q=(q-1)*(r-1)*(s-1);
            end
            if p>0
                q=-q;
            else
                p=-p;
            end
            s=e; e=d;
            if ( 2*p<3*m*q-abs(tol*q) ) && (p<abs(s*q/2))
                d=p/q;
            else
                d=m; e=m;
            end
        end

        a=b; fa=fb;

        if abs(d)>tol
            b=b+d
        else
            if m>0
                b=b+tol;
            else
                b=b-tol;
            end
        end
    else
        break;
    end

    fb=f(b);
 end

 xs=b;

example

For the function's zero located at ${\ displaystyle x = 1}$

{\ displaystyle f (x) = e ^ {- x} \ ln (x)}

With the starting values and and the desired accuracy of, the following results are obtained for the three methods: ${\ displaystyle a = 0 {,} 05}$ ${\ displaystyle b = 1 {,} 7}$ ${\ displaystyle t = 10 ^ {- 20}}$

Procedure	Number of iteration steps	Error at the end of the iteration
Brent	9	0
Secant method	does not converge in 1000 steps	not applicable
Bisection	31	1.164153 * 10 ⁻¹⁰

A closer look at the iteration steps of the Brent method:

Iteration step	applied step	current approximation x ≈
1	Linear interpolation	1.6457
2	Bisection	0.84785889251506
3	Linear interpolation	1.18604831457557
4th	Linear interpolation	1.04253452228117
5	Quadratic interpolation	0.99590946651532
6th	Linear interpolation	1.00026718046634
7th	Linear interpolation	1.00000163554039
8th	Quadratic interpolation	0.99999999999436
9	Linear interpolation	1

literature

Richard Brent: Algorithms for Minimization without Derivatives . Dover 2002
Press et al .: Numerical Recipes in C . Cambridge University Press, 1991

Web link

John Burkardt: BRENT - Algorithms for Minimization Without Derivatives , program library in C ++.