Questions tagged [iterative-method]

A method which produces a sequence of numerical approximations which converges (provided technical conditions are satisfied) to the solution of a problem, generally through repeated applications of some procedure. Examples include Newton's method for root finding, and Jacobi iteration for matrix-vector solves.

Filter by
Sorted by
Tagged with
2
votes
0answers
108 views

Modal analysis of structure with aerodynamic damping

I'm using modal decomposition to predict the steady state response of a beam structure to harmonic loading. The structure itself is very lightly damped, but we know from experiments that the ...
3
votes
2answers
2k views

What is the difference between “Newton-type” and “Newton-like” iteration?

Is there any clear classification between different iterative methods? What is the difference between Newton-type and ...
5
votes
0answers
203 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_*$ ...
12
votes
1answer
635 views

Using fixed point iteration to decouple a system of pde's

Suppose I had a boundary value problem: $$\frac{d^2u}{dx^2} + \frac{dv}{dx}=f \text{ in } \Omega$$ $$\frac{du}{dx} +\frac{d^2v}{dx^2} =g \text{ in } \Omega$$ $$u=h \text{ in } \partial\Omega$$ My ...
10
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 ...
5
votes
1answer
149 views

Can we compare the speed of convergence of two different iteration methods of same order looking at their error estimates?

I have a two iterative method for approximating the inverse of given square matrix $A$ whose error terms are given as follows Error estimate of method $1$: $\lVert A^{-1} - X_{k}\rVert \leq q^{2^{k+...
7
votes
2answers
584 views

Hartree Fock iteration problem

I am writing a program to compute the ground state energy for any closed shell atom using Hartree Fock Roothaan method, with GTO basis. The code works for the simplest case, the helium, but it fails ...
4
votes
1answer
162 views

Factorization for reweighted least squares

I am solving a problem using an iteratively-reweighted least squares method: http://en.wikipedia.org/wiki/Iteratively_reweighted_least_squares Essentially this requires solving a number of least-...
5
votes
4answers
3k views

Fastest polynomial root finder for a given accuracy

I am looking for a very fast polynomial root finder, hopefully with a matlab code. I don't need very accurate results, 2-3 decimal places would be fine. Also the method should be able to optionally ...
6
votes
1answer
92 views

Numerical iterative method, estimating error

Given iterative method: $x_{n+1}=0.7\sin x_n +5 = \phi(x_n)$ for finding solution for $x=0.7\sin x +5$, I want to estimate $|e_6|=|x_6-r|$ as good as possible, with $x_0=5$, where $r$ is exact ...
6
votes
3answers
141 views

Newton's method for a given polynomial

Let $f(x)=\frac{1}{5}x^5+\frac{1}{3}x^3+x-1$ Show that $f$ has only one zero $r$ in interval $(0,1)$ To find approximation of $r$ we apply Newton's method $x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}...
1
vote
0answers
86 views

Increase convergence of non-linear equations resulting from ODEs

I am trying to solve a set of couple ODEs: $V_l(r) - r W_l(r) - f1(r) W_l' = 0\tag 1$ $r^2 h''_l(r) + f2 r h_l'(r) + f3 h_l(r) - f4 U_l(r) = 0 \tag 2$ $\kappa (U_l + h_l) + V_{l+1} + W_{l+1} = 0\...
11
votes
2answers
345 views

What is the underlying structure of scientific code performance?

Consider two computers with different hardware and software configurations. When running the exact same serial Navier-Stokes code on each platform it takes x and y time to execute one iteration for ...
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 ...
5
votes
0answers
343 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 ...
2
votes
1answer
950 views

Convergence of GMRES

From what I understand the GMRES method is (using Arnoldi Iterations/Modified Gram-Schmidt): The first vector of the Krylov subspace span of A is the normalized vector $\frac{\vec b - A\vec x_0} {|| \...
7
votes
1answer
648 views

Decreasing spectral radius

I have a $4\times 4$ matrix and I want to use Jacobi iteration on it. Right now the spectral radius is higher than $1$. I know that the method is guaranteed to converge if the matrix is diagonally ...
4
votes
1answer
628 views

Is it possible to ensure global convergence of a fixed point iteration?

Suppose I have a fixed point iteration of the form $$x_{n+1}=f(x_n).$$ Suppose further that after some initial testing, I found that it does not converge to an a priori known fixed point $x^*$. I ...
3
votes
1answer
533 views

Jacobi Iteration diverges?

I'm working through a problem in a textbook as follows: "Consider the $d \times d$ Toeplitz matrix $$ A = \left[ \begin{array}{ccccc} 2 & 1 & 0 & \cdots & 0 \\ -1 &2 &1&\...
2
votes
0answers
71 views

What are Implications of Commutative Diagrams?

This question may be too broad. But I really want to know some concrete explanations. I often find various commutations appear here and there, which concerns the application order of two operators. ...
8
votes
2answers
301 views

Looking for an algorithm that allocates climbing hold colors to wall sectors

I posted this question earlier on stackoverflow, where it was closed as off-topic. I hope it survives here. I our climbing gym, the routes need to be re-set from time to time. The following rules ...
5
votes
2answers
303 views

Levenberg optimizer halts quickly when given more variables, or fewer constraints

I'm using the g2o C++ optimization library to refine a GPS trajectory using accelerometer data. The program uses a Levenberg-Marquardt optimizer over data points representing the position and ...
15
votes
1answer
667 views

What is the current state of polynomial preconditioners?

I wonder what has happened to polynomial preconditioners. I am interested in them, because they appear to be comparatively elegant from a mathematical perspective, but as far as I have read in surveys ...
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 ...
1
vote
2answers
430 views

Checking for error in conjugate gradient algorithm

What is a good way to check if the any numerical error is occured in conjugate gradient algorithm. Additionally why is it not suggested to check error by checking A-orthogonality of search direction ...
9
votes
2answers
5k views

How to remove Rigid Body Motions in Linear Elasticity?

I want to solve $K u = b$ where $K$ is my stiffness matrix. However some constraints may be missing an therefore some rigid body motion may be still present in the system (due to eigenvalue zero). ...
8
votes
5answers
369 views

Iterative solution to a nonlinear equation

I appologize in advance if this question is silly. I need to compute the root of \begin{equation} u -f(u) =0 \end{equation} Where $u$ is a real vector and $f(u)$ is a real-vector valued function. ...
6
votes
3answers
1k views

Eigenvectors with the Power Iteration

To compute the eigenvector corresponding to dominant eigenvalue of a symmetric matrix $A\in\mathbb{R}^{n\times n}$, one used Power Iteration, i.e., given some random initialization, $u_1\in\mathbb{R}^...
2
votes
3answers
1k views

Convergence of the gradient descent and linear vs non-linear fixed point iteration

Suppose a system $$Ax=b$$ is given, with $A\in\mathbb{R}^{n\times n}$ being a symmetric positive-definite matrix, and some non-zero $b\in\mathbb{R}^n$. The gradient method with optimum step length can ...
9
votes
1answer
382 views

Solving a system with a small rank diagonal update

Suppose I have the original large, sparse linear system: $A\textbf{x}_0=\textbf{b}_0$. Now, I do not have $A^{-1}$ as A is too large to factor or any sort of decomposition of $A$, but assume that I ...
8
votes
1answer
353 views

Is the sparsity pattern of a linear system important for iterative (KSP) solvers?

Pretty much the question. Given a general sparse, non-symmetric (both numerically and structurally) matrix, how important is the sparsity pattern (i.e. row/column permutation of matrix/vector) for ...
11
votes
1answer
798 views

Projecting out the null-space of $A$ from $b$ in $Ax=b$

Given the system $$Ax=b,$$ where $A\in\mathbb{R}^{n\times n}$, I read that, in case Jacobi iteration is used as a solver, the method will not converge if $b$ has a non-zero component in the null-space ...
3
votes
2answers
188 views

How to establish that an iterative method can be applied to large matrices whose size may reach 10^3?

I have an iterative method for computing the Moore-Penrose generalized inverse of matrices, that is $$X_{k+1} = ((I-\beta X_{k}A)^t) + X_{k}$$ with initial approximation: $$X_{0} = \beta AA^t$$ ...
20
votes
3answers
3k views

What guidelines should I use when searching for good preconditioning methods for a specific problem?

For the solution of large linear systems $Ax=b$ using iterative methods, it is often of interest to introduce preconditioning, e.g. solve instead $M^{-1}(Ax=b)$, where $M$ is here used for left-...
1
vote
1answer
766 views

Gradient descent to stationary, or accumulation point

I recently came across the notion of an accumulation point as a result of a certain gradient descent variation. The following definition was found: An accumulation point $P$ is such that there are an ...
1
vote
3answers
259 views

Unique coordinates (solutions) in a single Gauss-Seidel iteration

I managed to reduce certain computational problem to the Gauss-Seidel solution of the following linear system: $$Ax=Ly,$$ where $A, L\in\mathbb{R}^{n\times n}$ are weighted Laplacian matrices (...
9
votes
2answers
1k views

Safe application of iterative methods on diagonally dominant matrices

Suppose the following linear system is given $$Lx=c,\tag1$$ where $L$ is the weighted Laplacian known to be positive $semi-$definite with a one dimensional null space spanned by $1_n=(1,\dots,1)\in\...
0
votes
1answer
1k views

A Comparison between GMRES, QMR and LU for Dense Matrices

As I see it, there are 3 ways to solve unstructured dense system of equations: GMRES, QMR and LU. Has anyone done a comparison for these three? As far as I know, LU is the preferred choice and it is ...
6
votes
3answers
1k views

Krylov Subspace Methods for Dense Systems

I am currently researching on the viability of using KS methods for solving large dense systems. What I wish to prove (or disprove) is that methods like CG, BiCG and QMR are as good (if not better) ...
5
votes
3answers
634 views

On Vanilla Preconditioners for solving dense $Ax=b$ iteratively

I am looking for preconditioners which don't assume anything about the matrix or its origins. I basically want to be able to type in the following in MATLAB and have quick solving time: ...
4
votes
4answers
234 views

Determining the algorithmic complexity

A few of the iterative matrix algorithms (CG,GMRES etc.) I have authored are acting rather funny. They converge to the right answers but take abnormally long time to run. I am in the process of ...
9
votes
3answers
921 views

Iterative methods for indefinite systems without block structure

Indefinite systems of matrices appear for example in the discretization of saddle point problems by mixed finite elements. The system matrix can then be put in the form $$\begin{pmatrix} A & B^t \...
7
votes
1answer
635 views

Jacobi iteration to reduce the quadratic function

Given certain function $f(X)$ which is quadratic in $X\in\mathbb{R}^{n\times d}$, $$\frac{1}{2}tr(X^TAX) - tr(Y^TBX)$$ for positive definite weighted Laplacian matrices $A, B\in\mathbb{R}^{n\times n}...
6
votes
1answer
289 views

Question about the smoothing operators in multigrid methods for nonlinear PDEs

Suppose we are dealing with a nonlinear problem, say $$ A u := L u + G(u) = f $$ the nonlinearity of the operator $A$ is the polynomial type, ie, $L$ is a linear operator, and $G(u) = u^k$, or ...
11
votes
1answer
460 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 ...
10
votes
1answer
6k views

Are there any heuristics for optimizing the successive over-relaxation (SOR) method?

As I understand it, successive over relaxation works by choosing a parameter $0\leq\omega\leq2$ and using a linear combination of a (quasi) Gauss-Seidel iteration and the value at the previous ...
15
votes
1answer
2k views

Can a Krylov subspace method be used as a smoother for multigrid?

As far as I am aware, multigrid solvers use iterative smoothers such as Jacobi, Gauss-Seidel, and SOR to dampen the error at various frequencies. Could a Krylov subspace method (like conjugate ...
8
votes
1answer
3k views

What is a good stop criterion when using an iterative method to find eigenvalues?

I read this answer, and realized I have been using the difference between sucessive iterates to define a stop criterion for an iterative method of finding eigenvalues/vectors. What are good stop ...
27
votes
2answers
13k views

Why is my iterative linear solver not converging?

What can go wrong when using preconditoned Krylov methods from KSP (PETSc's linear solver package) to solve a sparse linear system such as those obtained by discretizing and linearizing partial ...

1 2 3 4
5