16 votes

Difference between Gauss-Newton method and quasi-Newton method for optimization

Quasi-Newton methods construct an approximate Hessian for an arbitrary smooth objective function $f(x)$ using values of $\nabla f$ evaluated at the current and previous points. At each iteration of ...
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,...
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 ...
user avatar
8 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" ...
user avatar
  • 2,001
7 votes
Accepted

Solving a system of nonlinear equations with an ODE solver is faster than with the Newton method?

This is somehow unexpected, but my recent experience with solving a system of nonlinear equations is that treating them as the right hand side of a system of ordinary equations and then evolve the ...
user avatar
7 votes
Accepted

Newton iteration applied to nonlinear PDE

It's a bit easier to see if you write your equation in the a semi-discretised system of the form $u^{\prime}(t) = F(u(t))$ and with the application of the $\theta$-method and approximating $u^{\prime}(...
user avatar
  • 5,259
7 votes

Strong coupling of a non-linear multiphysic problem: failure with Newton Raphson method

The issues you're running into now are not a failing of Newton-Raphson, but a question of coupling. You're doing iterated sequential coupling -- solving each equation sequentially and then iterating ...
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 ...
user avatar
  • 11.4k
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 $...
user avatar
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 ...
user avatar
6 votes
Accepted

Caveats of Hessian free method

The approximation error is $\mathcal{O}(\varepsilon)$, where $\varepsilon$ is the parameter in the finite difference calculation. It will be good to know how this approximation affects the number of ...
user avatar
6 votes

Do I need to impose boundary conditions in the Jacobian matrix?

There are multiple ways of implementing Dirichlet boundary conditions when using the finite element method. For each unknown $i$ of the system belonging to the Dirichlet boundary, you can zero out ...
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. ...
user avatar
  • 5,734
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)$. ...
user avatar
  • 3,673
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 ...
user avatar
  • 96
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 ...
user avatar
  • 599
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. ...
user avatar
  • 11.4k
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 ...
user avatar
  • 3,003
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 ...
user avatar
  • 657
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 ...
user avatar
4 votes
Accepted

Do I need to impose boundary conditions in the Jacobian matrix?

This remark is a bit too long for a comment, but regarding DanielShapero's remark with respect to changing the Jacobian matrix, for every degree of freedom $i$ corresponding to a Dirichlet boundary ...
user avatar
4 votes
Accepted

Solving Kepler equation for true or eccentric anomaly

The most robust way of answering this is to benchmark it. Failing that, there are several things to note (roughly in order of importance). First, the most cheap floating-point operations on a modern ...
user avatar
  • 11.4k
4 votes
Accepted

Doubt regarding stopping criterion for Newton method

If you converge, you would expect the steps to get small. Ideally, a step $\delta x_k$ in an optimization algorithm would go from the current iterate $x_k$ to the exact solution $x^\ast$, so $\|\delta ...
user avatar
4 votes
Accepted

Hessian-free and Truncated Newton methods

It looks like this paper is combining Hessian-free with truncated Newton method. Yes, it is. ...the approach is referred to as Hessian-free method. That is because the Hessian is never computed ...
user avatar
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 ...
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 ...
user avatar
  • 1,606
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}^{...
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 ...
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 ...
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: ...
user avatar
  • 1,075

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