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}}

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_i = a + h\,i} for $i\in 0,1,\ldots ,n$

We are given a method

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} w_0 = \alpha \\ w_{i+1} = w_i + h \, \phi(t_i, w_i) \end{cases}}

Last Time: Euler

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 \phi(t, y(t)) = f(t,y(t))}

Given a current approximation $w_{i}$ , we want 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} y'(t) = f(t, y(t)) \\ y(t_i) = w_i \end{cases}}
Approximate 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 f(t, y(t)) \approx 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'(t) = f(t_i, w_i)} by ODE definition
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(t_i+1) = w_i + h \, f(t_i, w_i)}

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 \left| y_i - w_i \right| \le \frac{h \, M}{2L} \, \left( \mathrm{e}^{L \, \left( t_i - a \right)} - 1 \right)}

In order 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 \left| y(b) - w_n \right| \in O(h)} , we must have 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 \left| y''(t) \right| \le M} and the IVP must be well-posed:

$f(t,y)$ is continuous in 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 D = \left\{ (t,y) ~\mid~ a \le t \le b, y \right\}}
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 f} must be Lipschitz continuous: 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 \left| f(t,x) - f(t,y) \right| \le L \, \left| x-y \right|} for all 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,x), (t,y) \in D}
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 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

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 \left| \frac{f(t,x) - f(t,y)}{x-y} \right| \le L}

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 \left| \frac{\partial f}{\partial y} (t,\xi) \right| \le L}

Euler Method Roundoff Error

Each step has a small 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_i} , so the accumulated error 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 \delta}

On most machines, 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 \approx 10^{-16}}

Then the error equation becomes 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 \left| y(b) - w_n \right| \in O \left( h + \frac{\delta}{h} \right)}

Don't make 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} 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 $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

${\begin{aligned}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{aligned}}$

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

${\begin{aligned}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{aligned}}$

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 $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)}