CS 314 Notes July 26 --- July 30

Monday July 26, 2004

Euler’s method:

Let [a,b] be the interval which we want to find the solution of y' = f(t,y), with y(a) = y₀. We will find a set of points (t₀,y₀), (t₁,y₁),...,(t_K,y_K) that are used to approximate y'(t) ~= y'(t_K).

h = (b-a)/m step size

Also, t_k = a + k*h for k = 0,1,2,...,m
we want to solve y' = f(t,y) over [t₀,t₁,...,t_m] with y(t0) = 0

Use Taylor Expansion to approximate y(t)

y(t) = y(t₀) + y'(t₀)(t-t₀) + y''(c₁)(t-t₀)²/2
y''(c₁)(t-t₀)²/2 is Error

Use equation to obtain y(t1)

y(t₁) = y(t₀) + y'(t₀)(t₁-t₀) + y''(c₁)(t₁-t₀)²/2

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

y₁ = y₀ + h*y'(t₀)
y₁ = y₀ + h*f(t₀,y₀)

In general:
t_k+1 = t_k + h
y_k+1 = y_k + h*f(t_k,y_k) for k = 0,1,...,m-1

Example:

y' = t² - y	y (0) = 1	h = .2
t₁ = 0 + .2 = .2 y₁ = y₀ + h¦(t₀, y₀) = 1 + .2(0² - 1) = .8 t₂ = .2 + .2 = .4 y₂ = .8 + .2(.2² - .8) = .648 t₃ = .4 + .2 = .6 y₃ = .648 + .2(.4² - .648) = .5504 t₄ = .6 + .2 = .8 y₄ = .5504 + .2(.6² - .5504) = .5123 The exact solution is .5907

If you want to get better precision with Euler’s method, you can make h (step size) smaller.

Also, the larger the k is, the larger the solution error will be.

Heun's Method

We want to solve y '(t) = f(t, y (t)) over [a, b] with y (t₀) = 0. We can integrate y '(t) over [t₀, t₁]:

t₁		t₁
ò	y '(t)dt =	ò	¦(t, y (t))dt = y (t₁) - y (t₀)
t₀		t₀

We use numerical integration to approximate the integral in the right side. Use the trapezoidal rule:

y (t₁) - y (t₀) = (h/2)[f(t₀, y (t₀)) +(t₁, y (t₁))]

Then we have:

y (t₁) = y (t₀) + (h/2)[f(t₀, y (t₀))+(t₁, y (t₁))]

Observe we still need to know (t₁, y (t₁)). That involves y (t₁) which is what we want to solve. To eliminate this circular reference, we use Euler's approximation to obtain y (t₁).

y (t₁) = y (t₀) + hf(t₀, y (t₀))

So we have:

y (t₁) = y (t₀) + (h/2)[f(t₀, y (t₀)) +f(t₁, y (t₀) + h*f(t₀, y (t₀)))
y₁ = y (t₁)
y₀ = y (t₀)
y₁ = y₀ + (h/2)[¦f(t₀, y₀) + ¦f(t₁, y₀ + h*f(t₀, y₀))]

In general:

P_k+1 = y_k + hf(t_k,y_k)

Y_k+1= y_k + h/2 (f(t_k,y_k) + f(t_y,P_k+1))

Euler approximation is used as a prediction and the integral approximation is used as correction

Example

f(y,t) = y’ = t² – y y(0) = 1 h = .2

k = 0 y₀ = 1 t₀ = 0

k = 1 t₁= 0 + .2 = .2

P₁= y₀ + hf(t₀,y₀)

= y₀ + h(t₀² – y₀)

= 1 + .2(0² – 1) = .8

y₁ = y₀ + h/2 ((t₀² – y₀) + (t₁² + P₁))

= 1 + .2/2 ((0² – 1) + ((.2)² + .8))

= .8240

k = 2 t₂ = .4

P₂ = .8240 + .2(.2² – 0.8240) = 0.6672

y₂ = .8240 + .2/2 ((.2² – 0.8240) + .4² - .6672)

= .6944

k = 3 t₃ = .6

P₃ = .6949 + .2(.4² - .6949) = .5879

y₃ = .6949 + .2/2 ((.4² - .6949) + (.6² - .5879))

= .6186

k = 4 t₄ = .8

P₄ = .6186 + .2(.6² - .6186) = .3669

y₄ = .6186 + .2/2 ((.6² - .6186) + (.8² - .5669))

= .6001

K	t_k	y_k(Euler)	y_k(Heun)	y_k(exact)
2	.4	.648	.6949	.6897
4	.8	.5123	.6001	.5907

Tuesday July 27, 2004

Taylor Series Method

Using the Taylor expansion to approximate the solution:

y(t₀+h) = y(t₀) + hy’(t₀) + h²y”(t₀)/2 + … + h^Ny^N(t₀)/N! + O(h^N+1)

We want to solve

y’ = f(y,t) y(t₀) = a

From the Taylor expansion we can find the successive points.

y_k+1 = y_k + hy_k’ + h²y_k”/2 + h³y”’/3! … + h^Ny^N/N!

We still need to compute y_k”, y_k”’ … etc using y’ = f(y,t).

The error in the approximation will be O(h^N+1). The higher the order of the Taylor series, the smaller the error.

Example

Solve: y’ = t² – y y(0) = 1 h = .2 Use N = 3

y_k+1= y_k + hy_k’ + h²y”(t₀)/2 + … + h³y^’’’(t₀)/6

y’ = t² – y

y” = 2t – y’

y”’ = 2 – y”

k=0 t=0 y₀ = 1

y₀’ = 0² – 1 = -1

y₀” = 2(0) – (-1) = 1

y₀”’ = 2 - 1 = 1

k=1 t=.2 y₁ = 1 + .2(.1) + (.2)²(1)/2 + (.2)³(1)/6 = .821333

y₁’ = (.2)² – .821333 = -.781333

y₁” = 2(.2) – (-.781333) = 1.181333

y₁”’ = 2 – 1.181333 = .818667

k=2 t=.4 y₂ = .821333 + .2(-.781333) + (.2)²(1.181333)/2 + (.2)³(.818667)/6 = .689785

y₂’ = (.4)² – .689785 = -.524785

y₂” = 2(.4) – (-.524785) = 1.329785

y₂”’ = 2 – 1.329785 = .670215

k=3 t=.6 y₃ = .689785 + .2(-.524785) + (.2)²(1.329785)/2 + (.2)³(.670215)/6 = .611317

y₃’ = (.6)² – .611317 = -.251317

y₃” = 2(.6) – (-.251317) = 1.451317

y₃”’ = 2 – 1.451317 = .548633

k=4 t=.8 y₄ = .611317 + .2(-.251317) + (.2)²(1.451317)/2 + (.2)³(.5486333)/6=.590812

y(.8) =

exact: .5907

Euler: .5123

Heun: .6001

To reduce approximation error, increase the order N of the expansion or reduce the value of h. I t is more effective to increase N since Error = O(h^N+1)

Wednesday July 28, 2004

Class has been canceled today.

Thursday July 29, 2004

Final exam: Next Thursday Aug 5 from 1:00 to 3:00, at Univ 303

You can use more time if you want

A review will be given on Friday July 30

Hw5 is posted due on next Tuesday during class

To test the correctness of a Spline, the following has to be true:

1. Continuity in the function

S₀(x₀)=y₀

S₀(x₁)=y₁

S₁(x₁)=y₁

S₁(x₂)=y₂

S₂(x₂)=y₂

S₂(x₃)=y₃

2. Continuity in 1^st derivative

S₀’(x₁)=S₁’(x₁)

S₁’(x₂)=S₂’(x₂)

3. Continuity in 2^nd derivative

S₀’’(x₁)=S₁’’(x₁)

S₁’’(x₂)=S₂’’(x₂)

Runge-Kutta

method of order 4.

- Taylor method gives a good approximation, but it requires the derivative of the function.

- The Runge-Kutta method of order 4 simulates the accuracy of the Taylor series method using an order N=4 but it does not require the computation of derivatives.

y_k+1 = y_k+ h(f₁ + f₂ + f₃ + f₄)/6

where:

f₁ = f(t_k,y_k)

f₂ = f(t_k + h/2, y_k + h/2 f₁)

f₃ = f(t_k+ h/2, y_k+ h/2 f₂)

f₄ = f(t_k+ h, y_k+ h f₃)

Example

y’ = f(t,y) = t²-y y(0) = 1 h = .2

t₀=0 y₀= 1

Iteration0 f₁= 0² -1 = -1

f₂ = f(0 + .2/2, 1+.2/2(-1))

= f(.1,.9) = .1² - .9 = -.89

f₃ = f(0 + .2/2, 1+.2/2(-.89))

= f(.1,.911) = .1² - .911 = -.901

f₄ = f(0 + .2, 1+.2(-.901))

= f(.2,.8198) = .2² - .8198 =- .7798

t₁=.2 y₁ = (1 + .2( -1 + 2(-.89) + 2 (-.901) + (-.7798))/6= .821273

Iteration1

f₁= .2² -.821273 = -.781273

f₂ = f(.2 + .2/2, 0.821273+.2/2(-.781273))

= f(.3,.743186) = .3² - .743146 = -.653146

f₃ = f(.2 + .2/2, .821273+.2/2(-.653146))

= f(.3,.755958) = .3² - .755958 = -.665958

f₄ = f(.2 + .2, .821273+.2(-.665958))

= f(.4,.688081) = .4² - .688081 = -.528081

t₂=.4 y₂ = (.821273 + .2( -.781273 + 2(-.653146) + 2 (-.665958) + (-.528001))/6

= .689688

exact: y(.4) = .6847

Taylor: y(.4) = .689783

Systems of Differential Equations

Assume we have equations:

dx/dt = f(t,x,y)
dy/dt = g(t,x,y)
with x(t₀) = x₀; y(t₀) = y₀

The solution to this system are functions x(t) and y(t) that when derivated and substituted in the system of equations give equality.

Ex of a system of differential equations

x' = x + 2y x(0) = 6
y' = 3x + 2y y(0) = 4

Solution
x(t) = 4e^4t + 2e^-t
y(t) = 6e^4t - 2e^-t

- Euler Method

We can extend Euler's method of a single differential equation to a system of equations

dx/dt = f(t,x,y) dx = f(t,x,y)dt
dy/dt = g(t,x,y) dy = g(t,x,y)dt

Approximate
        dx_k = x_k+1-x_k
        dy_k = y_k+1 - y_k
        dt_k = t_k+1 - t_k

x_k+1-x_k = f(t_k,x_k,y_k)(t_k+1-t_k)
y_k+1-y_k = g(t_k,x_k,y_k)(t_k+1-t_k)
x(t₀) = x₀ y(t₀) = y₀

Therefore
x_k+1 = x_k + f(t_k,x_k,y_k)*h
y_k+1 = y_k + g(t_k,x_k,y_k)*h

Bad Accuracy because it approximates Taylor to the 1st Derivative

- Runge-Kutta (Order 4) for a system of differential equations

x_k+1 = x_k + h * (f₁ + 2f₂ + 2f₃ + f₄) / 6
y_k+1 = y_k + h * (g₁ + 2g₂ + 2g₃ + g₄) / 6

f₁ = f( t_k, x_k, y_k )
f₂ = f( t_k + h/2, x_k + h/2*f₁, y_k + h/2*g₁ )
f₃ = f( t_k + h/2, x_k + h/2*f₂, y_k + h/2*g₂ )
f₄ = f( t_k + h, x_k + h*f₃, y_k + h*g₃ )

g₁ = g( t_k, x_k, y_k )
g₂ = g( t_k + h/2, x_k + h/2*f₁, y_k + h/2*g₁ )
g₃ = g( t_k + h/2, x_k + h/2*f₂, y_k + h/2*g₂ )
g₄ = g( t_k + h, x_k + h*f₃, y_k + h*g₃ )

Friday July 30, 2004

Higher Order Differential Equations

Higher order differential equations involved higher derivatives x”(t), y”(t).

For example:

mx”(t) + cx’(t) + kx(t) = g(t)

The higher order differential equations can be transformed to a system of differential equations of first order.

Use the substitution:

y(t) = x’(t)

The system

mx”(t) + cx’(t) + kx(t) = g(t)

obtain x”(t)

x”(t) = (g(t) – cx’(t) – kx(t)) / m

substituting x”(t)

y’(t) = (g(t) – cy(t) – kx(t)) / m --------- 1

This is the first differential equation of first order in the system.

The second equation is

x’(t) = y(t) ------------- 2

Example

4x” + 3x’ + 5x = 2 with x(0) = 1

x” = (2 – 3x’ – 5x) / 4 x’(0) = 3

Let y = x’ and substituting in x”

y’ = (2 – 3y – 5x)/4 x(0) = 1, y(0) = 3

x’ = y

Final Review

10% - First Half
90% - Second Half

Curve Fitting

Least Squares Line
Least Squares for Non-linear equations
Transformations for data linearization
Polynomial Fitting
Splines

The 5 Properties (I...V)
Proof
How to use the formulas to get the spline coefficients
end point constraints

Numerical Differentiation

Limit of the Difference Quotient
Central Difference formula of order O(h²)
Central Difference formula of order O(h⁴)

Numerical Integration

Trapezoidal Rule
Simpson's Rule

Numerical Optimization

Local/Global Min/Max
Properties of Min/Max points
The Golden Ratio method
Minimization using derivatives
Steepest descent of gradient method

Solution of Differential Equations

Euler's Method
Heun's Method
Taylor Series Method
Runge-Kutta Method Order 4
Systems of Differential Equations

Euler's Method
Runge-Kutta of Order 4

Higher order differential equations

Study Materials:

Do hw5
Class Notes
Book
Read Homework & Projects
Exercises in Book

May Bring

1/2 page formulary (one side)
Calculator

Hough Transform

It’s 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 0.
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_accum

most likely hypothesis = maximum <hypothesis_accum>