Let [a,b] be the interval over which we want to
find the Solution y'=f(t,y) with y(a)=yo
- We will find a set of points (to,yo),(t1,y1),...,(tk,yk)
that are used to approximate y(t)=y(tk)
-We Divide the interval [a,b] into M equal subintervals:
h=(b-a)/M where h is called 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.
h = (t1-t0),
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' = t^2 - y
y(0) = 1
h = .2
t[0] = 0
t[1] = .2, y[1] = y[0] + hy'[0] = 1 + .2(0^2 - 1) = .8
t[2] = .4, y[2] = .8 + .2(.2^2 - .8) = .648
t[3] = .6, y[3] = .648 + .2(.4^2 - .648) = .5504
t[4] = .8, y[4] = .5123
Analytical solution is y(t) = -e^(-t) + t^2 - 2t + 2
Using the analytical result, y(.4) = .6897, y(.8) = .5907
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.
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' = t^2 - y
y(0) = 1
h = .2
k=0, y[0]=1, t[0]=0
k=1, t[1]=.2, p[1] = y[0]+hf(t[0],y[0]) = 1+.2(0^2 - 1) = .8
y[1] = y[0]+h(f(t[0],y[0])+f(t[1],p[1]))/2 = 1+.2((0^2-1)+((.2)^2-1))/2
y[1] = .8240
k=2, t[2]=.4, p[2] = y[1]+hf(t[1],y[1]) = .8240+.2((.2)^2-.8240) = .6672
y[2] = y[1]+h(f(t[1],y[1])+f(t[2],p[2]))/2 = .6949
k=3, t[3]=.6, p[3] = .6949
y[3] = .6186
k=4, t[4]=.8, p[4] = .5669
y[4] = .6001
Using
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:
y' = t^2 - y, y(0) = 1, h = .2, n = 3
y[k+1] = y[k] + hy'[k] + (h^2/2)y"[k] + (h^3/6)y'"[k] + O(h^4)
y' = t^2 - y, y'[k] = t[k]^2 - y[k]
y" = 2t -y', y"[k] = 2t[k] - y'[k]
y'" = 2 - y", y'"[k] = 2 - y"[k]
k = 0, t = 0, y[0] = 1
y'[0] = 0^2 - 1 = -1
y"[0] = 2(0) - (-1) = 1
y'"[0] = 2 - (1) = 1
y[1] = 1 + .2(-1) + ((.2^2)/2)(1) + ((.2^3)/6)(1) = .821333
y'[1] = (.2)^2 - .821333 = -.781333
y"[1] = 2(.2) - (-.781333) = 1.181333
y'"[1] = 2 - 1.181333 = .818667
y[2] = .821333+.2(-.781333)+((.2^2)/2)(1.181333)+((.2^3)/6)(.818667)
y[2] = .689785
y'[2] = (.4)^2 - .689785 = -.529785
y"[2] = 2(.4) - (-.529785) = 1.329785
y'"[2] = 2 - (1.329785) = .670215
y[3] = .61337
y'[3] = -.251317
y"[3] = 1.451317
y'"[3] = .548683
y[4] = .590812
Exact solution: .5907
Euler method: .59123
Heun method: .6001
-
ADVANTAGE:to increase
accurracy increase n in the Taylor Series. This will also decrease the
error.
NO CLASS!!
Homework #5 due on Tuesday!! (Last day of Class)
Final Exam: August 5th (
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)
- Example
y' = t^2 - y, y(0) = 1, h = .2
t[0] = 0, y[0] = 1
f[1] = 0^2 - 1 = -1
f[2] = f(0+(.2/2),1+(.2/2)(-1))
= f(.1,.9) = .1^2-.9 = -.89
f[3] = f(0+(.2/2),1+(.2/2)(.89))
= f(.1,.911) = .1^2-.911 = -.901
f[4] = f(0+.2,1+.2(-.901))
= f(.2,.8198) = .2^2-.8918 = -.7798
t[1] = 0+.2 = .2, y[1] = 1+(.2(-1+2(-.89)+2(-.901)+(-.7798))/6 = .821273
f[1] = -.781273
f[2] = -.653146
f[3] = -.665958
f[4] = -.528081
t[2] = .4, y[2] = .689688
Exact value is .6897
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)
x' = x + 2y, y' = 3x + 2y, x(0) = 6, y(0) = 4
Analytical solution results in x(t)=4e^4t + 2e^-t, y(t)=6e^4t - 2e^-t
You can verify this by deriving x(t) and y(t) and substituting
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 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)
Numerical Solution of Higher Order Differential Equations
- mx"(t) + cx'(t) + kx(t) = g(t)
- Solve via transforming into a system of first-order differential equations
- y(t) = x'(t), y'(t) = x"(t) is the substitution
- y'(t) = (g(t)-cy(t)-kx(t))/m, x'(t) = y(t)
- Example
4x"(t) + 3x'(t) + 5x(t) = 2, x(0) = 1, x'(0) = 3
x"(t) = (2-3x'(t)-5x(t))/4
y'(t) = (2-3y-5x)/4
x'(t) = y
Solve via Runge-Kutta
Exam is cumulative.
10% weighted in first half of semester
90% weighted in second half of semester
-Least Squares line
-Least Squares for non-linear equations
-Transformations for data linearization that reduce least squares line
-Polynomial Fitting
-Spline Functions
For all of these it would be wise to know how to derive each equation method.
-Limit of Difference Quotient
-Central Difference formula of order O(h2)
-Central Difference formula of order O(h4)
-Trapezoidal Rule
-SimpSon Rule
-Local/Global Minimum/Maximum and properties
-Golden Ratio Method
-Minimization using derivatives (i.e. f'(x) = 0)
-Steepest decent or Gradient Method
-Euler's Method
-Heun's Method
-Taylor Series' Method
-Runge-Kutta Method of order 4
-Systems of Differential Equations
-Higher order Differential Equations and how they are transformed into systems of 1st order differential equations
-Do Homework #5
-Study class notes
-Study Book
-Solve Final from Summer 2003
-you may bring in equations/notes/whatever-you-like to the exam, but it can only fill 1/2 page of one side of a sheet of paper
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