# Tag Info

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 ...
• 10.3k
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,...
• 12.3k

### 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 ...
• 18.8k

### 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 ...
• 11.5k
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" ...
• 2,155
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 ...
• 11.4k
Accepted

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 $... • 18.8k 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 ... • 55.7k 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. ... • 6,144 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)$. ... • 4,258 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 ... • 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 ... • 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. ... • 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 ... • 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 ... • 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 ... • 2,575 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 ... • 10.3k 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 ... • 181 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 ..... • 141 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 ... • 1,648 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 \mathbf{f}^\textrm{int} = \sum_{e=1}^{... • 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 ... • 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 ... • 55.7k 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: ... • 1,943 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 ... • 12.3k 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 ... • 2,636 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.... • 55.7k 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_{\...
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,...