Manipulating an inequality in the bisection method

[reed2100]

Homework Statement

This is a homework problem for a numerical analysis class.

Use the following theorem to find bounds for the number of iterations needed to achieve an approximation with accuracy 10^-5 to the solution of the equation given in part (a) lying in the intervals [-3,-2] and [-1,0], respectively.

Here is another solved example:
Determine the number of iterations necessary to solve f (x) = x3 + 4x2 − 10 = 0 with
accuracy 10^−3 using a1 = 1 and b1 = 2.
| Pn − p| ≤ 2^−n(b − a) = 2^−n < 10^−3.

Homework Equations

Theorem 2.1
Suppose that f ∈ C[a, b] and f (a) ·f (b) < 0. The Bisection method generates a sequence
{ pn}∞
n=1 approximating a zero p of f with
| pn − p| ≤ b − a
2n , when n ≥ 1.

The Attempt at a Solution

I'm going crazy trying to remember and make sense of the inequality rules. Here's what I tried first.

|10^-5| ≤ (1) / 2^n

1 / (10^5) ≤ 1 / (2^n)

2^n ≤ 10^5
n * ln(2) ≤ 5*ln(10)
n ≤ 5*ln(10) / ln(2)
n ≤ 16.6

Obviously this is incorrect, even just intuitively. As the number of iterations increases the accuracy should increase toward infinity, so you would think that it should say n ≥ 16.6, or that n is really just 17 at a minimum in order to meet the desired 10^-5 accuracy. In fact, I KNOW the answer is 17 iterations from using provided code in matlab. I'm just struggling to remember how to interpret and deal with this inequality to arrive at the correct expression.

Can anyone please show me the proper way to arrive at the proper inequality, step by step? The only guess I have at the moment is that I'm incorrectly interpreting |[p][/n] - p| or something. [p][/n] can be above or below p, so the non-absolute value could be negative or positive. So if you don't know what n is going to be, do you reverse the inequality and set that absolute value equal to the desired accuracy? Because you don't care whether the difference is one way or the other, so long as it's within the desired range? Any help understanding how to do this is greatly appreciated, thank you.

 

[Dick]

Clearly, your starting point should be ##10^{-5} \ge 2^{-n}##. The value of ##n## should make the error LESS than ##10^{-5}##. The inequalities are backwards from the beginning.

 

[reed2100]

Clearly, your starting point should be ##10^{-5} \ge 2^{-n}##. The value of ##n## should make the error LESS than ##10^{-5}##. The inequalities are backwards from the beginning.

Thank you. With this and some more looking around I think I better understand how to read / work with the theorem now. I was misunderstanding the theorem and wasn't thinking it through properly. The value of |Pn - P| is supposed to be less than the specified tolerance, so since it's <= (b-a)/2^n, it follows that (b-a)/2^n <= tolerance, not tolerance <= (b-a)/2^n. Thank you for the sanity check, I really stumped myself for a bit.