1

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)?

Community
  • 1

1 Answers1

1

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.

lhf
  • 216,483
  • 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. – André Nicolas Jul 19 '13 at 02:04
  • Also, the two evaluations in the ternary method can be done in parallel (on any decent modern computer). – bubba Jul 19 '13 at 02:32
  • just verifying: the formula for accuracy is indeed $(\frac 2 3 )^n$ [or $(\frac 1 3 )^n$]? –  Jul 19 '13 at 02:48
  • 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. – André Nicolas Jul 19 '13 at 03:53
  • @AndréNicolas, good point on the average case. – lhf Jul 19 '13 at 03:58