3.03: Bisection Methods for Solving a Nonlinear Equation

Last updated
Save as PDF

Page ID: 126400

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

$ \newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$

( \newcommand{\kernel}{\mathrm{null}\,}\) $ \newcommand{\range}{\mathrm{range}\,}$

$ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$

$ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$

$ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$ \newcommand{\Span}{\mathrm{span}}$

$ \newcommand{\id}{\mathrm{id}}$

$ \newcommand{\Span}{\mathrm{span}}$

$ \newcommand{\kernel}{\mathrm{null}\,}$

$ \newcommand{\range}{\mathrm{range}\,}$

$ \newcommand{\RealPart}{\mathrm{Re}}$

$ \newcommand{\ImaginaryPart}{\mathrm{Im}}$

$ \newcommand{\Argument}{\mathrm{Arg}}$

$ \newcommand{\norm}[1]{\| #1 \|}$

$ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\AA}{\unicode[.8,0]{x212B}}$

$ \newcommand{\vectorA}[1]{\vec{#1}} % arrow$

$ \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow$

$ \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vectorC}[1]{\textbf{#1}} $

$ \newcommand{\vectorD}[1]{\overrightarrow{#1}} $

$ \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} $

$ \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} $

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

$\newcommand{\avec}{\mathbf a}$ $\newcommand{\bvec}{\mathbf b}$ $\newcommand{\cvec}{\mathbf c}$ $\newcommand{\dvec}{\mathbf d}$ $\newcommand{\dtil}{\widetilde{\mathbf d}}$ $\newcommand{\evec}{\mathbf e}$ $\newcommand{\fvec}{\mathbf f}$ $\newcommand{\nvec}{\mathbf n}$ $\newcommand{\pvec}{\mathbf p}$ $\newcommand{\qvec}{\mathbf q}$ $\newcommand{\svec}{\mathbf s}$ $\newcommand{\tvec}{\mathbf t}$ $\newcommand{\uvec}{\mathbf u}$ $\newcommand{\vvec}{\mathbf v}$ $\newcommand{\wvec}{\mathbf w}$ $\newcommand{\xvec}{\mathbf x}$ $\newcommand{\yvec}{\mathbf y}$ $\newcommand{\zvec}{\mathbf z}$ $\newcommand{\rvec}{\mathbf r}$ $\newcommand{\mvec}{\mathbf m}$ $\newcommand{\zerovec}{\mathbf 0}$ $\newcommand{\onevec}{\mathbf 1}$ $\newcommand{\real}{\mathbb R}$ $\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}$ $\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}$ $\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}$ $\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}$ $\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$ $\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$ $\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$ $\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$ $\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}$ $\newcommand{\laspan}[1]{\text{Span}\{#1\}}$ $\newcommand{\bcal}{\cal B}$ $\newcommand{\ccal}{\cal C}$ $\newcommand{\scal}{\cal S}$ $\newcommand{\wcal}{\cal W}$ $\newcommand{\ecal}{\cal E}$ $\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}$ $\newcommand{\gray}[1]{\color{gray}{#1}}$ $\newcommand{\lgray}[1]{\color{lightgray}{#1}}$ $\newcommand{\rank}{\operatorname{rank}}$ $\newcommand{\row}{\text{Row}}$ $\newcommand{\col}{\text{Col}}$ $\renewcommand{\row}{\text{Row}}$ $\newcommand{\nul}{\text{Nul}}$ $\newcommand{\var}{\text{Var}}$ $\newcommand{\corr}{\text{corr}}$ $\newcommand{\len}[1]{\left|#1\right|}$ $\newcommand{\bbar}{\overline{\bvec}}$ $\newcommand{\bhat}{\widehat{\bvec}}$ $\newcommand{\bperp}{\bvec^\perp}$ $\newcommand{\xhat}{\widehat{\xvec}}$ $\newcommand{\vhat}{\widehat{\vvec}}$ $\newcommand{\uhat}{\widehat{\uvec}}$ $\newcommand{\what}{\widehat{\wvec}}$ $\newcommand{\Sighat}{\widehat{\Sigma}}$ $\newcommand{\lt}{<}$ $\newcommand{\gt}{>}$ $\newcommand{\amp}{&}$ $\definecolor{fillinmathshade}{gray}{0.9}$

Lesson 1: Background of Bisection Method

Learning Objectives

After successful completion of this lesson, you should be able to

1) articulate the background to the bisection method

Introduction

One of the first numerical methods developed to find the root of a nonlinear equation $f(x) = 0$ was the bisection method (also called the binary-search method). The procedure is based on the following theorem.

Theorem

An equation$f(x) = 0$, where $f(x)$ is a real continuous function, has at least one root between $x_{l}$ and $x_{u}$ if $f(x_{l})f(x_{u}) < 0$ (See Figure $\PageIndex{1.1}$).

Note that if $f(x_{l})f(x_{u}) > 0$, there may or may not be any root between $x_{l}$ and $x_{u}$ (Figures $\PageIndex{1.2}$ and $\PageIndex{1.3}$). If $f(x_{l})f(x_{u}) < 0$, then there may be more than one root between $x_{l}$ and $x_{u}$ (Figure $\PageIndex{1.4}$). So the theorem only guarantees one root between $x_{l}$ and $x_{u}$.

Since the method is based on finding the root between two points, the technique falls under bracketing methods.

Since the root is bracketed between two points, $x_{l}$ and $x_{u}$, one can find the midpoint $x_{m}$ between $x_{l}$ and $x_{u}$. We hence get two new intervals $x_{l}$ and $x_{m}$, and $x_{m}$ and $x_{u}$.

A real, continuous function f(x) changes sign between points x_l and x_u, meaning at least one root exists between those points. — Figure $\PageIndex{1.1}$. At least one root exists between the two points if the function is real, continuous, and changes sign.

A function f(x) has the same sign at points x_l and x_u, but roots of the function may still exist between these points. — Figure $\PageIndex{1.2}$. If the function $f(x)$ does not change the sign between the two points, roots of the equation $f(x) = 0$ may still exist between the two points.

A function f(x) that has the same sign at points x_l and x_u may not have any roots between those points. — Figure $\PageIndex{1.3}$. If the function $f(x)$ does not change the sign between two points, there may not be any roots for the equation $f(x) = 0$ between the two points.

A function f(x) that changes sign between points x_l and x_u may have multiple roots between those points. — Figure $\PageIndex{1.4}$. If the function $f(x)$ changes the sign between the two points, more than one root for the equation $f(x) = 0$ may exist between the two points.

Is the root now between $x_{l}$ and $x_{m}$ or between $x_{m}$ and $x_{u}$? Well, one can find the sign of $f(x_{l})f(x_{m})$, and if $f(x_{l})f(x_{m}) < 0$ then the new bracket is between $x_{l}$ and $x_{m}$; otherwise, it is between $x_{m}$ and $x_{u}$. So, you can see that you are halving the interval. As one repeats this process, the width of the interval $\left\lbrack x_{l},x_{u} \right\rbrack$ becomes smaller and smaller, and you can zero on to the root of the equation $f(x) = 0$.

Audiovisual Lectures

Title: Bisection Method - Introduction

Summary: Learn what the bisection method of solving nonlinear equations is based on.