Transcription of Math 375: Lecture notes
1 math 375: Lecture notesProfessor Monika NitscheSeptember 21, 2011 Contents1 MATLAB Example: Plotting a function .. Scripts .. Setting up vectors .. Vector and Matrix operations .. Plotting .. Printing data .. For loops .. While loops .. Timing code .. Functions .. 172 Computing Vectorizing, timing, operation counts, memory allocation .. Vectorizing for legibility and speed .. Memory allocation .. Counting operations: Horner s algorithm .. Counting operations: evaluating series .. Machine Representation of real numbers, Roundoff errors.
2 Decimal and binary representation of reals .. Floating point representation of reals .. Machine precision, IEEE rounding, roundoff error .. Loss of significant digits during subtraction .. Approximating derivatives, Taylor s Theorem, plottingy=hp.. Big-O Notation .. 303 Solving nonlinear equationsf(x) = Bisection method to solvef(x) = 0 ( ) .. Fixed point iteration to solvex=g(x) (FPI, ) .. Examples .. The FPI .. Implementing FPI in Matlab .. Theoretical Results .. Definitions .. Stopping criterion .. Newton s method to solvef(x) = 0 ( ).
3 The algorithm .. Matlab implementation .. Theoretical results .. Secant method ( ) .. How things can go wrong. Conditioning. ( ) .. Multiple roots .. Forward and Backward error. Error magnification.. Other examples of ill-conditioned problems .. The condition number .. 414 Solving linear Gauss Elimination ( ) .. LU decomposition ( ) .. Partial Pivoting ( , ) .. Conditioning of linear systems ( ) .. Iterative methods ( ) .. 485 Polynomial Interpolants .. Vandermonde approach .. Lagrange interpolants.
4 Newton s divided differences .. Accuracy of Polynomial interpolation .. Uniform points vs Tschebischeff points .. Piecewise Polynomial interpolants .. Piecewise linear interpolant .. Cubic splines .. Trigonometric interpolants .. Using a basis of sines and cosines .. Using a basis of complex exponentials .. Using MATLAB sfftandifft.. What if period 6= 2 ? .. Music and Compression .. 696 Least Squares Solutions toAx= Least squares solution toAx=b.. Approximating data by model functions .. Linear least squares approximation.
5 Quadratic least squares approximation .. Approximating data by an exponential function .. Approximating data by an algebraic function .. Periodic approximations .. QR Factorization ..767 Numerical Integration (Quadrature) Newton-Cotes Rules .. Composite Newton-Cotes Rules .. More on Trapezoid Rule .. Gauss Quadrature .. 7948 Numerical Methods for Problem statement .. Euler s Method .. Second order Method obtained by Richardson Extrapolation .. Second order Method obtained using Taylor Series .. 4th order Runge Kutta Method.
6 865 Syllabus for Fall 20101. MATLAB (see Tutorial on web) Lecture 1 (Mon Aug 23) : Vectors, plotting, matrix 2 (Wed Aug 25) : Scripts, label plots, printing , for, while 3 (Fri Aug 27) : Functions. Timing code. Vectorizing. COMPUTING FUNDAMENTALSL ecture 4 (Mon Aug 30) : What affects execution time? Vectorizing, initializing,operation counts. Examples: Horners algorithm, Taylor series. Big-O notation. ( ) Lecture 5 (Wed Sep 1) : Binary numbers. Floating point representation. ( ) Lecture 6 (Fri Sep 3) : Loss of significance. ( )3. NONLINEAR EQUATIONSL ecture 7 (Wed Sep 8) : Bisection method, 8 (Fri Sep 10) : Fixed point iteration, 9 (Mon Sep 13): Fixed point iteration, 10 (Wed Sep 15): Ill-conditioned problems, Newton s Method, 11 (Fri Sep 17) : Newton s Method, Secant Method.
7 SOLVING LINEAR SYSTEMSL ecture 12 (Mon Sep 20): Gauss Elimination, 13 (Wed Sep 22): LU Decompo, 14 (Fri Sep 24) : EXAM 1 Lecture 15 (Mon Sep 27): PLU Decomposition, 16 (Wed Sep 29): Conditioning, 17 (Fri Sep 31) : Iterative methods: Example and convergence criteria, 18 (Mon Oct 4): Iterative methods: JacobiLecture 19 (Wed Oct 6): Iterative methods: Gauss-Seidel5. INTERPOLATIONL ecture 20 (Fri Oct 8) : Polynomial interpolation. 21 (Mon Oct 11): Polynomial interpolation. Lagrange 22 (Wed Oct 13): Polynomial interpolation. Vandermonde BREAKL ecture 23 (Mon Oct 18): Polynomial interpolation.
8 Newton 24 (Wed Oct 20): Polynomial interpolation. Interpolation 25 (Fri Oct 22) : Polynomial interpolation. Runge phenomena, Chebishev 26 (Mon Oct 25): Spline: linear splines, cubic splines, derivation. 27 (Wed Oct 27): Cubic spline: derivation, MATLAB codes. 28 (Fri Oct 29) : Cubic spline: MATLAB codes, examples. TRIG INTERPOLANTS AND FOURIER TRANSFORML ecture 29 (Mon Nov 1): Trig interpolation: fourier coefficients, 30 (Wed Nov 3): Trig interpolation: Derive DFT, 31 (Fri Nov 5) : Trig interpolation: Fourier coefficients and smoothness of LEAST SQUARESL ecture 32 (Mon Nov 8): Least Squares: normal equations.
9 33 (Wed Nov 10): Approximating data using models. 34 (Fri Nov 12) : QR decomposition. NUMERICAL INTEGRATIONL ecture 35 (Mon Nov 15): Numerical Integration: Newton-Cotes. 36 (Wed Nov 17): Numerical Integration: Composite N-C. 37 (Fri Nov 19) : REVIEWL ecture 38 (Mon Nov 22): EXAM 2 Lecture 39 (Wed Nov 24): Numerical Integration: Mac-Laurin Formula for Trapezoid rule error. BREAKL ecture 40 (Mon Nov 29): Numerical Integration: Gauss Quadrature. NUMERICAL DIFFERENTIATIONL ecture 41 (Wed Dec 1) : Numerical Differentiation. Truncationand Roundoff. ORDINARY DIFFERENTIAL EQUATIONSL ecture 42 (Fri Dec 1) : Euler s Method.
10 MATLAB Algorithm. S 43 (Mon Dec 3) : Local and global truncation errors. 44 (Wed Dec 5) : Euler s Method for systems. 45 (Fri Dec 7) : RK Methods. MATLAB Example: Plotting a functionStarting MATLAB:Windows: search for MATLAB icon or link and clickLinux:% ssh matlabor% matlab -nojvmSample MATLAB code illustrating several Matlab features; code to plot the graph ofy=sin(2 x),x [0,1]: What is really going on when you use software to graph a function?1. The function is sampled at a set of pointsxkto obtainyk=f(xk).2. The points (xk, yk) are then plotted together with some interpolant of the data (piece-wise linear or a smoother curve such as splines of Bezier curves).
