In a recent conversation, I realized that I had forgotten to post some of numerical linear algebra (NLA) projects that I had created in graduate school. These projects, along with a few others that I have already published in this blog, can help us appreciate the theories and applications of NLA.
Let’s look at one more way to solve the equation . We assume that is nonsingular, and define the -th Krylov subspace as follows:
Krylov subspace methods are efficient and popular iterative methods for solving large, sparse linear systems. When is symmetric, positive definite (SPD), i.e.
we can use a Krylov subspace method called Conjugate Gradient (CG).
Today, let’s find out how CG works and use it to solve 2D Poisson’s equation.
Last time, we looked at 2D Poisson’s equation and discussed how to arrive at a matrix equation using the finite difference method. The matrix, which represents the discrete Laplace operator, is sparse, so we can use an iterative method to solve the equation efficiently.
Today, we will look at Jacobi, Gauss-Seidel, Successive Over-Relaxation (SOR), and Symmetric SOR (SSOR), and a couple of related techniques—red-black ordering and Chebyshev acceleration. In addition, we will analyze the convergence of each method for the Poisson’s equation, both analytically and numerically.
Once again, we consider solving the equation , where is nonsingular. When we use a factorization method for dense matrices, such as LU, Cholesky, SVD, and QR, we make operations and store matrix entries. As a result, it’s hard to accurately model a real-life problem by adding more variables.
Luckily, when the matrix is sparse (e.g. because we used finite difference method or finite element method), we can use an iterative method to approximate the solution efficiently. Typically, an iterative method incurs operations, if not fewer, and requires storage.
Over the next few posts, we will look at 5 iterative methods:
- Successive Over-Relaxation (SOR)
- Symmetric SOR (SSOR)
- Conjugate Gradient (CG).
In addition, we will solve 2D Poisson’s equation using these methods. We will compare the approximate solutions to the exact to illustrate the accuracy of each method.
In numerical linear algebra, we create ways for a computer to solve a linear system of equations . In doing so, we analyze how efficiently and accurately we can find the solution .
Perturbation theory concerns how much error we incur in the solution when we perturb (spoil) the data and . A classic statement tells us that the amount of error depends on the condition number of the matrix .
I will define and prove the statement, and help you understand it by “hearing” it.