Bisection

•

ESTÁCIO

1

0

1

0

Camila Barata Cavalcanti

30.08.2015

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Click to edit Master title style
Click to edit Master subtitle style
*
*
*
Roots of a Nonlinear Equation
Topic: Bisection Method
Major: General Engineering
http://numericalmethods.eng.usf.edu
*
 *
*
Basis of Bisection Method
	Theorem:
An equation f(x)=0, where f(x) is a real continuous function, has at least one root between xl and xu if f(xl) f(xu) < 0.
http://numericalmethods.eng.usf.edu
 x
 f(x)
 xu
 x
*
 *
*
Theorem
 If function f(x) in f(x)=0 does not change sign between two points, roots may still exist between the two points. 
http://numericalmethods.eng.usf.edu
 x
 f(x)
 xu
 x
*
 *
*
Theorem
If the function f(x) in f(x)=0 does not change sign between two points, there may not be any roots between the two points. 
http://numericalmethods.eng.usf.edu
 x
 f(x)
 xu
 x
 x
 f(x)
 xu
 x
*
 *
*
Theorem
If the function f(x) in f(x)=0 changes sign between two points, more than one root may exist between the two points.
http://numericalmethods.eng.usf.edu
 x
 f(x)
 xu
 x
 
*
 *
*
Algorithm for Bisection Method
http://numericalmethods.eng.usf.edu
*
 *
*
Step 1
Choose xl and xu as two guesses for the root such that f(xl) f(xu) < 0, or in other words, f(x) changes sign between xl and xu. 
http://numericalmethods.eng.usf.edu
 x
 f(x)
 xu
 x
*
 *
*
Step 2
Estimate the root, xm of the equation f (x) = 0 as the mid-point between xl and xu as
http://numericalmethods.eng.usf.edu
 x
 f(x)
 xu
 x
*
 *
*
Step 3
Now check the following
If f(xl) f(xm) < 0, then the root lies between xl and xm; then xl = xl ; xu = xm.
If f(xl ) f(xm) > 0, then the root lies between xm and xu; then xl = xm; xu = xu.
If f(xl) f(xm) = 0; then the root is xm. Stop the algorithm if this is true.
http://numericalmethods.eng.usf.edu
 x
 f(x)
 xu
 x
 xm
*
 *
*
Step 4
New estimate
Absolute Relative Approximate Error
http://numericalmethods.eng.usf.edu
*
 *
*
Step 5
Check if absolute relative approximate error is less
than prespecified tolerance or if maximum number
of iterations is reached. 
Yes
No
Stop
Using the new upper and lower guesses from Step 3, go to Step 2.
http://numericalmethods.eng.usf.edu
*
 *
*
Example
You are working for ‘DOWN THE TOILET COMPANY’ that makes floats for ABC commodes. The ball has a specific gravity of 0.6 and has a radius of 5.5 cm. You are asked to find the distance to which the ball will get submerged when floating in water.
http://numericalmethods.eng.usf.edu
*
 *
*
Solution
The equation that gives the depth ‘x’ to which the ball is submerged under water is given by 
Use the Bisection method of finding roots of equations to find the depth ‘x’ to which the ball is submerged under water. Conduct three iterations to estimate the root of the above equation. 
http://numericalmethods.eng.usf.edu
*
 *
*
Graph of function f(x)
http://numericalmethods.eng.usf.edu
*
 *
*
Checking if the bracket is valid
Choose the bracket
http://numericalmethods.eng.usf.edu
*
 *
*
Iteration #1
http://numericalmethods.eng.usf.edu
*
 *
*
Iteration #2
http://numericalmethods.eng.usf.edu
*
 *
*
Iteration #3
http://numericalmethods.eng.usf.edu
*
 *
*
Convergence
Table 1: Root of f(x)=0 as function of number of iterations for bisection method.
http://numericalmethods.eng.usf.edu
		Iteration
		x
		xu
		xm
		
�%
		f(xm)
		1
2
3
4
5
6
7
8
9
10
		0.00000
0.055
0.055
0.055
0.06188
0.06188
0.06188
0.06188
0.0623
0.0623
		0.11
0.11
0.0825
0.06875
0.06875
0.06531
0.06359
0.06273
0.06273
0.06252
		0.055
0.0825
0.06875
0.06188
0.06531
0.06359
0.06273
0.0623
0.06252
0.06241
		----------
33.33
20.00
11.11
5.263
2.702
1.369
0.6896
0.3436
0.1721
		6.655x10-5
-1.6222x10-4
-5.5632x10-5
4.4843x10-6
-2.5939x10-5
-1.0804x10-5
-3.1768x10-6
6.4973x10-7
-1.2646x10-6
-3.0767x10-7
_921652806.unknown
*
 *
*
Advantages
Always convergent
The root bracket gets halved with each iteration - guaranteed.
http://numericalmethods.eng.usf.edu
*
 *
*
Drawbacks
Slow convergence
http://numericalmethods.eng.usf.edu
*
 *
*
Drawbacks (continued)
If one of the initial guesses is close to the root, the convergence is slower
http://numericalmethods.eng.usf.edu
*
 *
*
Drawbacks (continued)
If a function f(x) is such that it just touches the x-axis it will be unable to find the lower and upper guesses.
http://numericalmethods.eng.usf.edu
Chart3
		0
		1
		4
		9
		16
		25
		36
		49
		64
		81
		100
		
		0
		1
		4
		9
		16
		25
		36
		49
		64
		81
		100
f(x)
x
Sheet1
		
		0		0
		1		1
		2		4
		3		9
		4		16
		5		25
		6		36
		7		49
		8		64
		9		81
		10		100
		
		0		0
		-1		1
		-2		4
		-3		9
		-4		16
		-5		25
		-6		36
		-7		49
		-8		64
		-9		81
		-10		100
Sheet1
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
f(x)
x
Sheet2
		
Sheet3
		
*
 *
*
Drawbacks (continued)
Function changes sign but root does not exist
http://numericalmethods.eng.usf.edu
Chart4
		10
		5
		3.3333333333
		2.5
		2
		1
		0.5
		0.3333333333
		0.25
		0.2
		0.1666666667
		0.1428571429
		0.125
		0.1111111111
		0.1
		
		-10
		-5
		-3.3333333333
		-2.5
		-2
		-1
		-0.5
		-0.3333333333
		-0.25
		-0.2
		-0.1666666667
		-0.1428571429
		-0.125
		-0.1111111111
		-0.1
f(x)
x
Sheet1
		
		0		0
		1		1
		2		4
		3		9
		4		16
		5		25
		6		36
		7		49
		8		64
		9		81
		10		100
		
		-1		1
		-2		4
		-3		9
		-4		16
		-5		25
		-6		36
		-7		49
		-8		64
		-9		81
		-10		100
		
		
		
		
		
		0.1		10
		0.2		5
		0.3		3.3333333333
		0.4		2.5
		0.5		2
		1		1
		2		0.5
		3		0.3333333333
		4		0.25
5		0.2
		6		0.1666666667
		7		0.1428571429
		8		0.125
		9		0.1111111111
		10		0.1
		
		-0.1		-10
		-0.2		-5
		-0.3		-3.3333333333
		-0.4		-2.5
		-0.5		-2
		-1		-1
		-2		-0.5
		-3		-0.3333333333
		-4		-0.25
		-5		-0.2
		-6		-0.1666666667
		-7		-0.1428571429
		-8		-0.125
		-9		-0.1111111111
		-10		-0.1
Sheet1
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
f(x)
x
Sheet2
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
		0
f(x)
x
Sheet3
		
		
http://numericalmethods.eng.usf.edu
http://numericalmethods.eng.usf.edu
http://numericalmethods.eng.usf.edu
http://numericalmethods.eng.usf.edu
http://numericalmethods.eng.usf.edu
http://numericalmethods.eng.usf.edu
http://numericalmethods.eng.usf.edu
http://numericalmethods.eng.usf.edu
http://numericalmethods.eng.usf.edu
http://numericalmethods.eng.usf.edu
http://numericalmethods.eng.usf.edu
http://numericalmethods.eng.usf.edu
http://numericalmethods.eng.usf.edu
http://numericalmethods.eng.usf.edu
http://numericalmethods.eng.usf.edu
http://numericalmethods.eng.usf.edu
http://numericalmethods.eng.usf.edu
http://numericalmethods.eng.usf.edu
http://numericalmethods.eng.usf.edu
http://numericalmethods.eng.usf.edu
http://numericalmethods.eng.usf.edu
http://numericalmethods.eng.usf.edu
http://numericalmethods.eng.usf.edu
http://numericalmethods.eng.usf.edu