Brent's method

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

The basic idea

Problem: Find the zero of a continuous function Given are two starting values ​​a and b, whose function values ​​have f (a ) and f ( b ) have different signs, so that after intermediate value theorem one zero in the interval exist.

To solve this problem you can now use different approaches. In general, it will always come with the bisection to an approximation. But there are also methods that can converge faster for smooth functions, such as the secant method with super -linear convergence. However, there are examples where the secant does not converge, since this method is only locally convergent, that is, it depends on how the initial values ​​are chosen.

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

Method of Dekker

Three points belong to each iteration:

• Bk is the current iteration
• Ak is the opposite point, i.e. a point, so that f ( a k ) and f ( BK) have different signs, so that the interval [ k, b k ] contains the root. In addition, the following should still apply: | f (bk ) | ≤ | f ( ak) |, so that bk is a better approximation than ak
• Bk -1 is the previous iteration ( in the first iteration, we continued bk- 1 = a0).

For each iteration two preliminary values ​​are calculated. The first by the secant method:

And the second by the bisection:

If the value of S is between the secant and bk m, then, the new iteration (bk 1 = S), otherwise the center to bisection (bk 1 = m).

The new point ak 1 is chosen such that f (ak 1 ) and f ( bk 1) have different signs, this is done as follows: if f (ak ) and f ( bk 1) have different signs, then ak 1 = ak Otherwise have f ( bk 1 ) and f ( bk ) have different signs, so that ak 1 = bk.

Finally, bk 1 must be a better approximation, so it must be true | f (bk 1) | ≤ | f (ak 1 ) |, if not simply be exchanged both variables.

An iteration step is thus carried out.

Method of Brent

The Dekker method converges rapidly if the function is benign. However, there are examples where in each iteration step, the secant method is used, but the bk converge very slowly. In particular, | bk - bk- 1 | can be arbitrarily small, ie bk- 1 is very close to bk. In this case, Dekkers method requires far more iterations than the bisection.

To avoid this, Brent, the method slightly modified, can be used in the calculation of the new approximation, optionally three points a, b ​​and c, the three points include the approximation of the last iteration and the respective opposite point, the function value has a different sign, and an "older " approximation from a previous step. Also more requirements are required before any interpolation is performed, so that a too slow convergence can be excluded, and the process does not converge more slowly than the bisection. Brent also used not only linear interpolation, but also the inverse quadratic interpolation, when the three points a, b and c are different function values ​​f ( A) f (b ) and f ( c) have. This promises to be a slightly better efficiency, when approaching the zero point.

The interpolation is performed if the resulting new calculated point s in the interval [( cb), b] is, otherwise you are leading an Bisektionsschritt by. In addition to the change of the point bk 1 = bk d be larger than a certain tolerance value which is calculated from the desired accuracy and the machine precision. If the step be smaller, changing the point b to these tolerance step to at least | bk - bk- 1 | to ensure, so one expects bk 1 = bk. After such a small step to be carried out no later than a bisection in the next iteration, so as not converge much slower to make the process as the bisection itself.

Brent shows that his method most N iterations required ², where N is the number of iterations for the bisection. If the function f is benign, then the Brent method is to use the inverse square or linear interpolation in general and thus converge superlinearly.

Algorithm of Brent for Matlab

The following algorithm is based on the Brent method:

Fa = f ( a); fb = f ( b);   if fa * fb > 0      error ( ' f (a ) and f ( b ) should have different signs '); end   c = a; fc = fa; % Initially, 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; % tolerance        if ( abs ( m) > tol) && ( abs ( fb )> 0) % method has yet to be carried out            if ( abs ( e) < tol) | | ( abs ( fa) < = abs ( fb) )              d = m; s = 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; s = 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 at location zero of the function

Obtained with the starting values ​​and and the desired accuracy of the following for the three procedures:

The iteration of the Brent method considered in more detail: