Go over WEB pages Lecture 11 through 18. Open book, open notes, exam. Some things you should know: The roots of a polynomial with real coefficients can be complex. Some languages have "complex" as a built in type (e.g. Fortran, MatLab and Python) Some languages provide standard packages for "complex" (e.g. Ada and C++) Some languages require you find or make your own "complex" (e.g. C and Java) All elementary functions are defined and computable for complex arguments. All complex elementary functions may be computed with only real functions. Example: sin(z)=sin(re z)*cosh(im z) + i cos(re z)*sinh(im z) Some complex elementary functions are difficult to compute accurately. Some elementary functions have a branch cut in the complex plane. The branch cut is often along the negative real axis. The derivative is not defined across the branch cut. Eigenvalues must satisfy several definitions. There are exactly n eigenvalues for every n by n matrix. The eigenvalues of a non singular matrix of real elements may be complex. The determinant of a matrix with a variable subtracted from each diagonal element yields the characteristic equation of the matrix. e.g det|A - eI| = c_n*e^n + ... _ c_1*e + c_0 The roots of the characteristic equation are eigenvalues. det|A - eI|=0 is one definition of eigenvalues. Given a polynomial equation, the coefficients of the polynomial may be placed in a matrix such that the eigenvalues of the matrix are the roots of the polynomial. An eigenvector exists for every eigenvalue. It is always possible to find a set of orthogonal eigenvectors that form the basis of an n dimensional space for an n by n matrix. Eigenvectors may be complex when the matrix elements and the eigenvalues are real. The eigenvectors of a matrix of all ones are usually chosen as the unit vectors [1 0 ... 0] [0 1 0 ... 0] ... [0 ... 0 1] The equation A v = e v must be satisfied for every eigenvalue, e, and its corresponding eigenvector, v. |v| non zero. There are many possible test for a program that is supposed to compute eigenvalues and eigenvectors. MatLab may not produce unique eigenvectors using [v e]=eig(a) MatLab may not produce eigenvectors that are mutually orthogonal. LAPACK is a source of many numerical algorithms implemented in Fortran. LAPACK code may be converted to any other language. LAPACK object files may be used with most languages via some interface. LAPACK source code needs the BLAS, Basic Linear Algebra Subroutines. The BLAS may be available, optimized, for your computer. LAPACK is available with files to compile and install on many computers from www.netlib.org/lapack TOMS is numerical source code from the ACM Transactions on Mathematical software and may be found on www.netlib.org/toms Some problems require more than double precision floating point. "gmp" is the gnu multiple precision library of "C" functions. gmp is available from www.swox.com/gmp or other sites. gmp provides multiple precision integer, rational and floating point. Any language can implement multi-precision, Java has it available, other languages use libraries. 52! has too many significant digits to exactly represent in double precision floating point. Solving large systems of equation may require multi-precision in order to get reasonable results. A simple example of the need for complex roots is x^2+1 = 0 with roots i and -i . The roots of high order polynomials may be difficult to compute accurately, e.g. x^16 + 5 = 0 . There is no algorithm that can guarantee finding all the roots of every polynomial to a specified accuracy. Newtons method works most of the time for finding complex roots. (Using a different initial guess usually fixes the problem.) Optimization is finding the values of independent variables such that a function is minimized. Optimizing the absolute value of a function finds the values of the independent variables that make the function closest to zero. There is no algorithm that can guarantee finding the optimum value of every function to a required accuracy. There are many methods of implementing code to find local minima. The code varies depending on the assumption of a differentiable function and on the assumption of no local minima. The spiral trough is one test case that can be used to test optimization code. A Fourier transform of a finite set of data assumes that the data is repeated infinitely many times before and after the data. A FFT, Fast Fourier Transform implements a discrete Fourier transform using order n log n computations for an n point transform. Typically n must be a power of 2. The FFT of real data may be complex. The inverse FFT of the result of and FFT will be reasonably close to the original data. The Discrete Fourier transform and FFT of data sampled at time steps dt will be the frequency spectrum with highest unaliased frequency 1/(2*dt), the Nyquist frequency. Digital Filters can be low-pass, high-pass, or band-pass. Digital Filters can be described by a set of "a" and "b" coefficients.