\part{Zero finding methods}


\chapter{Introduction to zero finding}



\chapter{Fixed point iteration method}



During my freshman year, I stubled across the following formula while playing around. I called it the \emph{Gyakkin formula}.
\[ x_{n+1}=x_{n}+\frac{a-f(x_{n})}{a} \]
I noted that in some situations, the following would hold.
\[ \lim_{n \to \infty} x_{n} = f^{-1}(a) \]



Little did I know, I was implicitly leveraging ideas from the \emph{fixed point iteration method}. The fixed-point iteration method converge (hopefully) to \emph{fixed points}; elements $x_0$ such that $f(x_0)=x_0$, however one can easily make this a zero finding method by considering $g(x)=x - f(x)$. For simplicity, this section will consider the calculation of fixed points rather than zeros.

\begin{definition}[Fixed point iteration method]
\[x_{n+1}=f(x_{n})\]
\[ \lim_{n \to \infty} x_{n} \]
\end{definition}

One can tweak this to become a zero finding method.

\begin{definition}
\[x_{n+1}=x-f(x_{n})\]
\end{definition}

As alluded to, the fixed point iteration method unfortunately doesn't always converge to fixed points; for some pathological functions, the method simply explodes away from our desired value.

\begin{definition}
A fixed point $\xi$ of $f$ is called an \emph{attractor} iff the following holds.
\[x_{n+1}=f(x_{n})\]
\[ \lim_{n \to \infty} x_{n} = \xi\]
\end{definition}


The \emph{Banach fixed point theorem} is a notable result from topology that gives a condition when a function has an attractor.


\chapter{Bracketing}
- corrollary of IVT (bracketing method)
- bracketing method 
\chapter{Iterative methods}

We have investigated the fixed point iteration method as a precursor, however we'll now delve into more sophisticated iterative methods.

- bisection method (IVT)
- secant method
- forward difference
- backward difference
- central difference
- Newton-Raphson method
- false position method
\chapter{Interpolation methods}
- Dekker's method
- Brent's method

Durand-kerner method