SymmetricalDataSecurity: Galerkin Approximation

My first experience with the numerical solution of partial differential equations (PDEs) was with finite difference methods. I found finite difference methods to be somewhat fiddly: it is quite an exercise in patience to, for example, work out the appropriate fifth-order finite difference approximation to a second order differential operator on an irregularly spaced grid and even more of a pain to prove that the scheme is convergent. I found that I liked the finite element method a lot better as there was a unifying underlying functional analytic theory, Galerkin approximation, which showed how, in a sense, the finite element method computed the best possible approximate solution to the PDE among a family of potential solutions. However, I came to feel later that Galerkin approximation was, in a sense, the more fundamental concept, with the finite element method being one particular instantiation (with spectral methods, boundary element methods, and the conjugate gradient method being others). In this post, I hope to give a general introduction to Galerkin approximation as computing the best possible approximate solution to a problem within a certain finite-dimensional space of possibilities.

Systems of Linear Equations

Let us begin with a linear algebraic example, which is unburdened by some of the technicalities of partial differential equations. Suppose we want to solve a very large system of linear equations Ax = b , where the matrix is symmetric and positive definite (SPD). Suppose that is $N\times N$ where is so large that we don’t even want to store all components of the solution on our computer. What can we possibly do?

One solution is to consider only solutions lying in a subspace $\mathcal{X}$ of the set of all possible solutions $\mathbb{R}^N$ . If this subspace has a basis $x_1,x_2,\ldots,x_M \in \mathcal{X}$ , then the solution $x \in \mathcal{X}$ can be represented as $x = a_1x_1 + \cdots + a_Mx_M$ and one only has to store the M < N numbers $a_1,\ldots,a_M$ . In general, will not belong to the subspace $\mathcal{X}$ and we must settle for an approximate solution $\hat{x} \in \mathcal{X}$ .

The next step is to convert the system of linear equations Ax = b into a form which is more amenable to approximate solution on a subspace $\mathcal{X}$ . Note that the equation Ax = b encodes different linear equations $a_i^\top x = b_i$ where $a_i^\top$ is the th row of and b_i is the th element of . Note that the th equation is equivalent to the condition $e_i^\top A x = e_i^\top b$ , where e_i is the vector with zeros in all entries except for the th entry which is a one. More generally, by multiplying the equation Ax = b by an arbitrary test row vector $y^\top$ , we get $y^\top Ax = y^\top b$ for all $y \in \mathbb{R}^N$ . We refer to this as a variational formulation of the linear system of equations Ax = b . In fact, one can easily show that the variational problem is equivalent to the system of linear equations:

(1) $\begin{equation*} Ax = b \:\mbox{ if, and only if, }\: y^\top Ax = y^\top b \mbox{ for every } y \in \mathbb{R}^N. \end{equation*}$

Since we are seeking an approximate solution from the subspace $\mathcal{X}$ , it is only natural that we also restrict our test vectors to lie in the subspace $\mathcal{X}$ . Thus, we seek an approximate solution $\hat{x}$ to the system of equations Ax = b as the solution of the variational problem

(2) $\begin{equation*} y^\top A\hat{x} = y^\top b \mbox{ for every } y \in\mathcal{X}. \end{equation*}$

One can relatively easily show this problem possesses a unique solution $\hat{x}$ . In what sense is $\hat{x}$ a good approximate solution for Ax = b ? To answer this question, we need to introduce a special way of measuring the error to an approximate solution to Ax = b . We define the -inner product of a vector and to be $\langle x, y \rangle_A := y^\top Ax$ and the associated -norm $\|x\|_A = \sqrt{\langle x, x\rangle_A} = \sqrt{x^\top A x}$ . All of the properties satisfied by the familiar Euclidean inner product and norm carry over to the new -inner product and norm (e.g., the Pythagorean theorem). Indeed, for those familiar, one can show $\langle \cdot, \cdot \rangle_A$ satisfies all the axioms for an inner product space.

We shall now show that the error $x - \hat{x}$ between and its Galerkin approximation $\hat{x}$ is -orthogonal to the space $\mathcal{X}$ in the sense that $\langle y, x - \hat{x}\rangle_A = 0$ for all $y \in \mathcal{X}$ . This follows from the straightforward calculation, for $y \in \mathcal{X}$ ,

(3) $\begin{equation*} \langle y, x - \hat{x} \rangle_A = y^\top A (x - \hat{x}) = y^\top A x - y^\top A \hat{x} = y^\top b - y^\top b = 0, \end{equation*}$

where $y^\top A x = y^\top b$ since solves the variational problem Eq. (1) and $y^\top A \hat{x}$ since solves the variational problem Eq. (2).

The fact that the error $x - \hat{x}$ is -orthogonal to $\mathcal{X}$ can be used to show that $\hat{x}$ is, in a sense, the best approximate solution to Ax = b in the subspace $\mathcal{X}$ . First note that, for any approximate solution $z \in \mathcal{X}$ to Ax = b , the vector $\hat{x} - z \in \mathcal{X}$ is -orthogonal to $x - \hat{x}$ . Thus, by the Pythagorean theorem,

(4) $\begin{equation*} \|x - z\|^2_A = \|(x - \hat{x}) + (\hat{x}-z)\|_A^2 = \|x-\hat{x}\|_A^2 + \|\hat{x} - z\|_A^2 \ge \|x - \hat{x} \|_A^2. \end{equation*}$

Thus, the Galerkin approximation $\hat{x}$ is the best approximate solution to in the subspace $\mathcal{X}$ with respect to the -norm, $\|x - z\|_A \ge \|x - \hat{x} \|_A$ for every $z \in \mathcal{X}$ . Thus, if one picks a subspace $\mathcal{X}$ for which the solution almost lies in $\mathcal{X},$ then $\hat{x}$ will be a good approximate solution to Ax = b , irrespective of the size of the subspace $\mathcal{X}$ .

Variational Formulations of Differential Equations

As I hope I’ve conveyed in the previous section, Galerkin approximation is not a technique that only works for finite element methods or even just PDEs. However, differential and integral equations are one of the most important applications of Galerkin approximation since the space of all possible solution to a differential or integral equation is infinite-dimensional: approximation in a finite-dimensional space is absolutely critical. In this section, I want to give a brief introduction to how one can develop variational formulations of differential equations amenable to Galerkin approximation. For simplicity of presentation, I shall focus on a one-dimensional problem which is described by an ordinary differential equation (ODE) boundary value problem. All of this generalized wholesale to partial differential equations in multiple dimensions, though there are some additional technical and notational difficulties (some of which I will address in footnotes). Variational formulation of differential equations is a topic with important technical subtleties which I will end up brushing past. Rigorous references are Chapters 5 and 6 from Evans’ Partial Differential Equations or Chapters 0-2 from Brenner and Scott’s The Mathematical Theory of Finite Element Methods.

As our model problem for which we seek a variational formulation, we will focus on the one-dimensional Poisson equation, which appears in the study of electrostatics, gravitation, diffusion, heat flow, and fluid mechanics. The unknown is a real-valued function on an interval which take to be [0,1] . We assume Dirichlet boundary conditions that is equal to zero on the boundary u(0) = u(1) = 0 . Poisson’s equations then reads

(5) $\begin{equation*} -u''(x) = f(x) \mbox{ for every } x \in (0,1), \quad u(0) = u(1) = 0. \end{equation*}$

We wish to develop a variational formulation of this differential equation, similar to how we develop a variational formulation of the linear system of equations in the previous section. To develop our variational formulation, we take inspiration from physics. If u(x) represents, say, the temperature at a point , we are never able to measure u(x) exactly. Rather, we can measure the temperature in a region around with a thermometer. No matter how carefully we engineer our thermometer, our thermometer tip will have some volume occupying a region in space. The temperature $u_{\rm meas}$ measured by our thermometer will be the average temperature in the region or, more generally, a weighted average $u_{\rm meas} = \int_0^1 u(x) v(x) \, dx$ where $v(\cdot)$ is a weighting function which is zero outside the region . Now let’s use our thermometer to “measure” our differential equation:

(6) $\begin{equation*} \int_0^1-v(x) u''(x) \, dx = \int_0^1 v(x)f(x) \, dx. \end{equation*}$

This integral expression is some kind of variational formulation of our differential equation, as it is an equation involving the solution to our differential equation which must hold for every averaging function . (The precise meaning of every will be forthcoming.) It will benefit us greatly to make this expression more “symmetric” with respect to and . To do this, we shall integrate by parts:

(7) $\begin{equation*} \int_0^1-v(x)u''(x) \, dx = \int_0^1 v'(x)u'(x) \, dx - v(0) u'(0) - v(1)u'(1). \end{equation*}$

In particular, if is zero on the boundary v(0) = v(1) = 0 , then the second two terms vanish and we’re left with the variational equation

(8) $\begin{equation*} \int_0^1 v'(x)u'(x) \, dx = \int_0^1 v(x) f(x) \, dx \mbox{ for all \textit{nice} functions $v$ on $[0,1]$ with } v(0) = v(1) = 0. \end{equation*}$

Compare the variational formulation of the Poisson equation Eq. (8) to the variational formulation of the system of linear equations Ax = b in Eq. (1). The solution vector in the differential equation context is a function satisfying the boundary condition of being zero on the boundary u(0) = u(1) = 0 . The right-hand side is replaced by a function on the interval [0,1] . The test vector is replaced by a test function on the interval [0,1] . The matrix product expression $y^\top A x$ is replaced by the integral $\int_0^1 v'(x)u'(x) \, dx$ . The product $y^\top b$ is replaced by the integral $\int_0^1 v(x) f(x) \, dx$ . As we shall soon see, there is a unifying theory which treats both of these contexts simultaneously.

Before this unifying theory, we must address the question of which functions we will consider in our variational formulation. One can show that all of the calculations we did in this section hold if is a continuously differentiable function on [0,1] which is zero away from the endpoints and and is a twice continuously differentiable function on [0,1] . Because of technical functional analytic considerations, we shall actually want to expand the class of functions in our variational formulation to even more functions . Specifically, we shall consider all functions which are (A) square-integrable ( $\int_0^1|v(x)|^2 \,dx$ is finite), (B) possess a square integrable derivative ( $\int_0^1|v'(x)|^2 \,dx$ is finite), and (C) are zero on the boundary. We refer to this class of functions as the Sobolev space H_0^1((0,1)) .

Now this is where things get really strange. Note that it is possible for a function to satisfy the variational formulation Eq. (8) but for not to satisfy the Poisson equation Eq. (5). A simple example is when possesses a discontinuity (say, for example, a step discontinuity where is and then jumps to ). Then no continuously differentiable will satisfy Eq. (5) at every point in $\Omega$ and yet a solution to the variational problem Eq. (8) exists! The variational formulation actually allows us to give a reasonable definition of “solving the differential equation” when a classical solution to -u'' = f does not exist. Our only requirement for the variational problem is that , itself, belongs to the space H_0^1((0,1)) . A solution to the variational problem Eq. (8) is called a weak solution to the differential equation Eq. (5) because, as we have argued, a weak solution to Eq. (8) need not always solve Eq. (5).

The Lax-Milgram Theorem

Let us now build up an abstract language which allows us to use Galerkin approximation both for linear systems of equations and PDEs (as well as other contexts). If one compares the expressions $y^\top A x$ from the linear systems context and $\int_0^1 v'(x)u'(x) \, dx$ from the differential equation context, one recognizes that both these expressions are so-called bilinear forms: they depend on two arguments ( and or and ) and are a linear transformation in each argument independently if the other one is fixed. For example, if one defines $a(x,y) = y^\top A x$ one has $a(x,\alpha_1 y_1 + \alpha_2 y_2) = \alpha_1 a(x,y_1) + \alpha_2 a(x,y_2)$ . Similarly, if one defines $a(u,v) = \int_0^1 v'(x)u'(x) \, dx$ , then $a(\alpha_1 u_1 + \alpha_2 u_2,v) = \alpha_1 a(u_1,v) + \alpha_2 a(u_2, v)$ .

Implicitly swimming in the background is some space of vectors or function which this bilinear form $a(\cdot,\cdot)$ is defined upon. In the linear system of equations context, this space $\mathbb{R}^N$ of -dimensional vectors and in the differential context, this space is H_0^1((0,1)) as defined in the previous section. Call this space $\mathcal{V}$ . We shall assume that $\mathcal{V}$ is a special type of linear space called a Hilbert space, an inner product space (with inner product $\langle \cdot, \cdot \rangle_\mathcal{V}$ ) where every Cauchy sequence converges to an element in $\mathcal{V}$ (in the inner product-induced norm). The Cauchy sequence convergence property, also known as metric completeness, is important because we shall often deal with a sequence of entries $u_1,u_2,\ldots \in \mathcal{V}$ which we will need to establish convergence to a vector $u \in \mathcal{V}$ . (Think of $u_1,u_2,\ldots$ as a sequence of Galerkin approximations to a solution .)

With these formalities, an abstract variational problem takes the form

(9) $\begin{equation*} \mbox{Find $u \in \mathcal{V}$ such that }a(u,v) = \ell(v) \mbox{ for all } v \in \mathcal{V}, \end{equation*}$

where $a(\cdot,\cdot)$ is a bilinear form on $\mathcal{V}$ and $\ell(\cdot)$ is a linear form on $\mathcal{V}$ (a linear map $\ell: \mathcal{V} \to \mathbb{R}$ ). There is a beautiful and general theorem called the Lax-Milgram theorem which establishes existence and uniqueness of solutions to a problem like Eq. (9).

Theorem (Lax-Milgram): Let $a(\cdot,\cdot)$ and satisfy the following properties:

(Boundedness of ) There exists a constant $C \ge 0$ such that every $u,v \in \mathcal{V}$ , $|a(u,v)| \le C \|u\|_{\mathcal{V}}\|v\|_{\mathcal{V}}$ .
(Coercivity) There exists a positive constant such that $a(u,u) \ge c \|u\|_{\mathcal{V}}^2$ for every $u \in \mathcal{V}$ .
(Boundedness of $\ell$ ) There exists a constant such that $|\ell(v)| \le K \|v\|_{\mathcal{V}}$ for every $v\in \mathcal{V}$ .

Then the variational problem Eq. (9) possesses a unique solution.

For our cases, will also be symmetric a(u,v) = a(v,u) for all $u,v \in \mathcal{V}$ . While the Lax-Milgram theorem holds without symmetry, let us continue our discussion with this additional symmetry assumption. Note that, taken together, properties (1-2) say that the -inner product, defined as $\langle u, v \rangle_a = a(u,v)$ , is no more than so much bigger or smaller than the standard inner product $\langle u, v\rangle_{\mathcal{V}}$ of and .

Let us now see how the Lax-Milgram theorem can apply to our two examples. For a reader who wants a more “big picture” perspective, they can comfortably skip to the next section. For those who want to see Lax-Milgram in action, see the discussion below.

Applying the Lax-Milgram Theorem

Begin with the linear system of equations with

$\mathcal{V} = \mathbb{R}^N$

with inner product

$\langle x, y \rangle_{\mathbb{R}^N} = y^\top x$

$a(x,y) = y^\top Ax$

, and

$\ell(y) = y^\top b$

. Note that we have the inequality

$\lambda_{\rm min} x^\top x \le x^\top A x \le \lambda_{\rm max} x^\top x$

. In particular, we have that

$\|x\|_A = \sqrt{x^\top A x} \le \sqrt{\lambda_{\rm max}} \|x\|$

. Property (1) then follows from the

Cauchy-Schwarz inequality

applied to the

-inner product:

$|a(x,y)| = |\langle x, y\rangle_A| \le \|x\|_A \|y\|_A \le \lambda_{\rm max} \|x\|\|y\|$

. Property (2) is simply the established inequality

$a(x,x) = x^\top Ax \ge \lambda_{\min} = x^\top x$

. Property (3) also follows from the Cauchy-Schwarz inequality:

$|\ell(y)| = |y^\top b| \le \|b\|\|y\|$

. Thus, by Lax-Milgram, the variational problem

$y^\top Ax = y^\top b$

for

$y \in \mathbb{R}^N$

has a unique solution

. Note that the linear systems example shows why the coercivity property (2) is necessary. If

is positive semi-definite but not positive-definite, then there exists an eigenvector

with eigenvalue

. Then

$v^\top Av = 0 \not\ge c v^\top v$

for any positive constant

and

is singular, so the variational formulation of

has no solution for some choices of the vector

Applying the Lax-Milgram theorem to differential equations can require powerful inequalities. In this case, the $\mathcal{V} = H_0^1((0,1))$ -inner product is given by $\langle u, v \rangle_{H_0^1((0,1))} = \int_0^1 v(x)u(x) + v'(x)u'(x) \, dx$ , $a(u,v) = \int_0^1 v'(x)u'(x) \, dx$ , and $\ell(v) = \int_0^1 v(x)f(x) \, dx$ . Condition (1) is follows from a application of the Cauchy-Schwarz inequality for integrals:

(10) $\begin{equation*} \begin{split} |a(u,v)| &\le \int_0^1 |v'(x)||u'(x)| \, dx \\ &\le \left(\int_0^1 |v'(x)|^2 \, dx\right)^{1/2} \left(\int_0^1 |u'(x)|^2 \, dx\right)^{1/2} \\ &\le \|v\|_{H_0^1((0,1))}\|u\|_{H_0^1((0,1))}. \end{split} \end{equation*}$

Let’s go line-by-line. First, we note that the absolute value of integral is less than the integral of absolute value. Next, we apply the Cauchy-Schwarz inequality for integrals. Finally, we note that $\int_0^1|v'(x)|^2 \, dx \le \int_0^1|v(x)|^2 + |v'(x)|^2 \, dx = \langle v, v\rangle_{H_0^1((0,1))} = \|v\|_{H_0^1((0,1))}^2$ . This establishes Property (1) with constant C = 1 . As we already see one third of the way into verifying the hypotheses of Lax-Milgram, establishing these inequalities can require several steps. Ultimately, however, strong knowledge of just a core few inequalities (e.g. Cauchy-Schwarz) may be all that’s needed.

Proving coercivity (Property (2)) actually requires a very special inequality, Poincaré’s inequality. In it’s simplest incarnation, the inequality states that there exists a constant such that, for all functions $u \in H_0^1((0,1))$ ,

(11) $\begin{equation*} \int_0^1|u'(x)|^2 \, dx \ge k\int_0^1|u(x)|^2 \, dx. \end{equation*}$

With this inequality in tow, property (2) follows after another lengthy string of inequalities:

(12) $\begin{equation*} \begin{split} a(u,u) &= \int_0^1 |u'(x)|^2 \, dx \\ &= \frac{1}{2} \int_0^1 |u'(x)|^2 \, dx + \frac{1}{2} \int_0^1 |u'(x)|^2 \, dx \\ &\ge \frac{1}{2} \int_0^1 |u'(x)|^2 \, dx + \frac{k}{2} \int_0^1 |u(x)|^2 \, dx \\ &\ge \min \left(\frac{1}{2},\frac{k}{2}\right) \left( \int_0^1 |u'(x)|^2 \, dx + \int_0^1|u(x)|^2 \, dx\right) \\ &= \min \left(\frac{1}{2},\frac{k}{2}\right) \|u\|_{H_0^1((0,1))}^2. \end{split} \end{equation*}$

For Property (3) to hold, the function must be square-integrable. With this hypothesis, Property (3) is much easier than Properties (1-2) and we leave it as an exercise for the interested reader (or to a footnote for the uninterested reader).

This may seem like a lot of work, but the result we have achieved is stunning. We have proven (modulo a lot of omitted details) that the Poisson equation -u'' = f has a unique weak solution as long as is square-integrable! What is remarkable about this proof is that it uses the Lax-Milgram theorem and some inequalities alone: no specialized knowledge about the physics underlying the Poisson equation were necessary. Going through the details of Lax-Milgram has been a somewhat lengthy affair for an introductory post, but hopefully this discussion has illuminated the power of functional analytic tools (like Lax-Milgram) in studying differential equations. Now, with a healthy dose of theory in hand, let us return to Galerkin approximation.

General Galerkin Approximation

With our general theory set up, Galerkin approximation for general variational problem is the same as it was for a system of linear equations. First, we pick an approximation space $\mathcal{X}$ which is a subspace of $\mathcal{V}$ . We then have the Galerkin variational problem

(13) $\begin{equation*} \mbox{Find $\hat{u} \in \mathcal{X}$ such that } a(\hat{u},v) = \ell(v) \mbox{ for every } v \in \mathcal{X}. \end{equation*}$

Provided and $\ell$ satisfy the conditions of the Lax-Milgram theorem, there is a unique solution $\hat{u}$ to the problem Eq. (13). Moreover, the special property of Galerkin approximation holds: the error $u-\hat{u}$ is -orthogonal to the subspace $\mathcal{X}$ . Consequently, $\hat{u}$ is te best approximate solution to the variational problem Eq. (9) in the -norm. To see the -orthogonality, we have that, for any $v \in \mathcal{X}$ ,

(14) $\begin{equation*} \langle u-\hat{u}, v\rangle_a = a(u-\hat{u},v) = a(u,v) - a(\hat{u},v) = \ell(v) - \ell(v) = 0, \end{equation*}$

where we use the variational equation Eq. (9) for $a(u,v) = \ell(v)$ and Eq. (13) for $a(\hat{u},v) = \ell(v)$ . Note the similarities with Eq. (3). Thus, using the Pythagorean theorem for the -norm, for any other approximation solution $w \in \mathcal{X}$ , we have

(15) $\begin{equation*} \|u - w\|^2_a = \|(u - \hat{u}) + (\hat{u}-w)\|_a^2 = \|u-\hat{u}\|_a^2 + \|\hat{u} - w\|_a^2 \ge \|u - \hat{u} \|_a^2. \end{equation*}$

Put simply, $\hat{u}$ is the best approximation to in the -norm.

Galerkin approximation is powerful because it allows us to approximate an infinite-dimensional problem by a finite-dimensional one. If we let $\phi_1,\ldots,\phi_M$ be a basis for the space $\mathcal{X}$ , then the approximate solution $\hat{u}$ can be represented as $\hat{u} = x_1 \phi_1 + \cdots + x_M \phi_M$ . Since $\phi_1,\ldots,\phi_N$ form a basis of $\mathcal{X}$ , to check that the Galerkin variational problem Eq. (13) holds for all $v \in \mathcal{X}$ it is sufficient to check that it holds for $v = \phi_1, v=\phi_2,\ldots,v=\phi_M$ . Thus, plugging in $\hat{u} = \sum_{j=1}^M x_j \phi_j$ and $v = \phi_i$ into Eq. (13), we get (using bilinearity of )

(16) $\begin{equation*} a(\hat{u},v) = a\left(\sum_{j=1}^M x_j \phi_j, \phi_i\right) = \sum_{j=1}^M a(\phi_j,\phi_i) x_j = \ell(v) = \ell(\phi_i), \quad i =1,2,\ldots,M. \end{equation*}$

If we define $a_{ij} = a(\phi_j,\phi_i)$ and $b_i = \ell(\phi_i)$ , then this gives us a matrix equation Ax = b for the unknowns $x_1,\ldots,x_M$ parametrizing $\hat{u}$ . Thus, we can compute our Galerkin approximation by solving a linear system of equations.

We’ve covered a lot of ground so let’s summarize. Galerkin approximation is a technique which allows us to approximately solve a large- or infinite-dimensional problem by searching for an approximate solution in a smaller finite-dimensional space $\mathcal{X}$ of our choosing. This Galerkin approximation is the best approximate solution to our original problem in the -norm. By choosing a basis $\phi_1,\ldots,\phi_M$ for our approximation space $\mathcal{X}$ , we reduce the problem of computing a Galerkin approximation to a linear system of equations.

Design of a Galerkin approximation scheme for a variational problem thus boils down to choosing the approximation space $\mathcal{X}$ and a basis $\phi_1,\ldots,\phi_M$ . Picking $\mathcal{X}$ to be a space of piecewise polynomial functions (splines) gives the finite element method. Picking $\mathcal{X}$ to be a space spanned by a collection of trigonometric functions gives a Fourier spectral method. One can use a space spanned by wavelets as well. The Galerkin framework is extremely general: give it a subspace $\mathcal{X}$ and it will give you a linear system of equations to solve to give you the best approximate solution in $\mathcal{X}$ .

Two design considerations factor into the choice of space $\mathcal{X}$ and basis $\phi_1,\ldots,\phi_M$ . First, one wants to pick a space $\mathcal{X}$ , where the solution almost lies in. This is the rationale behind spectral methods. Smooth functions are very well-approximated by short truncated Fourier expansions, so, if the solution is smooth, spectral methods will converge very quickly. Finite element methods, which often use low-order piecewise polynomial functions, converge much more slowly to a smooth . The second design consideration one wants to consider is the ease of solving the system Ax = b resulting from the Galerkin approximation. If the basis function $\phi_1,\ldots,\phi_M$ are local in the sense that most pairs of basis functions $\phi_i$ and $\phi_j$ aren’t nonzero at the same point (more formally, $\phi_i$ and $\phi_j$ have disjoint supports for most and ), the system Ax = b will be sparse and thus usually much easier to solve. Traditional spectral methods usually result in a harder-to-solve dense linear systems of equations. It should be noted that both spectral and finite element methods lead to ill-conditioned matrices , making integral equation-based approaches preferable if one needs high-accuracy. Integral equations, themselves, are often solved using Galerkin approximation, leading to so-called boundary element methods.

Upshot: Galerkin approximation is a powerful and extremely flexible methodology for approximately solving large- or infinite-dimensional problems by finding the best approximate solution in a smaller finite-dimensional subspace. To use a Galerkin approximation, one must convert their problem to a variational formulation and pick a basis for the approximation space. After doing this, computing the Galerkin approximation reduces down to solving a system of linear equations with dimension equal to the dimension of the approximation space.

from Hacker News https://ift.tt/3tWT8WB

SymmetricalDataSecurity

Saturday, March 27, 2021

Galerkin Approximation

Systems of Linear Equations

Variational Formulations of Differential Equations

The Lax-Milgram Theorem

General Galerkin Approximation

No comments:

Post a Comment

Blog Archive

Search This Blog

Total Pageviews