Optimal P1 AFEM complexity for the Laplacian

By [F5] the weak solution exists uniquely under the stated choice assumptions. Since $f$ is piecewise constant on ${\mathcal{T}}_0$, every descendant cell has ${\mathrm{osc}}_K=0$. By [F1] there are $0<\alpha <1$ and $C_0$ such that $e_{k+1}^2\le \alpha e_k^2$; hence, with $q=\sqrt{\alpha }<1$, $e_j\le q^{j-k}{e}_k$ for $j\ge k$. If $\mathrm{\mid }u{\mathrm{\mid }}_{{\mathbb{A}}_s}=0$, then $E_0(u)=0$ and all nested Galerkin errors vanish. Assume $\mathrm{\mid }u{\mathrm{\mid }}_{{\mathbb{A}}_s}>0$.

For each $k$ with $e_k>0$, put ${ϵ}_k=\lambda e_k$ for the fixed $\lambda \in (0,1)$ in the statement. By [F4], if $N_k=\lceil (2\mathrm{\mid }u{\mathrm{\mid }}_{{\mathbb{A}}_s}\mathrm{/}{ϵ}_k{)}^{1\mathrm{/}s}\rceil$, then $E_{N_k}(u)\le {ϵ}_k\mathrm{/}2$: this follows directly from $(N_k+1{)}^s{E}_{N_k}\le \mathrm{\mid }u{\mathrm{\mid }}_{{\mathbb{A}}_s}$ and $N_k+1\ge (2\mathrm{\mid }u{\mathrm{\mid }}_{{\mathbb{A}}_s}\mathrm{/}{ϵ}_k{)}^{1\mathrm{/}s}$. By the definition of an infimum there is a conforming comparison mesh with at most $N_k$ added cells and best-approximation error at most ${ϵ}_k$. For a symmetric Galerkin solution, [F6] and expansion of $\mathrm{\parallel }\mathrm{\nabla }(u-v_T){\mathrm{\parallel }}_2^2=\mathrm{\parallel }\mathrm{\nabla }(u-U_T){\mathrm{\parallel }}_2^2+\mathrm{\parallel }\mathrm{\nabla }(U_T-v_T){\mathrm{\parallel }}_2^2$ show its exact Galerkin error is the best error, so this comparison mesh reduces the Galerkin error to at most ${ϵ}_k$. If $e_k=0$, the target conclusion is already true.

The comparison mesh from step 1.2 reduces the error by the factor $\lambda$. By [F2], the marked set therefore satisfies $\mathrm{\#}{M}_k\le N_k\le 1+(2\mathrm{/}\lambda {)}^{1\mathrm{/}s}\mathrm{\mid }u{\mathrm{\mid }}_{{\mathbb{A}}_s}^{1\mathrm{/}s}{e}_k^{-1\mathrm{/}s}\mathrm{.}$ Here $M_O=\mathrm{\varnothing }$ because the initial P0 data have zero oscillation, so $M_k=M_{E,k}$. The actual refinement request is its edge-neighbor set $Q_k$, whose cardinality is at most $4\mathrm{\#}{M}_k$; [F3] already absorbs this factor in $C_{\mathrm{c}\mathrm{l}}$. Summing and applying [F3] gives $\mathrm{\#}{\mathcal{T}}_n-\mathrm{\#}{\mathcal{T}}_0\le C{\sum }_{k=0}^{n-1}\mathrm{\#}{M}_k\le C^{\mathrm{\prime }}\mathrm{\mid }u{\mathrm{\mid }}_{{\mathbb{A}}_s}^{1\mathrm{/}s}{\sum }_{k=0}^{n-1}{e}_k^{-1\mathrm{/}s}\mathrm{.}$ The additive $1$ is absorbed into the right side because $e_k\le e_0=E({\mathcal{T}}_0;u)\le \mathrm{\mid }u{\mathrm{\mid }}_{{\mathbb{A}}_s}$ by [F4] at $N=0$.

Geometric contraction from step 1.1 implies $e_k^{-1\mathrm{/}s}\le q^{(n-k)\mathrm{/}s}{e}_n^{-1\mathrm{/}s}$ for $k<n$. Thus the sum in step 2.1 is at most $e_n^{-1\mathrm{/}s}{\sum }_{j\ge 1}{q}^{j\mathrm{/}s}$, a finite geometric series. Rearranging yields $e_n\le C^{\mathrm{\prime }\mathrm{\prime }}\mathrm{\mid }u{\mathrm{\mid }}_{{\mathbb{A}}_s}(\mathrm{\#}{\mathcal{T}}_n-\mathrm{\#}{\mathcal{T}}_0{)}^{-s}$ whenever the added-cell count is positive. If it is zero, [F4] at $N=0$ gives $e_n=e_0\le \mathrm{\mid }u{\mathrm{\mid }}_{{\mathbb{A}}_s}$. Enlarging $C^{\mathrm{\prime }\mathrm{\prime }}$ replaces the count by $1+\mathrm{\#}{\mathcal{T}}_n-\mathrm{\#}{\mathcal{T}}_0$.