# 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

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))$