The classic iterative method essentially only plays a "smooth" effect, even if it can quickly eliminate the high-frequency part of the residual, but the effect is not very good for the low-frequency part. The basic idea of the multi-grid method is: first of all Establish a set of coarse and fine grids for the fixed solution area, and form the corresponding difference or finite element discrete equation. For this discrete equation, first use the usual iterative method on the fine grid, such as Richardson iteration and Gauss-Seidel iteration. Iteratively eliminate the high-frequency part of the residual, and then transfer the low-frequency part of the residual to the coarse grid for correction. After several cycles, a solution that satisfies the accuracy is obtained. Since the residual correction is performed on the coarse grid , So the corresponding workload is relatively small.
The Jacobi and Gauss-Seidel iterations produce smooth errors. The error vector
On that coarser grid a big piece of the error is removable. We iterate only a few times before changing from fine to coarse and coarse to fine. The remarkable result is that multigrid can solve many sparse and realistic systems to high accuracy in a fixed number of iterations, not growing with
Multigrid is especially successful for symmetric systems. The key new ingredients are the (rectangular !) matrices
-
A restriction matrix R transfers vectors from the fine grid to the coarse grid
-
An interpolation matrix
returns to the fine grid -
The original matrix
on the fine grid is approximated by on the coarse grid. This is smaller and easier and faster than . I will start with interpolation (a 7 by 3matrix that takes 3 v's to 7 u's):
Interpolation , on the fine grid, on the coarse grid.
The second matrix we need is a restriction matrix
Fine grid
Geometric multigrid, GMG
Get the iterative result from the original mesh
Equivalent in coarse grid to solve
Among them,
After solving the
Interpolation is equivalent to left multiplication matrix
Sampling the residual to a coarse grid, and interpolate the solution to a fine grid after solving, that is
Comparison available
Multigrid algorithm solution
- If the grid size is small enough to solve the equation accurately or imprecisely, return the solution;.
- Otherwise ,Solve iteratively with
as the initial iterative step, obtain . And calculate residual . - Coarse the residuals
. - order
, Solve using multi-grid algorithm. - Interpolate the solution and accumulate
. - Iterate with
as the initial iterative step to obtain .
0 条评论