LEAST-SQUARES FINITE ELEMENT METHODS Max Gunzburger
LEAST-SQUARES FINITE ELEMENT METHODSMax GunzburgerDepartment of Scientific ComputingFlorida State Universitygunzburg@fsu.edu
WHY STUDY LEAST-SQUARES FINITE ELEMENT METHODS? Finite element methods were first developed and analyzed in the Rayleigh-Ritzsetting, i.e., problems whose solutions can be characterized as minimizers ofconvex, quadratic functionals– examples include- the equations of linear elasticity whose solutions can be characterizedas minimizers of the quadratic potential energy functional- the Poisson problem φ fin Ωandφ 0 on Γ Ωwhose solution φ can be characterized as the minimizer, over asuitable class of functions,of the DirichletfunctionalZZ1 φ 2 dΩ f φ dΩ2 ΩΩ
The Rayleigh-Ritz setting results in finite element methods having the following desirable features1. general regions and boundary conditions are relatively easy to handle andhigher-order accuracy is relatively easy to achieve2. the conformity of the finite element spaces is sufficient to guarantee stabilityand optimal accuracy3. for systems of PDEs, all variables can be approximated using a single typeof finite element space4. the resulting linear systems area) sparse; b) symmetric; c) positive definite FEMs were quickly applied in other settings– motivated by the fact that properties 1 and 4a are retained by all FEMs
Mixed FEMs arose from minimization problems constrained by PDEs– result in indefinite problems– the only other property (sometimes) retained from the Rayleigh-Ritz settingis symmetry– onerous compatibility conditions between finite element spaces often arise More generally, Galerkin FEMs are defined by forcing the residual of the PDEto be “orthogonal” to the finite element subspace– other than 1 and 4a, none of the advantages of the Rayleigh-Ritz settingare retained It is a testament to the importance of advantage 1 that despite the loss ofother advantages, mixed and Galerkin FEMs are in widespread use
Not surprisingly,despite the success of mixed and Galerkin FEMs,there has been substantial interest and effort devoted todeveloping finite element approaches that recover at least some of theadvantages of the Rayleigh-Ritz setting– stabilized FEMs– penalty methods Least-squares finite element methods can be viewed as another attempt atretaining the advantages of the Rayleigh-Ritz setting even for much moregeneral problems– in fact, they offer the possibility of, in principle, retaining all of the advantages of that setting for practically any PDE problem– let’s see how this is done
Straightforward LSFEM Consider the problemLu fin ΩandRu g on Γ– here Lu f is a PDE and Ru g is a boundary condition We assume nothing about this problem other than it is well posed– there existsa solution Hilbert space Sdata Hilbert spaces HΩ and HΓpositive constants α1 and α2such that the PDE estimate222α1kuk2S kLukH kRuk αkuk2HΓSΩholds u S
Now, consider the least-squares functional22 kRu gkJ(u; f, g) kLu f kHHΓΩand the unconstrained minimization problemmin J(u; f, g)u Sso that(Lv, Lu)HΩ (Rv, Ru)HΓ (Lv, f )HΩ (Rv, g)HΓ v S A LSFEM can be defined by– choosing a finite element subspace S h S– then restricting the minimization problem to the subspace Thus, the LSFEM approximation uh S h is the solution of the problemmin J(uh; f, g)uh S h All the desirable properties of the Rayleigh-Ritz setting are recovered!
The key is the norm equivalence of the functionalα1kuk2S J(u; 0, 0) α2kuk2S u Swhich follows fromJ(u; 0, 0) kLuk2HΩ kRuk2HΓ u Sand the well-posedness estimateα1kuk2S kLuk2HΩ kRuk2HΓ α2kuk2S u S Unfortunately, this is not the whole story– this straightforward procedure does not always lead to a practical method
Practicality issues We refer to a finite element method as being practical if it meets the followingcriteria– bases for the finite element spaces are easily constructed– linear systems are easily assembled– linear systems are relatively well conditioned In judging whether or not a LSFEM is practical, we will measure it up againstGalerkin FEMs for the Poisson equation
In particular, we will ask the questions:– can we use standard, piecewise polynomial spaces that are merely continuous and for which bases are easily constructed?– can the assembly of the linear systems be accomplished by merely applyingquadrature rules to integrals?– are the condition number of the linear systems of O(h 2)? Even in the Raleigh-Ritz setting, not all finite element methods are practical– for example, consider the following functionalZZ1 ψ ψ dΩ f ψ dΩ2 ΩΩwhose minimizers over a suitable function space are weak solutions of theDirichlet problem for the biharmonic equation: ψ 2ψ f in Ωandψ 0 and 0 on Γ n
– the Rayleigh-Ritz finite element setting- requires the use of C 1(Ω) finite element spaces- results in difficult assemblies of linear sysems- resulting condition numbers are of O(h 4)– none of the three practicality criteria are met We will later consider the keys to the practicality of LSFEMs
Further observations about the straightforward LSFEM We began with– the PDE problemLu fin ΩandRu g on Γ– the related PDE estimateα1kuk2S kLuk2HΩ kRuk2HΓ α2kuk2S u S– the least-squares functionalJ(u; f, g) kLu f k2HΩ kRu gk2HΓ– and the unconstrained minimization problemmin J(u; f, g)u S
A least-squares functional may be viewed as an “artificial” energy that playsthe same role for LSFEMs as a bona fide physically energy plays for RayleighRitz FEMs The least-squares functional J(·; ·, ·) measures the residuals of the PDE andboundary condition using the data space norms HΩ and HΓ, respectively The minimization problem seeks a solution in the solution space S for whichPDE estimate is satisfied The PDE system and the minimization problem are equivalent in the sensethat u S is a solution of the latter if and only if it is also a solution, perhapsin a generalized sense, of the former
A LSFEM was defined by– choosing a family of finite element subspaces S h S parameterized by htending to zero– then restricting the minimization problem to the subspacesso that the LSFEM approximation uh S h to the solution u S of theleast-squares minimization problem or of the PDE problem is the solution ofthe discrete least-squares minimization problemmin J(uh; f, g)uh S h The Euler-Lagrange equations corresponding to the two minimization problems are given byseeku Ssuch that B(u, v) F (v) v Sseekuh S hsuch that B(uh, v h) F (v h) vh S h
respectively, where we have the bilinear formB(u, v) (Lv, Lu)HΩ (Rv, Ru)HΓ u, v Sand the linear functionalF (v) (Lv, f )HΩ (Rv, g)HΓ v S The norm-equivalence of the functional now takes the formα1kuk2S J(u; 0, 0) B(u, u) α2kuk2S If we choose a basis {Uj }Jj 1, where J dim(S h), then we have thatuh JXj 1for some constants {cj }Jj 1cj Uj
Then the discretized problem is equivalent to the linear systemKc fwhere we have thatcj cjfor j 1, . . . , JKij B(Ui, Uj ) (LUi, LUj )HΩ (RUi, RUj )HΓfor i, j 1, . . . , Jfi F (Ui) (LUi, f )HΩ (RUi, g)HΓfor i 1, . . . , J The results of the following theorem follow directly from the PDE estimateand the resulting norm equivalence of the least-squares functional
THEOREM - Assume that the PDE estimate holds and that S h S. Then,– the bilinear form B(·, ·) is continuous, symmetric, and coercive and the linearfunctional F (·) is continuous– the problem B(u, v) F (v) for all v S has a unique solution u S thatis also the unique solution of the least-squares minimization problem– the problem B(uh, v h) F (v h) for all v h S h has a unique solution uh S hthat is also the unique solution of the discrete least-squares minimizationproblem– for some constant C 0, we have thatandkukS C(kf kHΩ kgkHΓ )kuhkS C(kf kHΩ kgkHΓ )– for some constant C 0, u and uh satisfy the optimal error estimateku uhkS C inf ku v hkSv h S h– the matrix K is symmetric and positive definite
Note that it is not assumed that the PDE problem is self-adjoint or positiveas it would have to be in the Rayleigh-Ritz setting– it is only assumed that it is well posed Despite the generality of the PDE problem, the LSFEM based recovers all thedesirable features of FEMs in the Rayleigh-Ritz setting The least-squares finite element approximation is optimally accurate with respect to solution norm k · kS for which the PDE problem is well posed In defining the least-squares minization principle, one need not restrict thespaces S and S h to satisfy the boundary conditions– instead, any boundary conditions can be imposed weakly by including theresidual Ru g of the boundary condition in the least-squares functionalJ(·; ·, ·)
– thus, we see that LSFEMs possess a desirable feature that is absent evenfrom standard FEMs in the Rayleigh-Ritz setting- the imposition of boundary conditions can be effected through thefunctional and need not be imposed on the finite element spaces– notwithstanding this advantage, one can, if one wishes, impose essentialboundary conditions on the space S- in this case, all terms involving the boundary condition are omitted andwe also set HΩ H Note also that sinceJ(uh; f, g) kLuh f k2HΩ kRuh gk2HΓ B(uh, uh) 2F (uh) (f, f )HΩ (g, g)HΓ ,the least-square functional J(uh; f, g) provides a computable indicator for theresidual error in the LSFEM approximation uh– such indicators are in widespread used for grid adaption
The problemB(u, v) F (v) v Sdisplays the normal equation form typical of least-squares systems, e.g., recallthat we have thatB(u, v) (Lv, Lu)HΩ (Rv, Ru)HΓ– it is important to note that since L is a differential operator, this probleminvolves the higher-order differential operator L L– we shall see that this observation has a profound effect on how practicalLSFEMs are defined The complete recovery, in general settings, of all desirable features of theRayleigh-Ritz setting is what makes LSFEMs intriguing and attractive– but, what about the practicality of the straightforward LSFEM?– we explore this issue using examples
An impractical application of the straightforward LSFEM Consider the problem u fin Ωandu 0 on Γ– of course, this is a problem which fits into the Rayleigh-Ritz framework sothat there is no apparent need to use any other type of FEM- inhomogeneous Dirichlet boundary conditions provide a situation inwhich one might want to use LSFEMs even for this problem– however, let us use the LSFEM method anyway, and see what happens We have (under some assumptions on the domain Ω) that the PDE estimateholds withS H 2(Ω) H01(Ω)H L2(Ω)L – note that, for simplicity, we impose the boundary condition on the solutionsspace S
We then have that, for all u, v H 2(Ω) H01(Ω),ZZJ(u; f ) k u f k20F (v) f v dΩB(u, v) v u dΩΩΩ Note that minimizing the least-squares functional has turned the second-orderPoisson problem into a fourth-order problem A LSFEM is defined by choosing a subspace S h S H 2(Ω) H01(Ω) andthen minimizing the functional J(·; f ) over S h It is well known that in this case, the finite element space S h has to consistof continuously differentiable functions– this requirement greatly complicates the construction of bases and the assembly of the matrix problem
Furthermore, it is also well known that the condition number of the matrixproblem is O(h 4)– this should be contrasted with the O(h 2) condition number obtainedthrough a Rayleigh-Ritz discretization of the Poisson equation Thus, for this problem, the straightforward LSFEM fails all three practicalitytests It is also true that PDE estimate holds withS H01(Ω)H H 1(Ω)– one could then develop a LSFEM based on the functional2J(u; f ) k u f k 1and the solution spaceS H01(Ω)
This approach would allow one to use a finite element space S h consisting ofmerely continuous functions so that bases may be easily constructed Moreover, it can be shown that because of the use of the H 1(Ω) norm inthe functional, the condition number of the resulting matrix system is O(h 2)which is the same as for a Rayleigh-Ritz discretization However, the H 1(Ω) inner product is computed by inverting the Laplacianoperator which makes the assembly of the matrix problem difficult– it also leads to the loss of property 4a, the sparsity of the matrix K So, as it stands, the straightforward LSFEM remains impractical for thesecond-order Poisson problem.
A practical application of the straightforward LSFEM Consider the problem (say in two dimensions) · u fand u g in Ωandn · u 0 on Γ Hereu S H1n (Ω) {v H1(Ω) n · v 0 on Γ}and{f, g} H L20(Ω) L2s (Ω)whereL20(Ω) {f L2(Ω) Zf dΩ 0}ΩandL2s (Ω) {g L2(Ω) · g 0 in Ω}
We then have that the PDE estimate holds so that we may define the leastsquares functionalJ(u; f, g) k · u f k20 k u gk20 u S H1n(Ω)– we then have thatZ B(u, v) ( ·u)( ·v) ( u)·( v) dΩ u, v S H1n(Ω)ΩandF (v) Z Ω f · v g · v dΩ v S H1n(Ω) A LSFEM is defined by choosing a subspace S h S H1n (Ω) and thenminimizing J(·; f , g) over S h
In this case, the LSFEM recovers all the good properties of the Rayleigh-Ritzsetting and also satisfies all three practicality criteria– since we merely require that S h H1n (Ω), we can choose standard finiteelement spaces for which bases are easily constructed– furthermore, since the functional J(·; ·, ·) only involves L2(Ω) inner products, the assembly of the matrix system is accomplished in a standardmanner– finally, it can be shown that the condition number of the matrix system isO(h 2).
Norm-equivalence vs. practicality We have referred to a functional satisfyingα1kuk2S J(u; 0, 0) α2kuk2Sas being norm equivalent– this property causes the LSFEM defined by minimizing such a functional torecover all the desirable properties of the Rayleigh-Ritz setting However, the norms that enter the definition of the functional J(·; ·, ·) as wellas the form of the PDE system can render the resulting LSFEM impractical Thus, in order to define a practical LSFEM, one may have to define a leastsquares functional that is not norm equivalent– we take up this issue in later– here, we examine the examples just discussed to see what guidance theygive us about what makes a LSFEM practical
First-order system form of the PDE Perhaps the most important observation that can be made from the examplesis that the div-curl example involved– a first-order system of PDEs- so that the normal equation operator L L is merely a second-orderdifferential operator– a LSFEM that allowed for the easy construction of finite element bases- because one could work with merely continuous finite element spaces– and resulted in a matrix systems with relative good O(h 2) conditioning As a result, modern LSFEMs are based on first-order formulations of PDEsystems– of course, many if not most PDEs of practical interest are not usually posedas first-order systems
Thus, the first step in defining a LSFEM should be recasting a given PDEsystem into a first-order system Unfortunately, there is no unique way to do this– for example, the u φ 0 ·u f φ 0three problems u φ 0in Ω ·u fin Ω u 0 on Γ φ 0 in Ω in Ωin Ω on Γ · u f in Ω u 0 in Ω n u 0 on Γare all first-order systems that are equivalent to the Poisson problem φ fin Ωφ 0 on Γ– each happens to be norm equivalent, but with respect to different norms
– if we assume that in each case the boundary condition is imposed on thesolutions space, we have that the space S is respectively given byH01(Ω) H(Ω, div)H01(Ω) H1(Ω)H1τ (Ω)whereH(Ω, div) {v L2(Ω) · v L2(Ω)}H1τ (Ω) {v H1(Ω) n v 0 on Γ}
Functionals formed using L2 norms of equation residuals Another observation that can be gleaned from the examples is that if onewants to be able to assemble the matrix system using standard finite element techniques, then one should use L2 norms of equation residuals in thedefinition of the least-squares functional– unfortunately, it is not always the case that the resulting least-squares functional is norm equivalent– let us explore this issue in more detail Consider the Stokes problem u p f , · u 0 in Ωandu 0 on Γ The most popular LSFEM for this problem is based on the first-order system ω p f ,ω u, ·u 0 in Ωandu 0 on Γthat is known for obvious reasons as the velocity-vorticity-pressure formulation
One would then be tempted to use the functionalJ0(u, ω, p; f ) k ω p f k02 k u ωk20 k · uk20that involves only L2(Ω) norms of equation residuals– indeed, this is the most popular approach for defining LSFEM for the Stokesequations– unfortunately, this functional is not norm equivalent On the other hand, the functional2J 1(u, ω, p; f ) k ω p f k 1 k u ωk20 k · uk20is norm equivalent tokuk21 kωk20 kpk20but involves the impractical H 1(Ω) norm
So, on the one hand– the lack of norm equivalence for the functional J0(·, ·, ·; ·) results in a lossof accuracy of the LSFEM approximations based on that functionalon the other hand– the appearance of the H 1(Ω) norm in the functional J 1(·, ·, ·; ·) results inan impractical LSFEM because the matrix systems are not easily assembled To resolve this dilemma, we have to turn to more sophisticated LSFEMs– here, we only give a brief and superficial review of this subjectfor details see the Springer book with Pavel Bochev
MORE SOPHISTICATED LSFEMS We refer to the variational principlemin J(u; f, g)u Sas the continuous least-squares principle Instead of using this principle as the basis for defining a LSFEM, we nowchoose– a finite element space S h and– a convex quadratic functionalJh(·; f, g) defined over S h The pair {S h, Jh(·; f, g)} gives rise to the discrete least-squares principlemin Jh(uh; f, g)uh S h
Since we only require that the functional Jh(·; f, g) be defined for functionsin S hand not necessarily over S,we refer to LSFEMs constructed in this manner as discrete LSFEMs The functional Jh(·; f, g) is required to satisfy the following non-restrictiveassumptionsH1. There existsa discrete energy inner product (·, ·)h : S h S h 7 ℜand1/2a discrete energy norm k · kh (·, ·)hsuch thatJh(uh; 0, 0) (uh, uh)h kuhk2h for all uh S hH2. There exist bilinear forms E(·, ·) and T (·, ·) such that for all smoothfunctions u S and all uh S hJh(uh; Lu, Ru) ku uhk2h E(u, uh) T (u, u)
The two assumptions are sufficient to prove the following resultsTHEOREM - Assume thatthe hypotheses H1 and H2 hold for {S h, Jh(·; f, g)}andlet u denote a sufficiently smooth solution of PDE problemThen,the discrete least-squares principle has a unique solution uh S hMoreover, uh satisfieshE(u,v)hhku u kh inf ku v kh suphv h S hv h S h kv kh
A discrete least-squares functional Jh(·; f, g) is referred to as being order rconsistent if, for any sufficiently smooth u S,E(u, uh) C(u)hr for some r 0 If Jh(·; f, g) is order r-consistent, then we have the error estimateku uhkh inf ku v hkh C(u)hrv h S h Defining pairs {S h, Jh(·; f, g)} such that the assumptions H1 and H2 aresatisfied is not a difficult task
Constructing discrete least-squares functionals We have an estimate for the error with respect to the discrete norm k · kh– of greater interest is estimating errors using the (mesh-independent) solution norm k · kS- since S h S, it is true that k · kS acts as another norm on S h- since S h is finite dimensional, the two norms k · kh and k · kS arecomparable– however, the comparability constants may depend on h- if they do, then error estimates in the norm k · kS will surely involveconstants that depend on inverse po
A least-squares functional may be viewed as an “artificial” energy that plays the same role for LSFEMs as a bona fide physically energy plays for Rayleigh-Ritz FEMs The least-squares functional J(·;·,·) measures the residuals of the PDE and boundary condition using the data space norms HΩ and HΓ, respectively
5.8.1 The Compatible Least-Squares Finite Element Method with a Reaction Term 177 5.8.2 The Compatible Least-Squares Finite Element Method Without a Reaction Term 181 5.9 Practicality Issues 182 5.9.1 Practical Rewards of Compatibility 184 5.9.2 Compatible Least-Squares Finite Element Methods on Non-Affine Grids 190
An adaptive mixed least-squares finite element method for . Least-squares Raviart–Thomas Finite element Adaptive mesh refinement Corner singularities 4:1 contraction abstract We present a new least-squares finite element method for the steady Oldroyd type viscoelastic fluids.
least-squares finite element models of nonlinear problems – (1) Linearize PDE prior to construction and minimization of least-squares functional Element matrices will always be symmetric Simplest possible form of the element matrices – (2) Linearize finite element equations following construction and minimization of least-squares. functional
Finite element analysis DNV GL AS 1.7 Finite element types All calculation methods described in this class guideline are based on linear finite element analysis of three dimensional structural models. The general types of finite elements to be used in the finite element analysis are given in Table 2. Table 2 Types of finite element Type of .
LEAST-SQUARES FINITE ELEMENT METHODS AND ALGEBRAIC MULTIGRID SOLVERS FOR LINEAR HYPERBOLIC PDESyy H. DE STERCK yx, THOMAS A. MANTEUFFEL {, STEPHEN F. MCCORMICKyk, AND LUKE OLSONz Abstract. Least-squares nite element methods (LSFEM) for scalar linear partial di erential equations (PDEs) of hyperbolic type are studied.
FINITE ELEMENT METHODS OF LEAST-SQUARES TYPE 791 nite element methods: nite element spaces of equal interpolation order, de ned with respect to the same triangulation, can be used for all unknowns; algebraic problems can be solved using standard and robust iterative methods, such as conjugate gradient methods; and
Linear Least Squares ! Linear least squares attempts to find a least squares solution for an overdetermined linear system (i.e. a linear system described by an m x n matrix A with more equations than parameters). ! Least squares minimizes the squared Eucliden norm of the residual ! For data fitting on m data points using a linear
ADAPTIVELY WEIGHTED LEAST SQUARES FINITE ELEMENT METHODS FOR PARTIAL DIFFERENTIAL EQUATIONS WITH SINGULARITIES B. HAYHURST , M. KELLER , C. RAI , X. SUNy, AND C. R. WESTPHALz Abstract. The overall e ectiveness of nite element methods may be limited by solutions that lack smooth-ness on a relatively small subset of the domain.
