Multi-level methods for degenerated problems with applications to p-versions of the fem [Elektronische Ressource] / vorgelegt von Sven Beuchler
126 Pages
English
Downloading requires you to have access to the YouScribe library
Learn all about the services we offer

Multi-level methods for degenerated problems with applications to p-versions of the fem [Elektronische Ressource] / vorgelegt von Sven Beuchler

-

Downloading requires you to have access to the YouScribe library
Learn all about the services we offer
126 Pages
English

Description

Multi level methods for degenerated problems withapplications top versions of the femVon der Fakultat¨ fur¨ Mathematik der Technischen Universitat¨ ChemnitzgenehmigteD i s s e r t a t i o nzur Erlangung des akademischen GradesDoctor rerum naturalium(Dr. rer. nat.)vorgelegtvon Dipl. Math. Sven Beuchlergeboren am 24. Juli 1975 in Karl Marx Stadteingereicht am 5. 2. 2003Gutachter: Prof. Dr. Arnd MeyerProf. Dr. Arnold ReuskenPD Dr. Markus MelenkTag der Verteidigung: 11. 7. 2003PrefaceMany physical problems lead to boundary value problems for partial differential equations whichcan be solved with theh−,hp−, andp−version of the finite element method. Such a discretiza tion leads to a system of linear algebraic equations. One of the most efficient methods in order tosolve systems of linear algebraic equations resulting fromp version finite element discretizationsof elliptic boundary value problems is the conjugate gradient method with domain decomposi tion preconditioners. The ingredients of such a preconditioner are a preconditioner for the Schurcomplement, a preconditioner related to the Dirichlet problems in the sub domains, and an ex tension operator from the boundaries of the sub domains into their interior.The aim of this monograph is to develop a preconditioner for the problems in the sub domains.

Subjects

Informations

Published by
Published 01 January 2003
Reads 13
Language English

Exrait

Multi level methods for degenerated problems with
applications top versions of the fem
Von der Fakultat¨ fur¨ Mathematik der Technischen Universitat¨ Chemnitz
genehmigte
D i s s e r t a t i o n
zur Erlangung des akademischen Grades
Doctor rerum naturalium
(Dr. rer. nat.)
vorgelegt
von Dipl. Math. Sven Beuchler
geboren am 24. Juli 1975 in Karl Marx Stadt
eingereicht am 5. 2. 2003
Gutachter: Prof. Dr. Arnd Meyer
Prof. Dr. Arnold Reusken
PD Dr. Markus Melenk
Tag der Verteidigung: 11. 7. 2003Preface
Many physical problems lead to boundary value problems for partial differential equations which
can be solved with theh−,hp−, andp−version of the finite element method. Such a discretiza
tion leads to a system of linear algebraic equations. One of the most efficient methods in order to
solve systems of linear algebraic equations resulting fromp version finite element discretizations
of elliptic boundary value problems is the conjugate gradient method with domain decomposi
tion preconditioners. The ingredients of such a preconditioner are a preconditioner for the Schur
complement, a preconditioner related to the Dirichlet problems in the sub domains, and an ex
tension operator from the boundaries of the sub domains into their interior.
The aim of this monograph is to develop a preconditioner for the problems in the sub domains.
For the Poisson equation, the preconditioner for this problem can be interpreted as the stiffness
matrix resulting from anh version finite element discretization of a degenerated operator. The
corresponding systems of finite element equations are solved by a multi grid algorithm. Al
ternatively, a preconditioned conjugate gradient method is used, where the preconditioner is a
multi grid preconditioner, an AMLI preconditioner, or a so called MTS BPX. A
rigorous mathematical theory analyzing the condition numbers of the preconditioned systems
and the convergence rate of the multi grid algorithm is given. The analysis is purely algebraic
and basically relies on two ingredients, the strengthened Cauchy inequality and the construction
of the smoother.
This work has been possible only with the help, stimulation and encouragement of many peo
ple. I want to thank Prof. Arnd Meyer for the supervision of my dissertation. Furthermore, I
wish to express my particular appreciation to Dr. Michael Jung for many stimulations, fruitful
discussions and proofreading. Chapter 7 comprises the results of a joint work with Prof. Rein
hold Schneider and Prof. Christoph Schwab. I would like to thank both for their contributions
and ideas. Furthermore, I would like to thank all colleagues of the faculty of mathematics at the
TU Chemnitz for the stimulating working atmosphere. Special thanks go to Dr. Gerd Kunert for
Aimproving the English and Roman Unger for removing all my LT X problems. This work wasE
supported by the Deutsche Forschungsgemeinschaft. At last I would like to thank my father for
his support and patience over the years. All this help and support is gratefully acknowledged.
1List of symbols
In this section, a list of the most important symbols is given.
• Domains:
d - space dimension,
I = (0,1),
2Ω = (0,1) ,
3Ω = (0,1) ,3
dR = (−1,1) .d
• Bilinear forms: R
a (u,v) = u v +u v ,4 x x y yR 1 0 0a (u,v) = u(x)v (x) dx,s 0R
1 2a (u,v) = x u(x)v(x) dx,m 0R
1 −2a (u,v) = x u(x)v(x) dx,m 0
a (u,v) = a (u,v)+a (u,v)+a (u,v),1 s m mR
2 2a(u,v) = y u v +x u v ,x x y yΩR
2 2 2a (u,v) = x u v +y u v +z u v .3 yz yz xz xz xy xyΩ3
• Polynomials:
p - polynomial degree,
L - i th Legendre polynomial,i
ˆL - i th integrated Legendre polynomial,i
T - i th Chebyshev polynomial.i
• Mesh parameter and shape functions:
k - level number,
kn = 2 ,
i i+1kτ - interval , ,i n n
k 1x - node (i,j),ij n
1,k k k kτ - triangle with verticesx ,x andx ,ij ij i,j+1 i+1,j+1
2,k k k kτ - with verticesx ,x andx ,ij ij i+1,j i+1,j+1
k k kE - squareτ ×τ ,ij i j
k k k kH - cubeτ ×τ ×τ ,ijl i j l
(1,k) (1,k) jφ - piecewise linear nodal hat function withφ ( ) =δ ,iji i n
k k kφ - piecewise linear nodal hat function withφ (x ) =δ δ ,il jmij ij lm
k k kφ - piecewise bilinear nodal hat function withφ (x ) =δ δ ,il jmb,ij b,ij lm
(1,k) (1,k) (1,k)kφ (x,y,z) = φ (x)φ (y)φ (z).t,ijl i j l
• Norms and function spaces:
2R
2 2L (Ω) - {u : Ω7→ , u measurable, u dx<∞},
Ω
1 2 2 d dH (Ω) - {u∈L (Ω),∇u∈ (L (Ω)) }, Ω⊂
1 1H (Ω) - {u∈H (Ω),u = 0 on∂Ω},0
ω(ξ) - weight function,
R
b2 2 2 2L ((a,b)) - {u∈L ((a,b)), ω (x)u (x) dx<∞},ω a
2k·k - L norm,0
1k·k - H1
2k·k - L norm,ω ω
k·k - energetic norm,a
k·k - Frobenius norm of a matrix,F
• quadratic matrices:
λ (M) - smallest eigenvalue ofM,min
λ (M) - largest eigenvalue ofM,max
κ(M) - condition number ofM in 2 norm,
−1 −1/2 −1/2κ(A B) - ofA BA , ifA andB
are symmetric and positive definite,
det(M) - determinant ofM,
trace(M) - trace ofM,
diag[ ] - diagonal matrix with the main diagonal equal to
the vector ,
tridiag[ , ] - tridiagonal symmetric matrix with main diago
nal and first sub diagonal ,
pentdiag[ , , ] - penta diagonal symmetric matrix with main di
agonal and sub diagonals and ,
jblockdiag[A ] - block diagonal matrix with blocksA .i ii=1
• special vectors and matrices:
T= [1,...,1] ,
1T = ·tridiag[2,− ],2 2 n2 1D = 4·diag[ ], where = i + ,4 6 i=1
C = D ⊗T +T ⊗D ,4 4 2 2 4
1 2 2K - C , stiffness matrix for−x u −y u using linear fi k 2 4 yy xx2n
nite elements,
μ˜C - AMLI preconditioner with the polynomial(1−rt) on levelk,r,μ
l = 1,...,k,
¯ ¯C =C - Multi grid preconditioner (1 iteration) on levelk with thek,S,μ k,S,μ,1
smootherS andμ cycles on each level,
ˆC - MTS BPX,k
ˆC - ILU BPX preconditioner.k
3
eacbaReRaababbeacbb4Contents
1 Introduction 7
2 Preliminary Tools 11
2.1 Iterative solution methods for systems of linear equations . . . . . . . . . . . . . 11
2.1.1 Simple iterative methods . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.1.2 Pcg method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2 Cholesky decomposition for banded matrices and related methods . . . . . . . . 13
2.3 Properties of the Legendre polynomials . . . . . . . . . . . . . . . . . . . . . . 14
2.4 Kronecker product . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3 Discretization by thep version of the fem 17
3.1 Formulation of the problem in two dimensions . . . . . . . . . . . . . . . . . . . 17
3.2 Domain decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.3 Properties of the element stiffness matrix . . . . . . . . . . . . . . . . . . . . . . 20
3.4 Preconditioner for the element stiffness matrix . . . . . . . . . . . . . . . . . . . 23
3.4.1 Preconditioner of Jensen and Korneev . . . . . . . . . . . . . . . . . . . 23
3.4.2 Modification of the preconditioner in 1D . . . . . . . . . . . . . . . . . 23
3.4.3 of the in 2D and 3D . . . . . . . . . . . . . 27
4 Interpretation of the preconditioners 29
4.1 The one dimensional case. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.1.1 Finite differences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.1.2 Finite elements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4.2 The two dimensional case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.2.1 Finite differences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.2.2 Linear elements on triangles . . . . . . . . . . . . . . . . . . . . . . . . 32
4.2.3 Bilinear on quadrilaterals . . . . . . . . . . . . . . . . . . . . . 35
4.2.4 Improvement for rectangular elements . . . . . . . . . . . . . . . . . . . 36
4.3 The three dimensional case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.3.1 Finite differences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.3.2 Trilinear elements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
5Contents
5 Fast solvers for degenerated problems 41
5.1 Introduction, aim, direct methods . . . . . . . . . . . . . . . . . . . . . . . . . . 41
5.2 Slowly convergent iterative methods . . . . . . . . . . . . . . . . . . . . . . . . 42
5.3 Multi grid proof for degenerated problems . . . . . . . . . . . . . . . . . . . . . 43
5.3.1 Multi grid algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
5.3.2 Algebraic convergence theory for multi grid . . . . . . . . . . . . . . . . 44
5.3.3 Basic definitions and helpful lemmata of the linear algebra . . . . . . . . 46
k5.3.4 Discussion of the strengthened Cauchy inequality on subelementsE . . 50ij
5.3.5 Construction of the smoother . . . . . . . . . . . . . . . . . . . . . . . . 57
2 25.3.6 Application of the multi grid theory to−x u −y u =g . . . . . . . 64yy xx
5.4 AMLI method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.4.1 Convergence theory for AMLI . . . . . . . . . . . . . . . . . . . . . . . 66
2 25.4.2 Application to−x u −y u =g. . . . . . . . . . . . . . . . . . . . . 68yy xx
5.5 Other multiplicative multi level algorithms. . . . . . . . . . . . . . . . . . . . . 70
5.5.1 Multi grid for finite element discretizations . . . . . . . . . . . . . . . . 70
5.5.2 preconditioner. . . . . . . . . . . . . . . . . . . . . . . . . . 71
5.5.3 Multi grid for finite difference . . . . . . . . . . . . . . . 74
5.6 BPX preconditioner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
5.6.1 Definition of the preconditioners . . . . . . . . . . . . . . . . . . . . . . 75
5.6.2 Proof of the upper eigenvalue estimate . . . . . . . . . . . . . . . . . . . 78
5.7 Implementational details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.7.1 Fast solver forC andL . . . . . . . . . . . . . . . . . . . . . . . . . 85kk
5.7.2 Complexity of the algorithm . . . . . . . . . . . . . . . . . . . . . . . . 88
5.8 Numerical examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
5.8.1 Convergence rates of multi grid . . . . . . . . . . . . . . . . . . . . . . 90
5.8.2 Multi grid preconditioner. . . . . . . . . . . . . . . . . . . . . . . . . . 93
5.8.3 AMLI . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
5.8.4 BPX preconditioner . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
6 Multi level preconditioner forp fem 97
6.1 Final estimates of the condition numbers . . . . . . . . . . . . . . . . . . . . . . 97
6.2 Numerical results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
6.2.1 Multi grid preconditioner. . . . . . . . . . . . . . . . . . . . . . . . . . 99
6.2.2 AMLI . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
6.2.3 BPX preconditioner . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
6.2.4 Comparison of all preconditioners . . . . . . . . . . . . . . . . . . . . . 102
7 Future work wavelets 103
7.1 1D case, motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
7.2 2D and 3D case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
7.3 Example of a wavelet basis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
7.4 Application to thep version and numerical experiments . . . . . . . . . . . . . . 108
6
W1 Introduction
Many problems in mechanics, natural sciences, and economy can be described by partial
differential equations (pde). Examples are the heat equation of thermodynamics
u =4u+f,t
(1) (2) (3) Tthe system of Lame´ equations foru = (u ,u ,u ) of linear elasticity
−μ4u−(λ+μ)grad divu = f,
the Schrodinger¨ equation of quantum mechanics
2~
i~Ψ =− 4Ψ,t
2m
or the Black Scholes partial differential equation of pricing of options
d d2X X∂v 1 ∂ v ∂v
+ σσ ρ SS +r S −rv = 0. (1.1)i j ij i j i
∂t 2 ∂S∂S ∂Si j i
i,j=1 i=1
However, for all these pde’s, the exact solution is only known for some academic examples by
giving suitably chosen right hand sides, initial values and boundary values. For the correspond
ing applications, it is important to obtain solutions of the pde also for those cases in which an
exact solution is not known.
For thirty years, applied mathematicians have studied discretization methods to obtain approxi
mate solutions of such pde’s. Examples for such approximation methods are the finite difference
method (fdm), [69], [41], and the finite element method (fem), [24], [74], [66], [16], which has
its origin in the simulation of aerodynamics for aero planes.
In order to understand the approximation theory, the Poisson equation
−4u =f
is often used as a reference example. In some cases, the theory can be extended to other examples.
E.g. by using Korn’s inequality, we obtain the same results for the system of the Lame´ equations.
For all methods, the described discretizations lead to a system of linear algebraic equations
Au =f.
Using the vectoru, an approximationu of the exact solutionu can be constructed by the usualh
finite element isomorphism. The error u −u tends to zero in a suitably chosen norm, if theh
71 Introduction
discretization parameter h tends to zero. Therefore for the practical implementation of such
algorithms, it is important to choose a discretization parameterh as small as possible in order to
obtain a sufficiently accurate approximationu to the exact solutionu. Then, the dimensionnh
n −dof the vectoru∈ will be nearly proportional toh , whered is the dimension of the domain
in which the partial differential equation is solved. Using finite differences or finite elements
of low order (h version of the fem), the corresponding system matrixA is a sparse matrix and
is positive definite for elliptic problems. More precisely, the number of nonzero elements is of
order n. For d > 1, the matrixA has a banded like structure. For todays computers, it is no
problem to store such a sparse matrix of dimensions up to some millions.
Instead of finite difference methods or the h version of the finite element method, collocation
methods, [52], and finite elements of high order (p version), [72], have become more popular
for twenty years. For theh version of the fem, the polynomial degreep of the shape functions
on the elements is kept constant and the mesh sizeh is decreased. This is in contrast to the the
p version of the fem in which the polynomial degreep is increased and the mesh sizeh is kept
constant. The advantage of thep version in comparison to theh version is that the approximate
solution u converges faster to the exact solution u, if u is sufficiently smooth. For example,p
∞ 1for the potential equation−4u = f with u ∈ C , the error in the H Sobolev norm fulfills
−rpk u−u k ≤ Ce (with some constantr > 0 independent ofp) in contrast to the algebraicp 1
convergence order of the h version withk u−u k ≤ Ch. Thus, the dimension of the femh 1
ansatz space can be reduced while obtaining an approximate solution with the same accuracy as
in theh version of the fem. Both ideas, mesh refinement and increasing the polynomial degree,
can be combined. This is called thehp version of the fem. Such discretizations lead to a system
of algebraic equations
A u =f (1.2)p p p
n ×n dp pwithA ∈ , wheren ≈ p is the number of unknowns. The question of the solution ofp p
such a systemA u =f is more difficult. The structure of the matrixA depends on the choicep pp p
of the basis of the fem ansatz space. For theh version of the fem, it is natural to use Lagrange
interpolation polynomials as basis. The case of thep version is more delicate. For some kinds of
elements, e.g. parallelepipeds in two dimensions, hierarchical polynomials are known for which
the matrixA has a sparse structure withO(n ) nonzero elements. One example is the basis ofp p
the integrated Legendre polynomials.
However, for each parallelepipedian element, the element stiffness matrixA has a banded struc p
ture. Therefore, by using direct solvers for (1.2), the memory requirement and the arithmetical
cost are not optimal because of fill in. Hence, iterative methods for (1.2) are better, ifp is suffi
λ (A )max pciently large. In all cases, the matrixA is ill conditioned which means that the ratio isp λ (A )min p
2 4 4(depending on the choice of the basis) of orderp ...p ford = 2 andp or worse ford = 3, see
e.g. [8], [58]. Thus, an efficient preconditioner for the matrixA is necessary.p
Several preconditioners for thep version of the fem and for thep version of the boundary element
method (bem) have been derived in the last years. Most of them, see [7], [35], [36], [59], [63], [1],
[49] for the fem, and [2], [76], [37], [45], [46] for the bem are based on domain decomposition
techniques. Efficient solvers for the subproblems are necessary for such a
preconditioner. One subproblem solver is the solver for the unknowns corresponding to the
8
RR