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.
208
questions
0
votes
1
answer
77
views
optimal gradient algorithm to determine best $α_k$
Let's consider an optimal-step gradient algorithm and assume that:
$g(α) := f(X_k - α∇f(X_k)) = 2α^2-4α+17$, how can we determine the optimal $α_k$?
Here is my simple solution:
$g(α) = 2α^2-4α+17$
$g'(...
- 25
0
votes
1
answer
47
views
step-fixed algorithm first iterates
let us have the fixed-step gradient algorithm, with $p = 2$ and we assume that for $X = (x, y)$,
$∇ f(X) = \begin{pmatrix}
x -1\\
y -2
\end{pmatrix}$
Let me assume we intialize with $X_0 = (0,0)$ what ...
- 25
0
votes
1
answer
66
views
step-fixed algorithm to minimize f, which step to ensure convergence?
If we want to apply the fixed-step gradient algorithm to the minimization of $f(x) = \frac{1}{2}(Ax, x)$ where $A$ is a symmetric 2x2 matrix with eigenvalues $\lambda_1 > \lambda_2 > 0$, for ...
- 25
0
votes
1
answer
40
views
Estimating the rate of convergence of Projected Gradient Descent on constrained polynomial objectives
I am estimating the order of convergence of Projected Gradient Descent (GD) on quadratic polynomials with random coefficients independently drawn from Uniform(-1,1) and bounded by a unit hypercube. I'...
- 23
1
vote
1
answer
136
views
How to refine $h$ and $\Delta t$ for convergence tests on evolution PDE
Setting
I am solving for $u(x,y,t)$ the wave equation $\partial_{tt} u - \partial_{xx} u = f$ on $(x,y)\in\Omega=[0,1]\times \mathbb{R}$ by splitting it into an equivalent first order system:
$$\...
- 13
0
votes
0
answers
117
views
Is there a fast matrix-free inverse power iteration?
Problem: I want to solve the eigenvalue problem
$$x=Ax$$
to the eigenvalue $1$ for a large matrix (roughly $N^3\times N^3$ and $N$ ranges from 10 to 100) where $A$ is stochastic (i.e. all entries are ...
0
votes
0
answers
58
views
Calculating a 2D Ewald sum for a multipolar expansion
I am attempting to calculate the potential of a particle at the center of an infinite two-dimensional lattice as per the following reference:
Reference: Lambin, PH & Senet, P. Ewald Summation of ...
- 43
3
votes
1
answer
199
views
Stability of Euler forward method
I am trying to solve a linear system of ODEs of the form:
$$ \frac{du}{dt} = A u, \quad u(0)=k$$
where $A$ is a 2x2 matrix and $u(t)$ is a 2x1 column vector. I want to solve this numerically, using ...
- 31
3
votes
1
answer
151
views
Role of rotation's pivot point in optimization?
In this paper, the authors describe how to use locally rigid transformations (sampled on nodes in space) to deform mesh vertices. In the paper, rotations are relative to the pivot point, which ...
- 31
1
vote
2
answers
81
views
Why is the definition of convergence different for root finding algorithms as compared to sequences?
The definition of convergence for root finding algorithms is given in a few sources as: A sequence ${x^k}$ generated by a numerical method is said to converge to the root $\alpha$ with order $p\geq 1$ ...
- 11
2
votes
1
answer
315
views
Why do we use modified pressure in incompressible multiphase solvers with gravity?
The context of my question is two-phase incompressible solvers such as interFoam in OpenFOAM, but I have seen this trick used ...
0
votes
0
answers
67
views
Faster convergence for minimizing least squares of forward modelling problems
This specific question was raised from optimizing parameters of column experiments in the hydrogeological context. I want to optimize a parameter of interest (in this case $D$), based on experimental ...
- 23
3
votes
1
answer
245
views
Convergence-test for ODE approximates wrong limit
I am trying to numerically solve a differential equation but I am having trouble getting the convergence test to run properly. The problem is as follows:
Consider an ODE
$$y'(t) \enspace = \enspace f(...
- 185
6
votes
1
answer
342
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 ...
- 201
0
votes
0
answers
78
views
Convergence rate for not smooth solution with classical $P^1$ Lagrangian FEM
I'm using classical $P^1$ finite elements to solve $- \Delta u = f$ with Dirichlet BC in a 2D domain $\Omega$.
I know from theory that the solution is not in $H^1$ for my particular choice of $f$, so ...
- 405
1
vote
0
answers
144
views
Convergence of Evolutionary Algorithms
When it comes to Evolutionary Algorithms (e.g. Genetic Algorithm), I have often heard people make the following broad statement: "Evolutionary Algorithms Do Not Converge."
I was curious ...
- 139
5
votes
3
answers
185
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_{\...
- 445
2
votes
0
answers
86
views
"Unspoken Tradeoff" in Convergence Rates for "Quasi-Newton vs. Gradient Descent"
Is there an "Unspoken Tradeoff" in Convergence Rates for "Quasi-Newton Methods vs. Gradient Descent"?
As a quick summary:
Gradient Descent based algorithms try to find the minimum ...
- 139
1
vote
0
answers
51
views
Solution fails to converge with different collocation point selection
I'm trying to learn about collocation. As an example, I am using Numerical Recipes, 20.7.12, but changing the basis. To wit, I'm trying to solve
$$y'' + y' - 2y + 2 = 0, -1 \le x \le 1, y(-1) = y(1) = ...
- 2,165
4
votes
0
answers
97
views
Computationnal Mechanics : Three Bodies contact problem with ALM
I am facing an issue with convergence of a contact problem consisting of three successive bars, as presented below.
A force is applied on the right hand of the first bar so there is contact between ...
- 41
6
votes
2
answers
156
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 \...
- 436
2
votes
1
answer
122
views
Discontinuous Galerkin order of convergence on arbirary refined mesh: step-12 deal.ii tutorial
I'm learning DG methods and in order to practice a little bit I'm using the deal.ii library. In particular, I'm looking at step-12, where they solve
$$\operatorname{div}(\beta u) = 0$$
$$u = g_D \text{...
- 405
0
votes
0
answers
142
views
Getting euclidean distance between vector A and C without anyway of retrieving them when their distances with a common vector B is known
Motivation:
My plan is to get the overall euclidean distance matrix for all the vectors in N number of dataset. Each dataset is basically an array of n-dimensional points. For e.g: A dataset can be ...
- 11
1
vote
0
answers
297
views
Confused on how Method of Manufactured solutions works?
I am new to computational science and I am trying to wrap my head around how MMS works. I am solving the time independent Helmholtz equation as a simple test of the technique
so my starting equation ...
- 201
2
votes
2
answers
192
views
Manufactured solution for $-\operatorname{div}(a(x) \nabla{u}) = f$ when $\alpha(x)$ is discontinuous
I'm studying the dealii tutorial number 4,5 and I understand the workflow. I've also been able to find the EOC by using manufactured solution where $f$ is a smooth r.h.s. and $\alpha(x)$ smooth too.
...
- 405
1
vote
1
answer
144
views
Step3 in deal.II - Convergence of the mean
I'm trying to understand the Convergence of the mean part of the Step-3 tutorial in deal.II. The authors say that $\frac{1}{|\Omega|}\int_{\Omega} u_h(x)dx$ converges with $\mathcal{O}(h^2)$, but I ...
- 405
0
votes
1
answer
112
views
2 point BVP solver: how to compute errors
Background
I am working with chapter 2 in LeVeque's book: https://faculty.washington.edu/rjl/fdmbook/
I have build my own solver in Python to solve the 2 point BVP:
$$
\epsilon u''+u(u'-1) =0 , \\
u(0)...
- 255
1
vote
0
answers
45
views
Convergence of the Roothaan-Hall equations
Suppose that we are given a time-independent quantum mechanical system whose wavefunction depends on three space coordinates. Let $F$ be the Fock operator of the system. Suppose also that we have a ...
- 331
2
votes
1
answer
516
views
Solving Cahn-Hilliard equation using semi-implicit Fourier spectral methods
So, I have written both a C and python code to solve the 2D Cahn-Hilliard equation:
\begin{equation}
\frac{\partial c}{\partial t} = \nabla^2\left(c^3 - c - \kappa\nabla^2c\right)
\end{equation}
...
- 113
1
vote
1
answer
84
views
Rate of convergence - Stochastic Euler Method
The absolute error criterion of the pathwise approximation of an Ito process $X$ by an Euler approximation $Y$ is:
$$
\epsilon=E\left(\left|X_{T}-Y(T)\right|\right)
$$
We shall say that a time-...
- 111
4
votes
3
answers
3k
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://...
- 43
1
vote
1
answer
329
views
FEM solution for Poisson is not exact at nodes
Let's consider the usual Poisson problem for FEM $$-u''(x)=1 \quad x \in [0,1]$$ with homogeneous Dirichlet boundary conditions. The solution is $u(x)=-\frac{1}{2}x(x-1)$
I know that the FEM solution (...
- 405
1
vote
1
answer
424
views
L2 norm optimization problem
I have an optimization problem where i need to find an image x, that is very close to x' such that:
monitor(x') is valid but monitor(x) is invalid. (output is valid
when the neural network output is ...
- 11
0
votes
1
answer
453
views
Finite elements with CFL condition - How to obtain correct order of convergence
I have discretized a PDE with continuous finite element method in spatial variable and with implicit Euler or Crank-Nicolson in temporal variable. In both cases, I have error estimates in $L_2$ norm ...
- 145
9
votes
3
answers
1k
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 ...
0
votes
0
answers
41
views
Devising Convergent Numerical Scheme for PDE
I'm currently looking at the PDE
\begin{align*}
u_t + \left[x(1-y) - (1-x)\right]u_x - (1-y) u_y + (z-xy) u_z = (z-xy) u_{xy} - (1-x)u& \\
\end{align*}
with
\begin{align*}
u(x,y,z,0) = 1& \\
...
- 141
1
vote
1
answer
177
views
Finite Difference for Advection Equation With Source
I'm trying to find a convergent finite difference scheme for the PDE
\begin{equation}
\begin{split}
u_t + (x-1) u_x &= (x-1)u, \hspace{.5cm} x \in [0,1] \\
u(x,0) &= 1 \\
u(1,t) &= 1. \\
\...
- 141
1
vote
1
answer
71
views
Where could error terms that blow up in SWE come from?
I have been working on a solver for shallow water equations with reflective boundary conditions. I have found that it diverges very fast. As a workaround I noticed yesterday that if I smooth the ...
- 159
4
votes
1
answer
457
views
When does L-BFGS outperform GD?
In practice, L-BFGS is frequently held comparably to other inexact QN methods, and it provides a middle ground of sorts between Hestenes–Stiefel CG and BFGS as memory goes from zero to infinity (...
- 211
1
vote
0
answers
73
views
Multigrid Reduction In Time Convergence
I am trying to solve a 2D dynamic linear elasticity model parallel in time using Xbraid. The spatial domain is [0,1]x[0,1] and time domain [0,1]. For time integration I am using a backward Euler ...
- 481
3
votes
1
answer
104
views
Numerical integration in time for finite elements
I am trying to solve $M\ddot{u}=-Ku+F_\text{ext}$ for a 2D linear elastic model with $M$ be the mass matrix,$K$ the stiffness matrix and $F_\text{ext}$ the external load vector coming from a uniformly ...
- 481
1
vote
0
answers
104
views
Convergence of Conjugate Gradient Algorithm
I am trying to solve a linear elasticity model using finite element discretization in a rectangle domain [0,1]x[0,1]. For the solution of the the linear system $Ku=F$ I am using the CG algorithm. ...
- 481
3
votes
1
answer
453
views
Choosing an appropriate time step for a discrete & continuous dynamics simulation
I have inherited of a flight dynamics simulation in C++ which represents a small drone with it's autopilot, actuator dynamics and a solid state IMU.
Hence, it is composed of a few models, some ...
- 131
1
vote
1
answer
122
views
interface value on the error equation
https://www.jstor.org/stable/pdf/2157482.pdf, here I have a problem in last equation of (2.6) in section (2.1). When they are considering error equation on the interface $\Gamma$ they get $e_v^{(n)} = ...
- 41
1
vote
1
answer
96
views
Issue solving nonlinear equation containing a quotient
I have a coupled set of PDEs that need to be solved as part of a larger problem. I am currently approaching this by computing spatial derivatives with finite differences and using PETSc's nonlinear ...
- 255
2
votes
2
answers
217
views
Accelerating convergence of a generalized continued fraction
I wish to compute
$$
\frac{1}{1 + \frac{1^3}{1 + \frac{2^3}{1 + \frac{3^3}{1+\cdots} } } }
$$
to high accuracy. To start, I tried computing
$$
\frac{1}{1 + \frac{1^2}{1 + \frac{2^2}{1 + \frac{3^2}{1+\...
- 2,165
5
votes
1
answer
157
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}...
- 2,165
1
vote
0
answers
53
views
Effect of reducing flux consistency order at boundary on convergence order
Consider the 1D nonstationary convection-diffusion PDE
$$
\begin{alignat}{2}
\partial_t u &= -a \partial_x u + D \partial_{xx}u, &\qquad x \in (0,1), t \in (0,T), \\
f(t) &= \left.\left( a ...
- 451
2
votes
1
answer
2k
views
what is non-asymptotic convergence?
I guess convergence in general means it is in asymptotic sense but what does non-asymptotic convergence mean?. Can someone please explain with an example?
2
votes
0
answers
38
views
Convergent Finite Difference Scheme for Parabolic Equation
Consider the PDE $$u_t = b_{11}u_{xx} + 2b_{12}u_{xy} + b_{22}u_{yy},$$
where $b_{11}, b_{22} > 0$, and $b_{12}^2 < b_1b_2$.
In Strikwerda's book, the ADI scehme \begin{align*}
\left( 1 - \frac{...
- 141