大型矩陣計算
Large Sparse Matrix Computations
學期
107-1
學分
3
學分
當期課號
5375
永久課號
IAM6507
開課單位
應用數學系
授課教師
林文偉
校區
光復
類別
選修
上課時間表
| 節 | 週三 | 週四 |
|---|---|---|
5 13:20–14:10 | 大型矩陣計算 SA223 2 節連堂 | 大型矩陣計算 SA223 |
6 14:20–15:10 |
* 根據陽明交大上課時間表所列
概述
1. Numerical methods for solving linear systems 2. Orthogonalization and least squares methods 3. Iterative methods for solving large linear systems 4. The unsymmetric eigenvalue problems 5. The symmetric eigenvalue problems 6. Lanczos method 7. Arnoldi method 8. Jacobi-Davidson method
先修科目
Calculus, Linear Algebra, Introduction to Computers and Programming, Numerical Analysis
評分方式
作業 60%、期末報告30%、出席10%
課程大綱
- Numerical Methods for Solving Linear Systems
- Orthogonalization and Least Squares Methods
- Iterative Methods for Solving Large Linear Systems
- The Unsymmetric Eigenvalue Problem
- The Symmetric Eigenvalue problem
- Lanczos Methods
- Arnoldi Method
- Jacobi-Davidson Method
- Introduction
週次計畫
| 週次 | 主題 |
|---|---|
| 第 1 週 | Chapter 1 Introduction 1.2 Norms and eigenvalues 1.3 The Sensitivity of Linear System Ax = b |
| 第 2 週 | Chapter 2 Numerical Methods for Solving Linear Systems 2.3 Gaussian elimination 2.3.1 Practical implementation 2.3.2 LDR- and LLT -factorizations 2.3.3 Error estimation for linear systems 2.3.4 Error analysis for Gaussian algorithm 2.3.5 Apriori error estimate for backward error bound of LR-factorization 2.3.6 Improving and Estimating Accuracy |
| 第 4 週 | Chapter 3 Orthogonalization and Least Squares Methods 3.1 QR-factorization (QR-decomposition) 3.1.1 Householder transformation 3.1.2 Gram-Schmidt method 3.1.3 Givens method 3.2 Overdetermined linear Systems - Least Squares Methods 3.2.1 Rank Deficiency I : QR with column pivoting 3.2.2 Rank Deficiency II : The Singular Value Decomposition 3.2.3 The Sensitivity of the Least Squares Problem 3.2.4 Condition number of a Rectangular Matrix 3.2.5 Iterative Improvement |
| 第 6 週 | Chapter 4 Iterative Methods for Solving Large Linear Systems 4.1 General procedures for the construction of iterative methods 4.1.1 Some theorems and definitions 4.1.2 The theorems of Stein-Rosenberg 4.1.3 Sufficient conditions for convergence of TSM and SSM 4.2 Relaxation Methods (Successive Over-Relaxation (SOR) Method ) 4.2.1 Determination of the Optimal Parameter for 2-consistly Ordered Matrices 4.2.2 Practical Determination of Relaxation Parameter 4.2.3 Break-off Criterion for SOR Method 4.6 Derivation and Properties of the Conjugate Gradient Method 4.6.1 A Variational Problem, Steepest Descent Method (Gradient Method) 4.6.2 Conjugate gradient method 4.6.3 Practical Implementation 4.6.4 Convergence of CG-method 4.7 CG-method as an iterative method, preconditioning 4.14 GMRES: Generalized Minimal Residual Algorithm for solving Nonsymmetric Linear Systems 4.14.1 FOM algorithm: Full orthogonalization method 4.14.2 The generalized minimal residual (GMRES) algorithm 4.14.3 Practical Implementation: Consider QR factorization of Hk 4.14.4 Theoretical Aspect of GMRES |
| 第 9 週 | 5.1 Orthogonal Projections and C-S Decomposition 5.2 Perturbation Theory 5.3 Power Iterations 5.3.1 Power Method 5.3.2 Inverse Power Iteration 5.3.3 Connection with Newton-method 5.3.4 Orthogonal Iteration 5.4 QR-algorithm (QR-method, QR-iteration) 5.4.1 The Practical QR Algorithm 5.4.2 Single-shift QR-iteration 5.4.3 Double Shift QR iteration 5.4.4 Ordering Eigenvalues in the Real Schur From 5.5 LR, LRC and QR algorithms for positive definite matrices 5.6 qd-algorithm (Quotient Difference) 5.6.1 The qd-algorithm for positive definite matrix |
| 第 11 週 | Chapter 6 The Symmetric Eigenvalue problem |
| 第 12 週 | 7.1 The Lanczos Algorithm 7.1.1 Reorthogonalization 7.1.2 Filter polynomials 7.1.3 Implicitly restarted algorithm 7.2 Approximation from a subspace 7.2.1 A priori bounds for interior Ritz approximations 7.3 Krylov subspace 7.3.1 The Error Bound of Kaniel and Saad 7.4 Applications to linear Systems and Least Squares 7.4.1 Symmetric Positive Definite System 7.4.2 Symmetric Indefinite Systems 7.4.3 Connection of Algorithm 7.4.1 and CG method 7.4.4 Bidiagonalization and the SVD 7.4.5 Least square problems 7.4.6 Error Estimation of least square problems 7.4.7 Perturbation of solutions of the least square problems 7.5 Unsymmetric Lanczos Method |
| 第 15 週 | Chapter 8 Arnoldi Method |
| 第 17 週 | 9.1 JOCC(Jacobi Orthogonal Component Correction) 9.2 Davidson method 9.3 Jacobi Davidson method 9.3.1 Jacobi Davidson method as on accelerated Newton Scheme 9.3.2 Jacobi-Davidson with harmonic Ritz values 9.4 Jacobi-Davidson Type method for Generalized Eigenproblems 9.4.1 The updating process for approximate eigenvector 9.4.2 Other projections for the eigenvector approximations 9.4.3 Equivalent formulations for the correction equation |
教科書
Textbook: Lecture Notes of Matrix Computations, edited by Wen-Wei Lin. (http://jupiter.math.nctu.edu.tw/~wwlin/2010_lecture_note.pdf) References: (1) Scientific Computing: An Introductory Survey, Michael T. Heath, 2nd edition (2) Scientific Computing with Case Studies, Dianne P. O'Leary
Office Hours
- 地點
- SA316