MATH 417 Lecture 16

« previous | Thursday, March 20, 2014 | next »

Differential Equations

Initial value problem ODE:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{cases} \frac{\mathrm{d}y}{\mathrm{d}t} = f(t, y(t)) \\ y(a) = \alpha \end{cases}}

for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t \in \left[ a,b \right]} .

Discretize the interval into Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} points, and let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle h = \frac{b-a}{n}}

$t_{i}=a+h\,i$ for $i\in 0,1,\ldots ,n$

We are given a method

${\begin{cases}w_{0}=\alpha \\w_{i+1}=w_{i}+h\,\phi (t_{i},w_{i})\end{cases}}$

Last Time: Euler

Let $\phi (t,y(t))=f(t,y(t))$

Given a current approximation $w_{i}$ , we want ${\begin{cases}y'(t)=f(t,y(t))\\y(t_{i})=w_{i}\end{cases}}$
Approximate $f(t,y(t))\approx f(t_{i},w_{i})$
$w'(t)=f(t_{i},w_{i})$ by ODE definition
$w(t_{i}+1)=w_{i}+h\,f(t_{i},w_{i})$

Error

$\left|y_{i}-w_{i}\right|\leq {\frac {h\,M}{2L}}\,\left(\mathrm {e} ^{L\,\left(t_{i}-a\right)}-1\right)$

In order for $\left|y(b)-w_{n}\right|\in O(h)$ , we must have $\left|y''(t)\right|\leq M$ and the IVP must be well-posed:

$f(t,y)$ is continuous in $D=\left\{(t,y)~\mid ~a\leq t\leq b,y\right\}$
$f$ must be Lipschitz continuous: $\left|f(t,x)-f(t,y)\right|\leq L\,\left|x-y\right|$ for all $(t,x),(t,y)\in D$
$D$ must be a convex set: for every two points in the set, the line between them must lie entirely in the set.

Lipschitz Continuity

There is an easy way to verify Lipschitz continuity using partial derivatives:

Rewrite definition as

$\left|{\frac {f(t,x)-f(t,y)}{x-y}}\right|\leq L$

Then $\left|{\frac {\partial f}{\partial y}}(t,\xi )\right|\leq L$

Euler Method Roundoff Error

Each step has a small $\delta _{i}$ , so the accumulated error is $\delta$

On most machines, $\delta \approx 10^{-16}$

Then the error equation becomes $\left|y(b)-w_{n}\right|\in O\left(h+{\frac {\delta }{h}}\right)$

Don't make $h$ too small, otherwise accumulated error Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \delta} will be more than the error of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle h}

Cost of evaluating is number of steps × local cost

Let error term be bounded by Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \epsilon} .

For euler, the cost is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{b-a}{\epsilon} \cdot 1}

Euler is an order-1 method

Taylor Series Based Methods

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} y(t_i + h) = y(t_i) + h \, y'(t_i) + \frac{h^2}{2} \, y''(t_i) + \frac{h^3}{3!} \, y'''(t_i) + \mbox{error} \\ h \cdot T^{(n)}(t,y) = h \, \left( y'(t_i) + \frac{h}{2} \, y''(t_i) + \frac{h^2}{6} y'''(t_i) + \dots \right) \end{align}}

Let's calculate for multiple values of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} :

n = 1

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} h \, T^{(1)}(t,y) &= h \, y'(t_i) \\ &= h \, f(t,y) \end{align}}

(this is Euler's method)

Our numerical method is then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w_{i+1} = w_i + h \, f(t_i,w_i)}

n = 2

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} h \, T^{(2)}(t,y) &= h \, y'(t_i) + \frac{h^2}{2} \, y''(t_i) \\ &= h \, f(t,y) + \frac{h^2}{2} \, \frac{\mathrm{d}}{\mathrm{d}t} \left( f(t,y(t)) \right) \\ &= h \, f + \frac{h^2}{2} \left( \frac{\partial f}{\partial t} + \frac{\partial f}{\partial y} \cdot y'(t) \right) \\ &= h \, f(t,y) + \frac{h^2}{2} \left( f_t(t,y) + f_y(t,y) \cdot f(t,y) \right) \end{align}}

Our numerical method is then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w_{i+1} = w_i + h \, f(t_i,w_i) + \frac{h^2}{2} \left( f_t(t_i,w_i) + f_y(t_i,w_i) \cdot f(t_i,w_i) \right)}

Local Truncation Error

At each step, how far off is our approximation?

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \tau_{i+1}(h) = \frac{y_{i+1} - \left( y_i + h \, \phi(t_i, y_i) \right)}{h}}

For Taylor-series-based methods, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi = T^{(n)}(t_i, y_i)} , and

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \tau_{i+1}(h) = \frac{h^{n+1}}{(n+1)!} \, y^{(n+1)}(\xi) \cdot \frac{1}{h} = C \, h^n}

n = 3

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle h \, T^{(3)}(t,y) = h \, y'(t_i) + \frac{h^2}{2} \, y''(t_i) + \frac{h^3}{6} \, y'''(t_i)}

Then

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} w_{i+1} &= w_i + h \, T^{(3)}(t_i, w_i) \\ &= \ldots \\ &= w_i + h \, \left( h \, f + \frac{h^2}{2} \, \left( f_t + f_y \, f \right) + \frac{h^3}{6} \, \left( f_{tt} + f_{ty} \, f + f \, \left( f_{yt} + f_{yy} \, f \right) + f_t \left( f_t + f_y \, f \right) \right) \right) \end{align}}

Numerical Integration Methods

Given Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w_i} , we want to construct Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w_{i+1}}

So far, we have seen:

Euler: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w_{i+1} = w_i + h \, f(t_i, w_i)}
Taylor: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w_{i+1} = w_i + h \, T^{(n)}(t_i, w_i)}

When we evaluate the exact solution to an ODE, we solve

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_{i+1} = y(t_i + h) = w_i + \int_{t_i}^{t_i + h} \, f(t, y(t)) \,\mathrm{d}t}

Let the integrand term be represented by Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(t)} (assume these values are approximated with accuracy Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(h^2)} ):

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_{i+1} = y(t_i + h) = w_i + \int_{t_i}^{t_i + h} \, g(t) \,\mathrm{d}t}

Modified Euler Method

Euler's method is analogous to evaluating the integral by using the left-riemann summ (a horrible approximation)

Let's use the trapezoidal rule instead:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w_{i+1} = w_i + \frac{h}{2} \left( g(t_i) + g(t_{i+1}) \right) = w_i + \frac{h}{2} \left( f(t_i, w_i) + f(t_{i+1}, w_i + h \, f(t_i, w_i)) \right)}

If we let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle z_{i+1} = w_i + h \, f(t_i, w_i)} be the standard Euler method, we can simplify the expression to:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w_{i+1} = w_i + \frac{h}{2} \, \left( f(t_i, w_i) + f(t_{i+1}, z_{i+1}) \right)}

Midpoint Method

Let's try using the midpoint method; this requires evaluation at half-time-steps

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w_{i+1} = w_i + h \, f \left( t_i + \frac{h}{2}, w_i + \frac{h}{2} \, f(t_i, w_i) \right)}

Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle z_{i + \frac{1}{2}} = w_i + \frac{h}{2} \, f(t_i, w_i)}

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w_{i+1} = w_i + h \, f \left( t_i + \frac{h}{2}, z_{i+ \frac{1}{2}} \right)}

Heun's Method

Let's use Gaussian Quadrature with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \int_{0}^{1} f(x) \,\mathrm{d}x \approx \frac{1}{4} \, f(0) + \frac{3}{4} \, f \left( \frac{2}{3} \right)} .

Then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w_{i+1} = w_i + \frac{h}{4} \, \left( f(t_i,w_i) + 3 \, f \left( \frac{t_i + \frac{2h}{3}}{t_i + \frac{2}{3}}, \frac{w_i + \frac{2h}{3} \, f(t_i, w_i)}{w_i + \frac{2}{3}} \right) \right)}