Manipulating an inequality in the bisection method

In summary, the theorem states that a sequence with an approximation to the solution of a equation can be generated using the bisection method. The bisection method generates a sequence of approximations to the zero point of the function. The sequence has an error less than the specified tolerance.
  • #1
reed2100
49
1

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.
 
Physics news on Phys.org
  • #2
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.
 
  • #3
Dick said:
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.
 

Related to Manipulating an inequality in the bisection method

1. What is the bisection method?

The bisection method is a numerical algorithm used to solve inequalities. It works by repeatedly dividing an interval into two smaller intervals and checking which interval contains the solution.

2. How do you manipulate an inequality in the bisection method?

To manipulate an inequality in the bisection method, you need to choose an initial interval that contains the solution, then divide the interval into two smaller intervals and check which interval contains the solution. Repeat this process until the solution is within a desired level of accuracy.

3. What is the role of the bisection method in solving inequalities?

The bisection method is an efficient and reliable way to find solutions to inequalities. It is especially useful when the inequality cannot be solved analytically or when other numerical methods may not converge to the solution.

4. What are the advantages of using the bisection method?

One of the main advantages of the bisection method is that it always converges to a solution, as long as the inequality is continuous and has a unique solution. It is also a relatively simple algorithm to understand and implement, making it accessible to a wide range of users.

5. Are there any limitations to the bisection method?

The bisection method may not be the most efficient algorithm for solving inequalities, as it requires a large number of iterations to achieve a high level of accuracy. It also cannot be used for inequalities with multiple solutions or when the solution is not within the chosen initial interval.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
2
Views
1K
  • Precalculus Mathematics Homework Help
Replies
11
Views
1K
  • Precalculus Mathematics Homework Help
Replies
3
Views
3K
  • Precalculus Mathematics Homework Help
Replies
21
Views
1K
  • Precalculus Mathematics Homework Help
Replies
11
Views
1K
  • Precalculus Mathematics Homework Help
Replies
34
Views
3K
Replies
1
Views
9K
  • Precalculus Mathematics Homework Help
Replies
8
Views
2K
  • Precalculus Mathematics Homework Help
Replies
4
Views
2K
  • Precalculus Mathematics Homework Help
Replies
11
Views
2K
Back
Top