Skip to main content
Contents Dark Mode Prev Up Next \(\newcommand{\N}{\mathbb N}
\newcommand{\Z}{\mathbb Z}
\newcommand{\Q}{\mathbb Q}
\newcommand{\R}{\mathbb R}
\newcommand{\bu}{\boldsymbol{u}}
\newcommand{\bv}{\boldsymbol{v}}
\newcommand{\bw}{\boldsymbol{w}}
\newcommand{\bzero}{\boldsymbol{0}}
\DeclareMathOperator{\rad}{rad}
\DeclareMathOperator{\midpt}{midpt}
\DeclareMathOperator{\diam}{diam}
\DeclareMathOperator{\mig}{mig}
\DeclareMathOperator{\magn}{mag}
\DeclareMathOperator{\abs}{abs}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\definecolor{fillinmathshade}{gray}{0.9}
\newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}}
\)
Section 8.4 Rootfinding using Intervals
Subsection 8.4.1 The Bisection Method Revisited
Let’s return to the problem we started with in
Chapter 2 in which we sought a numeric value to
\(\sqrt{65}\text{.}\) One method of solution was the bisection method from
Section 3.2 , that we revisit here with knowledge of interval arithmetic and functions of intervals.
Recall that we can “see” a root with a graph. Repeating the plot of
\(f(x) = x^2-65\)
Figure 8.4.1.
And in
Section 3.2 , we used the Intermediate Value Theorem to prove that there is a root in the interval
\([8,9]\text{.}\) With knowledge of functions on intervals,
\begin{equation*}
f([8,9]) = [-1,16]
\end{equation*}
and because \(0 \in f([8,9])\text{,}\) this proves that there is a root in the interval \([8,9]\text{.}\)
The bisection method works in almost exactly the same way with intervals. If we start with the interval \(A=[8,9]\) and define \(A_{\ell} = [8,8.5]\) and \(A_r = [8.5,9]\text{,}\) then
\begin{align*}
f(A_{\ell}) \amp = [-1,7.25] \amp f(A_r) = [7.25,16]
\end{align*}
and since \(0 \in f(A_{\ell})\text{,}\) then the root is in \([8,8.5]\text{.}\)
Algorithm 8.4.2 .
If the input is a function,
\(f\text{,}\) an interval,
\(X_0\) and
\(\epsilon\text{,}\) a interval diam for stopping, then
Check that
\(0 \in f(X_0)\) or declare an error that there is no root in the interval.
Construct
\(X_r = [\mig(X_i), \midpt(X_i)]\) and
\(X_{\ell} = [\midpt(X_i), \magn(X_i)]\text{.}\)
If
\(0 \in f(X_r)\) then
\(X_{i+1} = X_r\text{,}\) otherwise
\(X_{i+1} = X_{\ell}\)
If
\(\diam(X_{i+1}) \lt \epsilon\text{,}\) then stop. The root is in
\(X_{i+1}\text{.}\) Otherwise, go to step 2.
Subsection 8.4.2 Interval Newton’s Method
We revisit Newton’s method using intervals. To motivate this, let’s turn to a simple function
\(f(x) = x^2-5\) as shown below:
Figure 8.4.3.
Subsection 8.4.3 Krawczyk Method
Let \(f(x)\) have a zero, \(x^{\star}\) in the interval \(\boldsymbol{x}\text{.}\) The mean value theorem of \(f\) applied to the interval \([x,x^{\star}]\) where \(x \in \boldsymbol{x}\) is
\begin{equation*}
f'(\xi)(x-x^{\star}) = f(x) - f(x^{\star}) = f(x)
\end{equation*}
for some \(\xi \in [x,x^{\star}] \subset \boldsymbol{x}\text{.}\) This can be multiplied by \(C\) to get:
\begin{equation*}
C f(x) = C f'(\xi)(x-x^{\star})
\end{equation*}
adding \(x^{\star}-x\) to both sides:
\begin{equation*}
x^{\star}-x + C f(x) = x^{\star}-x + Cf'(\xi)(x-x^{\star})
\end{equation*}
or
\begin{equation*}
x^{\star} = x - C f(x) -(1-Cf'(\xi))(x-x^{\star})
\end{equation*}
since \(x^{\star}\) and \(\xi\) are both in \(\boldsymbol{x}\text{.}\)
