MAT3633

From Department of Mathematics at UTSA
Revision as of 14:34, 17 August 2020 by Weiming.cao (talk | contribs)
Jump to navigation Jump to search

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

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