10.12 Spectral Methods & the FFT ended with a list of things its transform trick cannot do: odd geometry, jumping coefficients, rough solutions. The finite element method (FEM) is built for exactly those. Finite differences ask the equation to hold at grid points; FEM asks it to hold on average against a family of test functions, which allows a mesh of any shape and coefficients as rough as the physics. It is how an airframe is simulated, and the matrix we assemble is the kind of object 10.9 Multigrid learned to solve fast. We work in one dimension first, where everything can be checked by hand, then look at triangles.
Transcript
- Take minus the derivative of a times u prime, equal to f, with u zero at both ends. Multiply by any test function v that vanishes at the ends, and integrate. Integration by parts moves one derivative onto v, and the boundary term disappears. What is left is the weak form: the integral of a u prime v prime equals the integral of f v, for every such v. It needs only one derivative of each function, so corners are allowed, and u minimizes an energy. A Dirichlet value is built into the space: essential. A flux condition appears as a boundary term, g times v at 1: natural.
- Galerkin's method searches a finite space, here continuous piecewise linear functions, and tests against the same space. Its basis is one hat function per interior node: height 1 at its own node, 0 at every other, so the unknowns are simply nodal values. Testing with each hat gives K u equals b, where K i j is the integral of a, phi i prime, phi j prime, and b i is the integral of f phi i. On a uniform mesh the diagonal is 2 over h and the neighbors are minus 1 over h: h times the finite difference matrix. Check an eigenvalue. With n equal to 10, the smallest is 9.951 for elements, 9.789 for differences, and the exact value is 9.870.
- Assembly visits each element once. An element of length h contributes a over h times the matrix 1, minus 1, minus 1, 1,. Take nodes 0, 0.25, 0.5 and 1, with a and f equal to 1. The three element lengths are 0.25, 0.25 and 0.5, so the scales are 4, 4 and 2. Node 1 touches elements 1 and 2, node 2 touches elements 2 and 3, so K is 8, minus 4, minus 4, 6. The load is 0.25 and 0.375. The determinant is 32, and the solution is 0.09375 and 0.125. The exact answer, x times 1 minus x, over 2, gives the same values at 0.25 and 0.5, to every digit, on an uneven mesh.
- Why? Let e be the exact solution minus its piecewise linear interpolant. It is zero at every node, and trial functions have constant slope on each element, so the integral of e prime times v prime is zero. The interpolant satisfies the Galerkin equations, so the finite element solution is exact at every node, on any mesh. For minus u double prime equals 1 at n equal to 8, the nodal error is 1.4 times 10 to the minus 17, uniform or graded. Load with nodal values h f of x i instead, and the error jumps to 1.3 times 10 to the minus 2, falling by 4.0 per doubling: the finite difference answer.
- How fast does the whole function converge? For sine pi x, a doubling of n divides the L2 error by 4, and the slope error, the H1 error, by 2. From n equal to 8 to 64, the L2 error falls from 9.92 times 10 to the minus 3 to 1.56 times 10 to the minus 4, order 2.00. The H1 error falls from 0.251 to 0.0315, order 1.00.
- Rough problems are where the weak form pays. A point load is simply b i equals phi i of c, and the nodal values are still exact. But with c equal to 0.4, inside an element, a straight line cannot follow the kink. From n equal to 16 to 64 the L2 error falls only from 2.17 times 10 to the minus 3 to 2.71 times 10 to the minus 4, order 1.5, and the H1 error from 0.1225 to 0.0612, order 0.5. A jumping coefficient, 1 then 10, does the same. With the interface at 0.5, a node, the nodal error is 2 times 10 to the minus 17. Move it to 0.4, inside an element, and the nodal error is 1.9 times 10 to the minus 3, and H1 falls only from 1.96 times 10 to the minus 2 to 1.03 times 10 to the minus 2. Align the mesh with material interfaces.
- In two dimensions an interval becomes a triangle. On a triangle of area A the element matrix is b i b j plus c i c j, over 4 A. Split a square grid by diagonals and assemble: an interior row has 4 on the diagonal and minus 1 for the four axis neighbors, the five-point stencil. On a square grid the method reproduces finite differences; on arbitrary triangles it generalizes them. Choose finite differences for simple geometry, finite volumes when conservation and shocks matter, and finite elements when geometry or coefficients are complicated. Next, Module 14 meets the same objects, mass and stiffness matrices for masses on springs, where K u equals lambda M u gives the normal modes.
From the strong form to the weak form
Take the model problem of 8.1 Two-Point Boundary Value Problems, with a variable coefficient (a conductivity, a stiffness, a viscosity):
This strong form asks for two derivatives of . Multiply by any smooth test function with and integrate; integration by parts moves one derivative onto :
The boundary term vanished because at both ends. This is the weak form. It needs one derivative of each function, so a continuous function with corners is allowed, yet for smooth it implies the strong form. It is also the stationarity condition of the energy
Perturbing, for admissible (the cross term is the weak form), so is the unique minimizer of . That is why the method’s error will be a best-approximation error.
Essential and natural conditions. The Dirichlet condition is imposed by allowing only functions that satisfy it: it is essential. If instead the right end has , the boundary term no longer vanishes and becomes on the right side; the minimizer satisfies the Neumann condition automatically: it is natural. In two and three dimensions the same step is Green’s first identity, from the divergence theorem of 2.10 Green, Stokes & the Divergence Theorem: .
Galerkin: choosing the pieces
Galerkin’s method picks a finite-dimensional space , searches for in it, and tests against the same space: find with for all . The space used here is the continuous, piecewise-linear functions on a mesh , zero at the ends. Its basis has one hat function per interior node:
Its height is at and at every other node, so . Hence has : the unknowns are nodal values and the solution is the straight-line interpolation between them. Testing with gives
is the stiffness matrix. It is symmetric, positive definite (a function with zero derivative and zero end values is zero), and tridiagonal, because hats overlap only with their neighbors. 10.8 Elliptic Solvers: Jacobi, Gauss–Seidel & SOR and multigrid solve such systems.
Stiffness, mass and load
On a uniform mesh on the two elements under the hat. With : , and , so
This is times the finite difference matrix of 10.1 Finite Differences: Discretizing Derivatives. For smooth the load is , since a hat has area . Divide row by and you get : the same equations, derived without a Taylor series. They differ only in how the right side is formed, and the lab shows that this is what separates them.
The same construction gives the mass matrix . On a uniform mesh and , so . It appears wherever there is no derivative: the heat equation becomes , and vibration the eigenproblem . Replacing by the diagonal of its row sums , mass lumping, gives back finite differences.
A check on eigenvalues (first playground below). For on the smallest eigenvalue is . With elements the generalized problem gives (FEM) and finite differences . In closed form, with ,
with relative errors and at leading order ( here). Finite element eigenvalues lie above the exact ones, finite difference ones below (the upper bound is the Rayleigh–Ritz principle, from memory).
Assembly, element by element
The standard loop visits each element once, builds a small matrix from its own geometry, and adds it into the global matrix at the element’s node numbers. For an element of length with mean coefficient ,
A shared node receives a contribution from each element (that is how arises); a nonuniform mesh needs no special treatment.
Worked example: three elements, nodes , with and . The lengths are , so the element matrices have scale . The interior unknowns are at and at . Node touches elements and ; node touches elements and :
The determinant is , so and . The exact solution of is , giving and . They agree to all digits, on a mesh with one coarse element and two fine ones. That is no accident.
Nodal exactness in one dimension
Let be the exact solution of () and its piecewise-linear interpolant. The difference is zero at every node. For any , is a constant on element , so
Then , so satisfies the Galerkin equations, and since they have one solution, : the finite element solution is the exact solution at every node, on any mesh, for any . It used two things: constant on each element, and exact load integrals. The error between the nodes is then only the error of straight-line interpolation, at most times the largest (standard, from memory). In two dimensions no such miracle exists, so nodal values are merely good.
The lab
Drag the interior nodes of anywhere. The nodal error stays at round-off: for on the uniform mesh and on the mesh graded as . For with exact load integrals it is at and at . Set the load vector to nodal values . The nodal error jumps to at and falls by a factor per doubling: , , at . That is the finite difference answer. For the whole function, a mesh helps only where it is fine where the solution bends: on at the graded mesh has error against uniform, being coarse near .
How fast does it converge?
Galerkin orthogonality, , says is the energy-closest function in to , so the error in is no larger than that of any other piecewise-linear function, in particular the interpolant. So for smooth :
- the (slope) error is first order, ;
- the error is second order, . Its proof (the Aubin–Nitsche duality argument) is omitted, but the numbers confirm it.
For the sim gives:
| 8 | 16 | 32 | 64 | |
|---|---|---|---|---|
| error | ||||
| error |
Each doubling divides the error by (order ) and the error by (order ). For the errors are explicit: on each element, so and : and at , as in the sim.
Rough problems: what the weak form buys
This keeps the previous lesson’s promise. A spectral method needs smoothness and a stencil needs two derivatives; the weak form needs neither.
A point load. Let , a concentrated force. The weak form is happy: . The exact solution is a tent with a kink at , and by nodal exactness the finite element answer is exact at every node for any (below in the sim at ). If is a node the whole tent is represented and every error is round-off. If lies inside an element (always, for and elements) the straight line cannot follow the kink:
| 16 | 64 | |
|---|---|---|
| error | ||
| error |
Over a factor in the error falls by (order ) and the error by (order ): half an order lost to the one element holding the kink. Put a node on the kink and the loss disappears.
A jumping coefficient. Let for and for (two materials), . The solution has a corner at the interface, since the flux is continuous but is not. Stiffness uses the exact mean of over each element. With a node on the interface (, even) the coefficient is constant on every element, nodal exactness applies, and the nodal error is at , with orders and in the other norms ( , at ). Move the interface to , inside an element: the nodal error is at and at , and the error falls only from to : the nodal argument’s hypothesis fails, and so does the rate. The rule: align the mesh with material interfaces.
Triangles in two dimensions
In two dimensions an interval becomes a triangle. The weak form of with on the boundary is . On a mesh of triangles the hat function is the continuous function that is linear on each triangle, equals at node and at the others (a pyramid; its gradient is constant on each triangle). For a triangle with vertices and area , let , , and , , . Then and
For legs (vertices ) this is , independent of . Split every square of a uniform grid by a diagonal and assemble. An interior node belongs to six triangles, and the row of the global matrix comes out as on the diagonal and for the four axis neighbors (the two diagonal neighbors cancel): the five-point stencil of 10.1 Finite Differences: Discretizing Derivatives, checked in the second playground cell below. On a square grid FEM reproduces finite differences; on arbitrary triangles it generalizes them. From memory: very small angles spoil the error bound, and Delaunay triangulation is the standard remedy.
FEM, finite differences and finite volumes
| Finite differences | Finite volumes | Finite elements | |
|---|---|---|---|
| Unknowns | point values | cell averages | coefficients of basis functions |
| Built from | Taylor series | flux balance on cells | weak form and test functions |
| Geometry | grid lines; awkward for curved walls | unstructured cells possible | unstructured meshes are the default |
| Rough coefficients | need averaging choices | via interface fluxes | align nodes with interfaces |
| Conservation | not built in | exact, cell by cell | global balance; local needs care |
| Shocks and advection | possible with upwinding | the natural home | needs stabilization (from memory) |
Choose finite differences for simple geometry, finite volumes when a conservation law with shocks is the point (10.10 The Finite Volume Method), spectral methods for smooth periodic boxes, and finite elements when the domain or coefficients are complicated or the problem is structural.
The exercise: assembling and solving
First a playground that builds and for and compares the eigenvalues, and a second that assembles triangles.
Concept checks
Problems
Solve on , , with linear elements on the nodes . Compare with the exact solution .
Show worked solution
The element matrices have scale , so and , . The determinant is . Then and . The exact values are and : nodal exactness again.
Solve with and using two equal elements, with unknowns at and . Show where the Neumann condition enters, and compare with .
Show worked solution
The node at is free, so the weak form gains the boundary term : the Neumann condition is used by adding nothing. With the stiffness is (the last node touches only one element) and the loads are , . The second row gives ; the first then gives , so and . The exact values are and .
Find for the triangle with vertices , , . Check that every row sums to zero, and say why.
Show worked solution
The area is . The three hat functions are , , , with gradients , , . Then , , , , , , and the matrix is symmetric. The rows sum to , and . The hats sum to the constant , whose gradient is zero.
What comes next
This ends the module: finite differences, finite volumes, spectral transforms and finite elements all turn a PDE into a matrix, and the matrices are close relatives. For fluid and flight simulation, the pressure solve of 11.10 The Projection Method for Incompressible Flow is one of these systems and a wing structure is another. The next lesson in the build, 14.1 Coupled Oscillators & Normal Modes, meets the mass and stiffness matrices again, for masses on springs: the eigenproblem gives the normal modes, and its continuum limit leads back to the wave equation.
Key Takeaways
- The weak form (test functions zero at Dirichlet ends) needs one derivative and is the minimizer of . Dirichlet conditions are essential, Neumann natural.
- Hat functions have , so unknowns are nodal values. is sparse, symmetric, positive definite; on a uniform mesh (finite difference matrix), and mass lumping gives the finite difference scheme.
- Assembly adds at each element’s nodes, on any spacing. At the smallest eigenvalue is (FEM), (FD), exact.
- For in 1D the linear-element solution is exact at every node on any mesh when the load integrals are exact; with nodal-value loads it is the second order finite difference answer.
- Smooth solutions converge at order in and in . A kink or jump inside an element costs half an order ( and for a point load at ); a node on it removes the loss.
- On triangles , and right triangles assemble into the five-point stencil. FEM suits complex geometry, rough coefficients and structures.
- Next: 14.1 Coupled Oscillators & Normal Modes, mass and stiffness matrices for masses on springs.