7-26-04

End of semester info
- 1 more homework assignment
- Possibly 1 more programming assignment

Euler's Method
- Let [a,b] by the interval over which we want to find the solution y' = f(t,y) with y(a) = y[0]
- We will find a set of points (t[0],y[0]), (t[1],y[1]), ... (t[k],y[k]) which are used to approximate y(t) = t(t[k])
- h = (b-a)/m, so it's divided into m different subintervals
- t[k] = a + kh for k = 0, 1, 2, ... m
- y' = f(t,y) over [t[0],t[1],...t[m]], y(t[0]) = y[0]
- y(t) = y(t[0]) + y'(t[0])(t-t[0]) + (y"(c[1])(t-t[0])^2)/2
- y(t[1]) ≈ y(t[0]) + y'(t[0])(h)
- y[1] = y[0] + hf(t[0],y[0]), which is called Euler's approximation
- t[k+1] = t[k] + h, y[k+1] = y[k] + hf(t[k],y[k])
- 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
- In order to improve precision, reduce h
- The larger the k in t[k], the larger the cumulative error

Heun's Method
- Want to solve y'(t) = f(t,y(t)) over [a,b] with y(t[0]) = y[0]
- Can use the Fundamental Theorem of Calculus and integrate
- y(t[1]) = y(t[0]) + ∫[t[0];t[1]] f(t,y(t))dt
- y(t[1]) = y(t[0]) + h(f(t[0],y(t[0]))+f(t[1],y(t[1])))/2
- Note that this is a recursive definition of y(t[1])
- An approximation p(t[1]) will be used in place of y(t[1])
- p(t[1]) = y[0] + hf(t[0],y(t[0]))
- y(t[1]) = y(t[0]) + h(f(t[0],y(t[0]))+f(t[1],[y[0]+hf(t[0],y(t[0]))]))/2
- Euler's method used as predictor, integral used as corrector
- Generalized form:
p[k+1] = y[k] + hf(t[k],y[k])
y[k+1] = y[k] + h(f(t[k],y[k])+f(t[1],p[k+1]))/2
- 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

7-27-04

Taylor Series Method
- Taylor approximation:
y(t[k] + h) = y(t[k]) + h y'(t[k]) + h^2/2! y"(t[k]) + ... h^n/n! y{n}(t[k])
y[k+1] = y(t[k]) + hy'[k] + (h^2/2!)y"[k] + ... (h^n/n!)y{n}[k] + O(h^(n+1))
- 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

7-29-04

Final Exam
- Thursday, August 5th from 1:00PM-3:00PM in UNIV303
- Last day of class is next Tuesday
- Written homework (due on Tuesday, August 3rd)

Solving Differential Equations Using Runge-Kutta Method Of Order 4
- Simulates the accuracy of Taylor series method of order N = 4 but does not require the computation of derivatives
- y[k+1] = y[k] + (h(f[1]+2f[2]+2f[3]+f[4]))/6
- f[1] = f(t[k],y[k])
- f[2] = f(t[k]+h/2,y[k]+(h/2)f[1])
- f[3] = f(t[k]+h/2,y[k]+(h/2)f[2])
- f[4] = f(t[k]+h,y[k]+hf[3])
- 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

Systems of Differential Equations
- Assume we have the equations dx/dt = f(t,x,y), dy/dt = g(t,x,y) with x(t[0]) = x[0] and y(t[0]) = y[0]
- The conditions are functions x(t) and y(t) that when derived they transform into f(t,x,y) and g(t,x,y)
- Example
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
- Euler method
   * x-x[0] = f(t,x,y)(t-t[0])
   * y-y[0] = g(t,x,y)(t-t[0])
   * x[1] = x[0] + f(t,x,y)(t[1]-t[0])
   * y[1] = y[0] + f(t,x,y)(t[1]-t[0])
   * In general,
t[k+1] = t[k] + h
x[k+1] = x[k] + h(f(t[k],x[k],y[k]))
y[k+1] = y[k] + h(g(t[k],x[k],y[k]))
   * The Euler method is not very accurate due to Taylor simplification
- Runge-Kutta method
   * x[k+1] = x[k] + (h/6)(f[1]+2f[2]+2f[3]+f[4])
   * y[k+1] = y[k] + (h/6)(g[1]+2g[2]+2g[3]+g[4])
   * f[1] = f(t[k],x[k],y[k])
   * f[2] = f(t[k]+h/2,x[k]+(h/2)f[1],y[k]+(h/2)g[1])
   * f[3] = f(t[k]+h/2,x[k]+(h/2)f[2],y[k]+(h/2)g[2])
   * f[3] = f(t[k]+h,x[k]+hf[3],y[k]+hg[3])

7-30-04

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

------------------------------------------------------------------------------

CS314 Final Review
- 10% first half, 90% second half
- Topics to be covered (know how formulas are derived)
   * Curve fitting
      + Least squares line
      + Least squares for non-linear equations
      + Transformations for data linearization (reduce least squares from non-linear equations into a least squares line)
      + Polynomial fitting
      + Spline functions (WILL DEFINITELY BE ON EXAM)
         - Know the rules in order to be able to prove correct
         - Know how to obtain the coefficients using the formulas
   * Numerical Differentiation
      + Limit of Difference Quotient
      + Central Difference formula of order O(h^2)
      + Central difference formula of order O(h^4)
   * Numerical Integration
      + Trapezoidal Rule
      + Simpson Rule
   * Numerical Optimization
      + Local/global minimum/maximum and properties
      + Golden Ratio method
      + Minimization using derivatives (f'(x) = 0)
      + Steepest descent/gradient method
   * Solutions of Differential Equations
      + Euler's method
      + Heun's method
      + Taylor series method
      + Runge-Kutta method of order 4
   * Solutions of Systems of differential equations
      + Euler method
      + Runge-Kutta method of order 4
   * Higher Order Differential Equations

Study recommendations
- Do homework #5
- Study class notes
- Study book
- Practice exam from last year
- Bring a formulary (1/2 page, 1 side)

------------------------------------------------------------------------------

Artificial Intelligence
- Deduction: If 1 then 2, If 2 then 3, so If 1 then 3
- Induction: Building up rules from sensory input
- Adduction: Choosing the most common situation from perceived state (without full information) and acting accordingly

Hough Transform
- Used in pattern recognition
- Assume you have n facts and m hypotheses
- Accumulator vector with m entries and initialize to 0
- Go through facts, and increment hypothesis if fact supports it
- The most likely hypothesis is the one with the largest value