Questions tagged [newton-method]
Method for finding successively better approximations to the roots (or zeroes) of a real-valued function
127
questions
3
votes
0
answers
89
views
A way to solve nonsmooth stiff ODEs
Let us considered the following ODEs
\begin{align*}
\dfrac{dX}{dt} = F(X), \tag{1.1}
\end{align*}
where the unknown $X\in \mathcal{D} \subset \mathbb{R}^l$ and it can be stiff. These ODEs can be ...
- 131
0
votes
0
answers
63
views
accelerating solutions of ODEs with close by parameters
Suppose $\mathbf{u}^1\in\mathbb{R}^n$ is an unknown and $\mu^1\in\mathbb{R}$ is a known parameter. Suppose we have solved the non-linear system of equation for $\mathbf{u}^1$ using Newton's iterations....
- 654
8
votes
2
answers
2k
views
Are Quasi-Newton methods computationally impractical?
I was reading a book by Simon Haykin on neural networks when I came across the following strong statement (on the pdf's page 188):
"However, we still have a computational complexity that is
$\...
- 195
0
votes
0
answers
145
views
Discontinuous Galerkin failing to converge Euler equations under p-refinement
I am solving the steady state compressible Euler equations in conservation form in 2D in a rectangular domain with a discontinuous Galerkin (DG) code I have developed. As a test, the boundary ...
- 63
1
vote
0
answers
48
views
Hessian-free preconditioner for non linear least squares
I am solving a nonlinear least squares problem using Gauss Newton method. Due to the large dimension of the problem, I use the Hessian-free approach. As a linear solver I use either MINRES or CG. To ...
4
votes
2
answers
194
views
Backward Euler + Quasi Newton(Broyden) method fails to solve Van der Pol's equation(Stiff ODE)
The first guess is using the forward Euler approach. The first jacobian is using finite differences. Then NR method is used to solve for the next iteration and Broyden's method is used to update the ...
- 43
3
votes
1
answer
118
views
Applying displacement control loading using lagrange multipliers in the material non-linear finite element method
Hi I am trying to implement a simple plasticity based finite element code. I am not clear how to set up displacement control applied through Lagrange multipliers. In case of a linear problem, I did ...
1
vote
0
answers
57
views
Viable algorithms for efficiently solving a block matrix system with non-uniform sparsity structure
I am trying to use Newton's method to get a stationary solution for a system of equations of the following form:
$$
\begin{Bmatrix}
\frac{\partial x}{\partial t} \\
0
\end{Bmatrix} = \begin{Bmatrix}
f(...
- 81
6
votes
0
answers
108
views
continuous analogues of Newton's method
Suppose we want to minimize some convex functional $J(u)$ where $u$ lives in some Banach space $V$.
The classical Newton method
$$\mathrm d^2J(u_n)(u_{n + 1} - u_n) = -\mathrm dJ(u_n)$$
can be viewed ...
- 9,013
1
vote
0
answers
61
views
tiny typo in Numerical Recipes Eq. 9.4.6 [closed]
The Numerical Recipes Forum http://numerical.recipes/forum/ is closed, so I will record a tiny typo here for the benefit of others who may wonder about this. (This typo is not in the software, but ...
- 11
0
votes
0
answers
60
views
Blown-up iterates in Gauss-Newton method
I am working on a non-linear least squares problem with standard form, in which I need to calibrate a parameter vector $\Theta$ to a set of inputs $\mathbf{x}$ and outputs $\mathbf{y}$:
$$\begin{align}...
- 109
0
votes
0
answers
77
views
Newton-Raphson for estimating Weibull distribution does not converge
I've been trying to estimate the two-parameter (a,b) Weibull distribution (loc. param. = 0).
$$f(t;a,b)=\frac{b}{a}\left(\frac{t}{a}\right)^{b-1}\exp(- \left(\frac{t}{a}\right)^b) $$
To find the ...
- 11
4
votes
3
answers
1k
views
Which absolute and/or relative stopping criteria do use for Newton's method?
I saw many stopping criteria for Newton's method all around Web and books.
Some are defined from the residuals:
of either current iteration only:
$$
\|f(\mathbf{x}^{(k)})\| \leq \epsilon
$$
(https://...
- 43
1
vote
1
answer
516
views
Drawing saddle node bifurcation diagram for a non-linear ODE in Python
I'm trying to draw the bifurcation diagram of the following ODE,
This ODE leads to a saddle-node bifurcation (see wiki)
However what I get is not exactly right. There's a lot of "noise" as ...
- 163
2
votes
2
answers
210
views
Numerical Methods of solving a non-linear ODE?
I want to solve the nonlinear equation $\frac{d^2x}{dt^2} + k\sin x = 0$, numerically. I found that solving this elliptic integral would be cumbersome, so is there a numerical method i could use to ...
- 21
1
vote
0
answers
71
views
Solution predictors for accelerating convergence in nonlinear FEM
I am looking for the details of commonly-used predictors for accelerating the convergence of iterations using Newton-Raphson scheme for nonlinear problems in FEM. I am looking specifically for static ...
- 810
0
votes
1
answer
145
views
Coding up Newton's method for a mapping from R^2 to R -- the Jacobian wouldn't be invertible
I'm trying to code up in Matlab a multivariable Newton's method, for a mapping from R^2 to R, but the Jacobian would be a 2x1 matrix, not square, so it wouldn't be invertible.
Does this mean that ...
2
votes
1
answer
192
views
Solving system of nonlinear vector functions
I am trying to figure out how to implement a solver for a system of nonlinear equations of the form
\begin{align*}
u_1 &= y_n + h\left(a_{1,1}f(t_n + c_1 h, u_1) + a_{1,2}f(t_n + c_2 h, u_2)\...
- 23
1
vote
0
answers
53
views
Quadratic optimization with nonlinear vector term
I wish to minimize the quantity $$W=1/2x^TAx-x^Tg(y)$$ with respect to $x$ and $y$, which are vectors of unknowns. $A$ is a sparse square symmetric positive definite matrix and $g(y)$ is a vector with ...
- 661
2
votes
0
answers
54
views
Convergence of Truncated Newton for non-convex Hessian
I was wondering if anyone could enlighten me about the convergence properties of the truncated newton method in case of a non-positive definite hessian $\nabla^2 f = H$. From the Book 'Numerical ...
0
votes
1
answer
36
views
How to check curvature of a vector valued function
In terms of numerical optimization, the newton-rapson method requires a pos. definite Hessian $\nabla^2f$ respectively pos. curvature for computing the next step $p_k$ by solving $$\nabla^2 f p_k = -\...
2
votes
1
answer
835
views
Constrained Newton-Raphson root finding
Original Question
I have a set of non-linear equations and I need to find the root where a subset of my solution vector is constrained to be greater than or equal to 0. I have implemented the Newton-...
- 21
1
vote
0
answers
54
views
Inverse Newton Method for optimization: is this the correct algorithm?
I am trying to implement the algorithm in this article. I have already asked a question before about it here, and I am trying to figure out what I am doing wrong. This time, it's this section of the ...
- 149
5
votes
1
answer
146
views
How do I globally change the precision of a piece of code in Python to debug it?
I am solving a system of non-linear equations using the Newton-Raphson method in Python. This involves using the solve(Ax,b) function (...
- 53
3
votes
1
answer
745
views
Parallelizing Newton-method in solving non-linear systems
Circuit simulation software based on SPICE (such as ngspice) uses Newton-Raphson method to solve non-linear system of equations ...
- 133
2
votes
1
answer
232
views
How to avoid gsl root finder evaluate function outside its domain
When I use the newton's method or hybrid solver in the GSL package to deal with 1-D or multidimensional root solving problems, the code frequently crashes when the solver requests function value ...
- 121
1
vote
2
answers
807
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 ...
- 111
2
votes
1
answer
426
views
Number of GMRES iterations increase when stepping forward in time, using the Newton method
I am solving a system of nonlinear time-dependent equations using the Newton method in a finite-element-setting, i.e. first I create the jacobian matrix for the current time, and afterwards I try to ...
- 543
2
votes
1
answer
395
views
How to use Newton-Raphson method to handle nonlinear terms in coupled system of PDEs?
I'm trying to solve the Nonlinear Schrodinger's Equation (NLSE) in 2D using Finite Elements, but I don't know how to handle the nonlinear term. I suppose I have to apply the Newton-Raphson algortihm ...
- 21
1
vote
0
answers
326
views
How to use Wolfe-Powell step-size control in quasi-Newton method?
I'm trying to find the minimum of a function using the quasi-Newton method with the Broyden-Fletcher-Goldfarb-Shanno (BFGS) algorithm.
But I want to change the following implementation, so that:
1) ...
- 131
2
votes
1
answer
378
views
Solving nonlinear PDE with finite difference based on Newton-Krylov
I am now working on solving MHD equations with finite difference method, which include nonlinear equations:
$$
\frac{\partial\rho}{\partial t}+\nabla\cdot\left[\left(\rho_0+\rho\right){v}\right]-\...
- 21
2
votes
1
answer
766
views
GMRES vs Newton-GMRES for Solving nonlinear PDE's
Often when numerically solving nonlinear PDE's using method of lines approach with an implicit integrator a system of nonlinear equations have to be solved.
To be more specific, let's say we have ...
- 95
2
votes
1
answer
221
views
Residual value goes to NaN while solving a system of nonlinear equations
I am solving a system of coupled nonlinear equations using Newton's method, similar to
$$\begin{split}
c_A(A, B)\partial_tA&=\nabla\left(k_A(A, B)\nabla A\right) + f_A(A, B, t)\\
c_B(A, B)\...
- 543
6
votes
2
answers
140
views
Positive root of $x^q + bx - b$
Is there either a closed-form expression or fast/elegant algorithm for computing the positive root of the polynomial
$$f(x)=x^q + \beta x - \beta,$$
where $\beta>0$ and $q\geq2$? How about the $q\...
- 1,341
1
vote
1
answer
101
views
Product of rank one updates as a low rank update for quasi newton/BFGS
I'm trying to improve the speed of the following iteration to calculate $s_k$:
$$B_k^{-1} = \Bigg( I + \frac{s_{k}s_{k-1}^T}{||s_{k-1}||^2}\Bigg)...\Bigg(I+ \frac{s_1s_0^T}{||s_0||^2}\Bigg) B_0^{-1}\\...
- 11
0
votes
1
answer
104
views
Debugging Newton-method used in a CG-approach
I am currently proof-checking my program, which is intended to use Newton's method for solving nonlinear equations, using a continuous galerkin approach. Thus, as first step I checked it using a time-...
- 543
7
votes
1
answer
509
views
Lack of quadratic convergence in Newton's method
It is well-known that Newton's method can converge quadratically, if initial guess is close enough and if the arising linear systems are solved accurately.
I am applying Newton's method to highly ill-...
2
votes
0
answers
104
views
Nonlinear system with diagonal nonlinearity
Consider a nonlinear system of the form $\boldsymbol{f}(\boldsymbol{x}) = \boldsymbol{0}_{\mathbb{R}^n}$ for $\boldsymbol{x} \in \mathbb{R}^n$, where the function $\boldsymbol{f}$ is given by
\begin{...
- 176
1
vote
2
answers
550
views
Implementation of the Jacobian-free Newton method
In my calculation (of a simple heat equation, for testing) using the Newton method, I tried to replace the full Jacobian matrix with an approximation vector, i.e. replacing $J$ in
$$J(u)\delta u=-F(u)...
- 543
6
votes
1
answer
778
views
Defining a condition number and termination criteria for Newton's method
The condition number of function evaluation
$$
\mathrm{cond}(f,x) := \left| \frac{x f'(x)}{f(x)} \right|
$$
is infinite at a root of $f$. Hence it is useless for rescaling a tolerance which defines an ...
- 2,055
1
vote
1
answer
281
views
Shooting method implementation
I have a trouble of defining a Jacobian matrix for my problem. Basically, I have 4 differential equations to be solved.
$$
\begin{aligned}
\dot x_1(t)&=x_2(t)\\
\dot x_2(t)&=p_2(t)−\sqrt 2 ...
3
votes
1
answer
2k
views
Computational complexity of Newton's method
the classical Newton's method for non-linear systems of equations is $x_{k+1} =x_k-J_F(x_n)^{-1} F(x_n)$. In pratice, rather than compute the inverse of the Jacobian matrix, one solves the systems $...
- 540
9
votes
0
answers
223
views
Imbalance of variables in Mixing Newton's method and Linear solver for a Non-linear system
Problem
Solving a non-linear system of equations.
The number of variables is the same as the number of equations.
When I fix a set of variables (say $\vec{y}$) and keep another set free (say $\vec{...
- 163
1
vote
1
answer
126
views
Newton's method problem
I struggle with this problem:
I understand how to apply Newton's method to a already given function but I can't seem to find that function in this case from the given input n, t, d and s. I'm ...
- 13
1
vote
1
answer
369
views
Root finding using Newton's method with quadratic interpolation - Is there a mistake in this textbook?
I've been trying to learn about root finding using Newton's method, which uses a quadratic interpolating polynomial. I found this text, Numerical methods for roots of polynomials, PART 2: McNamee &...
- 21
1
vote
1
answer
270
views
Muller's method is the same as Newton's method with a quadratic interpolating polynomial?
I'm new to numerical analysis, and have been learning root finding algorithms. I am a bit confused about the difference between Muller's method, and Newton's method using an n-degree interpolating ...
- 21
3
votes
0
answers
369
views
Difference between Dishonest Newton method and Very Dishonest Newton method
What is the difference between the Dishonest Newton method and the Very Dishonest Newton method? Is there a difference or do they mean the same thing?
I have tried searching for this on the internet ...
- 31
3
votes
2
answers
1k
views
Which SciPy nonlinear solver when Jacobian is analytically known and sparse?
I have a nonlinear function fun with n inputs and n outputs. I also have a function jac which calculates the Jacobian, which is ...
- 159
2
votes
0
answers
544
views
How to prevent BFGS from getting stuck on astronomically large gradient?
I have implemented BFGS myself from scratch in order to solve minimization problems. Part of BFGS, as I understand it, is that the approximation to the Hessian is supposed to be positive definite, ...
- 141
3
votes
2
answers
9k
views
How does one calculate reaction force in FEA?
I wrote a UEL (User Element in Abaqus) for one element and compared to a reference UEL which used standard FEM, where the results agreed satisfactorily, except the reaction force. The stress, strain, ...
- 33