1. Predictor Corrector Methods
   1. Overview
      1. Heun, Taylor, Runge-Kutta, and Euler are single-step methods: they only useto compute
      2. Multi-step methods use more than one previous value of
   2. Adams-Bashfourth-Moulton method
      1. Uses a Lagrange polynomial to obtainand then integrate over the interval
      2. ← Adams-Bashfourth predictor
      3. The corrector is also developed by constructing a second order Lagrange polynomial and then integrating
      4. 
1. Systems of Differential Equations
   1. Multiple Variables
      1. eg. Assume we have these equations:
      2. 
      3. 
      4. 
   2. The solutions are functions x(t) and y(t) that when derivated they transform intoand
   3. Example VIII.1
      1. Initial Conditions:
         1. 
         2. 
         3. 
         4. 
      2. Exact Solution:
         1. 
         2. 
   4. Euler Method for Systems of Differential Equations
      1. Extend Euler's method for systems of differential equations
         1. Substituteif we makesmall enough
         2. 
         3. As a result, we have
         4. Simplifying, we get
         5. Same for y:
         6. 
         7. 
         8. 
         9. 
      2. In general,
      3. 
      4. 
      5. 
      6. Example VIII.2 (Continuation of Example VIII.3)
         1. Initial Conditions
            • 
            • 
            • 
            • 
         2. Substitute our equations (given) and end up with these equations:
            • 
            • 
            • 
            • 
         3. Use these to walk the curve and obtain the following table:
            • 
         4. As we continue, the error grows.
         5. Comparison with exact solution:
            • 
            • 
            • 
            • 
            • 
            • 
         6. Conclusion:
            • is too large
            • Maybe choosingwill give a better result but it will be slower
   5. Runge-Kutta for Systems of Differential Equations
      1. Uses more than one evaluation of g and f so it gives better precision
      2. 
      3. 
      4. ← Equations 1, 2
      5. ← Equations 3, 4
      6. ← Equations 5, 6
      7. ← Equations 7, 8
   6. Higher Order Differential Equations
      1. Involve higher derivatives
         1. eg.,, etc.
      2. For example:
         1. 
      3. We can reduce this equation to a system of two differential equations of first order
         1. Let
         2. Then
      4. Then this second differential equation becomes
         1. 
         2. 
      5. Example IX.1
         1. with
         2. 
         3. Let
         4. So we have the system of differential equations:
            • 
            • 
         5. We can solve this system using the Runge Kutta methods.
2. Fourier Series
   1. Used to represent sequences in time
   2. We can express a functionas a summation of sin and cos functions with different frequencies and amplitudes
      1. Assumeis a function that is periodic with periodand it is continuous over
      2. 
      3. To obtain a_J and b_J we integrate f(x)
      4. 
      5. 
      6. 
      7. 
      8. 
      9. To obtain we multiply by where is the constant we want to determine
      10. 
      11. 
      12. We’re left with
      13. ← When
      14. Orthogonal Properties
          1. 
          2. 
          3. 
      15. 
      16. ← Fourier Transform
      17. We can use the same procedure to obtain
      18. 
   3. DFT (Discrete Fourier Transform)
      1. Input: a discrete signal (a signal that is sampled periodically over time)
      2. Example
         1. Our signal is sampled to create the sequence 3,5,6,5,3,3
         2. The number of bits to represent this sample is limited in the computer
         3. The analog values are rounded or truncated
         4. The rounding error is called the quantization error or quantization noise
         5. When we use more bits to represent our sample we reduce the quantization noise (eg. 16 bits → )
      3. High Fidelity Signals
         1. eg. CD music, etc.
         2. 44,000 samples/sec
         3. 2 bytes/sample
         4. 2 channels (stereo)
         5. 3 minutes per song (180 seconds)
         6. 
      4. Analog Transform
         1. Imaginary form
         2. ← Equation 1 (“i” is the imaginary number)
         3. This imaginary form is more compact that the sin cos version
         4. Euler’s Identity
            • ← Equation 2
         5. Substituting equation 2 in 1
            • 
            • 
            • is the real part ofandis the imaginary part of
      5. Discrete Fourier Transform
         1. We approximate the integral using a sum of rectangles
         2. 
         3. is a complex number
         4. It is easier to use the magnitude and angle ofinstead of real and imaginary components
         5. 
         6. 
         7. Relationship between Analog and Discrete Fourier Transform
            • Example
              • We obtain the amplitudes of the harmonics
              • Nyquist Theorem (Nyquist Limit)
                • We can’t go beyond the N/2 harmonic
                • Or….
                • If you have a signal with a maximum frequency F you have to sample it at 2F samples-per-second or the signal will degrade
         8. Applications
            • MP3 Sound Compression
              • Instead of storing samples over time, MP3 divides the samples into groups (eg. 576 samples)
              • Obtain DFT to get thecoefficients
              • Masked points are discarded or encoded with fewer points
              • By storing fewercoefficients MP3 is able to obtain up to 10:1 compression (1/10^th of the original size)
              • MP3 players take the A_k coefficients and rebuild the signal over time using an inverse discrete fourier transform
              • The reconstituted signal will be different than the original but it will sound similar
            • Speech Recognition
            • Pattern Recognition
              • The Problem
                • Given a series of pointsobtain the most likely lines that pass through those points
                • We have multiple lines!
                  • Least Squares? It won't give you both lines
                  • Use the Hough Transform!
      6. Hough Transform
         1. Explanation
            • A point in (x,y) can belong to a family of lines
            • In the real world, there are an infinite number of families; in the computer there is a definite number of families
            • Recall formula for a line: y=mx+b
            • For a specific point (x,y) we can define a family of lines
              • 
              • This is a line with slope
              • Assuming the m-b plane, the line crossesat
              • 
              • 
              • All the points (m,b) in the line on the m-b plane represent all the possible lines that pass through (x,y) on the x-y plane
            • If many points on the x-y plane are on the same line they will intersect at the same point on the m-b plane
            • We can use the m-b plane as an accumulator to count the intersections at each point (this is called an accumulator plane)
            • The points with the highest number of intersections on the m-b (b-m) plane will be the lines you would like to represent on the x-y plane
         2. Mathematics
            • Inputs are points that form multiple lines
            • Outputs are linesthat are the most likely lines that the points represent
            • Step 1
              • Create a 2-D accumulator matrix to represent the b-m space
            • Step 2
              • A point (x,y) is contained by the line→ A point (x,y) gives a line in the plane (b,m)
              • 
              • Plot the lineover x in the b-m accumulator plane
              • For every (b,m) that the line passes through increment that accumulator
            • Step 3
              • Iterate over the b-m matrix and find the top k counters
              • 
              • These are the most likely lines
         3. This can be extended to support many different shapes
         4. The problem is that this method can’t see vertical lines →can’t represent vertical lines
         5. In the Hough transform we use the polar line representation
            • 
         6. In this way, we rewrite the Hough algorithm to use theplane instead of the b-m plane
            • Step 1
              • Define a 2-D matrix:
            • Step 2
              • Initialize accum with 0s
            • Step 3
              • For all points (x,y) in
              • Forto
              • 
              • 
              • 
            • Step 4
              • For all values in accum find the top k
              • These are the most likely lines
         7. Example available at http://www.dis.uniroma1.it/~iocchi/slides/icra2001/java/hough.html
      7. Hough Transform for circles
         1. Explanation
            • We can build a hough transform for circles by using a similar approach
            • Input: a sequence of points (x_0 , y_0), … , (x_{n-1} , y_{n-1}) and a radius r
            • Output: a sequence of centers (p_0 , q_0), … , (p_{k-1}, q_{k-1}) of circles of radius R that are the most likely circles that pass through (x_0, y_0), … , (x_{n-1}, y_{n-1})
            • We have the x-y plane (circles) and the p-q plane (centers of circles)
            • 
            • 
            • These equations give a circle centered at (x,y) in the (p,q) plane
         2. Algorithm
            • Create an accumulator accum[m,n]
            • For each point
              • 
                • 
                • p=x_k + Rcos(t)
                • q=y_k + Rsin(t)
                • accum[p,q]++
              • 
                • 
                  • 
                    • 
         3. Example available at http://d0server1.fnal.gov/users/ngraf/Talks/UTeV/Java/Circles.html