Math 171 - Alexiades
Finding roots - Bisection
A. Bisection code
Write a code bisect.m that
implements the bisection method for finding a root of
F(x) = 0 in an interval [a , b] to a given accuracy.
The code should accept inputs: a , b, TOL ,
should print out the iterates:
n x F(x) ERRn
(neatly, in columns, use format: %d %f %14.5e %14.5e ),
and upon convergence it should print out:
value of the root, the residual, the error and
how many iterations it took.
The (formula for the) function F(x) should be coded in a
function y = FCN(x)
You may set maxIT=100; in the code.
Of course, you must debug the code
( on a problem with known solution,
e.g. F(x)=1.3−x on [1,2], TOL=1.e-7 and 1.e-14 ).
B. Graphical method
Let's try to find the zero(s) of the function
F(x) = x3 + x2 − 3x − 3
i.e. the root(s) of the equation: F(x) = 0.
1. First, of course, we ask: Are there any?
Plot it to get an idea what the curve y=F(x) looks like.
This is easiest to do in gnuplot:
gnuplot> F(x) = x**3+x**2−3*x−3 ; plot F(x)
To see the grid: set grid ; replot
It crosses the x-axis and looks very flat on it, ...many roots ?
(think: at most how many roots could this F have ? )
Notice the very big range on the y-axis which makes small variations
invisible, so we can't really see much at this scale.
2. To resolve it better, plot it on a smaller interval, say,
gnuplot> set xrange [−2:2] ; replot
( an alternative way is: plot [−2:2] F(x) )
It looks much better, doesn't it? It crosses the axis three
times, so there are three real roots.
Write down rough estimates of the three roots
(at least 2 decimals).
3. Now let's focus on the largest root to resolve it better:
Magnify the scale (zoom-in) around the largest root:
gnuplot> set xrange [1:2] and: replot
Now it's better resolved, and can zoom-in further:
gnuplot> set xrange [1.6 : 1.8] and: replot
Repeat zooming in until you can estimate the root to at least
four decimals, and write it down.
This is the Graphical Method for finding roots of (simple) functions.
Can you "guess" the exact value of the largest root ? Write it down.
C. Bisection Method
1. Now that we know our function has a (single) root in [1, 2], and
it has opposite signs at x=1 and x=2,
we can use the Bisection Method to locate the root as accurately
as we want,
provided F(x) is continuous on [1, 2]. Is it ?
Justify your answer, mathematically !
2. Now use your bisection code on the cubic, with the following inputs:
(a) a, b, TOL: 1 , 2 , 1.e-7
(b) a, b, TOL: 1 , 2 , 1.e-14
(c) a, b, TOL: -4 , 4 , 1.e-7 and 1.e-14
(d) a, b, TOL: 1 , 2 , 1.e-15
For each run, record the values found for root and F, and how many bisections it took.
Answer the questions:
Q1: Does the root agree with your estimate from plotting ?
What are the values?
Q2: What is the effect of changing the tolerance ?
Q3: What is the effect of changing the interval [a, b] ?
Q4: Can you explain the failure in (d) ?
D. Prepare Lab3.m for submission:
In a plain text file, insert your Name, Date, Lab3
% B.2: insert the values you found in part B.2
% B.3: insert the values you found in part B.3
% C.1: insert answer to the question in part C.1
% C.2: insert answer to each of the questions Q1-Q4 in part C.2
In your bisect.m code comment out the line
that prints the iterates n x F(x) ERRn
Then insert your bisect.m code (including FCN).
Edit the file Lab3.m to clean it up,
leaving only the correct version of what's asked for in this Lab.
Make sure it runs on Matlab (and does NOT print the iterates).
Produce PDF file on Matlab:
>> publish( 'Lab3.m' , 'pdf' )
Check that the PDF file contains only what it should.
Then submit it on Canvas by due date.