## 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: EASY

Starter code:
def ex_euler(n):
	

Solutions:
from math import floor, exp

def ex_euler(n):
	F = lambda t, y: 2 - exp(-4 * t) - 2 * y
	t0 = 0
	y0 = 1
	T = 1
	h = T / float(n)
	X = [t0]
	Y = [y0]
	Z = []
	R = []
	for k in range(0, n):
		X.append((k + 1) * h)
		Y.append(Y[k] + h * F(X[k], Y[k]))
	for k in range(0, n + 1):
		Z.append(1 + 0.5 * exp(-4 * X[k]) - 0.5 * exp(-2 * X[k]))
		R.append(abs(Y[k] - Z[k]) / float(Z[k]))
	return floor(sum(R) / float(n + 1) * 1000000.0) / 1000000.0


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) * 1000000.0) / 1000000.0


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-06 * trunc(1000000.0 * 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 + 0.5 * e ** (-4 * x * h) - 0.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