Algebraic Analysis of Multigrid Algorithms

摘要

We study the convergence rate of multilevel algorithms from an algebraic point of view, This requires a detailed analysis of the constant in the strengthened Cauchy-Schwarz inequality between the coarse-grid space and a so-called complementary space. This complementary space may be spanned by standard hierarchical basis functions, prewavelets or generalized prewavelets. Using generalized prewavelets, we are able to derive a constant in the strengthened Cauchy-Schwarz inequality which is less than 0.31 for the L~2 and H~1 bilinear form. This implies a convergence rate less than 0.15. so, we are able to prove fast multilevel convergence. Furthermore, we obtain robust estimations of the convergence rate for a large class of anisotropic ellipic equations. even for some that are not H~1 elliptic.