Finite element methods with hierarchical WEB-splines [Elektronische Ressource] / vorgelegt von Muhammad Mustahsan
73 Pages
English

Finite element methods with hierarchical WEB-splines [Elektronische Ressource] / vorgelegt von Muhammad Mustahsan

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

Description

Finite Element Methods with HierarchicalWEB-splinesVon der Fakult¨at Mathematik und Physik der Universit¨at Stuttgartzur Erlangung der Wu¨rde einesDoktors der Naturwissenschaften (Dr. rer. nat.)genehmigte Abhandlungvorgelegt vonMuhammad Mustahsangeboren in Chakwal, PakistanHauptberichter: Prof. Dr. Klaus H¨olligMitberichter: Prof. Dr. Ulrich ReifTag der Einreichung: 19.01.2011Tag der mu¨ndlichen Pru¨fung: 03.02.2011Institut fu¨r Mathematische Methoden in den Ingenieurwissenschaften,Numerik und geometrische ModellierungUniversit¨at Stuttgart20112Dedicated to my late fatherGhulam SarwariiiDas Gleichnis derjenigen, die ihren Besitz auf Allahs Weg ausgeben, ist das eines Saatkorns,¨ ¨das sieben Ahren wachsen la¨sst, in jeder Ahre hundert Ko¨rner. Allah vervielfacht, wem Er will.Und Allah ist Allumfassend und Allwissend(Koran 2:261)iiiivAbstractPiecewise polynomial approximations are fundamental to geometric modeling, computer graph-ics, and finite element methods. The classical finite element method uses low order piecewisepolynomials defined on polygonal domains. The domains are discretized into simple polygonscalled the mesh. These polygons might be triangles, quadrilaterals, etc., for two-dimensionaldomains, and tetrahedra, hexahedra, etc., for three-dimensional domains. Meshing is often themost timeconsuming process in finite element methods.

Subjects

Informations

Published by
Published 01 January 2011
Reads 26
Language English
Document size 1 MB
Finite Element Methods with Hierarchical WEB-splines
VonderFakulta¨tMathematikundPhysikderUniversita¨tStuttgart zurErlangungderWu¨rdeeines Doktors der Naturwissenschaften (Dr. rer. nat.) genehmigte Abhandlung
vorgelegt von
Muhammad Mustahsan
geboren in Chakwal, Pakistan
Hauptberichter: Mitberichter:
Prof.Dr.KlausHo¨llig Prof. Dr. Ulrich Reif
Tag der Einreichung: 19.01.2011 Tagdermu¨ndlichenPr¨ufung:03.02.2011
Institutf¨urMathematischeMethodenindenIngenieurwissenschaften, Numerik und geometrische Modellierung Universita¨tStuttgart 2011
2
Dedicated
to
my
Ghulam
i
late
Sarwar
father
ii
Das Gleichnis derjenigen, die ihren Besitz auf Allahs Weg ausgeben, ist das eines Saatkorns, ¨ ¨ dassiebenAhrenwachsenla¨sst,injederAhrehundertKo¨rner.Allahvervielfacht,wemErwill. Und Allah ist Allumfassend und Allwissend (Koran 2:261)
iii
iv
Abstract
Piecewise polynomial approximations are fundamental to geometric modeling, computer graph-ics, and finite element methods. The classical finite element method uses low order piecewise polynomials defined on polygonal domains. The domains are discretized into simple polygons called the mesh. These polygons might be triangles, quadrilaterals, etc., for two-dimensional domains, and tetrahedra, hexahedra, etc., for three-dimensional domains. Meshing is often the most timeconsuming process in finite element methods. In classical two-dimensional finite ele-ment methods, the basis functions are usually hat functions defined on triangulations. Another possible selection of a finite element basis in two dimensions are tensor product b-splines.
Bivariate B-splines are piecewise polynomials of degreenwith support having (n+ 1)2cells. The domain is discretized via a uniform grid. Relevant are those b-splines for which the support intersects the domain. To keep the support of a relevant B-spline within the domain, we mul-tiply it by a weight function. The weight function is positive in the interior of the domain and vanishes on the boundary and outside of the domain. The resulting weighted B-splines conform to homogeneous boundary conditions. They satisfy the usual properties of a finite element basis.
The insertion of new knots into the grid is not a good adaptive strategy because of the global effect of knot insertion. Instead, hierarchical refinement is very effective for tensor product splines. It permits the change of control points and subsequent editing of fine details in some parts while keeping the other parts unaffected. For programming, a data structure is required that not only keeps track of the refinement but also stores the information about the discretiza-tion of the domain. Moreover, algorithms for assembling and solving the finite element system are needed. In this thesis, we have developed such adaptive schemes with weighted B-splines and implemented them inMatlabwith an appropriate data structure.
v
vi
We proposed two different adaptive schemes for the selection of the sequence of subdomains characterizing the refinement. The first scheme uses a predefined and strongly nested domain sequence, appropriate, e.g., near a reentrant corner of the domain. For strongly nested domains, the distance between the boundary of the subdomain with grid widthhand the subdomain with grid widthh2 is(2n+ 1)h such a domain sequence, an error estimate can be obtained.. For
The second adaptive scheme is an automatic refinement process. The refinement is determined by comparing the B-spline coefficients of an approximation with those of an approximation ob-tained by refining all subdomains. The hierarchical refinement is then based on the regions where the difference between the coefficients exceeds a given tolerance. Both adaptive schemes yield convergence of the hierarchical approximations. The adaptive schemes are tested by solving Poisson’s problem on domains with reentrant corners with refinement in the neighborhood of the geometric singularity.
Abstract
St¨uckweisepolynomialeApproximationenspieleninderGeometrischenModellierung,Computer graphik und bei Finite-Elemente-Methoden eine fundamentale Rolle. Klassische Finite-Elemente-Verfahrenbenutzenst¨uckweisePolynomeniedrigerOrdnungaufpolygonalenGebieten.DieGe-bietewerdenineinfachePolygone,dassogenannteNetz,zerlegt.DiesePolygoneko¨nnenfu¨r zweidimensionaleGebietebeispielsweiseDreieckeoderViereckesein,f¨urdreidimensionaleGebie-teTetraederoderHexaeder.DieNetzgenerierungistoftderzeitaufwa¨ndigsteProzessinder Finite-Elemente-Methode. In der klassischen Finite-Elemente-Methode sind die Basisfunktionen inzweiDimensionenmeistaufTriangulierungendenierteHut-Funktionen.Eineanderem¨ogliche Wahl einer bivariaten Finite-Elemente-Basis sind Tensor-Produkt-B-Splines.
BivariateB-Splinessindst¨uckweisePolynomevomGradnetniim¨ageemTrstehr,besuadne (n+ 1)2Gitterzellen. Das Gebiet wird durch ein uniformes Gitter diskretisiert. Relevant sind diejenigenB-Splines,derenTra¨gerdasGebietschneidet.UmdenTra¨gereinesrelevantenB-SplinesaufdasGebieteinzuschr¨anken,wirdermiteinerGewichtsfunktionmultipliziert.Die Gewichtsfunktion ist im Innern des Gebietes positiv und verschwindet auf dem Rand und außer-halbdesGebietes.DieresultierendengewichtetenB-Splineserf¨ullenhomogeneRandbedingun-gen.Siebesitzendieu¨blichenEigenschafteneinerFinite-Elemente-Basis.
DasEinf¨ugenneuerKnotenindasGitteristkeineguteadaptiveStrategieaufgrundder globalenAuswirkungdesKnoteneinfu¨gens.StattdessenisteinehierarchischeVerfeinerungfu¨r ¨ Tensorprodukt-Splines sehr effektiv. Sie erlaubt eine lokale Anderung von Kontrollpunkten mit anschließender Modifikation kleiner Details in einigen Bereichen, ohne dabei andere Bereiche zu beeinflussen. Zur Programmierung ist eine Datenstruktur notwendig, die sowohl die Verfeinerung beschreibtalsauchdieDiskretisierungdesGebietesber¨ucksichtigt.DesWeiterenwerdenAlgo-rithmenzurAufstellungundLo¨sungdesFinite-Elemente-Systemsbeno¨tigt.IndieserDissertation vii
viii
wurdensolcheadaptiveVerfahrenfu¨rgewichteteB-Splinesentwickeltundmiteinerentsprechen-den Datenstruktur inMatlabimplementiert.
EswurdenzweiverschiedeneadaptiveSchematafu¨rdieAuswahlderFolgederTeilgebiete, die die Verfeinerung beschreiben, vorgeschlagen. Das erste Schema benutzt eine vorab definierte stark geschachtelte Gebietsfolge, wie sie beispielsweise in der Umgebung einer einspringenden Eckesinnvollist.Fu¨reinestarkgeschachtelteGebietsfolgeistderAbstandzwischendemRand des Gebiets mit Gitterweitehund dem Gebiet mit Gitterweitehg2(2cheigleroßr¨n+ 1)hru¨F. einesolcheGebietsfolgekanneineFehlerabsch¨atzunggezeigtwerden.
Das zweite adaptive Schema ist ein automatischer Unterteilungsprozess. Die Unterteilung wird durch Vergleich der B-Spline-Koeffizienten einer Approximation mit denen einer Approx-imation, die durch Unterteilung aller Teilgebiete entsteht, bestimmt. Die hierarchische Un-terteilung basiert dann auf den Bereichen, bei denen die Differenz zwischen den Koeffizienten einevorgegebeneToleranz¨uberschreitet.F¨urbeideadaptivenSchemataerha¨ltmanKonvergenz derhierarchischenApproximationen.DieadaptivenSchematawurdenfu¨rdasPoisson-Problem auf Gebieten mit einspringenden Ecken mit Verfeinerung in der Umgebung der geometrischen Singularita¨tgetestet.
Contents
1 Introduction 1.1 Outline of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Finite Element Approximation 2.1 Elliptic problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Sobolev space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Variational form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Ritz-Galerkin system . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Weighted Hierarchical Bases 3.1 Weight functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Linear B-splines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Approximation with linear splines . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Weighted linear B-splines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Hierarchical refinement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6 Error estimate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Implementation 4.1 Grid data structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Assembly of the Ritz-Galerkin system . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Numerical integration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Matrix assembly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5 Adaptive refinement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.6 Numerical examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Summary and Discussion 5.1 Possible generalizations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A Appendix A
ix
1 4 5 5 6 8 9 13 13 16 19 21 22 26 29 29 32 34 35 36 39 45 48 51