Non-Linear Equations

Bisection Method

Suppose $f:[a,b]\mapsto \mathbb{R}$, $a<b$ and suppose we want to find $x_{\ast }\in [a,b]$ such that $f(x_{\ast })=0$

For special $f$s we can get an exact solution in closed form, but this is the exception rather than the rule… In many cases, we can’t even write $f$ in closed form and instead treat it as a kind of black box with unpredictable behavior.

To find a root in the general case, we will work with an algorithm that generates a sequence $\{x_k{\}}_{k\ge 0}$ where $x_k\to x_{\ast }$ as $k\to \infty$, minimizing $|x_k-x_{\ast }|$

In practice, we’re looking to satisfy $|x_k-x_{\ast }|\le \mathcal{F}(k,f,x_0,\dots ,x_k)$, where $\mathcal{F}$ is a computable error bound

We want an algorithm that is,

• Robust - Always gives an approximate solution
• Accurate - Gets closer with more computation with a computable error bound
• Efficient - Gets to an approximation in as few evaluations as possible

The bisection method is a good example algorithm (but is not used in practice). It works because of the Intermediate Value Theorem; if we have an interval with a positive and negative value then there must be a zero. We iteratively cut our search interval in half, basically like binary search, until the length of the interval is satisfactory for our error bound.

How do we prove this formally? We have a few useful properties to work with:

• $a_k\le x_k\le b_k$
• $a=a_0\le a_1\le \cdots \le a_k\le x_{\ast }\le b_k\le \cdots \le b_1\le b_0=b$
• $b_k-a_k=(b_{k-1}-a_{k-1})/2$

It doesn’t take much experimenting to come up with the bound $|x_k-x_{\ast }|<\frac{b-a}{2^{k+1}}$
We’d like to prove this bound formally

Theorem: Suppose $a<b$, $f:[a,b]\mapsto \mathbb{R}$ isa continuous function and $f(a)f(b)<0$. Then the sequence $\{x_k\}$ defined by the bisection algorithm converges to a limit $x_{\ast }\in (a,b)$ such that $f(x_{\ast })=0$, and $|x_k-x_{\ast }|<\frac{b-a}{2^{k+1}}$.

To prove this, note that $\{a_k\}$ is bounded above and monotonically increasing and $\{b_k\}$ is bounded below and monotonically decreasing

$b_{\ast }={\lim }_{k\to \infty }{b}_k$ and $a_{\ast }={\lim }_{k\to \infty }{a}_k$
$b_k-a_k=\frac{b_{k-1}-a_{k-1}}{2}=\frac{b-a}{2^k}$
${\lim }_{k\to \infty }{b}_k-{\lim }_{k\to \infty }{a}_k={\lim }_{k\to \infty }(b_k-a_k)={\lim }_{k\to \infty }\frac{b-a}{2^k}=0$

So let’s define $x_{\ast }=a_{\ast }=b_{\ast }$
The Pinching Theorem gives us $x_k=x_{\ast }$

Since $f$ is continuous, we can use the inequalities to show that $f(x_{\ast })=0$,
$0\le {\lim }_{k\to \infty }f(a_k)=f({\lim }_{k\to \infty }{a}_k)=f(x_{\ast })$
${\lim }_{k\to \infty }f(b_k)=f(x_{\ast })\le 0$
So $f(x_{\ast })=0$

To get the bound,
$a_k\le x_{\ast }\le b_k$
$x_k-b_k\le x_k-x_{\ast }\le x_k-a_k$
$\frac{a_k+b_k}{2}-b_k\le x_k-x_{\ast }\le \frac{a_k+b_k}{2}-a_k$
$|x_k-x_{\ast }|\le \frac{b_k-a_k}{2}=\frac{b-a}{2^{k+1}}$

Simple Iteration

Another way to find $f(x_{\ast })=0$ is by writing $f(x)=x-g(x)$ and finding a fixed point $x_{\ast }=g(x_{\ast })$

Theorem: Suppose $g:[a,b]\mapsto [a,b]$ is continuous and a contraction ($|g(x)-g(y)|\le L|x-y|$ for some $0\le L\le 1$), then $g$ has a unique fixed point $g(x_{\ast })=x_{\ast }$. Furthermore, the sequence $\{x_k\}$ defined by $x_{k+1}=g(x_k)$ converges to the unique fixed $x_{\ast }$ as $k\to \infty$, with $|x_k-x_{\ast }|\le \frac{L^k}{1-L}|x_1-x_0|$

$k\ge \lceil \frac{\ln \frac{|x_1-x_0|}{(1-L)ϵ}}{\ln \frac{1}{L}}\rceil$

This method is robust, accurate, and efficient

Sometimes the conditions of our contraction mapping theorem are hard to check and we’d still like to know if convergence is possible

Theorem: Suppose $g:[a,b]\mapsto [a,b]$ is a continuous function, let $x_{\ast }$ be a fixed point of $g$ and assume that $g$ has a continuous derivative in some neighborhood of $x_{\ast }$ with $|g^{\prime }(x_{\ast })|<1$, then $x_{k+1}=g(x_k)$ converges to $x_{\ast }$ as $k\to \infty$, provided that $x_0$ is sufficiently close to $x_{\ast }$

Newton’s Method

Newton’s method is what we use in practice, because of its convergence rate

$x_{k+1}=x_k-\frac{f(x_k)}{f^{\prime }(x_k)}$

Where does this equation come from? You can gain an intuition of it geometrically

Consider $g(x)=x-\lambda f(x)$ where $\lambda$ is unknown and $f(x_{\ast })=0$ (i.e. $x_{\ast }=g(x_{\ast })$)
We’d like to pick $\lambda$ such that $|g^{\prime }(x_{\ast })|=0$, yielding super-linear convergence

$0=1-\lambda f^{\prime }(x_{\ast })⟹\lambda =\frac{1}{f^{\prime }(x_{\ast })}$

So we hope that in a neighborhood of $x_{\ast }$ we can get away with using $\lambda =\frac{1}{f^{\prime }(x_k)}$

Theorem: Assume $f\in C^2(I)$, $I=[x_{\ast }-\delta ,x_{\ast }+\delta ]$, $\lambda >0$, $\left|\frac{f^{\prime \prime }(x)}{f^{\prime }(y)}\right|\le A$ for all $x,y\in I$, and $|x_0-x_{\ast }|\le h$ where $h=\min \{\delta ,1/A\}$. Then $x_k\to x_{\ast }$ as $k\to \infty$, where $x_{k+1}=x_k-\frac{f(x_k)}{f^{\prime }(x_k)}$, and the convergence is at least quadratic, and precisely quadratic if $f^{\prime \prime }(x_{\ast })\ne 0$.

How do we make sense of it? Let’s show the proof

$\mathcal{P}(k)=|x_k-x_{\ast }|\le \frac{h}{2^k}$
$\mathcal{P}(0)$ is true by assumption, so we need to show $\mathcal{P}(k)⟹\mathcal{P}(k+1)$

$x_{k+1}-x_{\ast }=x_k-x_{\ast }-\frac{f(x_k)}{f^{\prime }(x_k)}=\frac{(x_k-x_{\ast })f^{\prime }(x_k)-f(x_k)}{f^{\prime }(x_k)}$
We use Taylor’s Theorem,
$f(x_{\ast })=f(x_k)+(x_{\ast }-x_k)f^{\prime }(x_k)+\frac{f^{\prime \prime }({\eta }_k)}{2}(x_{\ast }-x_k{)}^2$ for some ${\eta }_k\in (x_{\ast },x_k)$

$x_{k+1}-x_{\ast }=\frac{1}{2}\frac{f^{\prime \prime }({\eta }_k)}{f^{\prime }(x_k)}(x_k-x_{\ast }{)}^2$
$|x_{k+1}-x_{\ast }|=\frac{1}{2}\left|\frac{f^{\prime \prime }({\eta }_k)}{f^{\prime }(x_k)}\right||x_k-x_{\ast }{|}^2<\frac{Ah}{2}|x_k-x_{\ast }|\le \frac{1}{2}|x_k-x_{\ast }|\le \frac{h}{2^{k+1}}$