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 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

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

$\|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

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 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

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}(...


6

Looks like everything is working relatively OK? Your matrix is of order 1e10, so residuals of 1e-4 are actually close to machine precision. The convergence criterion is indeed violated, but not by much; not sure what's going on there, are you sure Arpack really guarantees it or is it a best effort kind of thing? It surprises me that you get different results ...


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

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 ...


4

The first order necessary optimality conditions for a minimization problem with inequality constraints are not that the gradient vanishes, since the minimum can be attained at the boundary of the feasible set (where only the directional derivatives into the interior of the set have to be non-negative, i.e., going away from the boundary leads to an increase ...


4

You've chosen a very specific example where the function in question has a single extremely narrow peak and is almost zero everywhere else in the domain. This is an example of a stiff problem where you must take a very tight discretization to resolve the peak. Finite difference approximations are based on polynomial approximations to a curve. In the case ...


4

These humps occur in the context of optimization when the solution is approached but we then go past it. This frequently occurs in gradient descent with momentum, where they appear regularly on plots because the gradient and momentum both decay in magnitude together. Usually this suggests a little too much momentum, since we're retaining speed as we reach ...


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