2

Galerkin Method
In this chapter, we discuss the fundamentals of the Galerkin method the idea of nite-dimensional approximation of the variational boundary-value problem (VBVP), the notion of the best approximation error, and an elementary approximation error analysis.

2.1

Finite-Dimensional Approximation of the VBVP

The space of test functions is a function space, and it is innite dimensional. In general, it takes an innite number of functions to approximate the unknown solution. Galerkin method approximates it with a nite number of linearly independent functions e i = e i (x) from test space V,
N

u(x) u0 (x) +
j=1

u j e j (x),

where the coefcients u j are to be determined. Functions e j are called the basis functions, and the unknown coefcients u j are called the global degrees of freedom (d.o.f.). The idea is very general, and we will discuss it in context of the abstract VBVP, using argumentless notation. Along with the solution, we use the same basis functions to approximate the test functions,
N N

u u0 +
j=1

uje j

v
l=1

vl e l .

We now substitute the approximations into the abstract VBVP: b u0 +

N N

vl e l = l

uje j,
j=1 l=1

vl e l .
l=1

(2.1)

The equation is to be satised for every test function which, for the nitedimensional approximation, translates into the condition: for every choice of
2007 by Taylor & Francis Group, LLC

33

34

Computing with hp-ADAPTIVE FINITE ELEMENTS

coefcients vl , l = 1, . . . , N. We select vl = li (Kroneckers delta) to arrive at a system of N algebraic equations: b u0 +

N

u j e j , e i = l(e i ),

i = 1, . . . , N.

j=1

Conversely, we can multiply the preceding equations with arbitrary coefcients vi , sum up wrt i, and use linearity of form l, and form b(u, v) wrt v, to arrive at the previous equation. The two formulations are thus equivalent. Additionally, if we also use the linearity of form b(u, v) in u (we are solving a linear problem), we realize that the algebraic equations are linear,
N

b( u0 , e i ) +
j=1

b(e j , e i )ui = l(e i ),

i = 1, . . . , N.

Function u0 representing a lift of Dirichlet data u0 is known, so it is advisable to move it to the right-hand side,
N

b(e j , e i )u j = l(e i ) b( u0 , e i ),
j=1

i = 1, . . . , N.

Matrix b i j = b(e j , e i ) will be called the (global) stiffness matrix, vector li = l(e i ) is the (global) load vector, and vector limod = l mod (e i ) = l(e i ) b( u0 , e i ) is the (global) modied load vector. To solve the approximate problem, we have to compute matrices B = {b i j }, lmod = {limod }, and solve the system of linear equations,
N

b i j u j = limod ,
j=1

i = 1, . . . , N,

(2.2)

or, using the matrix notation, Bu = lmod . Here, the unknown d.o.f. u j has been put into a vertical vector. Summing up, for determining the approximate solution, we need to:

Select lift u0 of Dirichlet data u0 Calculate the global stiffness matrix and the modied load vector Solve Equation 2.2

We can look at the Galerkin method more precisely using the language of vector spaces. Functions e j , j = 1, . . . , N span an N-dimensional subspace Vh of V. Index h is here an abstraction for a maximum element size, and it comes from the language of nite elements. Thus, by denition, functions e j indeed
2007 by Taylor & Francis Group, LLC

Galerkin Method

35

form a basis for space Vh . The Galerkin system of equations (Equation 2.1) can now be written in a more concise form of the approximate (abstract) variational boundary-value problem. uh u0 + Vh b(uh , vh ) = l(vh ), vh Vh .

(2.3)

In principle, approximate solution uh depends only upon the space Vh , and it is independent of the choice of basis functions e j , as long as they span the same approximate subspace. In practice, however, the choice of the basis functions affects the conditioning of the nal discrete system of equations and, because of round-off error effects, may signicantly inuence the actual approximate solution. When approximating a BVP, we construct a sequence of nite-dimensional spaces Vh , and solve the resulting linear systems for the corresponding approximate solution uh . In nite elements, these spaces correspond to different meshes that are rened to yield better and better approximations to the original problem. All discussed quantities basis functions e j = e h , dimenj sion N = Nh of Vh , global d.o.f. u j = uh , stiffness matrix, and load vector j depend upon index h. 2.1.1 PetrovGalerkin Method The discussed version of the Galerkin method is known as the Bubnov Galerkin method, in which both solution and test functions are approximated with the same basis functions. In a more general approach, known as Petrov Galerkin method, test functions are approximated using a different set of basis functions. The basis functions to approximate the solution are then called the trial basis functions, and those used for the test functions are known as the test basis functions. Specially selected test basis functions allow for improving stability properties of the Galerkin approximation for problems that lack such a stability to begin with, e.g., convection-dominated diffusion problems. In this monograph, however, we shall restrict ourselves to the BubnovGalerkin approach only. 2.1.2 Internal Approximation Approximate spaces Vh are assumed to be subspaces of the innite dimensional space of test functions V, i.e., basis functions e j belong to space V. This is called an internal approximation, and leads to conforming nite elements that are the subject of this monograph. In a more general version, functions e j may come from outside of space V. We then talk about external approximations of BVPs. The concept of internal and external approximations was introduced by Cea [45] in 1964.
2007 by Taylor & Francis Group, LLC

36

Computing with hp-ADAPTIVE FINITE ELEMENTS

2.1.3 Orthogonality Relation Substituting v = vh Vh in Equation 1.10 (we can do this because the approximation is internal, i.e., Vh V), and subtracting from it Equation 2.3, we obtain the famous orthogonality relation b(u uh , vh ) = 0 vh Vh . (2.4)

The orthogonality relation states that the approximation error e h = u uh is orthogonal (in the sense of bilinear form b(u, v)) to approximate test space Vh . 2.1.4 The Ritz Method In the case of a symmetric and positive denite bilinear form b(u, v), solution u to the variational problem can be obtained by solving the corresponding minimization problem, u u0 + V J(u) = 1 b(u, u) l(u) min. 2 Given the nite-dimensional approximate space Vh , it is natural to pose the corresponding nite-dimensional approximation minimization problem, uh u0 + Vh J(uh ) = 1 b(uh , uh ) l(uh ) min. 2 The idea of approximating the minimization problem is known as the Ritz method. As bilinear form b(u, v) preserves its properties on the nitedimensional level, the nite-dimensional minimization problem is equivalent with the approximate (abstract) VBVP, and the Ritz solution simply coincides with the Galerkin solution. The two methods are equivalent. The Galerkin procedure is more general, as it applies also to problems that do not admit the minimization principle.

2.2

Elementary Convergence Analysis

As we rene the mesh (mesh parameter h 0), dimension N of the approximate space grows to innity, and we expect the approximation error (function), e h = u uh , to get smaller. We can measure the error function using different norms. Although the choice of the norm is essentially up to us, some of them are naturally induced by the problem and the corresponding variational formulation.
2007 by Taylor & Francis Group, LLC

Galerkin Method

37

These include the energy norm and the (equivalent with energy norm) Sobolev (semi) norm of the rst order. 2.2.1 Symmetric Positive-Denite (SPD) Case Let u be the solution of the (abstract) VBVP, and wh u0 + Vh be any func tion (not necessarily the approximate solution). In the case of a symmetric, positive, denite bilinear form, we have the following algebraic identity. 2 ( J(wh ) J(u)) = b(wh , wh ) 2l(wh ) b(u, u) + 2l(u) = b(wh , wh ) b(u, u) + 2l(u wh ) = b(wh , wh ) b(u, u) + 2b(u, u wh ) = b(wh , wh ) + b(u, u) 2b(u, wh ) = b(u wh , u wh ) = u wh
2 E.

(2.5)

Twice the difference between the total potential energy corresponding to an approximation wh u0 + Vh and exact solution u is equal to the approxima tion error (squared) measured in the energy norm. Minimization of the total potential energy for the approximate solution is equivalent to the minimization of the energy norm of the approximation error 2 min J(wh ) J(u) = min u wh
2 E.

wh u0 +Vh

wh u0 +Vh

Consequently, the approximate solution uh is the best solution in terms of the energy norm u uh
2 E

wh u0 +Vh

min

u wh

2 E.

The quantity on the right-hand side is known as the best approximation error (with respect to energy norm), and it is equal to the actual approximation error. The result can also be shown in a different way using the orthogonality relation (Equation 2.4): u uh
2 E

= b(u uh , u uh ) = b(u uh , u wh ) + b(u uh , wh uh ) u uh

E

u wh

E,

where wh u0 + Vh is an arbitrary function. Notice that wh uh Vh , so we can use the orthogonality relation (Equation 2.4). Notice also that a symmetric positive-denite bilinear form denes a scalar product, so we can use the CauchySchwarz inequality (see Reference 175, p. 206).
2007 by Taylor & Francis Group, LLC

38

Computing with hp-ADAPTIVE FINITE ELEMENTS Consequently, owing to the arbitrariness of wh , u uh

E

wh u0 +Vh

min

u wh

E,

and, as substitution wh = uh is possible, we actually have the equality, u uh

E

wh u0 +Vh

min

u wh

E.

(2.6)

2.2.2 A General Positive-Denite Case In this case, form b(u, v) is no longer symmetric but it is still positive-denite on V, b(v, v) > 0 v V, v = 0.

The ellipticity condition (see discussion in the previous chapter) allows for assuming the stronger V-coercivity condition, b(v, v) v
2

v V,

(2.7)

where > 0 and denotes either the energy, or the rst-order Sobolev (semi) norm. We can also assume that the bilinear form is continuous with respect to the same norm, |b(u, v)| M v u . (2.8)

THEOREM 2.1 (Ceas Lemma) Let bilinear form b(u, v) be V-coercive and continuous. Let u and uh denote the exact and approximate solutions, respectively. Then: u uh M min u wh wh u0 +Vh (2.9)

where M and are the continuity and coercivity constants, respectively.

PROOF

We have: u uh
2

b(u uh , u uh ) = b(u wh , u wh ) + b(wh uh , u uh ) = b(u wh , u uh ) M u wh u uh

which implies the result. The result of Cea states that, in the discussed case, the approximation error is bounded by the best approximation error, premultiplied with a (possibly large, but) mesh-independent constant. Thus, up to that constant, the Galerkin method still delivers the best approximation.
2007 by Taylor & Francis Group, LLC

Galerkin Method

39

2.3

Comments

Notation. The notation for the bilinear form and the corresponding stiffness matrix denition suffers from the traditional inconsequence. In the denition of stiffness matrix, b i j = b(e j , e i ), the rst index corresponds to the test function, and the second to the trial functions. In the bilinear form notation, we have it the other way around rst trial and then test function. Some authors, e.g., Tom Hughes [131], have changed the abstract notation accordingly, and use b(v, u) or b(v; u) in place of b(u, v).

Exercises Exercise 2.1

Demonstrate that the Galerkin optimality result (Equation 2.6) generalizes to the complex case of a hermitian, positive denite form b(u, v), i.e., for the solution of the variational problem (Equation 1.10), with an arbitrary, antilinear form l(v) (see Subsection 1.6.4). Can you formulate an equivalent minimization problem in the complex case?

2007 by Taylor & Francis Group, LLC