12

Yes, this is the standard Aubin-Nitsche (or duality) trick. The idea is to use the fact that $L^2$ is its own dual space to write the $L^2$-norm as an operator norm $$\|u\|_{L^2} = \sup_{\phi\in L^2\setminus\{0\}} \frac{(u,\phi)}{\|\phi\|_{L^2}}.$$ We thus have to estimate $(u-u_h,\phi)$ for arbitrary $\phi\in L^2$. To do that, we "lift" $u-u_h$ to $H^1_0$ ...


10

It isn't so much that we want to compare the $p$-refinement and $h$-refinement errors directly, instead we want to compare the convergence properties (e.g. speed) of each refinement strategy. This requires more knowledge of the constant in the apriori error estimate. We'll illustrate by looking at the apriori error estimate of a discontinuous Galerkin ...


10

Let me first answer all the questions: What is the theoretical convergence rate for an FFT Poison solver? The theoretical convergence is exponential as long as the solution is sufficiently smooth. How fast should this energy converge? The Hartree energy $E_H$ should converge exponentially for a sufficiently smooth solution. If the solution is less ...


10

It is because we typically neglect higher order terms in error estimates. For example, we can show that $$ \|e\| \le C(u) h^2 + {\cal O}(h^3). $$ The point is that when $h$ is small, the cubic term is small and can be neglected. In fact, when $h$ is small, you can observe quadratic convergence. But whenever $h$ is not small (where "small" is relative to ...


10

$\|x^{(k)}-x^*\|$ is the error in the $k$th term, call it $E_k$. For a "good" numerical method, we want the approximation to get closer and closer to the desired result so $E_k$ has to decrease to zero. If the error is guaranteed to reduce to at least a certain fraction $L$ of the previous step, you have linear convergence: $$E_{k+1} \le L E_k.$$ This ...


10

Jean-Michel Muller, et. al., "Handbook of Floating-Point Arithmetic 2nd ed.", Birkhäuser 2018, gives the following example due to Muller, specifically constructed to deliver incorrect results with floating-point evaluation: $$ {u_{0} = 2,\\ u_{1} = -4,\\ u_{n} = 111 - \frac{1130}{u_{n-1}} + \frac{3000}{u_{n-1}u_{n-2}},\>\>\>\>n \ge 2.} $$ ...


10

Unfortunately, convergence of GMRES does not have a clear dependence on the distribution of eigenvalues. It was proved by Greenbaum, Ptak and Strakos in 1996 that you can construct examples with an arbitrary spectrum and an arbitrary convergence history: that is, give me any $n$ nonzero complex numbers, and any decreasing sequence $\|r_k\|$, and I can ...


9

It's fairly easy to evaluate, to do this expand the logs in Taylor series in $x=(k+1)^{-2}$: $$ \log_2(1-x) = \frac{-1}{\log 2}\sum_{m\geq1}\frac{x^{m}}{m}$$ $$ \log_2(-\log_2(1-x)) = \frac{\log x}{\log 2} - \frac{\log\log 2}{\log 2} + \sum_{n\geq 1}a_n x^n, $$ where $a_n$ are Taylor series coefficients of the l.h.s. after the log-singularity is subtracted. ...


8

Let's examine the one-dimensional three-point stencil case in detail, because I think it's important to be clear just how this behaviour arises, and what it means to set a point to a certain value in a finite-difference grid when the underlying function is discontinuous. The equation will be $$ u''(x) = \rho(x). $$ Instead of using the interval $[-1,1]$ with ...


8

Yes: See Higham's book "Accuracy And Stability of Numerical Algorithms", second edition, chapter 25: Nonlinear Systems and Newton's Method. In particular, see the section on the "limiting residual" in terms of a condition number for the Jacobian. It may well be that since your system is ill-conditioned, that you quickly hit the limiting residual and your ...


7

If analytic techniques are disallowed but the periodic structure is known, here is one approach. Let $$g(x) = \frac{\cos x}{2-\cos x}$$ be periodic with period $2 \pi$, so that $$g(x) = \sum_j w_j e^{ijx}$$ where $$w_j = \frac{1}{2\pi}\int_0^{2\pi} g(x) e^{-ijx} dx$$ Thus, $$\begin{aligned} f(x) &= \sum_{k \ge 1} \frac{g(kx)}{k^p} \\ &= \sum_{k ...


7

The Taylor-Hood approximation of the Stokes flow is a mixed finite element method, for which error estimates generally have the form $$ \|u-u_h\|_V + \|p-p_h\|_M \leq C (\inf_{w_h\in V_h}\|u-w_h\|_V + \inf_{q_h\in M_h}\|p-q_h\|_M), \tag{1} $$ where $(u,p)\in V\times M$ is the exact solution and $(u_h,p_h)\in V_h\times M_h$ is the approximation. For the ...


7

If your matrix is symmetric, positive definite, the CG method may converge slowly, but it converges for $n\to\infty$. The only reason it does not converge on a computer are round-off errors, in particular if the condition number of the matrix, the quotient of largest and smallest eigenvalue is large. Experience is, that with double precision arithmetic, ...


7

The two normalization formulas result in two different algorithms, that they both "normalize" a vector is not so relevant. As an example, consider the following transition matrix: $$M = \begin{pmatrix}0&1\\1&0\end{pmatrix}.$$ Starting with $r=(1,0)$, consecutive normalized vectors $r$ will be $(0,1)$ and $(1,0)$, so the algorithm clearly will not ...


7

The issues you're running into now are not a failing of Newton-Raphson, but a question of coupling. You're doing iterated sequential coupling -- solving each equation sequentially and then iterating until (hopeful) convergence. No solver choice in place of NR is going to fix this lack of convergence, as long as you are doing iterated sequential coupling. ...


7

High order methods are not necessarily always more accurate than low order methods; they simply have a more rapid convergence rate. For example, if you take the Taylor expansion of a function at a point $x$ and evaluate it at $x+h$, you have $$f(x+h) = f(x) + f'(x)h + \frac{f''(x)}{2}h^2 + \ldots$$ The order of a finite difference method is determined by ...


7

Standard terminology in nonlinear (i.e., derivative-based) optimization is that "global convergence" means "convergence to a stationary point no matter where you start from" (where the limit may in fact depend on the starting point). This is in contrast to local convergence, which requires that you start sufficiently close to a stationary point; if your ...


7

Some of the confusion comes about because mathematicians often consider artificial functions that happen to have size $O(1)$ whereas practitioners use functions and variables that just happen to be whatever they are, often vastly different from one. One of the considerations that is important in practice is to make sure that the choice of physical units does ...


6

I don't think there's enough information to give a heuristic like, "in general, it takes $k$ iterations for differential evolution to reach a global optimum". First, we don't know how many iterations deterministic global optimizers will take to converge to global $\varepsilon$-optimality in the general case. In limited special cases, we know that certain ...


6

First of all, rates of convergence are usually given in the form $$ \|u-u_h\| \leq C N^\alpha,$$ rather than equality. Furthermore, rates are asymptotic, i.e., only have to hold for $N\to \infty$. This means that you're unlikely to find a single $C$ and $\alpha$ such that your equation holds. Another reason why your approach doesn't work is that what you're ...


6

One thing that makes your non-dimensionalized ODE confusing is that you use the same symbols for dimensionalized and nondimensionalized variables, even though they are different variables. Consider writing it in a different way: let there be a new set of variables, $\tilde t, \tilde x,\ldots$, all unitless, defined by $$ \tilde t = n_{\mathrm{time}}t, \...


6

In my opinion, an example could be the calculation of the minimal solution of a three term recurrence relation (TTRR) $$y_{n+1} +a_{n}y_{n}+b_{n}y_{n-1} = 0, \quad n=1,2,3,\ldots$$. For example, the Bessel $J_{n}(x)$ function for a fixed $x$ satisfies the TTRR $$y_{n+1}-\frac{2n}{x}y_{n}+y_{n-1} = 0$$ Suppose you know $y_{0} = J_{0}(1)$ and $y_{1} = J_{1}(...


5

There is nothing that can guarantee converge of such a fixed point iteration, but there are criteria that if you can show that they hold, the iteration will converge. In particular, the fixed point iteration will converge if it is a contraction. I am quite sure, however, that it is not very difficult to find example of functions $f(x)$ where even with ...


5

The CFL number (or simply Courant number) is defined locally: $\nu = u(x,t) \frac{\Delta t}{\Delta x}$. The velocity may vary in time and space and the grid may be non-uniform (in $x$ and/or $t$). So the CFL number can be different at each point in time and space. A necessary condition for convergence of a consistent method is that the CFL condition be ...


5

The convergence rate that is mentioned here is in the sense that the error in iteration $k$ and $k-1$ are related by $$ \| x^{(k)} - x^\ast\| \le r \| x^{(k-1)} - x^\ast\|, $$ which implies that $$ \| x^{(k)} - x^\ast\| \le r^k \| x^{(0)} - x^\ast\|. $$ For this to converge at all, we need that $r<1$, which the statement you quote provides. But for ...


5

Estimates for GMRES convergence based on eigenvalue distribution often implicitly assume that the matrix is normal. Sometimes the convergence rate is still provable in an asymptotic sense in the non-normal case, but if the matrix is severely non-normal then the "pre-asymptotic" behavior will make such convergence rates never reachable in practice. Your ...


4

Preasymptotic refers to the following concept: A priori error estimates only say that as the mesh size $h\rightarrow 0$, we have that (for example) $\|e\|\le Ch^2$. But this is an asymptotic statement: it is not an equality that holds for all $h$ but one typically only sees the quadratic decay whenever $h$ is small enough. In other words, in numerical ...


4

The meanings of those terms depend on context. Superconvergence is usually used to mean you are converging faster than the "optimal" rate, and occasionally this sort of weirdly fast convergence can be proven rigorously. One example in DG is that hyperbolic problems generally have an optimal estimate that decays like $h^{n+1/2}$ but some recent ...


4

Pre-asymptoticity in conjugate gradient method: Asymptotic behavior sometimes assumes certain conditions. For example, given $h$ the meshsize or similar, and $h\to 0$: $$ \|f_h - g_h \| \leq c h. $$ but what if $$ \|f_h - g_h \| \leq c k h^2 $$ if we assume $kh = O(1)$ then $f_h$ is asymptotic to $g_h$, this is asympototic analysis. If we do not assume that ...


4

You might be familiar with the following paper already: http://link.springer.com/chapter/10.1007%2F978-3-642-22061-6_10 Problems which are highly indefinite and oscillatory are very difficult to design robust iterative methods for. The paper gives some suggestions which might be helpful to you though, many of them have been extended to the time-harmonic ...


Only top voted, non community-wiki answers of a minimum length are eligible