Skip to main content

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
30 votes
3 answers
5k 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 (...
Paul's user avatar
  • 12k
19 votes
2 answers
3k 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 ...
Jed Brown's user avatar
  • 25.7k
17 votes
1 answer
2k 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 + (...
Ondřej Čertík's user avatar
15 votes
1 answer
4k 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 ...
hchen's user avatar
  • 151
13 votes
3 answers
10k 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 ...
usero's user avatar
  • 1,673
13 votes
3 answers
319 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 ...
Kirill's user avatar
  • 11.4k
13 votes
2 answers
7k 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}...
Paul's user avatar
  • 12k
13 votes
1 answer
383 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 ...
Endulum's user avatar
  • 735
11 votes
3 answers
2k 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 ...
James Womack's user avatar
11 votes
2 answers
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)$ (...
olamundo's user avatar
  • 599
11 votes
1 answer
506 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 ...
Allan P. Engsig-Karup's user avatar
11 votes
1 answer
221 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 ...
iterrate's user avatar
  • 111
10 votes
1 answer
1k 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)} $...
Bananach's user avatar
  • 799
10 votes
1 answer
307 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 ...
danny_23's user avatar
  • 501
9 votes
3 answers
2k 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 ...
David Ketcheson's user avatar
9 votes
1 answer
2k 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 ...
xotix's user avatar
  • 241
9 votes
3 answers
989 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 ...
Stavros Kousidis's user avatar
9 votes
2 answers
408 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 ...
Dirk's user avatar
  • 1,738
8 votes
1 answer
603 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. ...
Lukas Bystricky's user avatar
8 votes
1 answer
750 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 ...
Godric Seer's user avatar
  • 4,597
8 votes
1 answer
339 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 ...
Thangachelli Debopritama's user avatar
8 votes
1 answer
359 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)...
Paul's user avatar
  • 12k
8 votes
0 answers
234 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 (...
Thomas Klimpel's user avatar
8 votes
0 answers
586 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 ...
user avatar
8 votes
0 answers
171 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}_{+}^{...
Gilles's user avatar
  • 253
7 votes
1 answer
702 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-...
computational_scientist's user avatar
7 votes
3 answers
451 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 ...
Johann's user avatar
  • 71
7 votes
2 answers
2k 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 ...
Costis's user avatar
  • 1,320
7 votes
1 answer
468 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?
learningmath's user avatar
6 votes
3 answers
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$...
bigge's user avatar
  • 293
6 votes
2 answers
5k 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. ...
vanCompute's user avatar
6 votes
1 answer
678 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 ...
bla_bla_bla's user avatar
6 votes
1 answer
300 views

Why FEM for incompressible materials is ill-posed?

I am an engineer who is trying to get a deeper understanding of FEM. I have been using the Zienkiewicz texts as my bible. It touches on the issue of incompressibility but I need a more intuitive way ...
TheCodeNovice's user avatar
6 votes
2 answers
153 views

Integrating exponential of second degree polynomials

I'm looking to compute the value of the following integral, for small values of $|a|$. $$u_n(a,b)=\frac{1}{2}\int_{-1}^1 x^ne^{ax^2+bx}\mathrm{d}x$$ In this equation, $a,b \in \mathbb{R}$ and $n \in \...
PC1's user avatar
  • 436
6 votes
1 answer
308 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. ...
tpg2114's user avatar
  • 608
6 votes
1 answer
16k views

The definition of asymptotic convergence?

What is the difference between convergence and asymptotic convergence? Why say the convergence is asymptotic?
JW Xing's user avatar
  • 133
5 votes
2 answers
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 ...
Paul's user avatar
  • 12k
5 votes
3 answers
183 views

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 peer reviewed numerical papers, the order of accuracy of finite difference and finite volume for PDEs is computed in multiple norms, usually $l_1$, $l_2$ and $l_{\infty}$, and other times $l_{\...
Millemila's user avatar
  • 435
5 votes
1 answer
156 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}...
user14717's user avatar
  • 2,155
5 votes
1 answer
3k views

Newton's method goes to zero determinant Jacobian

I am using the Newton's method to solve $3\times3$ systems. For some particular cases, it turns out that at a given iteration, the Jacobian matrix cannot be inverted and that its determinant is very ...
Sylvain B.'s user avatar
5 votes
2 answers
717 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$ ...
burk's user avatar
  • 185
5 votes
1 answer
234 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 ...
Matt Knepley's user avatar
  • 4,269
5 votes
1 answer
140 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 ...
Aage's user avatar
  • 188
5 votes
0 answers
142 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 ...
Milind R's user avatar
  • 607
5 votes
0 answers
248 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_*$ ...
Christian's user avatar
  • 501
5 votes
0 answers
446 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 ...
Hassan's user avatar
  • 151
5 votes
0 answers
88 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 ...
skybluecodeflier's user avatar
4 votes
2 answers
121 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 ...
Smilia's user avatar
  • 468
4 votes
3 answers
2k 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://...
Camille C's user avatar
4 votes
2 answers
11k 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)....
AGN's user avatar
  • 544

1
2 3 4 5