# Tag Info

### 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 ...
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 ...
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,...

### 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 ...

### 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 ...
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" ...
Accepted

### 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 ...

### 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. ...

### 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)$. ...
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 ...
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 ...
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. ...

### 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 ...
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 ...
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 ...
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 ...
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 ...
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 ...

### 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}^{...
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 ...

### 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 ...
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: ...
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 ...
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,...

### Are there special methods for solving $f'(z)=0$ for analytic $f$?

While it's especially well-suited for polynomial systems, Smale's $\alpha$-theory gives a way to be certain that the Newton iterates for a nonlinear analytic system will converge, and also gives a ...
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 \$...