# 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

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()
```

5e664baea8ae7d95b9288320f78f9205777b3a79
ipynb
Jupyter Notebook
Lectures/05 - Nonlinear equations and bisection.ipynb
soto97/NumericalMethods
513a281e7f2ac905263153cc8bb48c29deed60cd
MIT
2021-12-01T09:15:04.000Z
2021-12-01T09:15:04.000Z
Lectures/05 - Nonlinear equations and bisection.ipynb
indranilsinharoy/NumericalMethods
989e0205565131057c9807ed9d55b6c1a5a38d42
MIT
Lectures/05 - Nonlinear equations and bisection.ipynb
indranilsinharoy/NumericalMethods
989e0205565131057c9807ed9d55b6c1a5a38d42
MIT
2021-05-09T17:04:16.000Z
2021-05-09T17:04:16.000Z
Qwen/Qwen-72B
1. YES
2. YES