Back to the on-screen lesson ·
Trapping a root between a sign change, halving the trap, counting the steps in advance, and stating exactly what a bracket does and does not guarantee.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to run bisection step by step, predict the width of the bracket and the number of steps a tolerance needs before starting, and say precisely what having a bracket does and does not establish.
You know the intermediate value theorem: a continuous function that is negative at one end of an interval and positive at the other takes the value zero somewhere between. That theorem is an existence statement, and this lesson turns it into an algorithm.
A bracket is an interval whose two ends give function values of opposite sign. Bisection replaces a bracket by whichever half is still a bracket. The tolerance is how narrow the bracket must become before the run stops. Convergence is linear when each step multiplies the error by a constant factor — here, one half.
Bisection is the method that cannot fail and cannot hurry. Start with $a < b$ where $f(a)$ and $f(b)$ have opposite signs; take $m = \tfrac{a+b}{2}$, evaluate $f(m)$, and replace the bracket by $[a, m]$ or $[m, b]$ — whichever still has opposite signs at its ends. The sign change can never be lost, so a root is trapped for ever, and the width after $n$ steps is exactly $\dfrac{b - a}{2^{n}}$ whatever the function does. Reaching a width of $\tau$ therefore takes $n \ge \log_2\dfrac{b-a}{\tau}$ steps, known before the run starts. The error falls by a constant factor each step, which is linear convergence: about three decimal digits per ten steps. What the method promises is narrow and worth stating exactly: a sign change is inside the current bracket. Not that the root is unique, not that $f$ is small there, and not — as the transfer item shows — that the sign change is a root at all.
Another way: steps
Another way: example
On $[1, 2]$ with $f(x) = x^{2} - 2$: $f(1) = -1$, $f(2) = 2$. The midpoints are $1.5$ (positive, keep the left), $1.25$ (negative, keep the right), $1.375$ (negative, keep the right), leaving $[1.375, 1.5]$ — a width of $\tfrac18$ after three steps, exactly as predicted.
A narrow bracket is not a small function value, and a small function value is not a narrow bracket. These are the two stopping tests available, and they answer different questions: the width bounds the distance to the root, while $|f(m)|$ bounds the residual. On a flat curve the residual is tiny long before the root is located; on a steep one the root is located long before the residual is tiny. A run should say which test it used.
A bracket of width $1$ is to be narrowed to $10^{-6}$.
Set $2^{-n} \le 10^{-6}$.
$2^{20} \approx 10^{6}$, so twenty steps suffice.
Twenty evaluations of $f$.
Fifty-two steps would exhaust double precision entirely, so the whole run is bounded in advance whatever $f$ is.
The cost is known before the first call.
$f(x) = (x - 3)^{2}$ has a root at $3$ and is positive everywhere else.
No sign change anywhere.
So no interval brackets it, and bisection cannot be started at all.
The method is not applicable.
A repeated root is invisible to every sign-based method; finding it needs one that looks at values, such as Newton's.
This is why other methods exist.
The first step leaves the interval from $0.5$ to $1$.
The second leaves the interval from $0.75$ to $1$.
A width of one quarter, which is the starting width divided by four.
Bisection is run on $f(x) = x^{2} - 12$ starting from the interval between $3$ and $4$. Fill in each step's midpoint and the value of $f$ there.
| Left end | Midpoint | Value of f there | Right end | |
|---|---|---|---|---|
| Step 1 | 3 | 4 | ||
| Step 2 | 3 | 3.5 | ||
| Step 3 | 3.25 | 3.5 |
Bisection has run $11$ steps on a continuous $f$, starting from a bracket of width $1$. What may you conclude?
Put one turn of the bisection loop into order, for a run that is to stop after at most $14$ steps.
Number the steps in order (write the number in the box):
Bisection started between $3$ and $4$, kept the left half, then the right half of that. Place the next point it will evaluate.
3 |——————————| 4
Mark the position with a cross, then write the value:
Bisection is started on an interval around $2$ in each of four situations. Match each to what the method actually does.
| Converges to that root, at one evaluation a step | Converges to one of them, chosen by the halvings, and never mentions the rest | Refuses to start: the ends agree in sign although a root is inside | Converges neatly to a point where the function is not even finite | |
|---|---|---|---|---|
| One simple root inside, signs differing at the ends | ||||
| Three simple roots inside, signs differing at the ends | ||||
| A repeated root at $2$, as in $(x - 2)^{2}$ | ||||
| A pole at $2$, as in $\dfrac{1}{x - 2}$ |
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Bisection starts on an interval of width $2^{1}$. How many steps are needed before the bracket is at most $2^{-6}$ wide?
Answer:
You can carry out a bisection trace, count the steps a tolerance needs, and state the guarantee exactly. Say in your own words why the number of steps does not depend on the function at all.
8. Your turn: the bracket after two steps from $[0, 1]$, keeping the right half both times, step 3