# What does optimal convergence rate mean? How to prove whether a numerical method, e.g. FEM, has an optimal convergence rate or not?

I searched online about the way optimal is defined mathematically,but without any information acquired? How to prove whether a numerical method, e.g. FEM, has an optimal convergence rate or not? Anyone sheds a light on this?

• Optimal means it converges instantly? No, I don't think this question makes sense, at least without context. I have never heard someone using this term. Maybe something like, doing a numerical experiment and saying "Figure A shows that algorithm ____ on test problem ____ achieves its optimal convergence rate proved in _____" (but still, why add optimal?). Or if you have a proof that no numerical method can converge faster than X, but there are methods with increasingly good spectral convergence so I don't see how that's possible. So, can you give an example? Oct 7 '17 at 12:15
• I donot quite know why some guys tend to add 'optimal' before convergence rate. That is the reason I came here for posting this question. However,if you search online by keyword 'optimal convergence', you can find some sources on adaptive analysis for PDEs, ones by maybe Pro. Babuška who has a huge amount of work on error estimators and adaptive analysis. Oct 7 '17 at 12:47
• Optimal convergence rate/order is a phrase you'll come upon quite often in the FEM literature. It can be interpreted as the best (highest) convergence order that can be achieved for a particular problem given the regularity of the (weak) solution, the properties of your problem (e.g., self-adjointness) and your choice of test and trial spaces (e.g., the polynomial basis order). Oct 7 '17 at 14:23
• To get a basic grasp of convergence estimates in FEM, one can do worse than reading Joseph Flaherty's course notes - in particular chapter 7, which deals with the basics of both a priori and a posteriori error estimation. Oct 7 '17 at 15:41

The term is commonly used in the following way in the finite element context:

Let's assume that $u\in V$ is the exact solution of the PDE, and $u_h\in V_h$ the finite element approximation. Then we ask for the convergence order of the norm of the error $\|u-u_h\|_X$ with regard to some norm $\|\cdot\|_X$. We then say that the approximate solution "converges with optimal order" if $$\|u-u_h\|_X \le C \inf_{v_h \in V_h} \|u-v_h\|_X,$$ i.e., if the error can be bounded by a multiple of the best possible error.

In many cases, e.g. if $V_h$ are the usual piecewise polynomial finite element spaces and $\|\cdot\|_X$ is the $L_2$ or $H^1$ norm, then one can show that for all $v\in V$ there holds that $$\|v-I_h v\|_X \le \|v-I_h v\|_X \le C \|v-I_h v\|_X,$$ where $I_h v$ is the interpolant of $v$ onto $V_h$, and in those cases we say that the numerical solution $u_h$ of the PDE converges "with optimal order" if $$\|u-u_h\|_X \le C \|u-I_h u\|_X,$$ i.e., if the numerical solution converges at the same rate as the interpolant.

This is, for example, the case for the usual discretizations of the Laplace equation. But it is not true, for example, for many/most discretizations of the advection equation.

Assume you have a metric for some problem, e.g., the asymptotic convergence rate. If you can prove that there can be no algorithm that has a better value in the specific metric, then the algorithm is optimal.

For example, consider multigrid methods. Solving a linear system with $n$ unknowns cannot be done with less than $\mathcal{O}(n)$ operations, because every variable has to be set at least once. For some problems it can be shown that a multigrid method can solve a linear system with $\mathcal{O}(n)$ operations up to the discretization accuracy. Hence, if we consider the metric asymptotic-number-of-operations, multigrid methods are optimal.

Whether an algorithm is optimal, therefore, depends on the metric. And the metric will depend on the context and the assumptions made. In the example above we restricted ourselves to the accuracy of the discretization.

In all, what optimal means needs to be explained in the specific context.

• That is one definition for "optimal" convergence, but that's not what people typically mean in the context of FEM. Oct 9 '17 at 5:23