Residual-Based Discretization Methods

General Framework

Many numerical methods for solving equations can be described from the viewpoint of the residual. Consider an operator equation

where is an operator between two function spaces. The unknown belongs to an infinite-dimensional function space , and the residual takes values in the space .

To compute an approximate solution, we introduce a finite-dimensional approximation space

and seek an approximate solution .

Define the residual

Two general strategies are commonly used to determine based on the residual .

Residual Constraints via Linear Functionals

One approach is to impose independent constraints on the residual using a family of linear functionals

The discrete problem is formulated as

Different numerical methods correspond to different choices of the functionals .

Galerkin-Type Methods

If the functionals are defined through inner products with elements of a test space

then

where forms a basis of .

The constraints become

This condition enforces the residual to be orthogonal to the test space,

There are two types of Galerkin-Type methods:

1. If , the method is the Galerkin (Bubnov–Galerkin) method. This formulation is widely used in finite element and spectral Galerkin methods.

2. If , the method is the Petrov–Galerkin method. Many stabilized numerical methods belong to this class, such as streamline upwind Petrov–Galerkin (SUPG) and discontinuous Petrov–Galerkin (DPG).

Collocation Methods

If the residual is a function, the functionals can be chosen as point evaluations,

the constraints become

This approach is known as the collocation method. In spectral methods it is commonly referred to as the pseudospectral method.

Optimization-Based Formulations

Another strategy is to determine as the solution of an optimization problem of the residual. For example, in residual minimization methods one solves

Many numerical methods can be interpreted in this framework, including least-squares formulations and various residual-minimization algorithms.

Assume that is a real Hilbert space, the norm is induced by its inner product, and is Fréchet differentiable. At a local minimizer over the linear space , the first-order necessary condition is

where denotes the derivative of the residual (the Jacobian in finite dimensions). This condition is not generally sufficient for a minimum when is nonlinear. It has a Petrov–Galerkin form with test space

This test space has dimension if is injective on ; otherwise its dimension may be smaller.

In certain contexts, such as reduced-order modeling, the resulting Petrov–Galerkin structure is referred to as the Least-Squares Petrov–Galerkin (LSPG) method.

Variational Methods (Ritz Methods)

The methods discussed in the previous section are designed for solving operator equations of the form

and are based on different ways of handling the residual. However, many problems in applied mathematics are not originally formulated as equations but as optimization problems. A typical formulation is

where is an energy functional.

Introducing a finite-dimensional approximation space , the discrete problem becomes

This approach is known as the Ritz method.

If the Euler–Lagrange equation associated with exists, the first-order optimality condition leads to

which coincides with a Galerkin formulation.

Spectral Methods

In spectral methods the approximate solution is expanded as

The spectral Galerkin method enforces

Alternatively, the collocation method which is commonly referred to as the pseudospectral method, leads to

where the nodes are typically chosen as special quadrature points such as Chebyshev or Legendre nodes.

Finite Element Methods

Consider a general operator equation

defined on a domain , together with appropriate boundary conditions. In the finite element framework, the solution is sought in a finite-dimensional trial space . The test space may either coincide with the trial space or be chosen differently,

The discrete problem is formulated in weak form: find such that

where denotes the residual and represents the chosen duality pairing. The method falls into one of the following categories:

1. If , the method is the standard Galerkin finite element method.

2. If , the method falls into the Petrov–Galerkin framework. Such formulations are often used to improve numerical stability or to incorporate additional modeling considerations.

Finite element methods are also classified according to the relation between the discrete space and the underlying function space of the weak formulation.

1. If , the method is called a conforming finite element method. In this case the discrete functions satisfy the regularity requirements of the weak formulation.

2. If the inclusion does not hold, , the method is called a nonconforming finite element method. Such methods typically enforce weaker continuity conditions while maintaining consistency.

Remark

In practice, the spaces and are typically constructed from locally supported basis functions defined on a mesh, for example piecewise polynomial functions on elements of a triangulation. If the discrete functions are allowed to be fully discontinuous across element interfaces, the formulation leads to discontinuous finite element methods, most notably discontinuous Galerkin (DG) methods.

Finite Difference Methods

Finite difference methods approximate derivatives by difference quotients on a grid. Let denote the vector of grid values, and let be the discrete residual formed with these difference operators and the discretized boundary conditions. The discrete equations enforce

at grid points. This has a collocation-like form for the discrete operator. It does not generally imply that the original continuous residual vanishes for a reconstructed function , because the difference operators have truncation errors.

Linear Systems and Krylov Methods

Consider the linear system

Suppose the approximate solution is written as

The residual is defined as

There are two categories:

1. Galerkin-type Krylov methods impose

   Copy LaTeX

   Examples include conjugate gradient (CG) methods.

2. Alternatively, minimal residual methods solve

   Copy LaTeX

   which leads to algorithms such as MINRES and GMRES.

Linear Reduced-Order Models

In linear model reduction, a high-dimensional dynamical system

is approximated using a linear low-dimensional subspace

where has orthonormal columns and are the reduced coordinates.

1. Galerkin projection. Substituting the approximation into the governing equation yields the time-continuous residual

   Copy LaTeX

   The Galerkin reduced model is obtained by requiring the residual to be orthogonal to the trial space,

   Copy LaTeX

   This leads to the reduced dynamical system

   Copy LaTeX

2. Least-Squares Petrov–Galerkin (LSPG). Instead of enforcing orthogonality of the time-discrete residual, LSPG minimizes the residual of a time-discrete system. For example, using a backward Euler discretization, the time-discrete residual is

   Copy LaTeX

   The reduced state is obtained by solving

   Copy LaTeX

   The corresponding optimality condition leads to a Petrov–Galerkin formulation in which the test space depends on the Jacobian of the residual.