7/26/04

Numerical Methods for Differential Equations

Consider:
(dy/dt) = ky --> Solution y'-g(y,t)

The integral of dy/y = The integral of k*dt
Therefore,
ln(y) = k1t + k2 --> exp(k1t + k2)

Some differential equations do not have an analytical Soltuion. So they have to be approximated using numerical methods.
The numerical Solution to the differential equation is a sequence of points, (to,yo),(t1,y1),...,(tk,yk).

Euler's Method



We Divide the interval [a,b] into M equal subintervals:
h=(b-a)/M

h=step size

We make tk=a + kh for k=0,1,2,.....,M

We want to Solve:

y'=f(t,y) over [to,t1,t2,...,M]

Using Taylor Expansion to approximate y(t) around to we have:

y(t) = y(to) + y'(to)(t - to) +[y"(C)((t - to)2]/2

The last value is the error

Now substituting for y(t1)
y(t1) = y(to) + y'(to)(t1 - to) +[y"(C)((t1 - to)2]/2

If the step size is small enough we can neglect the second order error.

y(t1)=y(to) + y'(t0)(t1-to) *NOTE*(t1-t0)=h therefore y(t1) = y(to) + y'(to)h
y1=yo + y'o*h
y1=yo + h*f(to,yo)

In General:
tk+1 = tk + h
yk+1= yk + h*f(tk,yk) for k=0,1,2,...,M-1

Example

y'=t2 - y AND h=.2
k yk tk
0 yo = 1 to=0
1 y1=yo +h*y'o = 1 + .2(0 - 1) = .8 t1 = to + h = 0 + .2 = .2
2 y2 = y1 + h*y'1 = .8 + .2(.2^2 - .8) = .648 t2=t1+h=.2+.2=.4
3 .5504 .6
4 .5123 .8

Analytical Solution:
y(t) = -exp(-t) + t2 -2t +2
y(.4) = .6897
y(.8)= .5907

*NOTE* If you want to get better precision with Euler's method you can make h smaller. AlSo, the larger the k in tk, the larger the cumulative error.

Heun's Method

We want to Solve:
y'(t) = f(t,y(t)) over [a,b] with y(to) = yo

We can use the fundamental theorem of calculus and integrate y'(t) over [to,t1]
Now we can use any numerical integration method to approximate the integral.
Using the trapezoidal rule we get the following:
y(t1)=y(to) + (h/2) * [f(to,y(to)) + f(t1,y(t1))]

Observe that we still need to know y(t1) to compute y(t1).
to prevent this recursion, inside f(t1,y(t1)) we will use an approximation. P(t1) instead of y(t1). to compute P(t1) we use Euler's Method.
P(t1) = yo + h*f(to,y(to))
and
y(t1) = y(to) + (h/2)*[f(to,y(to)) + f(t1,P(t1))]


Euler's Method is used as a predictor and the integral is used as a correction

In General:
Pk+1 = yk + h*f(tk,yk)
yk+1 = yk + (h/2)*[f(tk,yk)+f(tk+1, Pk+1)]


Example

f(y,t) = y' = t2 -y AND y(0) = 1 AND h=.2
k yk tk Pk
0 1 0
1 y1 = yo + (h/2)*[f(to,yo)+f(t1,P1)] = .8240 t1 = to +h = 0 + .2 = .2 P1 = yo + h*f(to,yo) = 1 + .2(0-1) = .8
2 .6949 .4 .6672
Exact value for y(.4) = .6897
Euler value for y(.4) = .6480
3 y3 = y2 + (h/2)*[f(t2,y2)+f(t3,P3)]=.6186 t3 = t2 +h=.6 P3 = y2 + h*f(t2,y2)= .5879
4 .6001 .8 .5669
Exact value for y(.8) = .5907
Euler value for y(.8) = .5123



7/27/04

Taylor Series Method for Differential Equations

Using Taylor approximation
Obtain:
y(tk+h) = y(tk) + h*y'(tk) + (h^2/2!).....
yk+1 = .......


We can compute yk+1 using yk and alSo y'k,y"k...etc we can obtain y'k,y"k,...etc using the differential equation y'=f(y,t).

Example

Solve y'= t2 - y Given:yo = 1, h=.2, and use N=3
yk+1 = ....
y'= t2 -y --> yk'= tk2 - yk
y"=2t - y' --> yk"=2tk - yk'
y"'=2 - y" --> yk"'= 2 - yk"
k tk yk yk' yk" yk"'
0 0 1 -1 1 1
1 .2 .821333 -.781333 1.181333 .818667
2 .4 .689785 -.529785 1.389785 .670215
3 .6 .61137 -.251317 1.451317 .548683
4 .8 .590812
Exact Solution: y(.8) = .5907
Euler Solution: y(.8) = .59123
Heun Solution: y(.8) = .6001

ADVANTAGE:to increase accurracy increase n in the Taylor Series. This will also decrease the error.


7/28/04

NO CLASS!!


7/29/04

Homework #5 due on Tuesday!! (Last day of Class)

Final Exam: August 5th (8/5/04) 1pm - 3pm, UNIV 303

Q: How do you know a Spline is correct?
A: Testing a Spline: (Verifying) The following has to be true for splines: 
So(xo) = yo       So(x1) = y1
S1(x1) = y1       S1(x2) = y2
S2(x2) = y2       S2(x3) = y3

AND

Continuity in 1st Derivative: So'(x1) = S1'(x1)   AND   S1'(x2) = S2'(x2)

Continuity in 2nd Derivative: So"(x1) = S1"(x1)   AND   S1"(x2) = S2"(x2)

Runge-Kutta Method of Order 4

Solving Solutions of Differential Equations

This method simulates the accuracy of Taylor Series method of order N=4, but it doesn't require the computation of derivatives.
center>yk+1 = yk + (h/6)*(f1 + 2f2 + 2f3 + f4)

where: f1 = f(tk,yk)
f2 = f(tk + (h/2) , yk + (h/2)*f1)
f3 = f(tk + (h/2), yk + (h/2)*f2)
f4 = f(tk + h , yk + h*f3)
See an advanced text on numerical methods for a proof.

Example

y' = t2 - y , yo = 1, h=.2, and to = 0
k tk yk f1 f2 f3 f4
0 0 1 -1 -.89 -.9 -.7798
1 .2 .821273 -.781273 -.653146 -.665958 -.528081
2 .4 .689688
Exact value: y(.4) = .6897

Systems of Differential Equations

Assume we have the equations:
The Solutions are functions x(t) and y(t) that when derivated they transform into f(t,x,y) and g(t,x,y)

Example

xo = 6 , yo = 4
  1. x' = x + 2y
  2. y' = 3x + 2y

    3. Analytical Solution:
  3. x(t) = 4*exp(4t) + 2*exp(-t)
  4. y(t) = 6*exp(4t) - 2*exp(-t)
you can verify this by evaluating 3 and 4 and substituting into 1 and 2


Euler Method for Systems of Differential Equations

We have:
dx/dt = f(t,x,y) --> dx = f(t,x,y)dt ==> x1-xo = f(t,x,y)*(t1-to)

dy/dt = g(t,x,y) --> dy = g(t,x,y)dt ==> y1-yo = g(t,x,y)*(t1-to)

From the above two equations we get:
x1 = xo + f(t,x,y)*(t1-to)
y1 = yo + g(t,x,y)*(t1-to)
In General:
tk+1 = tk +h
xk+1 = xk + h*f(tk,xk,yk)
yk+1 = yk + h*g(tk,xk,yk)


It has to be noted that the Euler method doesn't give good accurracy

Runge-Kutta Method for Systems of Differential Equations

Runge-Kutta can be extended for systems of linear equations
The formulas are:
xk+1 = xk + (h/6)*(f1 + 2f2 + 2f3 + f4)
yk+1 = yk + (h/6)*(g1 + 2g2 + 2g3 + g4)

where: f1 = f(tk,yk)
f2 = f(tk + (h/2) , yk + (h/2)*f1)
f3 = f(tk + (h/2), yk + (h/2)*f2)
f4 = f(tk + h , yk + h*f3)

and where: g1 = g(tk,yk)
g2 = g(tk + (h/2) , yk + (h/2)*f1)
g3 = g(tk + (h/2), yk + (h/2)*f2)
g4 = g(tk + h , yk + h*f3)



7/30/04


Numerical Solution of Higher Order Differential Equations


Example

mx"(t) + Cx'(t) + kx(t) = g(t)


We Solve differential equations like the one in the example above by transforming them to a system of first order differential equations.

We do the substitution:
y(t) = x'(t) --> y'(t) = x"(t)

Then we get:
x"(t) = (g(t) - Cx'(t) - kx(t))/m

or
y'(t) = (g(t) - Cy(t) - kx(t))/m       (1)

and
x'(t) = y(t)             (2)
Equations 1 and 2 form a system of two 1st order differential equations that can be Solved using Euler or Runge-Kutta methods.

Example

4x"(t) + 3x'(t) + 5x(t) = 2
with x(0) = 1 and x'(0) = 3
Transform this second order differential equation into a system of two first order differential equations.

x"(t) = (2 - 3x'(t) - 5x(t))/4
let y' = x"
then
x"=(2 - 3y - 5x)/4 = y'

So we get the following system of 1st order differential equations:
(1) x' = y
(2) y' = (2 - 3y - 5x)/4
Which can be Solved using Euler or Runge-Kutta Methods.



CS 314 Review for Final


Exam is cumulative.
10% weighted in first half of semester
90% weighted in second half of semester

Topics Covered in Second half of Semester

Curve Fitting

Numerical Differentiation

For all of these it would be wise to know how to derive each equation method.

Numerical Integration

Numerical Optimization

Solution of Differential Equations



to Study




Brownie Point Information

Hough Transform

It is used in pattern recognition
Assume you have N facts and you have M hypothesis
Hough Algorithm
Have accumulator vector with M entries (M hypothesis) and initialize it to zero.
hypothesis_accumulator [i] = 0 for i=1....M
For all facts j=1....N
If facts[j] supports hypothesis k, increment hypothesis_accumulator[k]

The most likely hypothesis will be the one with the largest hypothesis_accumulator

most likely hypothesis = the maximum hypothesis_accumulator