\part{Numerical methods}


For many problems of mathematical analysis, an analytic solution is unavailable and hence one may resort to numerical solutions. The general approach is to use a \emph{numerical method} that converges towards the solution.

\begin{definition}
Given a well posed problem $F(x,y)=0$ with $F:X\times Y \to\mathbb{R}$ and with some locally Lipshitz function from $X$ to $Y$ at every solution $(x,y)$, a \emph{numerical method} is a sequence of problems $( F_n (x_n , y_n )=0 )_{n \in \mathbb{N}}$. In other words, it is a sequence of (hopefully easier or analytically solved) problems whose solutions are used to approximate the problem $F(x,y)=0$.
\end{definition}


Numerical methods with the same objective may differ in quality, primarily with regard to:
\begin{itemize}
\item Numerical stability
\item Rate of convergence
\end{itemize}

Numerical stability refers to whether...

A numerical method's rate of convergence describes, the rate at which absolute error decreases as the numerical method progresses to subsequent terms. Higher rates of convergence are highly desirable

A numerical method's rate of convergence describes 



\chapter{Errors}

One can analyze the efficacy of a numerical method by observing its error after $n$ steps. There are two main ways in which error is quantified.

\begin{definition}
The \emph{absolute error} of an estimation is its distance to the true value.
\[ \| \mathbf{x}  - \boldsymbol{\xi}\|\]
\end{definition}

\begin{definition}
The \emph{relative error} of an estimation is its distance to true value divided by the norm of the estimation.
\[ \frac{\| \mathbf{x}  - \boldsymbol{\xi}\|}{\| \mathbf{x} \|} \]
\end{definition}


\begin{itemize}
\item Approximation (the use of an approximate function induces error)
\item Truncation (error from terminating numerical method that converges to true value)
\item Roundoff (error due to limitations of model of computation to store the true value)
\item Statistical (error due to the randomness of a random sample possibly employed in the numerical method)
\end{itemize}

\section{Roundoff error}

In Python, $100000000000000000$ is recognized as the same number as $100000000000000001$. This is clearly false mathematically, however this phenomena occurs in real application. This is due to the limited storage space designated to a number on a PC, meaning that only a finite amount of numers are recognizable. Different implementations have different consequences, however this phenomena is a downside of floating-point arithmetic specifically.

This book aims to discuss numerical analysis in a theoretical, mathematical environment, and Turing machines (basically 'theoretical computers') do not have issues with roundoff error. That said, if one wants to create a mathematical environment that emulates roundoff error, one can introduce a quantity called \emph{machine epsilon}.


\begin{definition}
The \emph{machine epsilon} $\varepsilon$ of some model of computation is an upper bound on relative approximation error.
A model of computation with machine epsilon $\varepsilon$ cannot distinguish $x,y$ if $ |x-y| < |x|\varepsilon $
\end{definition}

\section{Approximation error}

Many numerical methods draw from approximation theory to use similar functions that are 'nicer' to make calculations. 

\section{Truncation error}

Numerical methods are employed in algorithms, and ideally the algorithms we use should terminate (at least in the context of numerical analysis).


\begin{itemize}
	\item Finite iterations
	\item Reaching predefined tolerance
\end{itemize}

When a certain amount of error is acceptable, and one has an infinite numerical method, one may be able to calculate a value with arbitrary \emph{tolerance} to the true value.

\begin{definition}
The \emph{tolerance} $\varepsilon$ is a value reperesenting the maximum  error.
\[ \| \mathbf{x} - \boldsymbol{\xi}\| \leq \varepsilon \]
\end{definition}