DerivationODEsintermediate

Derivation: Euler's method and its order

Three independent routes lead to Euler's formula (Taylor, incremental quotient and integration), and the analysis of the Taylor remainder proves the method is first order.

Route 1: Taylor expansion

tₖtₖ₊₁yₖyₖ₊₁current slopey(t)
The geometric reading of first-order Taylor: keeping only the linear term means advancing along the tangent.
Expand diagram

The geometric reading of first-order Taylor: keeping only the linear term means advancing along the tangent.

  1. Expand the solution yy by Taylor around tt, with the Lagrange form of the remainder (ξ\xi between tt and t+ht+h):

    y(t+h)=y(t)+h y′(t)+h22y′′(ξ)y(t+h)=y(t)+h\,y'(t)+\frac{h^2}{2}y''(\xi)

  2. The differential equation provides the derivative: y′(t)=f(t,y(t))y'(t)=f(t,y(t)). Substituting:

    y(t+h)=y(t)+h f(t,y(t))+h22y′′(ξ)y(t+h)=y(t)+h\,f(t,y(t))+\frac{h^2}{2}y''(\xi)

  3. Discard the remainder h22y′′(ξ)\frac{h^2}{2}y''(\xi) (the terms of order at least 2) and evaluate at the nodes t=tkt=t_k, with yk≈y(tk)y_k\approx y(t_k): Euler's scheme remains.

    yk+1=yk+h f(tk,yk)y_{k+1}=y_k+h\,f(t_k,y_k)

Route 2: incremental quotient

  1. The derivative is the limit of the incremental quotient; for small hh, that quotient approximates it. This gives the first-order forward difference:

    y′(t)=lim⁡h→0y(t+h)−y(t)h  ⇒  y′(t)≈y(t+h)−y(t)hy'(t)=\lim_{h\to 0}\frac{y(t+h)-y(t)}{h}\;\Rightarrow\; y'(t)\approx\frac{y(t+h)-y(t)}{h}

  2. Substituting the approximation into the equation y′=f(t,y)y'=f(t,y) and solving for y(t+h)y(t+h) recovers the same formula:

    y(t+h)−y(t)h≈f(t,y)  ⇒  y(t+h)≈y(t)+h f(t,y)\frac{y(t+h)-y(t)}{h}\approx f(t,y)\;\Rightarrow\; y(t+h)\approx y(t)+h\,f(t,y)

Route 3: integration

tₖtₖ₊₁h f(tₖ, yₖ)left rectanglef(τ, y(τ))
In integral form, explicit Euler approximates the area under f(τ,y(τ))f(\tau,y(\tau)) by a rectangle with left height f(tk,yk)f(t_k,y_k).
Expand diagram

In integral form, explicit Euler approximates the area under f(τ,y(τ))f(\tau,y(\tau)) by a rectangle with left height f(tk,yk)f(t_k,y_k).

  1. Before using the Fundamental Theorem of Calculus, write the ODE with the dummy variable τ\tau and integrate both sides over [tk,tk+1][t_k,t_{k+1}]:

    ∫tktk+1y′(τ) dτ=∫tktk+1f(τ,y(τ)) dτ\int_{t_k}^{t_{k+1}} y'(\tau)\,d\tau=\int_{t_k}^{t_{k+1}} f\bigl(\tau,y(\tau)\bigr)\,d\tau

  2. Now the Fundamental Theorem of Calculus turns the integral of y′y' into the exact difference of the solution:

    y(tk+1)=y(tk)+∫tktk+1f(τ,y(τ)) dτy(t_{k+1})=y(t_k)+\int_{t_k}^{t_{k+1}} f\bigl(\tau,y(\tau)\bigr)\,d\tau

  3. Approximate the integrand by its value at the left endpoint. In other words, interpolate it with the constant polynomial p0(τ)=f(tk,y(tk))p_0(\tau)=f(t_k,y(t_k)) and integrate that rectangle of base hh:

    ∫tktk+1f(τ,y(τ)) dτ  ≈  (tk+1−tk) f(tk,y(tk))=h f(tk,y(tk))\int_{t_k}^{t_{k+1}} f\bigl(\tau,y(\tau)\bigr)\,d\tau\;\approx\;(t_{k+1}-t_k)\,f(t_k,y(t_k))=h\,f(t_k,y(t_k))

  4. Substituting into the integral identity yields Euler's scheme again. Approximating the integrand with higher-degree polynomials produces, along this same route, Heun (trapezoid), RK4 (Simpson) and the Adams methods.

Local error, global error and order

  1. The local error of one step is the Taylor remainder discarded in Route 1 (ξk∈ ]tk,tk+1[\xi_k\in\,]t_k,t_{k+1}[):

    ek+1=y(tk+1)−(y(tk)+h y′(tk))=h22y′′(ξk)=O(h2)e_{k+1}=y(t_{k+1})-\bigl(y(t_k)+h\,y'(t_k)\bigr)=\frac{h^2}{2}y''(\xi_k)=\mathcal{O}(h^2)

  2. For the global error, sum the NN local errors. Since y′′y'' is continuous, the intermediate value theorem lets us collect the sum at a single point ξ∈[a,b]\xi\in[a,b]:

    ∑k=0N−1h22y′′(ξk)=h22N y′′(ξ)\sum_{k=0}^{N-1}\frac{h^2}{2}y''(\xi_k)=\frac{h^2}{2}N\,y''(\xi)

  3. With N=b−ahN=\frac{b-a}{h}, one power of hh cancels and the first-order global error remains: Euler's method is first order.

    h22 b−ah y′′(ξ)=b−a2 y′′(ξ) h=O(h)\frac{h^2}{2}\,\frac{b-a}{h}\,y''(\xi)=\frac{b-a}{2}\,y''(\xi)\,h=\mathcal{O}(h)