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?
$\begingroup$
$\endgroup$
4
-
1$\begingroup$ 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? $\endgroup$– Chris RackauckasOct 7, 2017 at 12:15
-
$\begingroup$ 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. $\endgroup$– Wenjin XingOct 7, 2017 at 12:47
-
1$\begingroup$ 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). $\endgroup$– GoHokiesOct 7, 2017 at 14:23
-
$\begingroup$ 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. $\endgroup$– GoHokiesOct 7, 2017 at 15:41
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
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 $$ \inf_{v_h \in V_h} \|v-v_h\|_X \le \|v-I_h v\|_X \le C \inf_{v_h \in V_h} \|v-v_h\|_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.
answered Oct 9, 2017 at 5:34
-
$\begingroup$ Could you please explain the second chain of inequalities? The arguments of all three norms are the same. $\endgroup$ Jan 1, 2022 at 18:47
-
$\begingroup$ @ZoltánCsáti Yes, this didn't make any sense and was the result of a poor attempt at editing several years ago. I fixed it. $\endgroup$ Jan 3, 2022 at 8:43
-
$\begingroup$ I agree with you that this is the usual way. However, there are instances in which lower orders (as compared to the interpolation error) are deemed optimal. For example, in the context of the Oseen equation (linearized Navier-Stokes), the order of convergence of the pressure is one less than that of the velocity for even the best numerical methods. And, still, these methods are classified as 'optimal' in the literature. This is because only the first derivative of the pressure appears in the equation, while the second derivative of the velocity is present. What about this case? $\endgroup$ Apr 14 at 9:46
$\begingroup$
$\endgroup$
1
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.
-
1$\begingroup$ That is one definition for "optimal" convergence, but that's not what people typically mean in the context of FEM. $\endgroup$ Oct 9, 2017 at 5:23