Why 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 implement Dekker method to see functions with bad behaviour. I have written based on Wikipedia and [1]. But in both cases is the same.

I do with $f(x) = (x + 3)(x − 1)^2$ and range $[−4, 4/3]$. $4/3$ is near point, $-4$ is further, series approaching to $1$ but left 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

Contrapoint $c_i$ is always $-4$. I have error in implementation or this method has 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.

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.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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