\part{Numerical solutions to differential equation}
\chapter{Runge-Kutta methods for order 1 ODEs}

The Runge-Kutta methods are a class of methods that aim to solve order 1 ODEs with an initial condition by generalizing a method called \emph{Euler's method}. These methods approximate the value that a function solution $y : \mathbb{R} \to \mathbb{R}$ would provide along a discrete set of evenly spaced points of an interval, therefore we will represent our domain as a vector $\mathbf{x}$ and the estimated image elements of the solution $f$ as the vector $\mathbf{y}$. 

From here, we could use approximation theory to interpolate a function to be the 'approximate' function that solves this ODE, or we could use apply a numerical integration method with these the discrete points to estimate the integral of the function solution.


As previously stated, we define our domain elements discretely and uniformly; so for the Runge-Kutta methods, we set our 'domain vector' as the following.
$\mathbf{x}_{k+1} =\mathbf{x}_{k}+h$

The idea will be to develop methods such that the following roughly holds with the 'image vector'.
\[y (\mathbf{x}_k ) \approx \mathbf{y}_k\]

As a reminder, we consider only ODEs of order 1 with an initial condition, that is, ODEs of the following form.
\[ y'(x)=f(x,y(x)), y(x_0)=y_0 \]
And we will set $\mathbf{x}_0 = x_0$ and $\mathbf{y}_0 = f(x_0) =y_0$.

We will later learn how to represent order $n$ ODEs as a system of order 1 ODEs.

\section{Euler's method (RK1)}

$y'(x)=f(x,y(x)), y(x_0)=y_0$
$\frac{y(x+h)-y(x)}{h} \approx f(x,y(x)), y(x_0)=y_0$
$y(x+h) \approx y(x)+hf(x,y(x)), y(x_0)=y_0$

Note that this essentially a Taylor series approximation that uses the first 2 terms of the true answer's Taylor series. Paired with our initial condition, we have enough information to estimate how this function would behave for small changes; using small increments we can evolve the .

Now let's formalize this method.
Given the problem $y'(x)=f(x,y), y(x_0)=y_0$, we want to estimate $y(x)$ using $n$ steps.

$h=\frac{x-x_0}{n}$
$\mathbf{x}_{0}=x_0$
$\mathbf{y}_{0}=y_0$
Repeat n times
$\mathbf{x}_{k+1} =\mathbf{x}_{k} +h$
$\mathbf{y}_{k+1} = \mathbf{y}_{k} +hf(\mathbf{x}_{k},\mathbf{y}_{k})$



Notice that we have truncation error and propagation error stacking onto eachother. Truncation error occurs due to truncating the Taylor series to 2 terms, and the propagation error occurs because we evolve ours solution using other estimated solutions from previous domain elements. 

We can do a more formal analysis of the truncation errors. We start by the analysis of the first iteration of the method out of $n$.


$\sum^{\infty}_{k=2} \frac{f^{(k)}(\mathbf{x}_{0})}{k!}h^k$
$\sum^{\infty}_{k=2} \frac{f^{(k)}(\mathbf{x}_{0})}{k!}(\frac{x_0-x}{n})^k$
$O(  \frac{f^{(2)}(\mathbf{x}_{0})}{2}(\frac{x_0-x}{n})^2 ) $


Remember that $x$ is some decided value that should be the final domain element for which $y$ is approximated; since it's value is fixed for the entire method, it is essentially constant. So the error is $O(\frac{1}{n^2})$

If one is concerned with the final point, these truncation errors accumulate onto eachother $n$ times, so we have  $ O(\frac{n}{n^2}) =O(\frac{1}{n})$

This analysis doesn't even consider the propagation error by using estimated results as a basis to derive futher estimated results, hence Euler's method doesn't scale very well if we would like to apply the data in $\mathbf{y}$ to find an interpolation $y$, or numerically integrate over $y$.

However, measures may be taken to help reduce some of this error.

\section{Midpoint method (RK2)}



$h=\frac{x-x_0}{n}$
$\mathbf{x}_{0}=x_0$
$\mathbf{y}_{0}=y_0$
Repeat n times
$\mathbf{x}_{k+1} =\mathbf{x}_{k} +h$
$c_1 = f(\mathbf{x}_{k},\mathbf{y}_{k})$
$c_2 = f(\mathbf{x}_{k}+\frac{h}{2},\mathbf{y}_{k}+\frac{c_1 h}{2})$
$\mathbf{y}_{k+1} = \mathbf{y}_{k} +hc_2$





\section{Runge-Kutta method (RK4)}



$h=\frac{x-x_0}{n}$
$\mathbf{x}_{0}=x_0$
$\mathbf{y}_{0}=y_0$
Repeat n times
$\mathbf{x}_{k+1} =\mathbf{x}_{k} +h$
$c_1 = f(\mathbf{x}_{k},\mathbf{y}_{k})$
$c_2 = f(\mathbf{x}_{k}+\frac{h}{2},\mathbf{y}_{k}+\frac{c_1 h}{2})$
$c_3 = f(\mathbf{x}_{k}+\frac{h}{2},\mathbf{y}_{k}+\frac{c_2 h}{2})$
$c_4 = f(\mathbf{x}_{k}+h,\mathbf{y}_{k}+ c_3 h)$
$\mathbf{y}_{k+1} = \mathbf{y}_{k} +\frac{h}{6}(c_1+2c_2+2c_3+c_4$




\chapter{Order $n$ ODEs}


\section{Conversion to system of order 1 ODEs}

Now let's consider the linear ODE $ r + \sum^{n}_{j=0} k_j y^{(j)}(x) = 0 , y^{(j)}(x_0)=y^{(j)}_0, j \in \mathbb{N} \cap [0,n-1]$.
For these problems, in addition to having our familiar $\mathbf{x},\mathbf{y}$ vectors, we will require vectors for the image elements of all derivatives up to $n-1$ since these are required to 'evolve' the method. We denote these $\mathbf{y}^{(j)}$
\[f^{}\]


By applying algebra to obtain $y^{(n)}$ on one side, we have the following equation.
\[ y^{(n)}(x) = \frac{1}{k_n} [ -r - \sum^{n-1}_{j=0} k_j y^{(j)}(x) ] \]

As for the rest of the derivatives, we know the following equation to be true.
\[ y^{(j)}(x) = (y^{(j-1)})'(x)\]

This gives us a way to update all the derivatives for each iteration.


\section{Multiple initial conditions}

2 initial conditions for the solution.
$y^{(j)}(x)=f(x,y(x)),y(x_0)=y_1.y(x_1)=y_1$

\subsection{Shooting method}


\section{Finite difference methods}



\[P[u](x)=f(x,u(x)\]

Where $P$ is some linear differential operator and $u : \mathbb{R} \to \mathbb{R}$ a real function that is known at $n$ equally spaced nodes on some interval. In our usual fashion, we can represent the domain and image vectors as $\mathbf{x},\mathbf{u}$ where $u(\mathbf{x}_j) = \mathbf{u}_j$ and $\mathbf{x}_{k+1} = \mathbf{x}_k +h$


\subsection{Finite difference representations of differential operators}

We can estimate the derivatives of $u$ , however we also require the initial conditions.
\[\mathbf{D}=\]
\[\mathbf{D}_{2}=\]

with initial conditions $u(x_0)=u_0,u(x_1)=u_1$, we make the first and last row of the difference matrixes 1 at the leftmost and rightmost indexes respectfully. Addiionally, the first and last entries of $\mathbf{u}$ are changed to $u_0,u_1$

For derivative initial conditions, we make forwards or backwards difference.

\subsection{PDEs}