Questions tagged [newton-method]
Method for finding successively better approximations to the roots (or zeroes) of a real-valued function
128
questions
15
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 ...
- 5,369
13
votes
2
answers
6k
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}...
- 11.9k
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 ...
- 231
10
votes
3
answers
931
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 ...
- 674
9
votes
0
answers
229
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
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
8
votes
1
answer
4k
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?
...
- 81
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} -...
- 183
7
votes
2
answers
638
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 $$
...
- 73
7
votes
1
answer
536
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-...
7
votes
3
answers
442
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 ...
- 71
7
votes
1
answer
406
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. ...
7
votes
1
answer
236
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 ...
- 73
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 ...
- 816
6
votes
2
answers
141
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
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 ...
P. S.
6
votes
1
answer
434
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 ...
- 656
6
votes
1
answer
205
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 \...
- 8,207
6
votes
1
answer
809
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,085
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<...
- 439
6
votes
0
answers
118
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,168
6
votes
0
answers
816
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}^...
- 443
5
votes
4
answers
943
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 ...
- 965
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 ...
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 ...
- 1,019
5
votes
1
answer
153
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 ...
- 103
5
votes
1
answer
152
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
5
votes
1
answer
720
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 ...
- 183
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 ...
- 153
5
votes
1
answer
149
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} = \...
- 151
5
votes
2
answers
216
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,...
- 157
5
votes
1
answer
912
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{...
- 153
5
votes
1
answer
501
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 ...
- 656
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://...
- 43
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 ...
- 719
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^{...
- 143
4
votes
1
answer
853
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)...
- 5,369
4
votes
2
answers
215
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
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}^{...
- 43
4
votes
2
answers
640
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 ...
- 41
4
votes
1
answer
360
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{...
- 81
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
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 ...
3
votes
1
answer
713
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 ...
- 41
3
votes
1
answer
674
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 ...
- 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}...
- 937
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
3
votes
1
answer
790
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
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 ...
- 159
3
votes
1
answer
378
views
Active Elements in Projected Newton's Method?
To those who are familiar with the projected Newton's method or projected gradient method...
We consider a constrained optimization problem with simple bounds. Particularly, minimize f(x) subject to ...
- 81