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	Topics	Prerequisite Skills	Student Learning Outcomes
Week 1	Section 0.2: Loss of significant digits	Loss of Significant Digits Nested Multiplication	Binary Number System Taylor's Theorem	Nested Multiplication for Evaluating Polynomials Machine Representation of Real Numbers Loss of Significant Digits in Numerical Computing Review of Taylor's Theorem
Week 1	Section 1.1: Fixed-Point Iteration	Bisection Method	Intermediate Value Theorem	Bisection Method and Implementation Brief Introduction to Matlab
Week 2	Section 1.2: Fixed-Point Iteration	Fixed-Point Iteration Order of Convergence of Iterative Methods	Limit of Sequences Solution Multiplicity of Equations	Geometric Interpretation of Fixed-Point Iteration Convergence of Fixed Point Iterations Order of Convergence of Iterative Methods
Week 2	Section 1.3: Limits of Accuracy: Conditioning of Problems	Wilkinson Polynomial	Limit of Sequences Solution Multiplicity of Equations	Sensitivity Analysis of Root-Finding Error Magnification Factor for Solution of Equations
Week 3	Section 1.4: Newton's Method	Newton's Method Error Analysis for Newton's Method Modified Newton's Method Root-Finding Without Derivatives Secant Method and its Convergence Method of False Position, Muller's Method Stopping Criteria for Iterative Methods	Remainder of Taylor's Series Intermediate Value Theorem Fixed-Point Iteration	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
Week 3	Section 1.5 Root-Finding Without Derivatives	Secant Method Method of False Position Muller's Method Stopping Criteria	Remainder of Taylor's Series Intermediate Value Theorem	Secant Method and its Convergence Stopping Criteria for Iterative Methods
Week 4	Section 2.1 Solve Systems of Linear Equations: Gaussian Elimination	Gaussian Elimination	Elementary Row Operations	Gaussian Elimination and its Operation Counts Gaussian Elimination with Pivoting Implementation of Gauss Elimination
Week 4	Section 2.2 Solve Systems of Linear Equations: LU Decomposition	LU Decomposition	Matrix-Matrix Products Matrix-Vector Products Inverse Matrix Elementary Row Operations	Matrices for Elementary Row Operations Gauss Elimination as Matrix Products Advantages of Solutions by LU Decomposition
Week 5	Section 2.3 Error Analysis for Solution of Ax=b	Norms Error Analysis for Solution of Ax=b Error Magnification Factor and Condition Number of Matrix	Length of Vectors Eigenvalues of a Matrix Eigenvectors of a Matrix	Various Norms for Vectors and Matrices: Compatibility of Vector and Matrix Norms Error Analysis for Solution of Ax=b Error Magnification Factor and Condition Number of Matrix
Week 5	Section 2.5: Iterative Methods for Solving Ax=b	Iterative Methods Jacobi Method Gauss-Seidel Method Successive-Over-Relaxation (SOR) Method Convergence of Iterative Methods Spectral Radius of Matrix Sparse Matrix	Length of Vectors Eigenvalues of a Matrix Eigenvectors of a Matrix	Convergence of General Iterative Method for Solving System of Linear Equations Comparison of Gauss Elimination and Iterative Methods
Week 6	Section 2.6: Conjugate Gradient (CG) Method	Conjugate Gradient Method Symmetric Positive Definite Matrix CG Method	Scalar Product of Vectors Determinant of a Matrix Eigenvalues of a Matrix Quadratic Polynomials of n-variables Partial Derivatives Gradients Chain Rule for Partial Derivatives	Symmetric Positive Definite Matrix and Properties Construction of Conjugate Gradient (CG) Method Properties of CG Method Preconditioning for CG Method
Week 6	Section 2.7: Nonlinear System of Equations	Nonlinear System of Equations Taylor's Theorem for Multi-Variate Vector Valued Functions Newton's Method Broyden's Method	Scalar Product of Vectors Determinant of a Matrix Eigenvalues of a Matrix Quadratic Polynomials of n-variables Partial Derivatives Gradients Chain Rule for Partial Derivatives	(TBD)
Week 7	Sections 3.1: Data and Interpolating Functions	Lagrange Basis Functions Newton's Divided Differences Properties of Newton's Divided Differences	Fundamental Theorem of Algebra Rolle's Theorem	Properties of Lagrange Basis Functions Lagrange Form of the Interpolation Polynomials Properties of Newton's Divided Differences Newton's Form of the Interpolation Polynomials
Week 7	Section 3.2: Interpolation Error and Runge Phenomenon	Interpolation Error Interpolation Error Analysis Runge Phenomenon Chebyshev Polynomial Error Estimates for Chebyshev Interpolation	Fundamental Theorem of Algebra Rolle's Theorem	(TBD)
Week 8	Section 3.4: Cubic Splines	Cubic Splines	One-Sided Limits Continuity of Functions Indefinite Integrals Extremum Values of Multivariate Quadratic Functions	Construction of Cubic Splines for Interpolation End Conditions Properties of Cubic Spline Interpolation
Week 8	Section 3.5: Bezier Curves	Bezier Curves	One-Sided Limits Continuity of Functions Indefinite Integrals Extremum Values of Multivariate Quadratic Functions	Bezier Curve and Fonts
Week 8	Section 4.1: Least Square Method	Least Square Method	One-Sided Limits Continuity of Functions Indefinite Integrals Extremum Values of Multivariate Quadratic Functions	Least Square Method for Solving Inconsistent System of Linear Equations] Basic Properties of Least Square Solutions
Week 9	Section 4.2: Mathematical Models and Data Fitting	Curve Fitting Statistical Modeling	Linear Spaces Basis Functions Product Rule for Vector Valued Multivariate Functions 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
Week 9	Section 4.5: Nonlinear Least Square Fitting	Taylor's Theorem for Vector Valued Multivariate Functions Gauss-Newton Method Levenberg-Marquardt Method	Linear Spaces Basis Functions Product Rule for Vector Valued Multivariate Functions Chain Rule for Vector Valued Multivariate Functions	(TBD)
Week 10	Section 5.1: Numerical Differentiation	Numerical Differentiation Finite Difference (FD) Undetermined Coefficient Method Extrapolation Technique	Taylor's Theorem Interpolation Error Estimates Properties of Definite Integrals	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 Extrapolation Technique for Improving the Order of Approximation
Week 10	Section 5.2: Numerical Integration: Newton-Cotes Formulas	Newton-Cotes Midpoint rule Trapezoid rule Simpson's rule Error Analysis based on Interpolation Errors Quadrature Rules Composite Quadrature Rules	Taylor's Theorem Interpolation Error Estimates Properties of Definite Integrals	Error Analysis based on Taylor's Theorem Error Analysis based on Interpolation Errors Degree of Precision of Quadrature Rules
Week 10	Section 5.3: Numerical Integration: Romberg's Technique	Romberg's Technique	Taylor's Theorem Interpolation Error Estimates Properties of Definite Integrals	Motivation, construction and implementation of Romberg's Technique.
Week 11	Section 5.4: Adaptive Numerical Integration	Adaptive Numerical Integration Implementation of Adaptive Numerical Integration Techniques	Long Divisions Substitution Methods for definite integrals	How to estimate the error on a sub interval How to mark sub intervals to be further refinement?
Week 11	Section 5.5: Gauss Quadrature Formulas	Gauss Quadrature Formulas Orthogonal Polynomials Legendre polynomials Gauss Quadrature Rule	Long Divisions Substitution Methods for definite integrals	Motivation and difficulties with straightforward approach 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	Section 10.1: Discrete Fourier Transform and Fast Fourier Transform (FTT)	Fourier Series Discrete Fourier Transform (DFT) Inverse Discrete Fourier Transform Fast Fourier Transform (FFT)	Complex Numbers Complex Variables Integration by Parts Convergence of Sequences Convergence of Series	Matrix Form of Discrete Fourier Transform DFT and Trigonometric Interpolation
Week 12	Section 11.1: Discrete Cosine Transform (optional)	Discrete Cosine Transform Discrete Cosine Transform(DCT)	Complex Numbers Complex Variables Integration by Parts Convergence of Sequences Convergence of Series	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
Week 12	Section 11.2: Image Compression (optional)	Quantization Image Compression Image Decompression	Complex Numbers Complex Variables Integration by Parts Convergence of Sequences Convergence of Series	Digital Gray scale images and color color images RGB format YCbCr (or YUV) format Convertion between RGB and YUV formats
Week 13	Section 12.1: Power Iteration Methods	Power Iteration Methods Inverse Power Iteration Inverse Power Iteration with Shift Rayleigh Quotient Iteration	Eigenvalues Eigenvectors Orthonormal Bases and the Gram-Schmidt Process	Convergence of Power Iteration Methods
Week 13	Section 12.2: QR Algorithm for Computing Eigenvalues	Orthogonal Matrices QR-Factorization Normalized Simultaneous Iteration(NSI) Unshifted QR Algorithm Shifted QR Algorithm	Eigenvalues Eigenvectors Orthonormal Bases and the Gram-Schmidt Process	Definition and basic properties of orthogonal matrices QR-Factorization based on Gram-Schmidt Orthogonalization
Week 14	Section 12.2: QR Algorithm for Computing Eigenvalues	Upper Hessenberg Form (UHF) Householder Reflector	Matrices for Orthogonal Projection Matrices for Reflection Block Matrices Similar Matrices	Convert a matrix into UHF by Householder reflectors