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

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

Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
126 pages
English
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

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.

Sujets

Informations

Publié par
Publié le 01 janvier 2003
Nombre de lectures 13
Langue English

Extrait

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 . . . . . . . . . . . . . .

  • Univers Univers
  • Ebooks Ebooks
  • Livres audio Livres audio
  • Presse Presse
  • Podcasts Podcasts
  • BD BD
  • Documents Documents