digesting hard math since 2016
Let’s look at one more way to solve the equation 
Krylov subspace methods are efficient and popular iterative methods for solving large, sparse linear systems. When 
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.
Continue reading “Iterative Methods: Part 3”
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 
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 
Over the next few posts, we will look at 5 iterative methods:
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 
Perturbation theory concerns how much error we incur in the solution 
I will define and prove the statement, and help you understand it by “hearing” it.
Buffon’s needle is a classic Monte Carlo simulation that we can conduct in a classroom. We give the students, say 10 needles each, and have them drop the needles on a paper that we provide also. The paper is special, in that it has parallel lines that are separated by the length of a needle. Each student records how many needles intersect one of the lines, then we tally their numbers to arrive at a very special number. (Guess who?)
In a class of 30, we have 300 samples to determine this special number. If the students had repeated the experiment ten times (any more than this risks frustration and wrath), we would have 3,000 samples at best. But with a computer program, we can make a million samples easily. In less than a second!
So today, we will learn how to write a program that generates needles (line segments). Our program needs to determine if a needle intersects a line. In general, checking if two line segments intersect is not an easy task. It’s rather amazing how we can look at many line segments (like the ones in the picture above) and instantly tell which lines intersect with which others. In our problem, fortunately, the lines on the paper are parallel and are equally spaced apart. We can use this fact to come up with a simple solution. Lastly, we will learn how to vectorize our code. Vectorization allows us to arrive at the answer quickly.
![\left\{\begin{array}{l} A^{T} = A \\[12pt] \vec{x}^{T}A\vec{x} > 0,\,\,\,\forall\,\vec{x} \neq \vec{0}, \end{array}\right.](https://s0.wp.com/latex.php?latex=%5Cleft%5C%7B%5Cbegin%7Barray%7D%7Bl%7D+A%5E%7BT%7D+%3D+A+%5C%5C%5B12pt%5D+%5Cvec%7Bx%7D%5E%7BT%7DA%5Cvec%7Bx%7D+%3E+0%2C%5C%2C%5C%2C%5C%2C%5Cforall%5C%2C%5Cvec%7Bx%7D+%5Cneq+%5Cvec%7B0%7D%2C+%5Cend%7Barray%7D%5Cright.&bg=ffffff&fg=1a1a1a&s=0 "\left\{\begin{array}{l} A^{T} = A \\[12pt] \vec{x}^{T}A\vec{x} > 0,\,\,\,\forall\,\vec{x} \neq \vec{0}, \end{array}\right.")
