Skip to main content

Questions tagged [newton-method]

Method for finding successively better approximations to the roots (or zeroes) of a real-valued function

Filter by
Sorted by
Tagged with
16 votes
2 answers
3k views

Is it possible to solve nonlinear PDEs without using Newton-Raphson iteration?

I am trying to understand some results and would appreciate some general comments on tackling nonlinear problems. Fisher's equation (a nonlinear reaction-diffusion PDE), $$ u_t = du_{xx} + \beta u ...
boyfarrell's user avatar
  • 5,409
13 votes
2 answers
7k views

Strategies for Newton's Method when the Jacobian at the solution is singular

I'm trying to solve the following system of equations for the variables $P,x_1$ and $x_2$ (all else are constants): $$\frac{A(1-P)}{2}-k_1x_1=0 \\ \frac{AP}{2}-k_2x_2=0 \\ \frac{(1-P)(r_1+x_1)^4}{L_1}...
Paul's user avatar
  • 12k
13 votes
1 answer
2k views

Can an approximated Jacobian with finite differences cause instability in the Newton method?

I have implemented a backward-Euler solver in python 3 (using numpy). For my own convenience and as an exercise, I also wrote a small function that computes a finite difference approximation of the ...
Stephen Bosch's user avatar
10 votes
3 answers
986 views

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

I'm working on a project where I have two adv-diff coupled domains through their respective source terms (one domain adds mass, the other subtracts mass). For brevity, I'm modeling them in steady ...
cbcoutinho's user avatar
9 votes
0 answers
233 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{...
R zu's user avatar
  • 163
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 $\...
Rubem Pacelli's user avatar
8 votes
1 answer
5k views

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

Can anybody help me? I heard that Gauss-Newton method compute an aproximation of the Hessian instead of the true Hessian, but, quasi-Newton method too, don't it? what is the differences between them? ...
mario faixat's user avatar
8 votes
1 answer
1k views

Newton iteration applied to nonlinear PDE

I'm having difficulty understanding how to apply Newton iteration to nonlinear PDEs and then use a fully implicit scheme to time step. For example, I want to solve Burgers equation $$u_{t} + u u_{x} -...
Matthew Cassell's user avatar
7 votes
2 answers
738 views

How to calculate/derive analytic FEM Newton Jacobian

I trying to wrap my head of derivation of the analytic FEM Jacobian for the Newton method. Say we have a nonlinear Poisson problem of the (weak) form $$ \int a(u)\nabla\ u\cdot \nabla v = \int f v $$ ...
B Ring's user avatar
  • 73
7 votes
1 answer
701 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-...
computational_scientist's user avatar
7 votes
3 answers
451 views

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

I am trying to solve a multiphysic problem using finite elements and a Newton Raphson solution scheme. I have two non-linear subsystems that are coupled bi-directionally. The first subsystem includes ...
Johann's user avatar
  • 71
7 votes
1 answer
449 views

Eigenvalues of $ab^T$

In deriving a Newton scheme, I end up with a Jacobian matrix of the form $J=I+ab^T$ where $a,b$ are vectors. For practical reasons, I want to approximate it by a symmetric positive definite matrix. ...
Wolfgang Bangerth's user avatar
7 votes
1 answer
209 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 ...
Daniel Shapero's user avatar
7 votes
1 answer
243 views

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

Introduction to Problem I'm using a Truncated Signed Distance Function to perform 3D reconstruction from depth images. Essentially I have a large voxel grid where each voxel contains the signed ...
Dave Durbin's user avatar
7 votes
1 answer
119 views

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

I am trying to solve a bunch of equations for the zeros of the derivative of an analytic function, and I would like to know if there exist methods that exploit this structure to provide better ...
Emilio Pisanty's user avatar
6 votes
2 answers
143 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\...
Justin Solomon's user avatar
6 votes
1 answer
9k views

Newton-Raphson method for nonlinear partial differential equations

For the numerical solution of Reynolds equations (a non-linear partial differential equation), the Newton-Raphson method is generally proposed. After getting algebraic equations from a finite ...
user avatar
6 votes
1 answer
453 views

Caveats of Hessian free method

Hessian free iterative optimization techniques like Newton-CG, do not explicitly compute the Hessian but instead approximate the product of the Hessian with a vector through finite difference. The ...
Hari's user avatar
  • 666
6 votes
1 answer
223 views

Roots of a function for eigensystem

I want to find the roots for $\kappa$ for the equation $$\sqrt{\alpha - 1} \cos{\left (\frac{\sqrt{2} \sqrt{\alpha - 1}}{2 \sqrt{\epsilon}} \right )} \cosh{\left (\frac{\sqrt{2} \sqrt{\alpha + 1}}{2 \...
nicoguaro's user avatar
  • 8,524
6 votes
1 answer
946 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 ...
user14717's user avatar
  • 2,155
6 votes
1 answer
2k views

Newton's method with box-constraints

I have to use an iterative method (Newton-Raphson, modified Newton and Broyden) to solve a system of nonlinear equations $f(x)=0$. Every unknown $x_i$ is bounded between $l_i$ and $u_i$, i.e., $l_i<...
Manu's user avatar
  • 459
6 votes
0 answers
970 views

Best way to add a positivity constraint to Newton's Method

So given an objective function $f({\bf x})$, I would like to include a positivity constraint when I perform the fixed point iteration: $${\bf x}^{(t+1)}={\bf x}^{(t)} - \text{H}_f^{-1}\nabla f({\bf x}^...
Set's user avatar
  • 503
5 votes
4 answers
1k views

Best method to find the zero of a decreasing function numerically

I need to find the zero of a function $f(\lambda)$ which is of the form $\sum \frac{c_i^2}{(1+\lambda d_i)^2} -1 $. I tried using Newton's method, and it works sometimes, but it is highly dependent on ...
Beni Bogosel's user avatar
  • 1,077
5 votes
2 answers
2k views

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

In the framework of Finite Element Method, when the Newton method is used, we solve $J(x^k) \delta x = -f(x^k)$, and the increment $\delta x$ would not change some entries from $x^k$ related to ...
Frederico Teixeira's user avatar
5 votes
2 answers
11k views

How to implement Newton's method for solving the algebraic equations in the backward Euler method

Can you explain me how does the backward Euler method works? I have seen the formula and try to understand the method, but what I can't understand is why and how to use the Newton-Rapson method. Do ...
BRabbit27's user avatar
  • 1,029
5 votes
1 answer
157 views

Can redundant variables be beneficial for root-finding convergence

Suppose I have $n$ generally nonlinear equations for $n$ variables, like e.g. for $n=2$ the system $F(x,y)=0$ $$ \begin{aligned} x^2+2y-4&=0\\ \sqrt{8}x+y^2-5&=0 \end{aligned} $$ By ...
oliver's user avatar
  • 103
5 votes
1 answer
264 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 (...
Abel Thayil's user avatar
5 votes
1 answer
803 views

Efficient and stable computation of inverse CDF

What is the most efficient and numerically stable algorithm for computing the inverse CDF $F^{-1}(y)$ of a probability function, assuming that both the PDF $f(x)$ and the CDF $F(x)$ are known ...
lacerbi's user avatar
  • 185
5 votes
1 answer
3k views

Newton's method goes to zero determinant Jacobian

I am using the Newton's method to solve $3\times3$ systems. For some particular cases, it turns out that at a given iteration, the Jacobian matrix cannot be inverted and that its determinant is very ...
Sylvain B.'s user avatar
5 votes
1 answer
152 views

Matlab help related with the scaled Newton's iteration method

I need a little help with Matlab code for the method mentioned in this paper for computing the inverse of the matrix. In this paper, the author presented scaled Newton iteration given by $X_{k+1} = \...
mathscrazy's user avatar
5 votes
2 answers
219 views

Solving a nonlinear algebraic system that includes a linear term

I am trying to solve a particular system of non linear equations written as $F(x) = 0$ in an efficient way. More specifically, $$F(x) = (I - \gamma A)x - g(x) + C$$ where $\gamma$ is a scalarconstant,...
Tibo's user avatar
  • 257
5 votes
1 answer
1k views

Solving a set of linear equations with block structure and weak coupling

I have a standard set of linear equations $Ax=b$ where the Hessian matrix $A$ has the special block structure as shown: $A= \begin{pmatrix} T & U\\ U^T & V \end{pmatrix}$, $x= \begin{...
Ophion's user avatar
  • 153
5 votes
1 answer
542 views

scaling and preconditioning for trust region Newton methods

Geometrically, scaling and preconditioning seem to address similar challenges in optimization. However, these two concepts are implemented very differently. Take trust region Newton method, as an ...
Hari's user avatar
  • 666
4 votes
3 answers
2k 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://...
Camille C's user avatar
4 votes
2 answers
2k views

What is the difference between "Newton-type" and "Newton-like" iteration?

Is there any clear classification between different iterative methods? What is the difference between Newton-type and ...
LCFactorization's user avatar
4 votes
3 answers
2k views

Beale's function and newton iteration

I am trying to find the minimum of the so called Beale’s function given by $f(x_1,x_2) = (1.5-x_1+x_1x_2)^2 + (2.25-x_1+x_1x_2^2)^2 + (2.625-x_1+x_1x_2^3)^2$ Using Newton iteration $x^{(k+1)} = x^{...
solid's user avatar
  • 143
4 votes
1 answer
921 views

Should the Jacobian of a system of PDEs be calculated from the main equations of the discretised equation?

I am solving a coupled system of non-linear PDEs in 1D. Something like, $$ u_t = F_1(u,v,w) \\ v_t = F_2(u,v,w) \\ w_t = F_3(u,v,w) $$ where each variable is a function of $x$ (the spatial dimension)...
boyfarrell's user avatar
  • 5,409
4 votes
2 answers
290 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 ...
underdog's user avatar
4 votes
3 answers
1k views

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

Suppose $ q $ and $ A $ are given and that $ q, p \in R^{N} $ and $ A \in R^{NxN} $, then how can I find the vector $ p $ such that $$ (q - p)^{T}A(q - p) $$ is minimized constraint to $ \sum_{i=1}^{...
Mike Chen's user avatar
4 votes
2 answers
711 views

Poisson-Nernst-Planck equations with ill-conditioned sparse matrix

I am trying to solve Poisson-Nernst-Planck system of equations for ions diffusion problem using finite volume method. Nernst-Planck equation for mass transport and Poisson equation for electrostatic ...
Ben's user avatar
  • 41
4 votes
1 answer
418 views

Methods for Constrained Optimization Problems with Box Constraints

Consider this problem: \begin{equation} \begin{array}{ll} \text{minimize } & f(x) \\ \text{subject to } & a \leq x \leq b \end{array} \end{equation} where $a,b,x \in \mathbb{...
Linh Huynh's user avatar
3 votes
4 answers
8k views

Solving Kepler equation for true or eccentric anomaly

Is there any reason to always solve the Kepler equation for the eccentric anomaly, $E$, instead of the more meaningful (at least to me) true anomaly, $\theta$? Solving for the eccentric anomaly ...
fibonatic's user avatar
  • 470
3 votes
2 answers
10k 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, ...
Schneider's user avatar
3 votes
2 answers
1k views

Low-rank updates in BFGS

I have read this and other threads on this site on BFGS, but I still don't have a clear understanding of what it's meant by low-rank updates. For example, I read the following in this book: The ...
Amelio Vazquez-Reina's user avatar
3 votes
1 answer
734 views

BFGS methods for constrained elasticity problems

My dear community, I am wondering why BFGS methods are not so widely used for simulating mechanical problems which heavily still relies on inverting the hessian matrix. I am essentially interested ...
tom's user avatar
  • 41
3 votes
1 answer
718 views

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 ...
D.F.J.'s user avatar
  • 133
3 votes
2 answers
1k views

Slow convergence of Newton's method for finite elements

The application is a simple non-linear advection diffusion problem (steady state) using DGFEM. My error at each iteration is given by $$ e_{n+1} = ||\mathbf{J}^{-1}(\mathbf{u}_{n})\mathbf{F}(\mathbf{u}...
Justin Dong's user avatar
3 votes
1 answer
3k 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 $...
VoB's user avatar
  • 550
3 votes
1 answer
1k 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 ...
bruin's user avatar
  • 133
3 votes
2 answers
2k 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 ...
user2357's user avatar
  • 169