MAT3633

Course Catalog

MAT 3633. Numerical Analysis. (3-0) 3 Credit Hours.

Prerequisites: MAT2233, MAT3213, and one of the following: CS1063, CS1714, or CS2073. Solution of linear and nonlinear equations, curve-fitting, and eigenvalue problems. Generally offered: Fall, Spring. Differential Tuition: $150.

Topics List

Date	Sections [Sauer 3rd ed]	Topics	Prerequisite Skills	Student Learning Outcomes
Week.1	0.2 and 1.1	Loss of significant digits Bisection Method Brief introduction to matlab	binary number system; Taylor's theorem; intermediate value theorem	Nested multiplication for evaluating polynomials Machine representation of real numbers Loss of significant digits in numerical computing Review of Taylor's Theorem Bisection method and implementation
Week.2	1.2 and 1.3	Fixed-Point Iteration Limits of Accuracy: Conditioning of problems	limit of sequences multiplicity of solution of equations.	Geometric interpretation Convergence of fixed point iterations Order of convergence of iterative methods Wilkinson polynomial and other examples Sensitivity analysis of root-finding Error magnification factor for solution of equations
Week.3	1.4 and 1.5	Newton's Method Root-Finding without Derivatives	Remainder of Taylor's series intermediate value theorem.	Algebraic and geometric interpretation of Newton's method Error analysis for Newton's method based on Taylor's theorem Newton's method as a fixed point iteration Modified Newton's method and its rate of convergence Secant Method and its convergence, Method of False Position, Muller's Method: Stopping criteria for iterative methods
Week.4	2.1 and 2.2	Solve Systems of Linear Equations: Gaussian Elmination Solve System of Linear Equations: LU Decomposition	Matrix-matrix products and matrix-vector products inverse matrix elementary row operations product and inverse of matrices for elementary row operations.	Gaussian elimination and its operation counts Gaussian elimination with pivoting Implementation of Gauss elimination Matrices for elementary row operations Gauss elimination as matrix products Advantages of solutions by LU decomposition
Week.5	2.3 and 2.4	Error Analysis for Solution of Ax=b Iterative Methods for Solving Ax=b	Length of vectors eigenvalue and eigenvectors of matrix	various norms for vectors and matrices: compatibility of vector and matrix norms. Error Analysis for the solution of Ax=b Error magnification factor and condition number of matrix Jacobi method, Gauss-Seidel method, Successive-Over-Relaxation (SOR) method Convergence of Jacobi Method, GS method and SOR method. spectral radius of matrix convergence of general iterative method for solving system of linear equations, Sparse Matrix Comparison of Gauss Elimination and iterative methods
Week.6	2.6 and 2.7	Conjugate Gradient Method Nonlinear System of Equations	scalar product of vectors determinant and eigenvalues of matrix quadratic polynomials of n-variables partial derivatives and gradients chain rule for partial derivatives.	Symmetric positive definite matrix and properties Construction of Conjugate Gradient (CG) Method Propertise of CG Method Preconditioning for CG method Taylor's Theorem for multi-variate vector valued functions: Newton's Method: Broyden's Method
Week.7	3.1 and 3.2	Data and Interpolating Functions Interpolation Error and Runge Phenomenon Chebyshev interpolation	Fundamental theorem of algebra Rolle's theorem.	Lagrange Basis Functions: Properties of Lagrange basis functions: Lagrange form of the interpolation polynomials Newton's Divided Differences: Properties of Newton's divided differences: Newton's Form of the interpolation polynomials Interpolation error analysis Runge phenomenon Chebyshev Polynomial Error estimates for Chebyshev interpolation
Week.8	3.4, 3.5 and 4.1	Cubic Splines Bezier Curves Least Square Method	one-sided limits continuity of functions indefinite integrals extremum values of multivariate quadratic functions.	Cubic splines construction of cubic splines for interpolation end conditions properties of cubic spline interpolation Bezier Curve and fonts Least square method for solving inconsistent system of linear equations. Basic properties of least square solutions:
Week.9	4.2 and 4.5	Mathematical Models and Data Fitting Nonlinear Least Square Fitting	linear spaces, basis functions product rule and chain rule for vector valued multivariate functions.	Least square method for curve fitting and statistical modeling. Survey of Models: linear model, periodic model, exponential models, logistic model, etc Taylor's theorem for vector valued multivariate functions. Gauss-Newton Method Levenberg-Marquardt Method
Week.10	5.1, 5.2 and 5.3	Numerical Differentiation Numerical Integration: Newton-Cotes Formulas Numerical Integration: Romberg's Technique	Taylor's theorem interpolation error estimates properties of definite inetgrals	Finite difference (FD) approximations of 1st order derivative and their error analysis FD approximations of 2nd order derivatives and their error analysis Undetermined coefficient method for FD approximation Extropolation technique for improving the order of approximation Midpoint rule, trapezoid rule and Simpson's rule; Error analysis based on Taylor's Theorem and interpolation errors Degree of precision of quadrature rules Composite quadrature rules Motivation, construction and implementation of Romberg's technique.
Week.11	5.4 and 5.5	Adaptive Numerical Integration Gauss Quadrature Formulas	long divisions changing variables for definite integrals	How to estimate the error on a subinterval How to mark subintervals to be further refinement? Implementation of adaptive numerical integration techniques. Motivation and difficulties with straightforward approach. Orthogonal polynomials, Legendre polynomials and their basic properties; Gauss quadrature rule based on Legendre polynomials Degree of precision of Gauss Quadrature Gauss quadrature formula on general interval and composite Gauss rules
Week.12	10.1 and 11.1	Discrete Fourier Transform and FFT Discrete Cosine Transform (optional) Image Compression (optional)	complex numbers and complex variables integration by parts convergence of sequences and series.	Fourier Series, Discrete Fourier Transform Matrix Form of Discrete Fourier Transform: Inverse Discrete Fourier Transform: DFT and Trigonometric interpolation Algorithm for computing DFT: Fast Fourier Transform (FFT) Discrete Cosine Transform (DCT), DCT and Interpolation by Cosine Functions Relation between DFT and DCT: Fourier Transform of 2-Dimensional Functions DCT of 2-Dimensional Functions: Interpolation Theorem for 2-Dimensional DCT Digital Gray scale images and color color images: RGB format: YCbCr (or YUV) format: Convertion between RGB and YUV formats: Quantization, Image Compression and Decompression
Week.13	12.1 and 12.2	Power Iteration Methods QR Algorithm for Computing Eigenvalues	properties of eigen values and eigenvectors Gram-Schmidt orthogonalization	Power iteration and its rate of convergence. Inverse Power Iteration, Inverse Power Iteration with Shift Rayleigh Quotient Iteration Definition and basic properties of orthogonal matrices: QR-Factorization based on Gram-Schmidt Orthogonalization: Normalized Simultaneous Iteration (NSI). Unshifted QR Algorithm: Shifted QR Algorithm:
Week.14	12.2	Algorithm for Computing Eigenvalues: Speed up of QR-algorithm:	matrices for orthogonal projection and reflection block matrices and their products similar matrices.	Upper Hessenberg form (UHF) Householder Reflector Convert a matrix into UHF by Householder reflectors