Comprehensive Overview of Numerical Linear Algebra Methods for Solving Linear Systems
Explore numerical linear algebra techniques for solving linear systems of equations, including direct and iterative methods. Delve into topics like Gaussian elimination, LU factorization, band solvers, sparse solvers, iterative techniques, and more. Gain insights into basic iterative methods, error correction, optimization-based directional searching methods, and preconditioning. Discover the applications of matrix factorizations in data analysis, eigenvalue/singular value computation, and enhance your understanding of solving linear systems efficiently.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Numerical Linear Algebra Mo Mu March 15,6:30-9:20
Linear Algebra Problems Solving Linear System Equations A u = b Matrix Factorizations with Applications in Data Analysis, Eigenvalue/Singular Value Computation,etc
Solving Linear System Equations Direct Methods Gaussian elimination, pivoting, LU factorization Band solvers Sparse solvers Minimum fill-in Nested disection Multi-frontal Iterative Methods
Solving Linear System Equations Iterative Methods Basic iterative methods Simple (one step) linear iterative methods Optimization based directional searching methods Advanced iterative techniques Preconditioning Polynomial acceleration Multigrid Domain decomposition Subspace decomposition Others: MinRes, GMRes, etc.
Basic Linear Iterative Methods Simple (one step) linear iterative methods (Linear fixed point iteration with the fixed point being the solution of the original linear system) un+1 = g(un) = Gun+ k Residual correction (RF method, with G = I-A) rn= b Aun un+1 = un+ rn = (I - A) un + b Matrix splitting for fixed point, with A = Q-N, or A = D L U specifically, which leads to Jacobi method: D u = (L+U) u = b, where Q = D Gauss-Seidel method: (D-L)u = U u + b, where Q = D-L SOR method, extrapolation with Gauss-Seidel Error correction, Improved RF, or Preconditioning
Basic Linear Iterative Methods, continued Error correction, Improved RF Compute rn= b Aun; Solve error equation approximately Aen= rn,or compute en=A-1rn, by e = Brn, with B being an approximation to A-1, called a preconditioner, and easily computable for Brn Error correction un+1 = un+ e Preconditioning un+1= un +B rn = (I - BA) un + Bb, G = I B A = I Q-1A (in D. Young, where Q is called a splitting matrix, with A = Q-N) in the linear fixed point iteration; This may be viewed as by applying B = Q-1 to the original system (preconditioning), then do RF
Directional Searching Methods Optimization Directional searching Steepest descent method Conjugate gradient method A BRIEF INTRODUCTION TO THE CONJUGATE GRADIENT METHOD
Linear Iteration and Preconditioners (J. Xu) Proposition 2.2 (J. XU) A symmetric iterative scheme gives rise to a preconditioner B for PCG, and the rate of the convergence of the iterative scheme may be accelerated by using PCG Proposition 2.3 (J. XU) Any preconditioner can also be used to construct a linear iterative scheme by the extrapolated preconditioned RF, with the optimal choice of the parameter: un+1= un + B rn
