Least-Squares Finite Element Methods

E-mail to Max Gunzburger

Recent collaborators

Description

Least-squares finite element methods are defined through the minimization of a least-squares functional. This functional is defined to be the sum of the squares of norms of residuals of the differential equations and, perhaps also, the boundary conditions. Great care must be exercised in choosing the norms used to measure each of the residuals and choosing the function spaces in which to seek minimizers of the least-squares functional. An improper choice of any of these can result in suboptimally accurate approximations, or even worse, ill-posed problems. The a priori estimates provided by Agmon-Douglis-Nirenberg theory for elliptic partial differential equations and/or direct coercivity estimates may be used as guides for choosing the proper residual norms and spaces for candidate minimizers. One important observation is that the choice of both residual norms and trial spaces depends not only on the partial differential equations, but also on the boundary condition operators. After a well-posed functional is defined, least-squares finite element methods may be easily defined by effecting the minimization with respect to finite dimensional finite element subspaces.

The practical success of least-square finite element methods for second-order or higher-order elliptic partial differential equations rests on re-writing these equations, through the introduction of new variables, as equivalent first-order systems. For example, a reduction to first-order form is necessary in order to easily keep the condition numbers of the discrete systems manageable and in order to use merely continuous finite element spaces in a conforming discretization of the corresponding least-squares principle. For a given partial differential equation or system of partial differential equations, one can usually define many different equivalent first-order formulations. Each of these can result in different residual norms and different trial spaces for the corresponding least-squares functional and thus can result in substantially different methods, from both the theoretical and practical points of view.

We give a brief description of some of our work in least-squares finite element methods for partial differential equations. Details may be found in the references cited below. In particular, a review article summarizes much of the current theoretical knowledge about least-squares finite element methods.

Stokes and Navier-Stokes equations

Least-squares finite elment methods offer the promise of having many advantages compared to other methods. This is especially true for the Navier-Stokes equations, where, from a theoretical viewpoint, least-squares finite element methods possess a number of significant and valuable properties. These properties can yield notable computational advantages and simplifications over other methods, e.g., mixed Galerkin methods, when properly accounted for in the algorithmic design and implementation of least-squares finite element methods. Least-squares principle based methods possess, among others, the following theoretically and practically desirable features.

• The weak problems are in general coercive.
• The choice of approximating spaces is not subject to the LBB condition.
• Conforming discretizations lead to stable and, ultimately, optimally accurate methods.
• Finite element spaces of equal interpolation order, defined with respect to the same triangulation, can be used for all unknowns.
• Used in conjunction with a Newton linearization results in symmetric, positive definite linear systems, at least in the neighborhood of a solution.
• When used in conjunction with properly implemented continuation (with respect to the Reynolds number) techniques, a solution method can be devised that will only encounter symmetric, positive definite linear systems.
• Algebraic problems can be solved using standard and robust iterative methods, such as preconditioned conjugate gradient methods.
• Methods can be implemented without any matrix assemblies, even at the element level.
• Essential boundary conditions may be imposed in a weak sense.
• No artificial boundary conditions for the vorticity need be introduced at boundaries at which the velocity is specified.
• Accurate vorticity approximations are obtained.

We have studied both theoretical and practical issues connected with least-squares finite element methods for the Stokes and Navier-Stokes equations. A brief list of our results is as follows.

• The velocity-vorticity-pressure equations are, in engineering practice, the most popular formulation used as a basis for defining least-squares finite element methods. We have shown, thorugh analyses and computational experiments, that a straightforward implementation using the velocity-vorticity-pressure formulation results in suboptimally accurate approximations.
• We have shown that by using appropriate mesh-dependent weights in the least-squares functional based on the velocity-vorticity-pressure formulation, one can recover the optimal accuracy of the approximations.
• We have analyzed least-squares finite element methods for the velocity-pressure-stress formulation of the Stokes equations and shown how such methods may be implemented so that optimal accuracy is achieved.

Second-order equations with discontinuous coefficients

We have examined least-squares finite element methods for second-order elliptic boundary value problems having interfaces due to discontinuous media properties. Both Dirichlet and Neumann boundary data have been treated. The boundary value problems are recast into a first-order formulation to which a suitable least-squares principle is applied. Among the advantages of the method are that nonconforming, with respect to the interface, approximating subspaces may be used and, moreover, the grids used on each side of an interface need not coincide along the interface. We have derived optimal-order error estimates that improve on other treatments of interface problems. We have also implemented least-squares finite element methods and performed some computational experiments that illustrate the method and its analysis.

Practical issues

Least-squares finite element methods have the potential of offering many advantages over other methods. Many of these advantages can be documented through theoretical analyses. However, in practice, there are questions that must be addressed in order to fully realize these advantages. Through a series of computational experiments, we have, in the Stokes and Navier-Stokes equations setting, identified a number such difficulties and devised means for their amelioration. A partial list of these is as follows.

• Seemingly practical finite element spaces not covered by existing theories are considered; included in these are piecewise linear approximations for the velocity. We have shown, through a number of computational experiments, that, properly implemented, one may indeed use piecewise linear spaces for the velocity.
• Existing theories do not address the question of mixed boundary conditions, e.g., velocity data in one portion of the boundary, stress data in another, and pressure data in still another. We have shown how some combination of boundary conditions can be treated through straightforwad implementations of least-squares methods for the velocity-vorticity-pressure formulation, while othe combinations require mesh-dependent weighted functionals in order to achieve optimal accuracy.
• It has been reported that least-squares finite element methods do not do a good job at conserving mass. We have examined this issue, and shown how, through the introduction of appropriate weights into the least-squares functional, satisfactory mass conservation can be achieved.
• Non-convex polygonal regions result in solutions that are not sufficiently smooth to achieve the full accuracy inherent in the approximation spaces. We have shown how, through the use of mesh refinement and/or mesh-dependent weights near re-entrant corners, the full accuracy of the finite element spaces can be recovered.

A conclusion that can be drawn from the computational experiments that we have performed is that the use of appropriate mesh-dependent weights in the least-squares functional almost always improves the accuracy of the approximations.

An abstract theory for least-squares finite element methods

We have developed an abstract, unified theory for least-squares finite element methods that includes, as special cases, almost all known members of that class of methods. The theory focuses on the notion of norm-equivalence of a least-squares functional and classifies the many concrete realizations into four categories which are characterized by how "close" the functionals manage to achieve norm-equivalence. Error estimates are derived for each case. The abstract theory is not just a mathematical nicety. In fact, a simple theory for totally norm-equivalent least-squares functionals can be developed (it is one of the four cases alluded to above) which, theoretically speaking, seems adequate for most problems. However, the least-squares finite element methods resulting from this approach are often not practical, e.g., they involve negative or factional-order Sobolev norms or require finite element basis functions that are too smooth, e.g., continuously differentiable, or require too much regularity of the exact solution. It is exactly for this reason, i.e., to come up with a practical method, that the many variations of least-squares finite element methods have been developed. Our more general theory encompasses these variants and systematically places them in a hierarchy of methods. This makes it easy to choose the "right" method (by "right" we mean mathematically well posed and practical) for a given problem, to compare different methods, and makes it easier to develop new methods for specific applications. This abstract theory is the centerpiece of the book we are writing (with Pavel Bochev) on least-squares finite element methods. In the book, the abstract theory is also applied to several classes of problems, e.g., second-order elliptic equations, the Stokes and Navier-Stokes equations, Maxwell equations, etc. Our goal is to make the book a definitive, state-of-the-art source for the mathematical theory of least-squares finite element methods and simultaneously provide the reader with practical knowledge about the choice, the implementation, the evaluation, and the performance characteristics of the many methods available.

Optimization problems for first-order elliptic systems

Optimal control and optimization problems for partial differential equations require the minimization of a given functional with repect to some data in the problem description. The partial differential equation system plays the role of a constraint. We have examined analytical and numerical aspects of optimal control problems for first-order elliptic systems in three dimensions. The particular setting we used is that of div-curl systems. After formulating some optimization problems, we proved the existence and uniqueness of the optimal solution, demonstrated the existence of Lagrange multipliers, and derived an optimality system of partial differential equations from which optimal controls and states may be deduced. We then defined least-squares finite element approximations of the solution of the optimality system and derived optimal estimates for the error in these approximations. We have also formulated a penalty/least-squares method for optimal control problems for first-order elliptic systems wherein the constraint equations are enforced via penalization. The convergence, as the penalty parameter tends to zero, of the solution to the penalized optimal control problem to that unpenalized one is demonstrated as is the convergence of a gradient method for determining solutions of the penalized optimal control problem. Finally, finite element approximations of the penalized optimal control problem are studied and optimal error estimates are obtained.

Least-squares collocation methods

A finite element method for the approximation of solutions of linear, first-order elliptic systems in two-dimensional domains is considered. The method differs from most common least-squares finite element methods in that the discretization is effected prior to the application of a least squares method. Thus, in our approach, we discretize Galerkin-like weak forms of the first order equations, using different test and trial spaces. The test spaces are discontinuous across element egdes and a basis can be chosen consisting of functions having support over a single element. In this manner, the discretized equations are equivalent to a rectangular linear algebraic system which we solve by a least-squares method. Optimal error estimates are derived for piecewise linear finite element trial spaces. Numerical examples are provided that illustrate the theoretical convergence rates and that indicate that the method is easy to implement and is computationally efficient.

On least squares approximations to indefinite problems of the mixed type; Numer. Methods Engng. 12, 1978, 453-469; G. Fix and M. Gunzburger.

On finite element methods of the least squares type; Comput. Math. Appl. 5, 1979, 87-98; G. Fix, M. Gunzburger and R. Nicolaides

A least squares finite element scheme for transonic flow around harmonically oscillating airfoils; J. Comp. Phys. 51, 1983, 387-403; C. Cox, G. Fix and M. Gunzburger.

A finite element method for first order elliptic systems in three dimensions; Appl. Math. Comput. 23, 1987, 171-184; C. Chang and M. Gunzburger.

A subdomain Galerkin/least squares method for first order elliptic systems in the plane; SIAM J. Numer. Anal. 27, 1990, 1197-1211; C. Chang and M. Gunzburger.

A least-squares finite element method for the Navier-Stokes equations; Appl. Math. Lett. 6. 1993, 27-30; P. Bochev and M. Gunzburger.

The accuracy of least-squares methods for the Navier-Stokes equations; Comput. Fluids. 22, 1993, 549-563; P. Bochev and M. Gunzburger.

Analysis of least-squares finite element methods for the Stokes equations; Math. Comp. 63, 1994, 479-506; P. Bochev and M. Gunzburger.

Least-squares methods for the velocity-pressure-stress formulation of the Stokes equations; Comput. Methods Appl. Mech. Engng. 126, 1995, 267-287; P. Bochev and M. Gunzburger.

Least squares finite element methods for viscous, incompressible flows; Proc. Fluids Engineering Division Summer Meeting, FEDSM97-3487, ASME; P. Bochev and M. Gunzburger.

Least-squares finite element approximations to solutions of interface problems; SIAM J. Numer. Anal. 35, 1998, 393-405; Y. Cao and M. Gunzburger.

Issues related to least-squares finite element methods for the Stokes problem; SIAM J. Sci. Comput. 20, 1998, 878-906; J. Deang and M. Gunzburger.

Finite element methods of least squares type; SIAM Review 40, 1998, 789-837; P. Bochev and M. Gunzburger.

Analysis and approximation of optimal control problems for first-order elliptic systems in three dimensions; Appl. Math. Comp. 100, 1999, 49-70; M. Gunzburger and H.-C. Lee.

A penalty/least-squares method for optimal control problems for first-order elliptic systems; Appl. Math. Comp. 107, 2000 57-75; H.-C. Lee and M. Gunzburger.

Finite Element Methods of Least-Squares Type; in preparation; to appear in 2002; P. Bochev and M. Gunzburger.

Abstracts

G. Fix and M. Gunzburger

A least squares method is presented for computing approximate solutions of indefinite partial differential equations of the mixed type such as those that arise in connection with transonic flutter analysis. The method retains the advantages of finite difference schemes namely simplicity and sparsity of the resulting matrix system. However, it offers some great advantages over finite difference schemes. First, the method is insensitive to the value of the forcing frequency, i.e., the resulting matrix system is always symmetric and positive definite. As a result, iterative methods may be successfully employed to solve the matrix system, thus taking full advantage of the sparsity. Furthermore, the method is insensitive to the type of the partial differential equations, i.e., the computational algorithm is the same in elliptic and hyperbolic regions. In this work the method is formulated and numerical results for model prolbems are presented. Some theoretical aspects of least squares approximations are also discussed.

G. Fix, M. Gunzburger and R. Nicolaides

A theoretical framework for the least squares solution of first order elliptic systems is proposed, and optimal order error esitmates for piecewise polynomial spaces are derived. Numerical examples of the least squares method are also provided.

C. Cox, G. Fix and M. Gunzburger

A finite element scheme based on a least squares variational principle is used to calculate the transonic flow around harmonically oscillating airfoils. The most important features of this procedure are its insensitivity to equation type and the absence of frequency limitations. Sample numerical results are reported including transonic flows containing shocks.

C. Chang and M. Gunzburger

We consider finite element approximation schemes for boundary value problems for linear first order elliptic systems in three dimensions. We also discuss div-curl type systems in three independent variables. Both a least squares method and a new subdomain-collocation-least-squares method are considered. The analysis yields optimal asymptotic H¹ and L² error estimates.

C. Chang and M. Gunzburger

A finite element method for the approximation of solutions of linear, first-order elliptic systems in two-dimensional domains is considered. The method differs from previous techniques in that the discretization is effected prior to the application of a least squares method. Optimal error estimates in H¹ and L²-norms are derived for piecewise linear finite element trial spaces. Numerical examples are provided that illustrate the theoretical convergence rates and that indicate that the method is easy to implement and is computationally efficient.

P. Bochev and M. Gunzburger

A finite element method based on a least-squares variational principle is developed for the approximate solution of the stationary, incompressible Navier-Stokes equations. These equations are cast into a first-order system of partial differential equations involving the velocity, vorticity, and pressure as dependent variables. In three-dimensions one has seven unknown scalar fields. However, the application of a least-squares principle along with, for example, a Newton linearization, results in symmetric, positive definite, linear systems, at least in a neighborhood of the solution. Thus, if properly implemented, one can expect to only encounter symmetric, positive definite, linear systems in the solution procedure. A further advantage of this method is that a single piecewise polynomial finite element space may be used for all test and trial functions. A final advantaged resulting from the use of a least-squares principle is that, unlike some other methods involving the vorticity, no artificial numerical boundary conditions for the vorticity need be devised.

P. Bochev and M. Gunzburger

Recently there has been substantial interest in least-squares finite element methods for velocity-vorticity-pressure fromulations of the incompressible Navier-Stokes equations. The main cause for this interest is the fact that algorithms for the resulting discrete equations can be devised which require the solution of only symmetric, positive definite systems of algebraic equations. On the other hand, it is well-documented that methods using the vorticity as a primary variable often yield very poor approximations. Thus, here we study the accuracy of these method through a series of computational experiments, and also comment on theoretical error estimates. It is found, despite the failure of standard methods for deriving error estimates, that computational evidence suggests that these methods are, at the least, nearly optimally accurate. Thus, in addition to the desirable matrix properties yielded by least-squares methods, one also obtains accurate approximations.

P. Bochev and M. Gunzburger

In this paper we consider the application of least-squares principles to the approximate solution of the Stokes equations cast into a first-order velocity-vorticity-pressure system. Among the most attractive features of the resulting methods are that the choice of approximating spaces is not subject to the LBB condition and a single continuous piecewise polynomial space can be used for the approximation of all unknowns, that the resulting discretized problems involve only symmetric, positive definite systems of algebraic equations, that no artificial boundary conditions for the vorticity need be devised, and that accurate approximations are obtained for all variables, including the vorticity. Here we study two classes of least-squares methods for the velocity-vorticity-pressure equations. The first one uses norms prescribed by the a priori estimates of Agmon, Douglis, and Nirenberg and can be analyzed in a completely standard manner. However, conforming discretizations of these methods require C¹ continuity of the finite element spaces, thus negating the advantages of the velocity-vorticity-pressure fomulation. The second class uses weighted L²-norms of the residuals to circumvent this flaw. For properly choosen mesh-dependent weights, it is shown that the approximations to the solutions of the Stokes equations are of optimal order. The results of some computational experiments are also provided; these illustrate, among other things, the necessity of introducing the weights.

P. Bochev and M. Gunzburger

We formulate and study finite element methods for the solution of the incompressible Stokes equations based on the application of least-squares minimization principle to an equivalent first order velocity-pressure-stress system. Our least-squares functional involves the L²-norms of the residuals of each equation multiplied by a mesh-dependent weight. Each weight is determined according to the Agmon-Douglis-Nirenberg index of the corresponding equation. As a result, the approximating spaces are not subject to the LBB condition and conforming discretizations are possible with merely continuous finite element spaces. Moreover, the resulting discrete problems involve only symmetric, positive definite systems of linear equations, i.e., assembly of the discretization matrix is not required even at the element level. We prove that the least-squares approximations converge to the solution of the Stokes problem at the best possible rate and then present some numerical examples illustrating the theoretical results. Among other things, these numerical exmpales indicated that the method is not optimal without the weights in the least-squares functional.

P. Bochev and M. Gunzburger

In this paper we examine the use of least-squares variational principles for the numerical solution of the incompressible, steady state Navier-Stokes equations. In the last few years the corresponding least-squares finite element methods have been receiving increasing attention in both the engineering and mathematics communities. This interest has been largely motivated by the significant analytic and computational advantages offered by least-squares principles in the algorithmic design, that are not present in, e.g., mixed Galerkin discretizations. However, it is now well-understood that succesfull utilization of these advantages requires a thorough consideration of the settings for the least-squares method. As a result, most of the recent research has focused on applications of the least-squares methodology to the Navier-Stokes equation written in an equivalent first-order form. Besides the fact that the use of first-order systems helps to avoid the above two problems, it also has the significant added advantage of allowing direct approximations of physically meaningfull quantities such as vorticity and stress. Here, we give a necessarily brief outline of three basic first-order decomposition approaches that have been used in the context of least-squares methods. Then we describe the corresponding finite element methods and their respective properties.

Y. Cao and M. Gunzburger

A least-squares finite element method for second-order elliptic boundary value problems having interfaces due to discontinuous media properties is proposed and analyzed. Both Dirichlet and Neumann boundary data are treated. The boundary value problems are recast into a first-order formulation to which a suitable least-squares principle is applied. Among the advantages of the method are that nonconforming, with respect to the interface, approximating subspaces may be used. Moreover, the grids used on each side of an interface need not coincide along the interface. Error estimates are derived that improve on other treatments of interface problems and a numerical example is provided to illustrate the method and the analyses.

J. Deang and M. Gunzburger

Least-squares finite element methods have become increasingly popular for the approximate solution of first-order systems of partial differential equations. Here, after a brief review of some existing theories, a number of issues connected with the use of such methods for the velocity-vorticity-pressure formulation of the Stokes equations in two-dimensions in realistic settings are studied through a series of computational experiments. Finite element spaces that are not covered by existing theories are considered; included in these are piecewise linear approximations for the velocity. Mixed boundary conditions, which are also not covered by existing theories, are also considered. as is enhancing mass conservation. Next, problems in non-convex polygonal regions and the resulting non-smooth solutions are considered with a view towards seeing how accuracy can be improved. A conclusion that can be drawn from this series of computational experiments is that the use of appropriate mesh-dependent weights in the least-squares functional almost always improves the accuracy of the approximations. Concluding remarks concerning three-dimensional problems, the nonlinear Navier-Stokes equations, and the conditioning of the discrete systems are provided.

P. Bochev and M. Gunzburger

We consider the application of least-squares variational principles to the numerical solution of partial differential equations. Our main focus is on the development of least-squares finite element methods for elliptic boundary value problems arising in fields such as fluid flows, linear elasticity, and convection-diffusion. For many of these problems, least-squares principles offer numerous theoretical and computational advantages in the algorithmic design and implementation of corresponding finite element methods, that are not present in standard Galerkin discretizations. Most notably, the use of least-squares principles leads to symmetric and positive definite algebraic problems and allows one to circumvent stability conditions such as the inf-sup condition arising in mixed methods for the Stokes and Navier-Stokes equations. As a result, application of least-squares principles has led to the development of robust and efficient finite element methods for a large class of problems of practical importance.

H.-C. Lee and M. Gunzburger

We examine analytical and numerical aspects of optimal control problems for first-order elliptic systems in three dimensions. The particular setting we use is that of div-curl systems. After formulating some optimization problems, we prove the existence and uniqueness of the optimal solution. We then demonstrate the existence of Lagrange multipliers and derive an optimality system of partial differential equations from which optimal controls and states may be deduced. We then define least-squares finite element approximations of the solution of the optimality system and derive optimal estimates for the error in these approximations.

H.-C. Lee and M. Gunzburger

A penalty/least-squares method for optimal control problems for first-order elliptic systems is considered wherein the constraint equations are enforced via penalization. The convergence, as the penalty parameter tends to zero, of the solution to the penalized optimal control problem to that unpenalized one is demonstrated as is the convergence of a gradient method for determining solutions of the penalized optimal control problem. Finally, finite element approximations of the penalized optimal control problem are studied and optimal error estimates are obtained.

Return to

E-mail to Max Gunzburger

Last updated: December 10, 2001 by Max Gunzburger