12 votes
Accepted

$L^2$-convergence of finite element method when right hand side is only in $H^{-1}$ (Poisson eqn)

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\...
user avatar
11 votes

Convergence rate vs convergence order

$\|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 ...
user avatar
10 votes
Accepted

Analytical convergent sequence and numerical divergent sequence

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 ...
user avatar
  • 1,030
10 votes
Accepted

How does gmres method iteration behave for this non-diagonalizable matrix?

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 ...
user avatar
10 votes

Why in scientific papers convergence of finite difference and finite volume schemes is tested using multiple norms ($l_1$, $l_2$ and $l_{\infty}$)?

In finite dimensional spaces (say, in $\mathbb R^n$), all norms are equivalent and as a consequence, if something converges with a specific rate in one norm, it also converges with the same rate in ...
user avatar
9 votes
Accepted

Accurate computation of Gauss-Kuzmin entropy

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}{\...
user avatar
  • 11.4k
8 votes
Accepted

The rate of convergence for finite difference methods for Poisson's equation with piecewise constant data

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 ...
user avatar
  • 11.4k
8 votes
Accepted

Lack of quadratic convergence in Newton's method

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" ...
user avatar
  • 2,001
7 votes

Strong coupling of a non-linear multiphysic problem: failure with Newton Raphson method

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 ...
user avatar
7 votes
Accepted

When and why is `r./sum(r)` not a good way to renormalize a vector in PageRank computation?

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{...
user avatar
  • 11.4k
7 votes
Accepted

Error in result of finite-difference approximation when refining

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 ...
user avatar
  • 2,961
7 votes
Accepted

Finite element convergence rates for mixed problems

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 + ...
user avatar
7 votes

What are some reasons that Conjugate Gradient iteration does not converge?

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 ...
user avatar
7 votes
Accepted

Global convergence in trust region algorithm

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 ...
user avatar
7 votes

Which absolute and/or relative stopping criteria do use for Newton's method?

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 ...
user avatar
6 votes

How many generations does it typically take for a differential evolution method to reach a global optimum?

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 ...
user avatar
6 votes
Accepted

Finding rate of convergence by curve fitting in Matlab

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$. ...
user avatar
6 votes

Scaling/nondimensionalization for numerical optimization

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 ...
user avatar
  • 11.4k
6 votes

Analytical convergent sequence and numerical divergent sequence

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 ...
user avatar
  • 6,066
6 votes

Accuracy issues with Arpack in Julia for eigenvalues of smallest magnitude

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 ...
user avatar
6 votes

Why in scientific papers convergence of finite difference and finite volume schemes is tested using multiple norms ($l_1$, $l_2$ and $l_{\infty}$)?

Both your questions have been addressed in the answer of @WolfgangBangerth. Here is an applied example of the behaviour of the different norms in the context of polynomial approximation (which is for ...
user avatar
  • 2,557
5 votes

CFL condition for variable coefficients

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$). ...
user avatar
5 votes
Accepted

Convergence rate Jacobi/Gauss-Seidel with mesh resolution

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 $$ ...
user avatar
5 votes

How does gmres method iteration behave for this non-diagonalizable matrix?

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-...
user avatar
4 votes

How to test convergence of an algorithm for constrained optimization

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 ...
user avatar
4 votes

Error in result of finite-difference approximation when refining

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 ...
user avatar
4 votes

What causes periodic humps in residual plots?

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 ...
user avatar
4 votes
Accepted

convergence of unconstrained convex optimization

What about $$ F(x,y) = \frac{x^2}{y} + \frac{\epsilon}{x^2}, \qquad \nabla F(x,y) = \Big( \frac{2x}{y}-\frac{2\epsilon}{x^3}, -\frac{x^2}{y^2} \Big), \qquad x,y>0$$ with the sequence $(x_k,y_k) = (...
user avatar
  • 11.4k
4 votes
Accepted

What should I put on the paper to show the correctness and convergence of my solution?

You should definitely do a mesh refinement study (some conferences and journals require this). You should compare the results of this study to a known, analytical solution. You can either get this ...
user avatar
  • 10.8k
4 votes
Accepted

$O(h^2)$ convergence for Elliptic PDE

You appear (and correct me if I am wrong, i do not wish to presume) to be confused on the notion of what is an order of convergence. The order of convergence is the order at which your approximate ...
user avatar
  • 1,127

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