People who code: we want your input. Take the Survey

Questions tagged [convergence]

Questions related to whether the sequence of iterates generated by an iterative method has one or more limit points, and if those limit points have the correct properties.

Filter by
Sorted by
Tagged with
25
votes
3answers
3k views

What is the principle behind the convergence of Krylov subspace methods for solving linear systems of equations?

As I understand it, there are two major categories of iterative methods for solving linear systems of equations: Stationary Methods (Jacobi, Gauss-Seidel, SOR, Multigrid) Krylov Subspace methods (...
19
votes
2answers
2k views

How to determine if a numerical solution to a PDE is converging to a continuum solution?

The Lax equivalence theorem states that consistency and stability of a numerical scheme for a linear initial value problem is a necessary and sufficient condition for convergence. But for nonlinear ...
16
votes
1answer
1k views

Convergence rate of FFT Poisson solver

What is the theoretical convergence rate for an FFT Poison solver? I am solving a Poisson equation: $$\nabla^2 V_H(x, y, z) = -4\pi n(x, y, z)$$ with $$n(x, y, z) = {3\over\pi} ((x-1)^2 + (y-1)^2 + (...
15
votes
1answer
3k views

Comparing Jacobi and Gauss-Seidel methods for nonlinear iterations

It is well known that for certain linear systems Jacobi and Gauss-Seidel iterative methods have the same convergence behavior, e.g. Stein-Rosenberg Theorem. I am wondering if similar results exist for ...
13
votes
3answers
9k views

Understanding the “rate of convergence” for iterative methods

According to Wikipedia the rate of convergence is expressed as a specific ratio of vector norms. I'm trying to understand the difference between "linear" and "quadratic" rates, at different points of ...
13
votes
3answers
304 views

Computing slightly oscillatory series to high precision?

Suppose I have the following interesting function: $$ f(x) = \sum_{k\geq1} \frac{\cos k x}{k^2(2-\cos kx)}. $$ It has some unpleasant properties, like its derivative not being continous at rational ...
13
votes
1answer
317 views

Non-monotonic convergence in fixed-point problem

Background I am solving a variant of the Ornstein-Zernike equation from liquid theory. Abstractly, the problem can be represented as solving the fixed point problem $A c(r)=c(r)$, where $A$ is an ...
12
votes
2answers
5k views

Strategies for Newton's Method when the Jacobian at the solution is singular

I'm trying to solve the following system of equations for the variables $P,x_1$ and $x_2$ (all else are constants): $$\frac{A(1-P)}{2}-k_1x_1=0 \\ \frac{AP}{2}-k_2x_2=0 \\ \frac{(1-P)(r_1+x_1)^4}{L_1}...
11
votes
3answers
1k views

Why does iteratively solving the Hartree-Fock equations result in convergence?

In the Hartree-Fock self-consistent field method of solving the time-independent electronic Schroedinger equation, we seek to minimize the ground state energy, $E_{0}$, of a system of electrons in an ...
11
votes
1answer
463 views

How to establish that an iterative method for large linear systems is convergent in practice?

In computational science we often encounter large linear systems which we are required to solve by some (efficient) means, e.g. by either direct or iterative methods. If we focus on the latter, how ...
11
votes
1answer
197 views

Implications of thermodynamic inconsistency in CFD calculations

During my PhD work, I had to use tabulated values of thermodynamic properties of gases in some Computational Fluid Dynamics (CFD in short) simulations. My tables are discretized in temperature and ...
10
votes
2answers
1k views

Which iterative linear solvers converge for positive semidefinite matrices?

I want to know which of the classic linear solvers (e.g Gauss-Seidel, Jacobi, SOR) are guaranteed to converge for the problem $Ax=b$ where $A$ is positive semi definite and of course $b \in im(A)$ (...
10
votes
1answer
292 views

Why do we have to rerun the CFD solver for higher Reynolds number?

I started to learn OpenFOAM from the Cavity tutorial which is provided at the web-site. When experimenting with different Reynolds numbers, in section "2.1.8.2 Running the code", tutorial says to ...
9
votes
3answers
1k views

Basin of attraction for Newton's method

Newton's method for solving nonlinear equations is known to converge quadratically when the starting guess is "sufficiently close" to the solution. What is "sufficiently close"? Is there literature ...
9
votes
1answer
760 views

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

I know that the piecewise linear finite element approximation $u_h$ of $$ \Delta u(x)=f(x)\quad\text{in }U\\ u(x)=0\quad\text{on }\partial U $$ satisfies $$ \|u-u_h\|_{H^1_0(U)}\leq Ch\|f\|_{L^2(U)} $...
9
votes
2answers
345 views

How does weak convergence feel, numerically?

Consider, you have a problem in an infinite dimensional Hilbert or Banach space (think of a PDE or an optimization problem in such a space) and you have an algorithm that converges weakly to a ...
8
votes
1answer
1k views

Convergence rate vs convergence order

I'm a bit confused about the concepts of convergence rate and convergence order. Let me first give you the definitions we use: [sorry for the English, it's all self translated] Let $x^{*}$ be our ...
8
votes
1answer
508 views

Finite element convergence rates for mixed problems

I've coded up a Stokes Flow problem using finite elements and am in the process of verifying that it works. I'm just not sure what convergence rate I should be expecting as I globally refine the mesh. ...
8
votes
1answer
591 views

Demonstrating that the time step size is small enough in a code with automatic step size selection

I recently inherited a large body of legacy code that solves a very stiff, transient problem. I would like to demonstrate that the spatial and temporal step sizes are small enough that the ...
8
votes
1answer
234 views

Should we always expect FEM error plots to be straight lines?

The error estimates in FEM are usually of the form $$||u^h-u||\leq Ch.$$ Taking logarithm on both sides, we obtain $$\log ||u^h-u||\leq \log C + \log h.$$ This estimate implies that the error lies ...
8
votes
1answer
321 views

Asymptotic convergence of the solution to a parabolic pde to the solution of an elliptic pde

Suppose I have the parabolic system $$u_t=\nabla\cdot(k(x)\nabla u)+f,\quad (x,t)\in\Omega\times I$$ with Dirichlet boundary conditions $$u=g, \quad x\in\partial\Omega$$ and initial condition $$u(x,t)...
8
votes
0answers
519 views

DIIS method to accelerate SCF convergence for stretched geometries

I am implementing from scratch an Hartree-Fock calculation in the STO-3G basis set to perform Born-Oppenheimer molecular dynamics. I have a Restricted Hartree-Fock procedure that can reproduce very ...
8
votes
0answers
160 views

Accelerated convergence for Sparse NMF

In the Non-Negative Matrix factorization (NMF), you basically compute an approximation of a given matrix $V \in \mathbb{R}_{+}^{n \times m}$ into matrices $W$ and $H$ such that $W \in \mathbb{R}_{+}^{...
7
votes
1answer
324 views

Lack of quadratic convergence in Newton's method

It is well-known that Newton's method can converge quadratically, if initial guess is close enough and if the arising linear systems are solved accurately. I am applying Newton's method to highly ill-...
7
votes
3answers
401 views

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

I am trying to solve a multiphysic problem using finite elements and a Newton Raphson solution scheme. I have two non-linear subsystems that are coupled bi-directionally. The first subsystem includes ...
7
votes
2answers
1k views

Convergence/stagnation of BiCGStab(l)

I am solving 3D time-harmonic Maxwell FDFD problems (which result in huge sparse linear systems) using BiCGStab(l). I have tried out a bunch of different methods and for my specific use case, it seems ...
7
votes
1answer
365 views

Richardson extrapolation for strong rate of convergence of SDE

Is it possible to apply Richardson extrapolation with Euler-Maruyama scheme to improve strong rate of convergence of stochastic differential equations?
7
votes
0answers
76 views

Why not use the preconditioned residual as termination criterion for preconditioned CG?

I have a Poisson equation with wildly varying material parameters (1 .. 1000), wildly varying element sizes (5 nm .. 100 um) and some quite anisotropic (tetrahedral) elements (100 nm x 100 um). I use (...
6
votes
3answers
1k views

Significance of p-convergence studies

Consider a method (e.g., FEM) with variable approximation order $p$. Now, we know that the optimal order of convergence is given by $$e = C h^{p+1},$$ where $h$ denotes the mesh size and a constant $C$...
6
votes
2answers
4k views

When to stop Gauss-Seidel-iterations?

I want to have an estimation, that my solution has an error, let's say less than 1e-8. Usually, I stop the Gauss-Seidel algorithm, when the residual is "small enough" and this is already the problem. ...
6
votes
1answer
516 views

Global convergence in trust region algorithm

I was reading about TR methods and there are some terms, which are confusing for me. It says, method is globaly convergent. What does it really mean? Converges to global minima, or converges for ...
6
votes
2answers
230 views

Accuracy issues with Arpack in Julia for eigenvalues of smallest magnitude

Following the documentation of Julia's Arpack package (Cf. https://julialinearalgebra.github.io/Arpack.jl/stable/eigs/) I have computed some largest and smallest magnitude eigenvalues of sparse ...
5
votes
2answers
1k views

Sufficient conditions to ensure convergence of the conjugate gradient method

I know that a conjugate gradient method is guaranteed to converge to the solution of a linear system if the matrix is positive definite. I'm working with a family of matrices that have the following ...
5
votes
1answer
151 views

Accurate computation of Gauss-Kuzmin entropy

The Gauss-Kuzmin distribution gives the probability of an integer appearing as a partial denominator in the continued fraction of a real number $x$ as $$ P(a_k = k) = -\log_2\left(1 - \frac{1}{(k+1)^2}...
5
votes
2answers
487 views

Proving convergence of 5 point scheme for the Poisson equation

So, we are solving the Biharmonic equation ($\Delta^2 u = f$) on a rectangle by solving the Poisson equation ($\nabla^2 u = f$) two times. We have nice boundary conditions, $u = 0$ and $\Delta u = 0$ ...
5
votes
1answer
11k views

The definition of asymptotic convergence?

What is the difference between convergence and asymptotic convergence? Why say the convergence is asymptotic?
5
votes
1answer
214 views

Discretization of Classical Density Functional Theory (CDFT) problems

I formulate questions about ion densities in biological and materials problems using Classical Density Functional Theory, as in this paper which is also on the arXiv. The discretization in that paper ...
5
votes
1answer
105 views

Non-conforming bi-linear finite element

The four-noded bi-linear rectangle element, which sometimes goes under the name Melosh element, is non-conforming unless the element sides are aligned. Out of curiosity I have implemented this element ...
5
votes
0answers
128 views

Are there any benefits of computable analysis to numerical algorithms

Computers can work only with computable numbers, while most of the algorithms are based on analysis of real numbers (real analysis). When I heard of the existence of computable analysis I ...
5
votes
0answers
191 views

What causes periodic humps in residual plots?

When using many iterative methods, whether for solving linear systems, looking for steady-state convergence in CFD, etc., the semilog plot of the residual often shows "humps" as the residual decays. ...
5
votes
0answers
208 views

Conjugate residual/gradient convergence checking in practice

Let's say we want to solve $Ax=b$ ($A$ symmetric positive /semi/definite) with the conjugate residual/gradient method. $A$ comes from FEM where the mesh is being refined. The exact solution is $x_*$ ...
5
votes
0answers
352 views

Understanding the meaning of Computational Order of Convergence

I am a postgraduate student with interest in numerical methods for solving nonlinear systems of equations. I have read some papers that discussed about 'computational order of convergence' for some ...
5
votes
0answers
84 views

Non-convergance when calculating temperature/heat flows through a section of rock

I am attempting to calculate temperature of section of rock in the earth as a function of vertical position in the rock and time. Along with it I am calculating the heat flow through the rock as a ...
4
votes
2answers
109 views

Analytical convergent sequence and numerical divergent sequence

Is it possible to construct a sequence that converges in theory but when computed numerically with a computer program is diverging. I feel that today our computer programs doesn't allow such ...
4
votes
3answers
261 views

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

I saw many stopping criteria for Newton's method all around Web and books. Some are defined from the residuals: of either current iteration only: $$ \|f(\mathbf{x}^{(k)})\| \leq \epsilon $$ (https://...
4
votes
2answers
8k views

Error in result of finite-difference approximation when refining

I have calculated the first derivative of following equation using Euler method (first order), Three point Finite Difference method (second order) and Four point Finite Difference method (third order)....
4
votes
1answer
163 views

What is the origin of the preasymptotic convergence behaviour in FEM?

When you have fine-scale features (e.g. boundary layers) in the solution, its FEM approximation on coarse meshes converge at strange apparent rates. Looking at Cea's lemma, is this behaviour because ...
4
votes
2answers
4k views

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

I am solving the following PDE; $$ \nabla^2 u = \frac{\partial^2 u}{\partial x^2} + \frac{\partial^2 u}{\partial y^2} = \rho, $$ where $\rho(0.5,0.5) = 2$ (zero elsewhere), $0\leq x,y\leq1$ and the ...
4
votes
1answer
298 views

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

I experimented with the PageRank algorithm. When the number of pages is large, I encountered a situation when one formula for re-normalizing a vector (so that sum of its components is equal to 1; ...
4
votes
3answers
1k views

Beale's function and newton iteration

I am trying to find the minimum of the so called Beale’s function given by $f(x_1,x_2) = (1.5-x_1+x_1x_2)^2 + (2.25-x_1+x_1x_2^2)^2 + (2.625-x_1+x_1x_2^3)^2$ Using Newton iteration $x^{(k+1)} = x^{...