Projection onto a given divergence

by Alec Johnson, June 13, 2007

1 Abstract Problem

1.1 Definitions

Let H denote a Hilbert space with inner product denoted by ⟨, ⟩ and norm ∥ · ∥ defined by ∥w∥ = ⟨w, w⟩^{1/2} ∀w.

1.2 Problem

Given vectors v and s, minimize ∥u − v∥^{2} subject to the constraint that div u = s.

1.3 Solution framework

Suppose that u is the minimizer. Let f = u+w also satisfy div f = s, i.e., div w = 0. Now ∥f −v∥^{2} = ∥(u−v)+w∥^{2} = ∥u − v∥^{2} + 2⟨u − v, w⟩ + ∥w∥^{2}. Since we could replace w with its opposite, this is minimized at w = 0 only if ⟨u − v, w⟩ = 0. (That is, u is the orthogonal projection of v onto the linear manifold of all f satisfying div f = s.)

In general we will claim that the minimizer u is specified by

(u − v) = grad λ,  (1)

where λ is restricted to belong to a class of functions satisfying the adjoint property

⟨grad λ, w⟩ = −⟨λ, div w⟩.  (2)

In each particular case, we show that λ will satisfy this adjoint property if we require λ to satisfy an appropriate Dirichlet boundary condition of the form λ = 0 on ∂Ω.

Since div w = 0, it is enough for there to exist a λ satisfying (8) and satisfying (7). Substituting (8) into the constraint div u = 0 gives the abstract Poisson equation

div grad λ = s − div v.  (3)

So the problem reduces to showing that there is a unique λ that solves the Poisson equation (9) from a class of vectors λ which satisfy the adjoint property (7).

2 Continuum problem

2.1 Definitions of continuum problem

Let Ω be a nice domain. For u, w vector fields on Ω, let ⟨u, w⟩ := ∫_{Ω} u · w.

2.2 Statement of continuum problem

Let v be a vector field on the domain Ω. Let σ be a desired divergence. Find u that minimizes ∥u − v∥^{2} subject to the constraint

that ∇ · u = σ in Ω.

2.3 Solution

For this continuum problem there exists a unique solution to the Poisson equation (9) with Dirichlet boundary conditions λ = 0 on ∂Ω, and such λ indeed satisfies the adjoint property (7):

⟨grad λ, w⟩ = ∫_{Ω}(∇λ) · w = ∫_{Ω} ∇ · (λw) − ∫_{Ω} λ∇ · w = −⟨λ, ∇ · w⟩, as needed.

3 Definitions for discrete calculus

Let ⟨f, g⟩_{a}^{b} = ∑_{i=a}^{b} f_{i}g_{i} denote a generalized inner product. Let E^{k} = f ↦ {f_{i+k}}_{i∈ℤ} be the shift operator. Let E^{+} :=

E^{+1} and E^{−} := E^{−1}. Let D^{+} := E^{+} − E^{0} Let D^{−} := E^{0} − E^{−}

Observe that ⟨f, g⟩_{a}^{b} = ⟨E^{k}f, E^{k}g⟩_{a−k}^{b−k}.

4 Staggered discrete 1D problem

4.1 Problem

Given the scalar sequences v = {v_{i}}_{i=1}^{m} and s = {s_{i}}_{i=1}^{m−1}, find u = {u_{i}}_{i=1}^{m} that minimizes ∥u − v∥ = ∑_{i=1}^{m}(u_{i} − v_{i})^{2}, subject to the constraint that (D^{+}u)_{i} = s_{i} for i = 1, …, (m − 1).

4.2 Solution

Adopt the following definitions

Let div = D^{+}. Let grad = D^{−}. Require that λ satisfy the Dirichlet boundary conditions

λ_{0} = 0 = λ_{m}.  (4)

We need to show that for such λ the following properties hold.

1. λ satisfies the adjoint property. Indeed,

⟨grad λ, w⟩ := ⟨D^{−}λ, w⟩_{1}^{m} = ⟨λ, w⟩_{1}^{m} − ⟨E^{−}λ, w⟩_{1}^{m} = ⟨λ, w⟩_{1}^{m} − ⟨λ, E^{+}w⟩_{0}^{m−1} = −⟨λ, D^{+}w⟩_{1}^{m−1} + λ_{m}w_{m} − λ_{0}w_{1} = 0, using (4) and div w = 0.

2. There is a unique λ that satisfies the Poisson equation (9).

To show this, we write out the Poisson equation (9) explictly as a linear system:

−λ_{i+1} + 2λ_{i} − λ_{i−1} = g_{i} for 1 ≤ i ≤ (m − 1), where g := div v − s.

Using the Dirichlet boundary conditions λ_{0} = 0 = λ_{m} and writing the system in matrix form, we see that we have a tridiagonal system:

[\begin{matrix}2 & −1 \\ −1 & 2 & ... \\ & ... & ... & ... \\ & & ... & 2 & −1 \\ & & & −1 & 2 \end{matrix}] [ λ_{1} ; λ_{2} ; ⋮ ; λ_{m−2} ; λ_{m−1}] = [ g_{1} ; g_{2} ; ⋮ ; g_{m−2} ; g_{m−1}]

5 Staggered discretized 1D problems

5.1 Staggered divergence problem

Find u that minimizes ∥u − v∥ := ∑_{i=1}^{m}(u_{i} − v_{i})^{2} subject to \frac{u_{i+1}−u_{i}}{dx} = s_{i+1/2} for i = 1, …, (m − 1).

Solution: Let s̃_{i} = (dx) s_{i+1/2}, and map onto the previous problem. (It’s also helpful to consider a mapping λ̃_{i} = λ_{i+1/2}.)

5.2 Staggered vector problem

Find u that minimizes ∥u − v∥ := ∑_{i=1}^{n}(u_{i−1/2} − v_{i−1/2})^{2} subject to \frac{u_{i+1/2}−u_{i−1/2}}{dx} = s_{i} for 1 ≤ i ≤ (n − 1).

Solution: Let ũ_{i} = u_{i−1/2}, let s̃ = (dx) s, let m = n − 1, and map onto the previous problem.

A Even/odd discrete 1D problem

A.1 Problem

Find u = {u_{i}}_{i=0}^{m+1} that minimizes ∥u − v∥ = ∑_{i=0}^{m+1}(u_{i} − v_{i})^{2}, subject to the constraint that (Du)_{i} = s_{i} for i = 1, …, m, where D := E^{+} − E^{−}.

A.2 Solution

Let n = m + 1. Let div : u ↦ {u_{i+1} − u_{i−1}}_{i=1}^{m} be the discrete divergence

operator. Let grad : λ ↦ {λ_{i+1} − λ_{i−1}}_{i=0}^{n} be the discrete gradient

operator. Let ⟨f, g⟩ := ⟨f, g⟩_{0}^{n} for f, g ∈ V and let ⟨λ, div f⟩ :=

⟨λ, div f⟩_{1}^{m} denote default inner products.

Impose the boundary conditions

0 = λ_{m+2} = λ_{m+1} and 0 = λ_{−1} = λ_{0},  (5)

For Section 1 to go through, we must verify the following two properties.

• We need that λ satisfies the adjoint property ⟨grad λ, w⟩ = 0, as in (7). Indeed: ⟨grad λ, w⟩ := ⟨grad λ, w⟩_{0}^{n} = ⟨E^{+}λ, w⟩_{0}^{n} − ⟨E^{−}λ, w⟩_{0}^{n} = ⟨λ, E^{−}w⟩_{1}^{n+1} − ⟨λ, E^{+}w⟩_{−1}^{n−1} = λ_{n+1}w_{n} + λ_{n}w_{n−1} − λ_{0}w_{1} − λ_{−1}w_{0} − ⟨λ, div w⟩_{1}^{m} = 0, using (5) and div w = 0.

This decouples the system into a pair of tridiagonal systems for even and odd indices.

• We need that

div grad λ = s − div v.  (6)

as in (9).

Writing out the system explicitly and using the Dirichlet boundary conditions gives a decoupled pair of tridiagonal systems for even and odd indices.

B Even/odd discretized 1-D problem

Let dx be the mesh size. Let div : u ↦ \{\frac{u_{i+1}−u_{i−1}}{2 dx} \}_{i=1}^{m} be the discrete divergence

operator. Let s = {s_{i}}_{i=1}^{m} be a desired discrete divergence. Let grad : λ ↦ \{\frac{λ_{i+1}−λ_{i−1}}{2 dx} \}_{i=0}^{n} be the discrete gradient

operator.

B.1 Problem

Find u = {u_{i}}_{i=0}^{n} that minimizes ∥u−v∥ = ∑_{i=0}^{n}(u_{i} −v_{i})^{2}. subject to the constraint that (div u)_{i} = s_{i} for i = 1, …, m.

Solution: Let s̃ = 2 dx s and map onto the previous problem.

C Derivation of solution using Lagrange multipliers

C.1 Statement of abstract problem

We recall the abstract problem: Given vectors v and s, minimize ∥u − v∥^{2} subject to the constraint that div u = s.

C.2 Derivation of solution

Use Lagrange multipliers. Let L(u, λ) = ∥u−v∥^{2}+2⟨λ, div u−s⟩. We seek a stationary point.

Set 0 = d_{ϵ}|_{ϵ=0}L(u, λ + ϵλ′) = 2⟨λ′, div u − s⟩. Since this must be true for arbitrary λ′, we recover the constraint equation div u = s.

Set 0 = d_{ϵ}|_{ϵ=0}L(u + ϵu′, λ) = d_{ϵ}|_{ϵ=0}(∥u + ϵu′ − v∥^{2} + 2⟨λ, div (u + ϵu′) − s⟩)

= d_{ϵ}|_{ϵ=0}(∥u − v∥^{2} + ϵ2⟨u′, u − v⟩ + ϵ^{2}∥u′∥^{2}) + 2⟨λ, div u′⟩ = 2⟨u′, u − v⟩ + 2⟨λ, div u′⟩.

At this point in the derivation one restricts u′ by requiring u′ to satisfy some appropriate kind of zero-value boundary condition so that.

⟨λ, div u′⟩ = −⟨grad λ, u′⟩.  (7)

So 0 = ⟨u′, u−v−grad λ⟩. Assume that there is still enough freedom in the choice of u′ to conclude that

u = v + grad λ.  (8)

Substituting this into the constraint equation div u = s gives

div grad λ = s − div v  (9)

This is a necessary condition to have a minimum. To pick out a single solution, we need to impose boundary conditions on this abstract Poisson equation. We derive these boundary conditions by attempting to show that u satisfying (8) and (9) is the minimum and seeing what additional assumptions we need.

Let f be another vector that satisfies the discrete divergence condition div f = s, and write f = u + w. So div w = 0. f = v + (grad λ) + w. Then ∥f − v∥^{2} = ∥grad λ + w∥^{2} = ⟨grad λ+w, grad λ+w⟩ = ∥grad λ∥^{2} +2⟨grad λ, w⟩+∥w∥^{2}. Since we could replace w with its opposite, this is minimized at w = 0 if and only if

⟨grad λ, w⟩ = 0.  (10)

So the key to minimizing distance is orthogonal projection. Indeed, observe that

⟨u − v, w⟩ = ⟨grad λ, w⟩ = 0  (11)

C.3 Statement of continuum problem

We recall the continuum problem:

Let v be a vector field on the domain Ω.

Let σ be a desired divergence.

Find u that minimizes ∥u − v∥^{2} subject to the constraint that ∇ · u = σ in Ω.

C.4 Solution

Use Lagrange multipliers.

Let L(u, λ) = ∫_{Ω}(u − v)^{2} + ∫_{Ω} 2λ(∇ · u − σ), where λ is a Lagrange multiplier function, and where dom(λ) = Ω.

We minimize L.

Perturbing the multipliers simply recovers the constraints. Let u′ be a test perturbation. d_{ϵ}|_{ϵ=0}L(u + ϵu′) = ∫_{Ω} 2(u − v) · u′ + ∫_{Ω} 2λ∇ · u′. The left hand side should be zero. If we impose u′ = 0 on

∂Ω, we get: 0 = ∫_{Ω} 2(u − v) · u′ − ∫_{Ω} 2∇λ · u′.

Since u′ is arbitrary, we get 0 = 2(u − v) − 2∇λ, i.e.,

u = v + ∇λ in Ω. (12)

Substituting this into the constraint equations gives the equation:

∇^{2}λ = σ − ∇ · v in Ω.  (13)

This is a necessary condition to have a minimum. To pick out a single solution, we need to impose boundary conditions on this Poisson equation. We derive these boundary conditions by attempting to show that u satisfying equations (12) and (13) is the minimum and seeing what additional assumptions are necessary.

Let f be another function that satisfies ∇ · f = σ, and write f = u + w = v + ∇λ + w. So ∇ · w = 0. Then ∥f − v∥^{2} = ∥∇λ + w∥^{2} = ⟨∇λ + w, ∇λ + w⟩ = ∥∇λ∥^{2} + 2⟨∇λ, w⟩ + ∥w∥^{2}. Since we could replace w with its opposite, this is minimized at w = 0 if and only if ⟨∇λ, w⟩ = 0. So the key to minimizing distance is orthogonal projection.

But ⟨∇λ, w⟩ = ∫_{Ω} ∇λ·w = ∫_{Ω} ∇·(λw)−∫_{Ω} λ \underbrace{∇ · w}_{0} = ∮_{∂Ω} n·

(λw), which equals 0 if we impose homogeneous Dirichlet boundary conditions, i.e., λ = 0 on ∂Ω.