Section3.1The Bisection Method
Theorem3.1.1The Intermediate Value Theorem
If \(f\) is a continuous function on the closed interval \([a,b]\) and \(y_*\) lies between
\(f(a)\) and \(f(b)\), then there is a point \(x \in [a,b]\) where \(f(x) = y_*\).
Draw a picture of what the intermediate value theorem says graphically.
If \(y_*=0\) the intermediate value theorem gives us important information about solving
equations. What does it tell us?
The following (partial) algorithm (known as the Bisection Method) uses the Intermediate
Value Theorem to systematically approximate solutions to the algebraic equation \(f(x) =
0\).
Assume that \(f(x)\) is continuous on the interval \([a,b]\). To make approximations of
the solutions to the equation \(f(x) = 0\), do the following:
Check to see if \(f(a)\) and \(f(b)\) have opposite signs
(why is this important?).
Compute the midpoint \((a+b)/2\) and evaluate \(f(\frac{a+b}{2})\).
Compare the signs of \(f(a)\), \(f(b)\), and \(f(\frac{a+b}{2})\). Replace one of
the endpoints with \((a+b)/2\) … which one and why?
Repeat steps 2 and 3
Stop when \(a\) and \(b\) are close enough to each other
Draw a picture illustrating what the Bisection Method does to approximate solutions to
the algebraic equation \(f(x) = 0\).
Write a MATLAB function for the Bisection Method. Be sure that it can take an
anonymous function handle as an input along with an initial lower bound, an initial
upper bound, and an error tolerance.
Test your Bisection Method code on the following algebraic equations.
\(x^2 - 2 = 0\) on \(x \in [0,2]\)
\(\sin(x) + x^2 = 2\ln(x) + 5\) on \(x \in [0,5]\) (be careful! make a plot
first)
\((5-x)e^{x}=5\) on \(x \in [0,5]\)
Let \(f(x)\) be a continuous function on the interval \([a,b]\) and assume that \(f(a)
\cdot f(b) \lt 0\). If we want to approximate the solution to the equation \(f(x)=0\) to
within \(\delta\) how many iterations will the bisection method need?
Hint: If we
want an approximation within \(\delta\) then the width of the interval is \(2\delta\).
How many iterations of the bisection method are necessary to approximate \(\sqrt{3}\) to
within \(10^{-3}\), \(10^{-4}\), …, \(10^{-15}\) using the initial interval
\([a,b]=[0,2]\)?
(Coding Challenge) The sum of the squares of the first ten natural numbers is,
\begin{equation*}
1^2 + 2^2 + \dots + 10^2 = 385
\end{equation*}
The square of the sum of the first ten natural numbers is,
\begin{equation*}
(1 + 2 + \dots + 10)^2 = 55^2 = 3025
\end{equation*}
Hence the difference between the sum of the squares of the first ten natural numbers
and the square of the sum is \(3025 - 385 = 2640\).
Write code to find the difference between the sum of the squares of the first one
hundred natural numbers and the square of the sum. Your code needs to run error free
and output only the difference. Consult Chapter 2 of the text if you are stuck.
(Coding Challenge) The prime factors of \(13195\) are \(5, 7, 13\) and \(29\). Write
code to find the largest prime factor of the number \(600851475143\)? Your code needs to
run error free and output only the largest prime factor. Consult Chapter 2 of the text if you are
stuck.
On page 79 of the text the author describes the regula falsi method for solving
algebraic equations of the form \(f(x)=0\). Write MATLAB code to implement the regula falsi method and test it on the previous problems. Compare the number of
iterations necessary for convergence to within \(10^{-8}\) for both the bisection method
and the regula falsi method on several test problems. Find example problems where
bisection converges faster and examples where regula falsi converges faster.