Dekker's method and in its evolution Brent's method have as design goal to combine the certainty of a root, certified by function values of opposite sign in an increasingly smaller interval, of bracketing methods like bisection and regula falsi with the fast convergence of the secant (and higher degree of (reverse) interpolation) methods. Especially in the regula falsi method without modification one observes with regularity that one border of the bracketing interval becomes fixed, which causes the convergence to be linear, sometimes even slower than the bisection method.


Why experiment with the Dekker's method, not Brent's method? I have implemented Brent's method based on English Wiki but I can't understand two conditionals for $\delta$: condition 4 and condition 5.

If $\delta$ is rather big (for example $10^{-4}$) this conditionals are bad, if $\delta$ is small ($10^{-14}$) it is no difference in my sample functions.


I try to implement Dekker's method to explore functions with bad behaviour. I have written code based on Wikipedia and [1]. But in both cases is the same.

I do with $$f(x) = (x + 3)(x − 1)^2~~\text{ and range }~~[−4, 4/3].$$ $4/3$ is near the root $1$, $-4$ is further away from the root $-3$. The sequence of iteration points approaches $1$ but the left border point of the range is always $-4$.

#Based on [1]
a1=-4.00000000 b1=1.33333333 c1=-4.00000000
a2= 1.33333333 b2=1.23255814 c2=-4.00000000
a3= 1.23255814 b3=1.14122330 c3=-4.00000000
a4= 1.14122330 b4=1.08966720 c4=-4.00000000
a5= 1.08966720 b5=1.05556489 c5=-4.00000000

The contrapoint $c_i$ is always $-4$.

Do I have an error in implementation or has this method this bad behaviour in this function? How to modify point $c_i$ ?

References

  1. Bus, J. C. P., and T. J. Dekker. "Two efficient algorithms with guaranteed convergence for finding a zero of a function." ACM Transactions on Mathematical Software (TOMS) 1.4 (1975): 330-345.

put on hold as unclear what you're asking by David Ketcheson, Christian Clason, Mauro Vanzetto, nicoguaro 2 days ago

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

I think, Dekker method has bad behaviour if is more than one root in given interval.

See this method on Cleve’s Corner (http://blogs.mathworks.com/cleve/2015/10/12/zeroin-part-1-dekkers-algorithm/) where method is good enough for one root in interval.

A full log of the Dekker method run as in [1] (but with function value equality relaxed based on the tolerances) reads

    initial: x[ 0] =  -4.000000000000000,  f(x[ 0]) = -25.000000000000000;  a=x[ 0], b=x[ 0], c=x[ 0]
    initial: x[ 1] =   1.333333333333333,  f(x[ 1]) =   0.481481481481481;  a=x[ 0], b=x[ 0], c=x[ 0]
     secant: x[ 2] =   1.232558139534884,  f(x[ 2]) =   0.228910661954293;  a=x[ 0], b=x[ 1], c=x[ 0]
     secant: x[ 3] =   1.141223295849618,  f(x[ 3]) =   0.082592637299225;  a=x[ 1], b=x[ 2], c=x[ 0]
     secant: x[ 4] =   1.089667203324025,  f(x[ 4]) =   0.032881772315203;  a=x[ 2], b=x[ 3], c=x[ 0]
     secant: x[ 5] =   1.055564885924540,  f(x[ 5]) =   0.012521380362105;  a=x[ 3], b=x[ 4], c=x[ 0]
     secant: x[ 6] =   1.034592397360872,  f(x[ 6]) =   0.004827930257963;  a=x[ 4], b=x[ 5], c=x[ 0]
     secant: x[ 7] =   1.021431369375937,  f(x[ 7]) =   0.001847057878276;  a=x[ 5], b=x[ 6], c=x[ 0]
     secant: x[ 8] =   1.013276313630701,  f(x[ 8]) =   0.000707382104210;  a=x[ 6], b=x[ 7], c=x[ 0]
     secant: x[ 9] =   1.008214575350145,  f(x[ 9]) =   0.000270471306102;  a=x[ 7], b=x[ 8], c=x[ 0]
     secant: x[10] =   1.005081086844448,  f(x[10]) =   0.000103400954756;  a=x[ 8], b=x[ 9], c=x[ 0]
     secant: x[11] =   1.003141749908864,  f(x[11]) =   0.000039513380892;  a=x[ 9], b=x[10], c=x[ 0]
     secant: x[12] =   1.001942302905629,  f(x[12]) =   0.000015097489725;  a=x[10], b=x[11], c=x[ 0]
     secant: x[13] =   1.001200628613113,  f(x[13]) =   0.000005767766984;  a=x[11], b=x[12], c=x[ 0]
     secant: x[14] =   1.000742115041459,  f(x[14]) =   0.000002203347648;  a=x[12], b=x[13], c=x[ 0]
     secant: x[15] =   1.000458684641088,  f(x[15]) =   0.000000841662903;  a=x[13], b=x[14], c=x[ 0]
     secant: x[16] =   1.000283495152734,  f(x[16]) =   0.000000321500791;  a=x[14], b=x[15], c=x[ 0]
   midpoint: x[17] =  -1.499858252423633,  f(x[17]) =   9.374822745209075;  a=x[15], b=x[16], c=x[ 0]
   midpoint: x[18] =  -2.749929126211817,  f(x[18]) =   3.516488737876408;  a=x[16], b=x[17], c=x[ 0]
   midpoint: x[19] =  -3.374964563105908,  f(x[19]) =  -7.176939824849181;  a=x[17], b=x[18], c=x[ 0]
     secant: x[20] =  -2.955469385046399,  f(x[20]) =   0.696714337038388;  a=x[19], b=x[18], c=x[19]
     secant: x[21] =  -3.006254598617412,  f(x[21]) =  -0.100386782589438;  a=x[18], b=x[20], c=x[19]
     secant: x[22] =  -2.999858717256849,  f(x[22]) =   0.002260364206725;  a=x[20], b=x[21], c=x[20]
     secant: x[23] =  -2.999999559177439,  f(x[23]) =   0.000007053159416;  a=x[21], b=x[22], c=x[21]
     secant: x[24] =  -3.000000000031142,  f(x[24]) =  -0.000000000498268;  a=x[22], b=x[23], c=x[21]
exit by interval length
 best value: x[25] =  -3.000000000031142,  f(x[25]) =  -0.000000000498268;  a=x[23], b=x[24], c=x[23]

The interpretation is that the method follows first the secant method in $b_i, a_i=b_{i-1}$ towards the double root $x=1$. Because of the multiplicity the convergence is linear. As there is no exit condition based on the function value, at the moment that the points $a_i,b_i$ are close enough so that the function values are almost equal the secant root computation fails and Dekker's method switches to the midpoint of the bisection method. In the first bisection the root $x=1$ is now outside the bracketing interval/segment $[b_i,c_i]$. The bisection steps continue until the midpoint value is the first time negative, ending the stalling at $c_i=-4$. At this point the secant method restarts and now also reduces the length $|b_i-c_i|$ of the bracketing interval to zero.

Not the answer you're looking for? Browse other questions tagged or ask your own question.