Show that the Bisection Method converges to

In summary: I'll keep that in mind.Thanks!In summary, the Bisection method fails to converge to zero for the case of -1<a<0 and 2<b<3.
  • #1
GTdan
39
0
1. The function defined by f(x)=[tex]\sin(\pi*x)[/tex]has zeros at every integer x. Show that when -1<a<0 and 2<b<3, the Bisection method converges to

a. 0, if a+b<2
b. 2, if a+b>2
c. 1, if a+b=2


2. Bisection Method

An interval [tex][a_{n+1},b_{n+1}][/tex]containing an approximation to a root of f(x)=0 is constructed from an interval [tex][a_{n},b_{n}][/tex] containing the root by first letting

[tex]p_{n}=a_{n}+\frac{(b_{n}-a_{n})}{2}[/tex]

Then set
[tex]a_{n+1}=a_{n}[/tex] and [tex]b_{n+1}=p_{n}[/tex] if [tex]f(a_{n})*f(p_{n})<0[/tex]

and

[tex]a_{n+1}=p_{n}[/tex] and [tex]b_{n+1}=b_{n}[/tex] otherwise.

3. I attempted to randomly choose numbers for a and b to satisfy the relations a+b<2 , -1<a<0, and 2<b<3. I picked a=-0.5 and b=2.5 and went through many iterations of the Bisection method to see if p[n] converged to zero. It didn't. I'm not sure if I am approaching the problem correctly. Can someone give me a good head start with this?
 
Last edited:
Physics news on Phys.org
  • #2
Ok, I thought that maybe I wasn't doing enough iterations. So to avoid hours of number crunching I wrote the bisection method in True Basic code and made it print out the results so I could graph it. It worked for parts (a) and (b) because when I graph p vs n, p converges to 0 for part (a) and 2 for part (b). Strangely enough, when I do the same for part (c) it converges to 0 instead of 1. Can anyone tell me why?

I did the same as before:
For part (a) I used a=- 0.75 and b= 2.5
part (b) a= -0.25 and b= 2.5
part (c) a=-0.5 and b=2.5

Here is the code and graphs of all 3 parts:

Code
program Bisection

option nolet
input prompt "a: ":aa
input prompt "b: ":bb
input prompt "TOL: ":tol
print "Enter file name for saving data (enter it as filename.dat)"
input prompt "(AND make sure there isn't already a file with that name): ": file$
open #23: name file$, access output, create newold, org text
nn=log((bb-aa)/tol)/log(2)
kk=1
print "a", "b", "f*f", "p", "k"
print #23: "a", "b", "f*f", "p", "k"
do while kk<nn
pp=aa+(bb-aa)/2
ff=sgn(sin(Pi*pp))*sgn(sin(Pi*aa))
print aa, bb, ff, pp, kk
print #23: aa, bb, ff, pp, kk
if ff<0 then
bb=pp
else
aa=pp
end if
kk=kk+1
loop
pp=aa+(bb-aa)/2
print aa, bb, ff, pp, kk
print #23: aa, bb, ff, pp, kk
end

Graphs

http://home.comcast.net/~dannyrod/parta.jpg [Broken]
http://home.comcast.net/~dannyrod/partb.jpg [Broken]
http://home.comcast.net/~dannyrod/partc.jpg [Broken]
 
Last edited by a moderator:
  • #3
Your general problem here is that floating point numbers are not exact. In the a=-0.5, b=2.5 case your first midpoint is at 1.0. In an ideal world the value of the function SHOULD be exactly zero there. But it is not. So it tries for another midpoint either to the right or left of 1.0 - which one depends on roundoff error. It should have actually STOPPED at 1.0. How can you fix it?
 
  • #4
Oh ok. Thanks. Maybe if I set a and b so that it doesn't equal 1 exactly, it will converge like it's supposed to. I'll try it and let you know. Thanks
 
  • #5
That will work - but it's not a complete solution. Your current algorithm doesn't have any way to terminate. Since you can't generally expect to find an x value such that f(x)=0.0 EXACTLY, one easy way out is to pick a small number d and stop if f(x)<d. Also you probably want to terminate if |a-b|<e for some other small number e.
 
Last edited:
  • #6
Well I have it set so that the while loop terminates within a tolerance:

nn=log((bb-aa)/tol)/log(2)
kk=1
.
.
do while kk<nn


You input tolerance at the beginning and it gives you nn, an approximate number of iterations. I have it set so that once kk > nn, the loop stops. The problem usually gives a tolerance, but since this problem didn't, I chose a really small tolerance so I could be as accurate as possible.
 
  • #7
Ah, ok. As long as you see what the problem is in this particular case.
 

1. How does the Bisection Method work?

The Bisection Method is an algorithm used to find the root of a continuous function. It works by repeatedly dividing an interval in half and then checking whether the root lies in the left or right half. This process is continued until the interval becomes small enough to contain the root.

2. What is the formula for the Bisection Method?

The formula for the Bisection Method is:
xn+1 = (xn + xn-1) / 2
where xn+1 is the next approximation of the root, xn and xn-1 are the current approximations, and n is the iteration number.

3. How do you know when the Bisection Method has converged?

The Bisection Method is considered to have converged when the difference between two consecutive approximations is smaller than a given tolerance value. This means that the root has been found within a certain degree of accuracy.

4. What are the advantages of using the Bisection Method?

The Bisection Method is relatively easy to implement and is guaranteed to converge if certain conditions are met. It also does not require the function to be differentiable, making it suitable for a wider range of functions.

5. Are there any limitations to the Bisection Method?

One limitation of the Bisection Method is that it may converge slowly, especially if the initial interval is large. It also requires the function to have different signs at the endpoints of the interval, which may not always be the case. Additionally, for functions with multiple roots, the Bisection Method may only find one of them.

Similar threads

  • Calculus and Beyond Homework Help
Replies
2
Views
88
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
5
Views
435
  • Calculus and Beyond Homework Help
Replies
3
Views
515
  • Calculus and Beyond Homework Help
Replies
1
Views
89
  • Calculus and Beyond Homework Help
Replies
11
Views
1K
  • Calculus and Beyond Homework Help
Replies
8
Views
1K
  • Calculus and Beyond Homework Help
Replies
12
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
273
Replies
1
Views
569
Back
Top