1
$\begingroup$

The question is:

Assume we change the bisection method into "tertiary bisection" which divides the interval into 3 parts and chooses the one from the left which is minimal and changes sign. e.g in the following sketch enter image description here

if the first interval is $[a,b]$ and we assign $h1=a-\frac {(b-a)} 3$,$h2=a-\frac {2(b-a)} 3$, then the chosen interval is $[a,h1]$.Give a formula for the accuracy of the method after n iterations. Is this method "better" then "regular" bisection (hint: calculate how many actions exist in iteration and compare between the algorithms).

In each iteration we define two new points and choose an interval in third of the original length. so I thought after n iterations the accuracy will be $(\frac 2 3)^n $. If it's correct, then since $\frac 2 3>\frac 1 2$whis algorithm is not as efficient as the "original" bisection. Am I right (in both sub-questions)?

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

That method reduces the interval to one third of its original width at each step and so may seem more efficient that bisecting but you have to consider that it evaluates the function twice at each step and so you should compare one third with one quarter which is what bisecting does after two function evaluations.

I conclude that the ternary method is less efficient than the binary one.

$\endgroup$
5
  • $\begingroup$ This is perfectly correct for worst case performance. However, if we evaluate at a point only if there was no sign change, then on average (?) we will only use $\frac{3}{2}$ evaluations per cycle. In that case, there seems to be a small advantage to the trisection. $\endgroup$
    – André Nicolas
    Commented Jul 19, 2013 at 2:04
  • $\begingroup$ Also, the two evaluations in the ternary method can be done in parallel (on any decent modern computer). $\endgroup$
    – bubba
    Commented Jul 19, 2013 at 2:32
  • $\begingroup$ just verifying: the formula for accuracy is indeed $(\frac 2 3 )^n$ [or $(\frac 1 3 )^n$]? $\endgroup$
    – user65985
    Commented Jul 19, 2013 at 2:48
  • $\begingroup$ The rate is $1/3)^n$ at the worst-case cost of two function evaluations, or equivalently the convergence $(1/\sqrt{3})^n$ if (large) $n$ is the number of evaluations. $\endgroup$
    – André Nicolas
    Commented Jul 19, 2013 at 3:53
  • $\begingroup$ @AndréNicolas, good point on the average case. $\endgroup$
    – lhf
    Commented Jul 19, 2013 at 3:58

You must log in to answer this question.