A Posteriori Error Estimation

1. Motivations & Preliminaries

1.1. « Truth » Problem statement

Let $\mu \in \mathcal{D}^{\mu}$ , evaluate $\displaystyle s (\mu) = \ell (u (\mu))$ where $u (\mu) \in X$ satisfies $a (u (\mu), v; \mu ) = f (v), \quad \forall \: v \in X$ .

Assumptions :

linearity, coercivity, continuity
affine parameter dependence; and
compliance: $\ell=f$ , $a$ symmetric

1.2. Reduced Basis Sample and Space

Parameter Samples: $S_N = \{ \mu_1 \in \mathcal{D}^{\mu}, \ldots, \mu_N \in \mathcal{D}^{\mu} \}\quad 1 \leq N \leq N_{\mathrm{max}}$ , with $S_1 \subset S_2 \ldots S_{N_\mathrm{max}-1} \subset S_{N_\mathrm{max}} \subset \mathcal{D}^\mu$ .

Lagrangian Hierarchical Space $W_N = {\rm span} \: \{ \xi^n \equiv \underbrace{ u (\mu^n)}_{u^{\mathcal{N}} (\mu^n)}, n = 1, \ldots, N \}$ , with $W_1 \subset W_2 \ldots \subset W_{N_\mathrm{max}} \subset X^{\mathcal{N}} \subset{X}$

1.3. Reduced basis approximation

Given $\mu \in \mathcal{D}^{\mu}$ evaluate $s_N (\mu) = f(u_N (\mu);\mu)$ where $u_N (\mu) \in X_N$ satisfies $a (u_N (\mu), v; \mu) = f(v;\mu), \ \forall \: v \in X_N$ .

Recall:

RB Space: $X_N=« \text{Gram-Schmidt} »(W_N)$
$u_N(\mu)$ unique (coercivity, continuity, linear dependence)

1.4. Coercivity and Continuity Constants

We assume $a$ coercive and continuous

Recall that

coercivity constant $(0 < ) \alpha(\mu) \equiv \inf_{v\in X}\dfrac{a(v,v;\mu)}{||v||^2_X}$ ,
continuity constant $\gamma(\mu) \equiv \sup_{w\in X} \sup_{v\in X}\dfrac{a(w,v;\mu)}{\|w\|_X \|v\|_X} ( < \infty)$

Affine dependence and parametric coercivity We assume that $a: X\times X \times \mathcal{D} \rightarrow \mathbb{R}$ is

affine : $a(u,v;\mu) = \displaystyle\sum_{q=1}^{Q_a} \Theta^q_a(\mu)\ a^q( u, v ),\, \forall u,v \in X$
and paraletrically coercive : $\Theta^q_a(\mu) > 0\quad \forall \mu \in \mathcal{D}, \, 1 \leq q \leq Q_a$ and $a^q(u,v) \geq 0\quad \forall u,v \in X, \, 1 \leq q \leq Q_a$

1.5. Inner Products and Norms

energy inner product and associated norm (parameter dependant)

$\begin{aligned} (((w,v)))_\mu &= a(w,v;\mu) &\ \forall u,v \in X\\ |||v|||_\mu &= \sqrt{a(v,v;\mu)} &\ \forall v \in X \end{aligned}$

$X$ -inner product and associated norm (parameter independant)

$\begin{aligned} (w,v)_X &= (((w,v)))_{\bar{\mu}} \ (\equiv a(w,v;\bar{\mu})) &\ \forall u,v \in X\\ ||v||_X &= |||v|||_{\bar{\mu}} \ (\equiv \sqrt{a(v,v;\bar{\mu})}) & \ \forall v \in X \end{aligned}$

2. Bound theorems

2.1. Questions

What is the accuracy of $u_N(\mu)$ and $s_N(\mu)$ ? Online

$\begin{aligned} \|u(\mu)-u_N(\mu)\|_X &\leq \epsilon_{\mathrm{tol}}, \quad \forall \mu \in \mathcal{D}^\mu\\ |s(\mu)-s_N(\mu)\|_X &\leq \epsilon^s_{\mathrm{tol}}, \quad \forall \mu \in \mathcal{D}^\mu\\ \end{aligned}$

What is the best value for $N$ ? Offline/Online
- $N$ too large $\Rightarrow$ computational inefficiency
- $N$ too small $\Rightarrow$ unacceptable error
How should we build $S_N$ ? is there an optimal construction ? Offline
- Good approximation of the manifold $\mathcal{M}$ through the RB space, but
- need for well conditioned RB matrices

2.2. A Posteriori Error Estimation: Requirements

We shall develop the following error bounds $\Delta_N(\mu)$ and $\Delta^s_N(\mu)$ with the following properties

Rigorous : $1 \leq N \leq N_{\mathrm{max}}$ ,

$\begin{aligned} \|u(\mu)-u_N(\mu)\|_X &\leq \Delta_N(\mu), \quad \forall \mu \in \mathcal{D}^\mu\\ |s(\mu)-s_N(\mu)| &\leq \Delta^s_N(\mu), \quad \forall \mu \in \mathcal{D}^\mu \end{aligned}$

reasonably sharp $1 \leq N \leq N_{\mathrm{max}}$

$\begin{gathered} \frac{\Delta_N(\mu)}{\|u(\mu)-u_N(\mu)\|_X} \leq C,\\ \frac{\Delta^s_N(\mu)}{|s(\mu)-s_N(\mu)|} \leq C,\\C\approx 1 \end{gathered}$

efficient : Online cost depend only on $Q$ and $N$ and not $\mathcal{N}$ .

2.3. $u_N(\mu)$ : Error equation and residual dual norm

Given our RB approximation $u_N(\mu)$ , we have $e(\mu) \equiv u(\mu) - u_N(\mu)$ that satisfies $a( e(\mu), v; \mu ) \ = \ r( u_N(\mu), v; \mu ), \forall v \in X$ , where $r( u_N(\mu), v; \mu ) = f(v) - a( u_N(\mu), v; \mu )$ is the residual. We have then from coercivity and the definitions above that

$||e(\mu)||_{X} \ \leq\ \dfrac{||r( u_N(\mu), v; \mu )||_{X'}}{\alpha(\mu)}\ =\ \dfrac{\varepsilon_N(\mu)}{\alpha(\mu)}$

2.4. Dual norm of the residual

Proposition

Given $\mu \in \mathcal{D}^\mu$ , the dual norm of $r(u_N(\mu),\cdot;\mu)$ is defined as follows

$\begin{aligned} ||r(u_N(\mu),\cdot;\mu)||_{X'} & \equiv \sup_{v\in X} \frac{r(u_N(\mu),v;\mu)}{||v||_X}\\ & = ||\hat{e}(\mu)||_X \end{aligned}$

where $\hat{e}(\mu)\in X$ satisfies $(\hat{e}(\mu),v)_X = r(u_N(\mu),v;\mu)$

The error residual equation can then be rewritten $a( e(\mu), v; \mu ) \ = (\hat{e}(\mu),v)_X, \quad \forall v \in X$

2.5. $u_N(\mu)$ : Definitions of energy error bounds and effectivity

Given $\alpha_\mathrm{LB}(\mu)$ a nonnegative lower bound of $\alpha(\mu)$ :

$\alpha(\mu)\geq {\alpha_{{\mathrm{LB}}}}(\mu)\geq \epsilon_{\alpha} \alpha(\mu), \epsilon_{\alpha} \in ]0,1[,\, \forall \mu \in \mathcal{D}^\mu$

Denote $\varepsilon_N(\mu) = \|\hat{e}(\mu)\|_X = \|r(u_N(\mu),v;\mu\|_{X'}$

Definition : Energy error bound

$\Delta^{\mathrm{en}}_N(\mu) \ \equiv \ \frac{\varepsilon_N(\mu)}{\sqrt{{\alpha_{{\mathrm{LB}}}}(\mu)}}$

Definition : Effectivity

$\eta^{\mathrm{en}}_N(\mu) \ \equiv \ \frac{\Delta^{\mathrm{en}}_N(\mu)}{|||e(\mu)|||_\mu}$

Proposition : Energy error bound

$1 \ \leq\ \eta^{\mathrm{en}}_N(\mu) \ \leq \sqrt{\frac{{\gamma_{{\mathrm{UB}}}}(\mu)}{{\alpha_{{\mathrm{LB}}}}(\mu)}}, \quad 1 \leq N \leq N_{\max}, \quad \forall \mu\ \in \ \mathcal{D}^\mu$

Remarks :

Rigorous : Left inequality ensures rigorous upper bound measured in $||\cdot||_{X}$ , i.e. $||e(\mu)||_{X} \leq \Delta_N(\mu),\ \forall \mu \in \mathcal{D}^\mu$
Sharp : Right inequality states that $\Delta_N(\mu)$ overestimates the « true » error by at most $\gamma(\mu) / {\alpha_{{\mathrm{LB}}}}(\mu)$
for $a$ paralmetrically coercive and symmetric

$\theta^{\bar{\mu}} \equiv \frac{\Theta^{\max,\bar{\mu}}_a(\mu)}{\Theta^{\min,\bar{\mu}}_a(\mu)} = \frac{\gamma_{\mathrm{ub}}(\mu)}{\alpha_{\mathrm{lb}}(\mu)}$

2.6. $s_N(\mu)$ : output error bounds

Proposition : Output error bound

$1 \ \leq\ \eta^s_N(\mu) \ \leq \dfrac{{\gamma_{{\mathrm{UB}}}}(\mu)}{{\alpha_\mathrm{LB}}(\mu)}, \quad 1 \leq N \leq N_{\max}, \quad \forall \mu\ \in \ \mathcal{D}^\mu$

where $\Delta^s_N (\mu) = {\Delta_N^{\mathrm{en}}}(\mu)^2$ and $\eta^s_N(\mu)\equiv \frac{\Delta^s_N(\mu)}{s(\mu)-s_N(\mu)}$

Rapid convergence of the error in the output : Note that the error in the output vanishes quadratically

2.7. Relative output error bounds

We define

the relative output error bound $\Delta^{s,rel}_N (\mu) \equiv \frac{\|\hat{e}(\mu)\|^2_X}{ \alpha_\mathrm{lb}(\mu) s_N(\mu)}= \frac{\Delta_N^{\mathrm{en}}(\mu)^2}{s_N(\mu)}$
the relative output effectivity $\eta^{s,rel}_N(\mu)\equiv \frac{\Delta^{s,rel}_N(\mu)}{s(\mu)-s_N(\mu)/s(\mu)}$

Proposition : Relative output error bound

$1 \ \leq\ \eta^{s,rel}_N(\mu) \ \leq 2 \frac{{\gamma_{{\mathrm{UB}}}}(\mu)}{{\alpha_{{\mathrm{LB}}}}(\mu)}, \quad 1 \leq N \leq N_{\max}, \quad \forall \mu\ \in \ \mathcal{D}^\mu$

for $\Delta^{s,rel}_N \leq 1$

2.8. $X$ -norm error bounds

We define

the relative output error bound $\Delta_N (\mu) \equiv \frac{\|\hat{e}(\mu)\|_X}{\alpha_\mathrm{lb}(\mu)}$
the relative output effectivity $\eta_N(\mu)\equiv \frac{\Delta_N(\mu)}{\|e(\mu)\|_X}$

Proposition : Relative output error bound

$1 \ \leq\ \eta_N(\mu) \ \leq \frac{{\gamma_{{\mathrm{UB}}}}(\mu)}{{\alpha_{{\mathrm{LB}}}}(\mu)}, \quad 1 \leq N \leq N_{\max}, \quad \forall \mu\ \in \ \mathcal{D}^\mu$

2.9. Remarks on error bounds

The error bounds are rigorous upper bounds for the reduced basis error for any $N = 1,\ldots,N_{max}$ and for all $\mu \in \mathcal{D}$ .
The upper bounds for the effectivities are
- independent of $N$ , and
- independent of $\mathcal{N}$ if $\alpha_{\mathrm{lb}}(\mu)$ only depends on $\mu$ , and are thus stable with respect to RB and FEM refinement.
Results for energy norm (and $X$ -norm) bound directly extend to noncompliant (& nonsymmetric) problems
- if we choose an appropriate definition for the energy (and $X$ ) norm

3. Offline-Online decomposition

Denote $\hat{e}(\mu)\in X$ $||\hat{e}(\mu)||_X = \varepsilon_N(\mu) = ||r(u_N(\mu),\cdot;\mu)||_X$ such that $(\hat{e}(\mu),v)_X = -r(u_N(\mu),v;\mu), \quad \forall v \in X$ .

And recall that $-r(u_N(\mu),v;\mu) = f(v) - \displaystyle\sum_{q=1}^Q \sum_{n=1}^N\ \Theta^q(\mu)\ {u_N}_n(\mu)\ a^q( \zeta_n,v), \quad \forall v\ \in\ X$

It follows next that $\hat{e}(\mu)\in X$ satisfies

$(\hat{e}(\mu),v)_X = f(v) - \displaystyle\sum_{q=1}^Q \sum_{n=1}^N\ \Theta^q(\mu)\ {u_N}_n(\mu)\ a^q( \zeta_n,v), \quad \forall v\ \in\ X$

Observe then that the rhs is the sum of products of parameter dependent functions and parameter independent linear functionals, thus invoking linear superposition

$\hat{e}(\mu)\ = \ \mathcal{C} - \sum_{q=1}^Q \sum_{n=1}^N\ \Theta^q(\mu)\ {u_N}_n(\mu)\ \mathcal{L}^q_n$

where

$\mathcal{C} \in X$ satisfies $(\mathcal{C},v) = f(v), \forall v \in X$
$\mathcal{L} \in X$ satisfies $(\mathcal{L}^q_n,v)_X = -a^q(\zeta_n,v), \forall v \in X, \, 1 \leq n \leq N, 1 \leq q \leq Q$ which are parameter independent problems

3.1. Error bounds

From a previous equation, we get

Error bound decomposition

$||\hat{e}(\mu)||_X^2 = (\mathcal{C},\mathcal{C})_X + \sum_{q=1}^Q \sum_{n=1}^N\ \Theta^q(\mu)\ {u_N}_n(\mu)\ \displaystyle \left( 2 ( \mathcal{C}, \mathcal{L}^q_n)_X + \sum_{q'=1}^{Q'} \sum_{n'=1}^{N'}\ \Theta^{q'}(\mu)\ {u_N}_{n'}(\mu)\ ( \mathcal{L}^{q}_{n}, \mathcal{L}^{q'}_{n'})_X \right)$

Remark In (Error bound decomposition), $||\hat{e}(\mu)||_X^2$ is the sum of products of

parameter dependant (simple/known) functions and
parameter independant inner-product,

the offline-online for the error bounds is now clear.

3.2. Steps and complexity

Offline :

Solve for $\mathcal{C}$ and $\mathcal{L}^q_n,\ 1 \leq n \leq N,\ 1 \leq q \leq Q$
Form and save $(\mathcal{C},\mathcal{C})_X$ , $( \mathcal{C}, \mathcal{L}^q_n)_X$ and $( \mathcal{L}^{q}_{n}, \mathcal{L}^{q'}_{n'})_X$ , $1 \leq n,n' \leq N,\ 1 \leq q, q' \leq Q$

Online :

Given a new $\mu \in \mathcal{D}^\mu$
Evaluate the sum $||\hat{e}(\mu)||_X^2$ (Error bound decomposition) in terms of $\Theta^q(\mu)$ and ${u_N}_n(\mu)$
Complexity in $O(Q^2 N^2)$ independent of $\mathcal{N}$

4. Sampling strategy: a Greedy algorithm

4.1. Offline-Online Scenarii

Offline : Given a tolerance $\tau$ , build $S_N$ and $W_N$ such that $\forall \ \mu\ \in \mathcal{P} \equiv \mathcal{D}^{\mu} \ , \ \Delta_N(\mu) < \tau$

Online : Given $\mu$ and a tolerance $\tau$ , find $N^*$ and thus $s_{N^*}(\mu)$ such that $N^* = \operatorname{arg\ max}_N\ \left( \Delta_{N}(\mu) < \tau \right)$ , or given $\mu$ and a max execution time $T$ , find $N^*$ and thus $s_{N^*}(\mu)$ s.uch that $N^* = \operatorname{arg\ min}_N\ \left( \Delta_{N}(\mu) \mbox{ and execution time } < T \right)$

4.2. $S_N$ and $W_N$ Generation Strategies

Offline Generation

Input : a tolerance $\epsilon$ , set $N = 0$ and $S_0 = \emptyset$
While $\Delta_N^{\mathrm{max}}> \epsilon$
- $N = N+1$
- If N == 1; then Pick ((log-)randomly) $\mu_1 \in \mathcal{D}^\mu$
- Build $S_N:= \{ \mu_N \} \cup S_{N-1}$
- Build $W_N:= \{ \xi = u(\mu_N) \} \cup W_{N-1}$
- Compute $\Delta_N^{\mathrm{max}}:= \mathrm{max}_{\mu \in \mathcal{D}^\mu}\, \Delta_N(\mu)$
- $\mu^{N+1} := \operatorname{arg\ max}_{\mu\in\mathcal{D}^\mu} \Delta_N(\mu)$
End While

Condition number : recall that the $\zeta_n$ are orthonormalizes, this ensures that the condition number will stay bounded by $\gamma(\mu)/\alpha(\mu)$ .

4.3. Online Algorithm I

$\mu$ adaptive online

Input : $\mu \in \mathcal{D}^\mu$
Compute $(s_{N^{*}}(\mu), \Delta_{N^{*}}(\mu))$ such that $\Delta_{N^{*}}(\mu) < \tau.$
$N = 2$
While $\Delta_N(\mu) > \tau$
- Compute $(s_N(\mu), \Delta_N(\mu))$ using $(S_N,W_N)$
- $N = N * 2$ use the (very) fast convergence properties of RB
End While

4.4. Online Algorithm II

Offline

While $i \leqslant \mathrm{Imax} \gg 1$
- Pick log-randomly $\mu \in \mathcal{D}^\mu$
- Store in table $\mathcal{T}, \Delta_N(\mu)$ if worst case for $N=1,..., {N^{\mathrm{max}}}$
- $i = i + 1$
End While

Online Algorithm II –

$\mu$ adaptive online – worst case

Given $\mu \in \mathcal{D}^\mu$ , compute $(s_{N^{*}}(\mu), \Delta_{N^{*}}(\mu))$ such that $\Delta_{N^{*}}(\mu) < \tau.$
$N^{*} := \mathrm{arg} \mathrm{max}_{\mathcal{T}}\, {\Delta_N(\mu) \, < \, \tau}$
Use $W_{N^{*}}$ to compute $(s_{N^{*}}(\mu),\Delta_{N^{*}}(\mu))$