# 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.
• 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

• Nonlinear System of Equations
• scalar product of vectors
• determinant and eigenvalues of matrix
• 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
• Motivation, construction and implementation of Romberg's technique.

Week.11

5.4 and 5.5

• 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