Register to reply

Show that the Bisection Method converges to...

by GTdan
Tags: bisection, converges, method
Share this thread:
GTdan
#1
Feb1-07, 09:02 PM
P: 70
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?
Phys.Org News Partner Science news on Phys.org
Apple to unveil 'iWatch' on September 9
NASA deep-space rocket, SLS, to launch in 2018
Study examines 13,000-year-old nanodiamonds from multiple locations across three continents
GTdan
#2
Feb2-07, 11:34 AM
P: 70
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



Dick
#3
Feb2-07, 12:07 PM
Sci Advisor
HW Helper
Thanks
P: 25,228
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?

GTdan
#4
Feb3-07, 11:25 PM
P: 70
Show that the Bisection Method converges to...

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
Dick
#5
Feb4-07, 11:05 AM
Sci Advisor
HW Helper
Thanks
P: 25,228
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.
GTdan
#6
Feb5-07, 01:32 AM
P: 70
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.
Dick
#7
Feb5-07, 08:01 AM
Sci Advisor
HW Helper
Thanks
P: 25,228
Ah, ok. As long as you see what the problem is in this particular case.


Register to reply

Related Discussions
Show series [sin(n)]/n converges? Calculus & Beyond Homework 51
Fortra 90 : Error in my program of bisection method Programming & Computer Science 4
Bisection method General Math 1
Bisection (trigonometry) General Math 1
Bisection method of approximation(proof) Calculus 0