# Nonlinear Equations and bisection

A large number of  nonlinear equations obviously *have* solutions, but the solutions cannot always be found in closed form. For example,

\begin{equation}
  f(x) = e^x + x - 2 = 0.
\end{equation}


```
%matplotlib inline
```


```
import matplotlib.pyplot as plt
import numpy as np
from matplotlib import rcParams
rcParams['font.family'] = 'serif'
rcParams['font.size'] = 16
rcParams['figure.figsize'] = (12,6)
```


```
x = np.linspace(0.0, 1.0)
def fn(x):
    return np.exp(x) + x - 2.0
f = fn(x)

plt.figure()
plt.plot(x, f, label = r'$f(x) = e^x + x - 2$')
plt.xlabel('$x$')
plt.ylabel('$f(x)$')
plt.legend(loc = 2)
plt.show()
```

Numerical methods can give accurate, approximate solutions.

Write the problem as
  
\begin{equation}
    f(x) = 0.
\end{equation}
  
Goal: given $f$, find $x$. 

Assume: $f$ real, continuous. Sometimes restrict to $f$ differentiable.

May consider equivalent problem

\begin{equation}
    g(x) = x.
\end{equation}
  
Same problem, different (geometric) interpretation.

Assume that evaluating $f$ or $g$ is \emph{expensive}. Want to minimize the number of evaluations. 

Given $f: x \in \mathbb{R} \to \mathbb{R}$, continuous, find $x$ such that

\begin{equation}
    f(x) = 0.
\end{equation}

Simple and robust method: **bisection**. 

1. Assume we have found (somehow!) two points, $x^{(L)}$ and $x^{(R)}$ that bracket root. 
2. Check halfway point $x^{(M)}$. Either $f(x^{(M)})=0$ (problem solved), or $x^{(M)}$ and one of $x^{(L,R)}$ bracket the root. 
3. Repeat to converge.


```
xL = 0.1
xR = 0.9
xM = 0.5 * (xL + xR)

plt.figure()
plt.plot(x, f)
plt.plot([xL], [fn(xL)], 'bo'); plt.plot([xL, xL], [0, fn(xL)], 'b--')
plt.plot([xR], [fn(xR)], 'bo'); plt.plot([xR, xR], [0, fn(xR)], 'b--')
plt.plot([xM], [fn(xM)], 'go'); plt.plot([xM, xM], [0, fn(xM)], 'g--')
plt.axhline(color = 'black', linestyle = '--')
plt.xlabel('$x$')
plt.ylabel('$f(x)$')
plt.show()
```

27c2aad257a6ab955bf97344abadc1c1cfda403e
ipynb
Jupyter Notebook
Lectures/05 - Nonlinear equations and bisection.ipynb
josh-gree/NumericalMethods
03cb91114b3f5eb1b56916920ad180d371fe5283
CC-BY-3.0
2015-02-12T19:51:52.000Z
2022-03-26T15:34:11.000Z
Lectures/05 - Nonlinear equations and bisection.ipynb
josh-gree/NumericalMethods
03cb91114b3f5eb1b56916920ad180d371fe5283
CC-BY-3.0
2017-05-24T19:49:52.000Z
2018-01-23T21:40:42.000Z
Lectures/05 - Nonlinear equations and bisection.ipynb
josh-gree/NumericalMethods
03cb91114b3f5eb1b56916920ad180d371fe5283
CC-BY-3.0
2015-01-05T13:30:47.000Z
2022-02-15T09:59:39.000Z
Qwen/Qwen-72B
1. YES
2. YES