Multigrid method: Difference between revisions

Revision as of 08:58, 20 September 2007

Revision as of 09:06, 20 September 2007

Line 21:

Assume that one has a differential equation which can be solved approximately (with a given accuracy) on a grid <math>i</math> with a given grid point

density <math>N_i</math>. Assume furthermore that a solution on any grid <math>N_i</math> may be obtained with a given

effort <math>W_i = \rho K N_i</math> from a solution on a coarser grid <math>i+1</math>. Here, <math>\rho = N_{j+1} / N_j < 1</math> is the ratio of grid points on "neighboring" grids and is assumed to be constant throughout the grid hierarchy, and <math>K</math> is some constant modeling the effort of computing the result for one grid point.

UsingThe thefollowing [[geometricrecurrence series]],relation weis then findobtained for the effort involvedof in findingobtaining the solution on grid <math>k</math>:

the finest grid :<math>N_1W_k = W_{k+1} + \rho K N_k</math>

And in particular, we find for the finest grid <math>N_1</math> that

:<math>W_1 = W_2 + \rho K N_1</math>

Combining these two expressions (and using <math>N_{k+1} = \rho N_k</math>) gives

:<math>W_1 = K N_1 \sum_{p=0}^n \rho^p </math>

or

:<math>W_1 = W_3 + \rho^2 K N_1 + \rho K N_1</math>

:<math>W_1 / (K N_1) + 1 = 1 + \sum_p \rho^p </math>

Line 31 ⟶ 35:

:<math>W_1 = (K N_1) (1 / (1 - \rho) - 1),</math>

that is, a solution may be obtained in <math>O(N)</math> time.

Using the [[geometric series]], we then find for t

== See also ==