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.
299
questions
1
vote
1
answer
2k
views
Solve linear system with Newton-Raphson method
Is it possible to solve a linear matrix system $A x = b$ using the Newton-Raphson method? If yes, how can this be done? More special, how is the derivative build?
1
vote
1
answer
1k
views
How to solve the problem without using symbolic computation
I have the following simple nonlinear equations with two unknowns only:
$$\left\{
\begin{array}{c}
\int_1^2{\dfrac{ e^{{a_1} x+{a_2} x^3}}{1+x^2}} \, dx=1 \\[13pt]
\int_1^2{ x^2 e^{{a_1} x+{a_2} x^...
1
vote
1
answer
527
views
Direct or iterative solver for ill-conditioned problems
I have to solve an ill-conditioned sparse matrix. Once I read that iterative solvers are the better tool for such problems. Is that true? If yes, why?
1
vote
1
answer
93
views
Why do not we choose the error solution norm as an iterative method's criterion?
For solving linear system
$$
Ax=b,
$$
using iterative mehods, we often use the terminate criterion as follows:
$$
\frac{\|r_k\|}{\|r_0\|}=\frac{\|b-Ax_k\|}{\|b-Ax_0\|}<eps.
$$where $x_0$ is the ...
1
vote
2
answers
99
views
Implementing matrix term version of Gauss-seidel
I am trying to implement the below description from Ch. 11 of Heath's "Scientific Computing An Introductory Survey" of the Gauss-Seidel iterative method for solving a system of linear ...
1
vote
2
answers
499
views
How can I color my Mandelbrot set like this?
I have a background image of a fractal on my phone that I would like in a higher resolution with super sampling, and decided to write my own program for it. I've got down rendering a Mandelbrot set, ...
1
vote
2
answers
1k
views
Linear solvers: How to deal with a singular system? (Poisson equation with Neumann boundary conditions)
The question is in the context of iterative numerical solution of large PDE systems with Finite Differences or Finite Elements:
Stating the Poisson equation with Neumann boundary conditions will lead ...
1
vote
2
answers
199
views
Finding null vectors of a parameter-dependent matrix
I have dense complex matrices $M(z)$ in which each element $M_{ij} = M_{ij}(z)$
depends on a complex parameter $z$. I need to find $z$ such that the matrix $M$
gets singular, i.e. I am looking for ...
1
vote
1
answer
1k
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
1
answer
277
views
Convergence stall when solving 2D Poisson PDE with pure Neumann boundaries (finite differences)
I recently started coding a small library of 2D PDE solvers (time dependent and time independent), and my first attempt was a 2D Poisson equation of the form:
$$\nabla(\epsilon\nabla\varphi)=\nabla\...
1
vote
1
answer
63
views
Wrong results for $2$ stage multistep method $y_{n+2} - y_n = h\left[(1/3)f_{n+2} + (4/3)f_{n+1} + (1/3)f_n\right]$
I need to fix a code to utilise the $2$ stage multistep method :
$$y_{n+2} - y_n = h\left[(1/3)f_{n+2} + (4/3)f_{n+1} + (1/3)f_n\right]$$
Since this is an implicit method, I used a Newton-Raphson ...
1
vote
1
answer
948
views
Jacobi iteration for finite difference: when to stop?
I implemented a finite difference scheme to solve Poisson's equation in a 2D grid in C. I solve the system by using Jacobi iteration. Everything works fine until I use a while loop to check whether it ...
1
vote
1
answer
83
views
Powers of convergent DPR1 matrices in $O(d)$ time?
Suppose $u$,$v$ are vectors and $A$ is a convergent $d\times d$ diagonal + rank-1 matrix.
How do I estimate $u^T A^k v$ in $O(d)$ time?
Powers of convergent diagonal $D$ can be computed in $O(d)$ time ...
1
vote
1
answer
83
views
Memory issues with iterative solvers
Was trying to implement a poisson 2d solver using Conjugate Gradient Method, so from 10x10 grid the matrix becomes 100x100 (since we have 100 nodes to find the values at), 100x100 grid goes to ...
1
vote
2
answers
254
views
When should I write a matrix-vector function to handle the sparse matrix vector multiplication?
This semster, I have been studying the iterative methods for large sparse matrix system. But I have some questions.
For large sparse matrix, we must use an economic storage to store them. The most ...
1
vote
2
answers
930
views
Evaluation of slope at iteration ith - Newton-Raphson method
I'd like to know how Ansys computes the slope (=stiffness matrix) at point x1 in figure. I'm studying the way in which Ansys uses the Newton-Raphson method when there are nonlinearities.
In the slide ...
1
vote
1
answer
779
views
Conjugate gradient - ill-conditioning and numerical tolerance
I would like to solve system $Ax=b$, where $A$ is SPD, but very ill-conditioned ($\text{cond}(A)>10^{11}$). I am interested in using UNpreconditioned version of the conjugate gradient method.
Is ...
1
vote
1
answer
135
views
Questions about iterative projection methods in Saad book
I am reading Chapter 5 of Saad's iterative methods book, and I don't understand section 5.2.1 about the two propositions of optimality results.
In the statements of the propositions, what does it mean ...
1
vote
1
answer
8k
views
Implementation of the Jacobi iteration to find the solution to $Ax = b$
I implemented the Jacobi iteration using Matlab based on this paper, and the code is as follows:
...
1
vote
1
answer
295
views
OpenMP threaded nonlinear solver for complex numbers
Problem:
I have translated Jacobian-Free Newton-Krylov solver written by
C. T. Kelley to Fortran and now want to parallelize it on a shared-memory system with OpenMP. In addition, I want to ...
1
vote
2
answers
96
views
Performance metrics to compare initial-boundary value problem solutions
I am comparing the performance several finite difference methods of solving an initial-boundary value problem. There are several dimensions to this comparison:
Number of cells
Number of timesteps
...
1
vote
2
answers
638
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 ...
1
vote
3
answers
290
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 (...
1
vote
1
answer
32
views
Find best matching ranges below limit in defined set of numbers
I am trying to calculate the best set of cuts for some wood cutting to reduce the waste.
So: Given a set of numbers, the goal is to find the best matches below a limit (size of wood beam).
Example of ...
1
vote
1
answer
513
views
Effecient method for iterating over sparse dataset
Apologies if this isn't the appropriate forum for this question.
I have a set of elements that I need to iterate over as part of a modeling workflow. The elements exists over a set of dimensions (i, ...
1
vote
1
answer
521
views
2D heat equation in both steady state and Transient state using iterative solvers
While solving a 2D heat equation in both steady-state and Transient state using iterative solvers like Jacobi, Gauss seidel, SOR. Should the answers, I mean the converged results of Temperature ...
1
vote
1
answer
110
views
How to implement Geometric Multigrid in non-rectangular grids?
It is quite easy to implement multigrid on a rectangular grid but what about an non-rectangular?How to coarse a non-rectangular grid and apply multigrid(assume an easy non-rectangular grid capital ...
1
vote
1
answer
210
views
How suitable is multigrid method for time-dependent PDEs?
For elliptic PDEs (Poisson-type), the multigrid method is very sufficient, but how about time-dependent problems (i.e parabolic or hyperbolic PDEs)?
Is it efficient to solve such problems using a ...
1
vote
1
answer
362
views
Difference between explicit and implicit preconditioning
What is the difference between an explicit and implicit preconditioner?
1
vote
1
answer
863
views
Iterative Closest Point Algorithm
I am currently working on an iterative closest point algorithm (in C++, see here).
I understand the basic premise of an ICP algorithm. You have two point clouds (a target and a reference) and you ...
1
vote
1
answer
244
views
Iterative solution of ill-conditioned matrix systems
I want to solve a matrix system of the form $Ax=b$ where $A$ is ill-conditioned. The matrix system comes from a structural simulation problem which was discretized using finite elements. I do not have ...
1
vote
1
answer
66
views
Optimal algorithm choice for mixed diagonal/dense problem
$$
\text{Let}\\
A, B \in \mathbb{C}^{n \times n} \text{ and } \hat{\alpha}, \hat{\beta} \in \mathbb{C}^{n}, \hat{f} \in \mathbb{C}^{2n}
\\
\text{Find }\\
\underline{\mathbf{x}} \in \mathbb{C}^{2n} \...
1
vote
1
answer
793
views
Convergence problem in iterative method
I am trying to solve two non-linear equations self-consistently in a Gummel loop. Sometimes (every once in a while), I get to a situation when the loop repeats itself with wrong solutions and a ...
1
vote
0
answers
119
views
Which dense matrices are hard to invert?
Suppose I'm solving $Ax=b$ for dense $m\times d$ matrix $A$. For which $A$ is this hard to do?
More concretely, is there any work on estimating the error after $k$ steps of iterative solver, $k\le d$, ...
1
vote
0
answers
62
views
Does the choice of a complex inner product affect Krylov methods?
As far as I understand there are two definitions of the complex inner product:
$$(a,b) = b^H a$$
and
$$(a,b) = a^H b$$
I know some linear algebra libraries such as BLAS and Eigen uses the second one.
...
1
vote
0
answers
39
views
Solution to minimization problem when variables factor in 2 analytical problems
I am asking a follow up question to this question, but I could probably have written it as an answer instead. However, I don't know if what I am doing here makes sense or is too complicated for my ...
1
vote
0
answers
73
views
Slow convergence of Stokes solver used with the Immersed Boundary method
I am using Immersed Boundary Method to simulate elastic particles in 3D Stokes flow. Specifically, one has $\nabla ^2 \mathbf{u}-\nabla p + \mathbf{f}(t) = 0$, $\nabla \cdot \mathbf{u} \; $, where $\...
1
vote
0
answers
37
views
Approximation in the derivation of the Arc Length method
I am studying the proof of the Arc Length method in section 2.2 of this thesis. In equation (2.2) the author introduces the supplementary conditions
$$
(\Delta {\bf u} + \delta {\bf u})^T \cdot (\...
1
vote
0
answers
152
views
Upper bound on condition number in linear preconditioning
I'm studying iterative methods for solving linear system, and I find the following setting in Wikipedia:
Consider a matrix splitting $A = M-N$, where $A,M,N$ are all symmetric and positive definite ...
1
vote
0
answers
44
views
Problem with recursive implementation of Subspace Iteration method in Numpy
I am having trouble with implementing the method of subspace iteration to find the eigenvalues and vectors of a random, symmetric matrix, A that is mxm with m = 10. ...
1
vote
0
answers
289
views
Minimax optimization with an oracle
I have an optimization problem of the following form: $$\min_y\left[\max_x f(x,y)\right].$$ It is fairly straightforward to minimize $f(x,y)$ over $y$ with $x$ fixed, and similarly to maximize $f(x,...
1
vote
0
answers
791
views
Is there any function to calculate condition number of sparse matrix in Eigen libraray?
The function JacobiSVD and BDCSVD can calcuate condtion number of a dense matrix via singular values.
However I need to know condition number of a sparese matrix due to slow computation speed using ...
1
vote
0
answers
88
views
2-norm of solution update suddenly becomes zero after a few iterations
I am trying to solve the Poisson equation in 2D for heterostructure devices. I have linearized the equation and discretized it using FDM. I am using BiCGStab to iteratively solve for the solution as ...
1
vote
0
answers
390
views
1-D Conduction Steady state heat transfer using FD
I have tried to solve 1-D Conduction Steady state heat transfer problems in Matlab (see below).
Here is the 1-D model:
T''[x] == 0, T[0] == 100, T'[100] == 0
...
1
vote
0
answers
96
views
Bifurcation points on homotopy path by numerical continuation?
I am trying to implement an algorithm that finds (possibly) all solutions of a system of nonlinear polynomial equations $$F(X) = 0$$ I thought about using the (convex) homotopy $$H(X,T) = TF(X) + (1-T)...
1
vote
0
answers
62
views
Can the standard multigrid performance be used for time-dependent PDEs?
Consider a time dependent pde(i.e u(x,t)).I know when only space-coarsening is used the standard multigrid performance can be applied but what if instead we use only time-coarsening?Can we apply the ...
1
vote
0
answers
99
views
BicgStab is not able to solve while Jacobi or GaussSeidel Methods can
I am trying to solve the 2D laplace equation,
$\frac{\partial^2 T}{\partial x^2} + \frac{\partial^2 T}{\partial y^2} = 0; \qquad 0 \lt x \lt 1, \quad0 \lt y \lt 1$
Subjected to the boundary ...
1
vote
0
answers
78
views
Kinetic preconditioning
Publication arXiv:0804.2583 describes a method for doing self-consistent iteration without having to diagonalize the Hamiltonian operator at every step.
IX. PRECONDITIONING
As already mentioned, ...
1
vote
0
answers
41
views
Logging vs outputs in iterative optimisation
I'm coding an iterative algorithm of constrained continuous optimisation. An augmented Lagrangian algorithm (outer) calls a bound-constrained L-BFGS-B algorithm (inner), which calls a line search ...
1
vote
0
answers
69
views
Fixed point iteration reduction factor
In a book for solving a nonlinear differential equation with $N+1$ points, $u_{xx} = e^{u}, u(-1)=u(1) = 0$, in $[-1,1]$ with homogeneous Dirichlet boundary conditions, the fixed point iteration is ...