Difference between revisions of "MAT3633"

From Department of Mathematics at UTSA
Jump to navigation Jump to search
Line 10: Line 10:
 
|Week 1
 
|Week 1
 
||
 
||
Section 0.2 & 1.1
+
Section 0.2: Loss of significant digits
 
||
 
||
 
* [[Loss of Significant Digits]]
 
* [[Loss of Significant Digits]]
* [[Nested Multiplication for Evaluating Polynomials]]
+
* [[Nested Multiplication]]
* [[Machine Representation of Real Numbers]]
 
* [[Loss of Significant Digits in Numerical Computing]]
 
* [[Review of Taylor's Theorem]]
 
 
 
* [[Bisection Method]]
 
* [[Bisection Method and Implementation]]
 
* [[Brief Introduction to Matlab]]
 
 
||
 
||
 
* [[Binary Number System]]
 
* [[Binary Number System]]
 
* [[Taylor's Theorem]]
 
* [[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]]
 
* [[Intermediate Value Theorem]]
 
||
 
||
* (To be Entered)
+
* Bisection Method and Implementation
 +
* Brief Introduction to Matlab
 
|-
 
|-
 
|Week 2
 
|Week 2
 
||
 
||
Sections 1.2 & 1.3
+
Section 1.2: Fixed-Point Iteration
 
||
 
||
 
* [[Fixed-Point Iteration]]
 
* [[Fixed-Point Iteration]]
* [[Geometric Interpretation]]
+
* [[Order of Convergence]] of Iterative Methods
* [[Convergence of Fixed Point Iterations]]
+
||
* [[Order of Convergence of Iterative Methods]]
+
* [[Limit of Sequences]]
 
+
* [[Solution Multiplicity of Equations]]
* [[Limits of Accuracy: Conditioning of Problems]]
+
||
 +
* 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]]
 
* [[Wilkinson Polynomial]]
* [[Sensitivity Analysis of Root-Finding]]
 
* [[Error Magnification Factor for Solution of Equations]]
 
 
||
 
||
 
* [[Limit of Sequences]]
 
* [[Limit of Sequences]]
 
* [[Solution Multiplicity of Equations]]
 
* [[Solution Multiplicity of Equations]]
 
||
 
||
* (TBD)
+
* Sensitivity Analysis of Root-Finding
 +
* Error Magnification Factor for Solution of Equations
 
|-
 
|-
 
|Week 3
 
|Week 3
 
||
 
||
Sections 1.4 & 1.5
+
Section 1.4: Newton's Method
 
||
 
||
 
* [[Newton's Method]]
 
* [[Newton's Method]]
* [[Algebraic and Geometric Interpretation of Newton's method]]
+
* [[Error Analysis]] for Newton's Method
* [[Error Analysis for Newton's Method Based on Taylor's Theorem]]
+
* [[Modified Newton's Method]]
* [[Newton's Method as a Fixed Point Iteration]]
 
* [[Modified Newton's Method and its Rate of Convergence]]
 
  
 
* [[Root-Finding Without Derivatives]]
 
* [[Root-Finding Without Derivatives]]
Line 64: Line 75:
 
* [[Remainder of Taylor's Series]]
 
* [[Remainder of Taylor's Series]]
 
* [[Intermediate Value Theorem]]
 
* [[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]]
 
||
 
||
* (TBD)
+
* Gaussian Elimination and its Operation Counts
 +
* Gaussian Elimination with Pivoting
 +
* Implementation of Gauss Elimination
 
|-
 
|-
 
|Week 4
 
|Week 4
 
||
 
||
Sections 2.1 & 2.2
+
Section 2.2 Solve Systems of Linear Equations: LU Decomposition
 
||
 
||
* [[Solve Systems of Linear Equations: Gaussian Elimination]]
+
* [[LU Decomposition]]
* [[Gaussian Elimination and its Operation Counts]]
 
* [[Gaussian Elimination with Pivoting]]
 
* [[Implementation of Gauss Elimination]]
 
 
 
* [[Solve System of Linear Equations: LU Decomposition]]
 
* [[Matrices for Elementary Row Operations]]
 
* [[Gauss Elimination as Matrix Products]]
 
* [[Advantages of Solutions by LU Decomposition]]
 
 
||
 
||
 
* [[Matrix-Matrix Products]]
 
* [[Matrix-Matrix Products]]
Line 86: Line 120:
 
* [[Elementary Row Operations]]
 
* [[Elementary Row Operations]]
 
||
 
||
* (TBD)
+
* 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
 
|Week 5
 
||
 
||
Sections 2.3 & 2.5
+
Section 2.5: Iterative Methods for Solving Ax=b
 
||
 
||
* [[Error Analysis for Solution of Ax=b]]
+
* [[Iterative Methods]]
* [[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]]
 
 
 
* [[Iterative Methods for Solving Ax=b]]
 
 
* [[Jacobi Method]]
 
* [[Jacobi Method]]
 
* [[Gauss-Seidel Method]]
 
* [[Gauss-Seidel Method]]
Line 103: Line 150:
 
* [[Convergence of Iterative Methods]]
 
* [[Convergence of Iterative Methods]]
 
* [[Spectral Radius of Matrix]]
 
* [[Spectral Radius of Matrix]]
* [[Convergence of General Iterative Method for Solving System of Linear Equations]]
 
 
* [[Sparse Matrix]]
 
* [[Sparse Matrix]]
* [[Comparison of Gauss Elimination and Iterative Methods]]
 
 
||
 
||
 
* [[Length of Vectors]]
 
* [[Length of Vectors]]
Line 111: Line 156:
 
* [[Eigenvectors of a Matrix]]
 
* [[Eigenvectors of a Matrix]]
 
||
 
||
* (TBD)
+
* Convergence of General Iterative Method for Solving System of Linear Equations
 +
* Comparison of Gauss Elimination and Iterative Methods
 
|-
 
|-
 
|Week 6
 
|Week 6
 
||
 
||
Sections 2.6 & 2.7
+
Section 2.6: Conjugate Gradient (CG) Method
 
||
 
||
 
* [[Conjugate Gradient Method]]
 
* [[Conjugate Gradient Method]]
* [[Symmetric Positive Definite Matrix and Properties]]
+
* [[Symmetric Positive Definite Matrix]]
* [[Construction of Conjugate Gradient (CG) Method]]
+
* [[CG Method]]
* [[Properties of CG Method]]
+
||
* [[Preconditioning for 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]]
 
* [[Nonlinear System of Equations]]
 
* [[Taylor's Theorem for Multi-Variate Vector Valued Functions]]
 
* [[Taylor's Theorem for Multi-Variate Vector Valued Functions]]
Line 140: Line 201:
 
|Week 7
 
|Week 7
 
||
 
||
Sections 3.1 & 3.2
+
Sections 3.1: Data and Interpolating Functions
 
||
 
||
* [[Data and Interpolating Functions]]
 
 
* [[Lagrange Basis Functions]]
 
* [[Lagrange Basis Functions]]
* [[Properties of Lagrange Basis Functions]]
 
* [[Lagrange Form of the Interpolation Polynomials]]
 
 
* [[Newton's Divided Differences]]
 
* [[Newton's Divided Differences]]
 
* [[Properties of Newton's Divided Differences]]
 
* [[Properties of Newton's Divided Differences]]
* [[Newton's Form of the Interpolation Polynomials]]
+
||
 
+
* [[Fundamental Theorem of Algebra]]
* [[Interpolation Error and Runge Phenomenon]]
+
* [[Rolle's Theorem]]
* [[Interpolation Error Analysis]]
+
||
 +
* 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]]
 
* [[Runge Phenomenon]]
 
* [[Chebyshev Polynomial]]
 
* [[Chebyshev Polynomial]]
* [[Error Estimates for Chebyshev Interpolation]]
+
* [[Error Estimates]] for Chebyshev Interpolation
 
||
 
||
 
* [[Fundamental Theorem of Algebra]]
 
* [[Fundamental Theorem of Algebra]]
Line 163: Line 232:
 
|Week 8
 
|Week 8
 
||
 
||
Sections 3.4, 3.5, & 4.1
+
Section 3.4: Cubic Splines
 
||
 
||
 
* [[Cubic Splines]]
 
* [[Cubic Splines]]
* [[Cubic Splines]]
+
||
* [[Construction of Cubic Splines for Interpolation]]
+
* [[One-Sided Limits]]
* [[End Conditions]]
+
* [[Continuity of Functions]]
* [[Properties of Cubic Spline Interpolation]]
+
* [[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]]
 
* [[Bezier Curves]]
* [[Bezier Curve and Fonts]]
+
||
 
+
* [[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]]
 
* [[Least Square Method]]
* [[Least Square Method for Solving Inconsistent System of Linear Equations]]
 
* [[Basic Properties of Least Square Solutions]]
 
 
||
 
||
 
* [[One-Sided Limits]]
 
* [[One-Sided Limits]]
Line 183: Line 269:
 
* [[Extremum Values of Multivariate Quadratic Functions]]
 
* [[Extremum Values of Multivariate Quadratic Functions]]
 
||
 
||
* (TBD)
+
* 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
 
|Week 9
 
||
 
||
Sections 4.2 & 4.5
+
Section 4.5: Nonlinear Least Square Fitting
 
||
 
||
* [[Mathematical Models and Data Fitting]]
 
* [[Least square method for curve fitting and statistical modeling]]
 
* [[Survey of Models]]: linear model, periodic model, exponential models, logistic model, etc
 
 
* [[Nonlinear Least Square Fitting]]
 
 
* [[Taylor's Theorem for Vector Valued Multivariate Functions]]
 
* [[Taylor's Theorem for Vector Valued Multivariate Functions]]
 
* [[Gauss-Newton Method]]
 
* [[Gauss-Newton Method]]
Line 207: Line 304:
 
|Week 10
 
|Week 10
 
||
 
||
Sections 5.1, 5.2, & 5.3
+
Section 5.1: Numerical Differentiation
 
||
 
||
 
* [[Numerical Differentiation]]
 
* [[Numerical Differentiation]]
* [[Finite difference (FD) Approximations of 1st order Derivative and Their Error Analysis]]
+
* [[Finite Difference]] (FD)
* [[FD approximations of 2nd order Derivatives and Their Error Analysis]]
+
* [[Undetermined Coefficient Method]]
* [[Undetermined Coefficient Method for FD Approximation]]
+
* [[Extrapolation Technique]]
* [[Extrapolation Technique for Improving the Order of Approximation]]
+
||
 
+
* [[Taylor's Theorem]]
* Numerical Integration: [[Newton-Cotes Formulas]]
+
* [[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]]
 
* [[Midpoint rule]]
 
* [[Trapezoid rule]]
 
* [[Trapezoid rule]]
 
* [[Simpson's rule]]
 
* [[Simpson's rule]]
* [[Error Analysis based on Taylor's Theorem]]
 
 
* [[Error Analysis based on Interpolation Errors]]
 
* [[Error Analysis based on Interpolation Errors]]
* [[Degree of Precision of Quadrature Rules]]
+
* [[Quadrature Rules]]
 
* [[Composite Quadrature Rules]]
 
* [[Composite Quadrature Rules]]
 
* Numerical Integration: [[Romberg's Technique]]
 
* Motivation, construction and implementation of [[Romberg's Technique]].
 
 
||
 
||
 
* [[Taylor's Theorem]]
 
* [[Taylor's Theorem]]
Line 231: Line 336:
 
* [[Properties of Definite Integrals]]
 
* [[Properties of Definite Integrals]]
 
||
 
||
* (TBD)
+
* 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
 
|Week 11
 
||
 
||
Sections 5.4 & 5.5
+
Section 5.4: Adaptive Numerical Integration
 
||
 
||
 
* [[Adaptive Numerical Integration]]
 
* [[Adaptive Numerical Integration]]
 
* [[Implementation of Adaptive Numerical Integration Techniques]]
 
* [[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]]
 
* [[Gauss Quadrature Formulas]]
 
* [[Orthogonal Polynomials]]
 
* [[Orthogonal Polynomials]]
Line 248: Line 377:
 
* [[Substitution Methods]] for definite integrals
 
* [[Substitution Methods]] for definite integrals
 
||
 
||
* How to estimate the error on a sub interval
 
* How to mark sub intervals to be further refinement?
 
 
 
* Motivation and difficulties with straightforward approach
 
* Motivation and difficulties with straightforward approach
 
* Legendre polynomials and their basic properties
 
* Legendre polynomials and their basic properties
Line 259: Line 385:
 
|Week 12
 
|Week 12
 
||
 
||
Sections 10.1, 11.1, & 11.2
+
Section 10.1: Discrete Fourier Transform and Fast Fourier Transform (FTT)
 
||
 
||
* [[Discrete Fourier Transform and Fast Fourier Transform (FTT)]]
 
 
* [[Fourier Series]]
 
* [[Fourier Series]]
 
* [[Discrete Fourier Transform]] (DFT)
 
* [[Discrete Fourier Transform]] (DFT)
* [[Matrix Form of Discrete Fourier Transform]]
 
 
* [[Inverse Discrete Fourier Transform]]
 
* [[Inverse Discrete Fourier Transform]]
* [[DFT and Trigonometric Interpolation]]
 
 
* [[Fast Fourier Transform (FFT)]]
 
* [[Fast Fourier Transform (FFT)]]
 
+
||
* [[Discrete Cosine Transform]](optional)
+
* [[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)
 
* [[Discrete Cosine Transform]](DCT)
 
* [[Image Compression]](optional)
 
* [[Quantization]]
 
* [[Image Compression]]
 
* [[Image Decompression]]
 
 
||
 
||
 
* [[Complex Numbers]]
 
* [[Complex Numbers]]
Line 288: Line 419:
 
* DCT of 2-Dimensional Functions
 
* DCT of 2-Dimensional Functions
 
* Interpolation Theorem for 2-Dimensional DCT
 
* Interpolation Theorem for 2-Dimensional DCT
 
+
|-
 +
|Week 12
 +
||
 +
Section 11.2: Image Compression (optional)
 +
||
 +
* [[Image Compression]
 +
* [[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
 
* Digital Gray scale images and color color images
 
* RGB format
 
* RGB format
Line 296: Line 442:
 
|Week 13
 
|Week 13
 
||
 
||
Sections 12.1 & 12.2
+
Section 12.1: Power Iteration Methods
 
||
 
||
 
* [[Power Iteration Methods]]
 
* [[Power Iteration Methods]]
* [[Power Iteration Methods]]
 
* [[Convergence of Power Iteration Methods]]
 
 
* [[Inverse Power Iteration]]
 
* [[Inverse Power Iteration]]
 
* [[Inverse Power Iteration with Shift]]
 
* [[Inverse Power Iteration with Shift]]
 
* [[Rayleigh Quotient Iteration]]
 
* [[Rayleigh Quotient Iteration]]
 
+
||
* [[QR Algorithm for Computing Eigenvalues]]
+
* [[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]]
 
* [[Orthogonal Matrices]]
 
* [[QR-Factorization]]
 
* [[QR-Factorization]]
Line 321: Line 474:
 
|Week 14
 
|Week 14
 
||
 
||
Sections 12.2
+
Section 12.2: QR Algorithm for Computing Eigenvalues
 
||
 
||
* [[QR Algorithm for Computing Eigenvalues]]
 
 
* [[Upper Hessenberg Form]] (UHF)
 
* [[Upper Hessenberg Form]] (UHF)
 
* [[Householder Reflector]]
 
* [[Householder Reflector]]

Revision as of 07:28, 3 August 2020

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

  • 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 and Implementation
  • Brief Introduction to Matlab
Week 2

Section 1.2: Fixed-Point Iteration

  • 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

  • Sensitivity Analysis of Root-Finding
  • Error Magnification Factor for Solution of Equations
Week 3

Section 1.4: Newton's Method

  • 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 and its Convergence
  • Stopping Criteria for Iterative Methods
Week 4

Section 2.1 Solve Systems of Linear Equations: Gaussian Elimination

  • 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

  • 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

  • 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

  • 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

  • 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

  • (TBD)
Week 7

Sections 3.1: Data and Interpolating Functions

  • 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

  • (TBD)
Week 8

Section 3.4: Cubic Splines

  • Construction of Cubic Splines for Interpolation
  • End Conditions
  • Properties of Cubic Spline Interpolation
Week 8

Section 3.5: Bezier Curves

  • Bezier Curve and Fonts
Week 8

Section 4.1: Least Square Method

  • 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

  • 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

  • (TBD)
Week 10

Section 5.1: Numerical Differentiation

  • 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

  • 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

  • Motivation, construction and implementation of Romberg's Technique.
Week 11

Section 5.4: Adaptive Numerical Integration

  • 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

  • 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)

  • Matrix Form of Discrete Fourier Transform
  • DFT and Trigonometric Interpolation
Week 12

Section 11.1: Discrete Cosine Transform (optional)

  • 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)

  • 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

  • Convergence of Power Iteration Methods
Week 13

Section 12.2: QR Algorithm for Computing Eigenvalues

  • Definition and basic properties of orthogonal matrices
  • QR-Factorization based on Gram-Schmidt Orthogonalization
Week 14

Section 12.2: QR Algorithm for Computing Eigenvalues

  • Convert a matrix into UHF by Householder reflectors