## Euler's Method

We want to calculate the shape of an unknown curve which starts at a given point 
with a given slope. This curve satisfies an ordinary differential equation (ODE):

```math
\frac{dy}{dx} = f(x, y);\\
y(x_0) = y_0
```

The starting point `$ A_0 (x_0, y_0) $` is known as well as the slope to the curve 
at `$ A_0 $` and then the tangent line at `$ A_0 $` .

Take a small step along that tangent line up to a point `$ A_1 $`. Along this small step, 
the slope does not change too much, so `$ A_1 $` will be close to the curve. 
If we suppose that `$ A_1 $` is close enough to the curve, the same reasoning 
as for the point `$ A_1 $` above can be used for other points. 
After several steps, a polygonal curve `$ A_0, A_1, ..., A_n $` is computed. 
The error between the two curves will be small if the step is small.

We define points `$ A_0, A_1, A_2, ..., A_n $`
whose x-coordinates are `$ x_0, x_1, ..., x_n $`
and y-coordinates are such that `$ y_{k+1} = y_k + f(x_k, y_k) \times h $` 
where `$ h $` is the common step. If `$ T $` is the length `$ x_n - x_0 $` we have `$ h = T/n $`.

## Task

For this kata we will focus on the following differential equation:

```math
\frac{dy}{dx} = 2 - e^{-4x} - 2y; \\
A_0 = (0,1)
```
with `$ x ∈ [0, 1] $`. We will then take a uniform partition of the region of `$ x $` between `$ 0 $` and `$ 1 $` and split it into `$ n $` + 1 sections. `$ n $` will be the input to the function `ex_euler(n)` and since `$ T $` is always 1, `$ h = 1/n $`.

We know that an exact solution is
```math
y = 1 + 0.5e^{-4x} - 0.5e^{-2x}.
```
For each `$ x_k $` we are able to calculate the `$ y_k $` as well as the values `$ z_k $` of the exact solution.

Our task is, for a given number `$ n $` of steps, to return the mean (*truncated* to 6 decimal places)
of the relative errors between the `$ y_k $` (our aproximation) and the `$ z_k $` (the exact solution). 
For that we can use:

error in `$ A_k = abs(y_k - z_k) / z_k $` and then the mean is sum(errors in `$ A_k $`)/ (`$ n $` + 1)

## Examples

```python
ex_euler(10) should return: 0.026314 (truncated from 0.026314433214799246)
with
Y = [1.0,0.9..., 0.85..., 0.83..., 0.83..., 0.85..., 0.86..., 0.88..., 0.90..., 0.91..., 0.93...]
Z = [1.0, 0.9..., 0.88..., 0.87..., 0.87..., 0.88..., 0.89..., 0.90..., 0.91..., 0.93..., 0.94...]
Relative errors = [0.0, 0.02..., 0.04..., 0.04..., 0.04..., 0.03..., 0.03..., 0.02..., 0.01..., 0.01..., 0.01...]
```
`ex_euler(17)` should return: `0.015193 (truncated from 0.015193336263370796)`.
As expected, as `$ n $` increases, our error reduces.
### Links and graphs

Wiki article

![alternative text](http://i.imgur.com/vjK7edl.png)

Below comparison between approximation (red curve) and exact solution(blue curve) for n=100:
![alternative text](http://i.imgur.com/KufSkYEm.png)

Difficulty: introductory

Starter code:

def ex_euler(n):
	

Solutions:
from math import floor, exp
    
def ex_euler(n):
    # fct to study
    F = lambda t,y : 2 - exp(-4 * t) - 2 * y
    # initial conditions
    t0 = 0; y0 = 1; # pt A0
    T = 1; 
    # variables
    h = T / float(n); X = [t0]; Y = [y0]; Z = []; R = []
    # points A1 ... An
    for k in range(0, n):
        X.append((k + 1) * h)
        Y.append(Y[k] + h * F(X[k],Y[k]))
    # pts on the exact curve
    for k in range(0, n + 1):
        # exact solution
        Z.append(1 + 0.5 * exp(-4 * X[k]) - 0.5 * exp(-2 * X[k]))
        # relative error
        R.append(abs(Y[k] - Z[k]) / float(Z[k]))
    return floor((sum(R) / float(n + 1)) * 1e6) / 1e6 

from math import exp
def ex_euler(n):
    f = lambda x, y: 2 - exp(-4*x) - 2*y
    exact = lambda x: 1 + 0.5*exp(-4*x) - 0.5*exp(-2*x)
    x, y, T = 0, 1, 1
    h = T/n
    mx = [0]
    for _ in range(n):    
        y += h*f(x, y)
        x += h
        z = exact(x)
        mx.append(abs(y-z)/z)
    return float(str(sum(mx)/(n+1))[:8])

def ex_euler(n):
    import numpy as np
    n_steps = n+1
    T=1
    t = np.linspace(0,T,n_steps)
    h=T/n
    zk = 1+0.5*np.exp(-4*t)-0.5*np.exp(-2*t)
    yk = [1]
    
    for i in range(1,n_steps):
        dy_dt = 2 - np.exp(-4*t[i-1])-2*yk[i-1]
        yk.append(yk[i-1]+dy_dt*h)
        
    err = np.divide(np.abs(np.array(yk) - zk),zk)
    err = str(np.sum(err)/(n+1))
    err = float(err[:err.find('.')+7])
    return err
    


import math

def exact_sol(t):
    return  1 + 0.5*math.exp(-4*t) - 0.5*math.exp(-2*t)

def slope(y, t):
    return 2 - math.exp(-4*t) - 2*y
    
def ex_euler(n):
    y = 1
    t = 0
    error = abs(y - exact_sol(t))/exact_sol(t)
    for _ in range(n):
        y += slope(y,t)*(1/n)
        t += 1/n
        error += abs(y - exact_sol(t))/exact_sol(t)
    
    return (int((error/(n+1))*1e6))/1e6

import math
def ex_euler(n):
    h = 1.0 / n
    xk = 0
    yk = 1
    sm = 0
    Y = [1.0]
    Z = [1.0]

    for i in range(n):
        
        yk += (2 - math.exp(-4 * xk) - 2 * yk) * h
        Y.append(yk)

        xk += h

        zk = 1 + 0.5 * math.exp(-4 * xk) - 0.5 * math.exp(-2 * xk)
        Z.append(zk)

    for i in range(len(Y)):
        sm += abs(Y[i] - Z[i]) / Z[i]

    return int(sm/(n+1)*1000000) / 1000000.0

from math import *
import numpy as np
from decimal import *

def f(xk,yk):
    return 2 - exp(-4*xk) - 2*yk
def Y(t):
    return 1 + 0.5*exp(-4*t) - 0.5*exp(-2*t)
    
def ex_euler(n):
        x = 0
        y0 = 1
        T = 1
        h = 1/n
        y = np.zeros(n+1)
        z = np.zeros(n+1)
        y[0] = y0        
        for i in range(n):
            y[i+1] = y[i] + f(x,y[i])*h
            z[i] = Y(x)
            x+=h
        z[len(z)-1] = Y(x)
        A = [abs(y[i] - z[i])/z[i] for i in range(n+1)]
        return round(1e-6 * trunc(1e6*(np.mean(A, dtype=np.float32))),6)    


from math import exp

def ex_euler(n):
    e=0
    h=1/n
    y=1-h
    for i in range(1,n+1):
        t=i/n
        e2=exp(-2*t)
        e4=e2**2
        z=1+(e4-e2)/2
        e+=abs(y-z)/z
        y+=(2-e4-2*y)*h
    return e*1000000//(n+1)/1000000

from math import exp

def ex_euler(n):
    dx = 1 / n
    def f(x, y):
        return 2 - exp(-4*x) - 2*y
    def z(x, y):
        return 1 + 0.5*exp(-4*x) - 0.5*exp(-2*x)
    x, y = 0, 1
    errors = []
    for _ in range(n + 1):
        errors.append(abs(y - z(x, y)) / z(x, y))
        y += f(x, y)*dx
        x += dx
    return float(str(sum(errors) / (n + 1))[:8])

from math import e

def ex_euler(n):
    x,y,h,r = 0,1,1/n,[1]
    for _ in range(n):
        f = 2 - e**(-4*x) - 2*y
        yy = y + h*f
        r.append(yy)
        x,y = x+h,yy

    real = [(1+.5*e**(-4*x*h)-.5*e**(-2*x*h)) for x in range(n+1)]
    err = [abs(i-j)/j for i,j in zip(r,real)]
    return float(str(sum(err)/(n+1))[:8])

from math import exp, floor
def ex_euler(n):
    y = 1
    x = 0
    T = 1/n
    error = 0
    
    for i in range (n):
        y = y + (2 - exp(-4*x) - 2*y)*T 
        x = x + T
        zk = (1 + 0.5 * exp(-4*x) - 0.5 * exp(-2*x))
        error = error + abs(y - zk)/zk
    return floor(error/(n+1) * 10 ** 6 )/10 ** 6
#float("{:.6f}".format(error/(n+1)))
#round(error/(n+1),6)