17 votes
Accepted

Are Quasi-Newton methods computationally impractical?

I'm guessing you're referring to the discussion on pages 188-189 of that book. The author doesn't give much detail on quasi-Newton methods or substantiate the $\mathscr O(W^2)$ complexity estimate. To ...
Daniel Shapero's user avatar
11 votes
Accepted

How to calculate/derive analytic FEM Newton Jacobian

Your example is a pretty good indication that the two derivatives (with respect to $x$ and with respect to $u$) do not commute :) (In fact, they're very different beasts -- one is a Fréchet derivative,...
Christian Clason's user avatar
11 votes

Are Quasi-Newton methods computationally impractical?

Traditional quasi-newton methods like BFGS require $O(n^{2})$ storage for a potentially fully dense quasi-Hessian matrix and $O(n^{2})$ work in each iteration to update the factorized quasi-Hessian ...
Brian Borchers's user avatar
10 votes

Positive root of $x^q + bx - b$

According to Wolfram Alpha, $x^5+3(x-1)=0$ has no closed-form solution, so you can forget about a nice closed-form expression. :) I see nothing wrong with Newton's method; it should be quick and ...
Federico Poloni's user avatar
9 votes
Accepted

Lack of quadratic convergence in Newton's method

Yes: See Higham's book "Accuracy And Stability of Numerical Algorithms", second edition, chapter 25: Nonlinear Systems and Newton's Method. In particular, see the section on the "limiting residual" ...
user14717's user avatar
  • 2,155
7 votes
Accepted

Low-rank updates in BFGS

A low rank update to an $n$ by $n$ matrix $A$ is an update of the form $A=A+UU^{T}$ where $U$ is matrix with $n$ rows but very few columns (typically just one or two.) If the matrix $UU^{T}$ has $...
Brian Borchers's user avatar
7 votes
Accepted

Eigenvalues of $ab^T$

This is sometimes known as Buzano's inequality (http://www.jstor.org/stable/2159168). In general, if $\|x\|=1$, $P=xx^{\top}$ is a projection operator, so a simple application of Cauchy-Schwarz leads ...
Kirill's user avatar
  • 11.4k
7 votes

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

Some of the confusion comes about because mathematicians often consider artificial functions that happen to have size $O(1)$ whereas practitioners use functions and variables that just happen to be ...
Wolfgang Bangerth's user avatar
6 votes

How does one calculate reaction force in FEA?

To calculate the reaction forces at a node, Abaqus (or any structural FE code) simply sums the internal forces for all elements attached to that node. The reaction forces are the negative of that sum. ...
Bill Greene's user avatar
  • 5,984
6 votes

Implementation of the Jacobian-free Newton method

Not sure where you get your equation for $\epsilon$, but ultimately your approximation for the Jacobian matvec operation is a finite difference approximation to the directed derivative of $F(\cdot)$. ...
spektr's user avatar
  • 4,228
6 votes
Accepted

GMRES vs Newton-GMRES for Solving nonlinear PDE's

The reason is that GMRES can only be used for solving linear equations, i.e. equations of the form $Ax=b$, where $A$ is some matrix and $x,b$ are vectors. What GMRES does, essentially, is it ...
bgav's user avatar
  • 106
5 votes
Accepted

What would be a good approach to solving this large data non-linear least squares optimisation

I don't know much about tracking implicit surfaces, so I'm just going to start with the optimization problem and go from there. The optimization problem is, at the core, nonlinear least squares, and ...
Nick Alger's user avatar
  • 3,143
5 votes
Accepted

Roots of a function for eigensystem

I suspect the main problem is the magnitude of the values. If you divide through by $\cosh$ to make all the numbers smaller, then ApproxFun doesn't seem to have a problem finding all the roots. ...
Kirill's user avatar
  • 11.4k
5 votes

Why do Newton-Krylov iterations stagnate in this problem?

I'm not sure if this is the answer, but consider the case as $\alpha \rightarrow \infty$. In this case you're trying to solve $\iint_{\Omega} \cosh(P) dxdy = 0$ And since cosh looks like this: You ...
Charles's user avatar
  • 619
5 votes
Accepted

Newton's method problem

The Netwon(-Raphson) method helps you finding the root(s) of a function $f(x)$, that is, those values of $x_0$ for which $f(x_0) = 0$. In your case, the unknown value is $c$, so we start by writing ...
lr1985's user avatar
  • 677
5 votes
Accepted

Solving system of nonlinear vector functions

If you have a single vector equation $\vec{F}(\vec{x})=0$ then you solve it by representing that state vector $\vec{x}$ as a set of amplitudes $[x_0,x_1,...,x_{n-1}]$ after discretization by your ...
Maxim Umansky's user avatar
5 votes
Accepted

continuous analogues of Newton's method

No, it is not possible to use higher-order ODE integration methods on the Newton dynamical system to do better than vanilla Newton with some globalization strategy. Brezinski (2001) gives a negative ...
Daniel Shapero's user avatar
4 votes

Solving Kepler equation for true or eccentric anomaly

This question now has quite some age, but its subject crops up so repeatedly, that perhaps the following answer and references may still be helpful and not out of place. (a) 'Is there a reason to .....
terry-s's user avatar
  • 141
4 votes
Accepted

Methods of solving non-linear advection-diffusion systems beyond Newton-Raphson?

I'm assuming the limitation in 2D and 3D is storing the Jacobian. One option is to retain the time derivatives and use an explicit "pseudo" time-stepping to iterate to steady state. Normally the CFL ...
Aditya Kashi's user avatar
4 votes
Accepted

Can redundant variables be beneficial for root-finding convergence

In terms of computational effort, it is useless. I mean, you are still having a nonlinear problem with a bigger Jacobian (which is the worst part to be computed quickly). For next thoughts: dense ...
HBR's user avatar
  • 1,628
4 votes

How does one calculate reaction force in FEA?

Once the solution of the problem is known, i.e. you know displacement vector, to calculate reaction/internal forces an integral is evaluated \begin{equation} \mathbf{f}^\textrm{int} = \sum_{e=1}^{...
likask's user avatar
  • 906
4 votes
Accepted

Computational complexity of Newton's method

If you take $m$ steps, and update the Jacobian every $t$ steps, the time complexity will be $O(m N^2 + (m/t)N^3)$. So the time taken per step is $O(N^2+N^3/t)$. You're reducing the amount of work you ...
Kirill's user avatar
  • 11.4k
4 votes

How to use Newton-Raphson method to handle nonlinear terms in coupled system of PDEs?

The Nonlinear Schroedinger Equation is special. Instead of applying a Newton-Raphson method, it is easier to use an operator splitting scheme that uses the particular form of the nonlinearity because ...
Wolfgang Bangerth's user avatar
4 votes
Accepted

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

This is not a definite answer, but I highly recommend the work of Deuflhard on Newton methods (e.g. this report, this book, and another report I cannot find just yet). The basic idea is the following: ...
Laurent90's user avatar
  • 1,808
4 votes
Accepted

Backward Euler + Quasi Newton(Broyden) method fails to solve Van der Pol's equation(Stiff ODE)

This is not surprising. For one, Broyden is not very stable for highly ill-conditioned nonlinear systems, and having a stiff ODE means that the nonlinear system will be ill-conditioned. This is why ...
Chris Rackauckas's user avatar
3 votes

Which SciPy nonlinear solver when Jacobian is analytically known and sparse?

I believe newton_krylov may be what you are looking for. The documentation is confusing but I think you can do what you want. There doesn't seem to be any way to ...
whpowell96's user avatar
  • 2,259
3 votes
Accepted

Newton's method goes to zero determinant Jacobian

From what you describe, you have an ill-posed problem: The solution is not unique (not even locally). A standard way of dealing with this is the following: Instead of trying to solve $F(x)=y$, where $...
Christian Clason's user avatar
3 votes

How to calculate/derive analytic FEM Newton Jacobian

You need to understand how to actually compute derivatives when you want to take the derivative with respect to a function. I've recorded a lengthy example in lecture 31.55 here: http://www.math....
Wolfgang Bangerth's user avatar
3 votes

How can I use Projected Gradient Descent for this optimization problem with constraint?

Unfortunately, there is no closed form expression for the projection to the $\ell^1$ ball; it is also not a componentwise operation. In principle, the projection onto the scaled unit ball $\alpha B_{\...
Christian Clason's user avatar
3 votes
Accepted

The linear system in Quasi Newton method

It is a well-known theorem that conjugate gradients is guaranteed to converge (in exact arithmetic) within $r+1$ steps for an identity-plus-rank-$r$ matrix, regardless of its size. In finite precision,...
Richard Zhang's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible