The special formula for order of convergence

141 Views Asked by At

In numerical analysis, for the problems (mainly PDE) for which analytical solution is not available, the error computation can be done often with 'double mesh principle'.

For instant, Let $\mathcal U_{i,j}^{M,N}$ be the numerical approximation with $M$ and $N$ points in space and time directions respectively. Suppose we need error at the final time axis, Then the $L_{\infty}$ norm error (maximum absolute error, $e_{\max}^{M,N}$) is given by $$e_{\max }^{M, N}=\max _{0 \leq m \leq M}\left|\mathcal U_{m,N}^{M,N}-\mathcal U_{2m,2N}^{2M,2N}\right|,$$

and the corresponding order of convergence is given by $$p_{\max}^{M,N}=\log_2\left(\frac{e_{\max}^{M,N}}{e_{\max}^{2M,2N}}\right),$$ On what logic the spatial order can be calculated by this formula using $\log$ function with base $2$? This formula has been used in several articles, but I am not sure about the justification behind it.

1

There are 1 best solutions below

0
On BEST ANSWER

Suppose that the error satisfies the following asymptotic approximation:

$$\epsilon_M\sim\frac\alpha{M^\beta},\quad\alpha\in\mathbb R\land\beta\in\mathbb R_{>0}$$

This means we have:

$$\mathcal U_M-\mathcal U_\infty\sim\frac\alpha{M^\beta}$$

Plugging it into the first equation, we can then see that:

\begin{align}\mathcal U_M-\mathcal U_{2M}&=(\mathcal U_M-\mathcal U_\infty)-(\mathcal U_{2M}-\mathcal U_\infty)\\&\sim\frac\alpha{M^\beta}-\frac\alpha{(2M)^\beta}\\&=\left(1-\frac1{2^\beta}\right)\frac\alpha{M^\beta}\\&\sim\left(1-\frac1{2^\beta}\right)\epsilon_M\\&=\hat\epsilon_M\end{align}

is a rough approximation of $\epsilon_M$ (it's only off by a constant factor).

Plugging it into the second equation, we can see that:

\begin{align}\log_2\left(\frac{\hat\epsilon_M}{\hat\epsilon_{2M}}\right)&\approx\log_2\left(\frac{(1-2^{-\beta})\alpha M^{-\beta}}{(1-2^{-\beta})\alpha(2M)^{-\beta}}\right)\\&=\log_2\left(\frac1{2^{-\beta}}\right)\\&=\log_2\left(2^\beta\right)\\&=\beta\end{align}

which is in fact the order of convergence.