Questions tagged [newton-method]
Method for finding successively better approximations to the roots (or zeroes) of a real-valued function
1
vote
1answer
53 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}\\...
0
votes
0answers
20 views
Non linear Parametric BVP with inequalities
Consider a non linear ode in dimension $10$: $\dot x = f(t,x,\lambda)$ where $\lambda$ is a vector of $p$ parameters.
Consider a boundary value problem of the form :
$\dot x(t) = f(t,x(t),\lambda)$ ...
0
votes
1answer
55 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-...
7
votes
1answer
191 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
0answers
50 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{...
0
votes
1answer
67 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)$...
7
votes
1answer
146 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 ...
1
vote
1answer
85 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
1answer
173 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 $...
8
votes
0answers
178 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{...
1
vote
1answer
88 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 ...
1
vote
1answer
72 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 &...
1
vote
1answer
41 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 ...
3
votes
0answers
105 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 ...
2
votes
0answers
96 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 ...
2
votes
0answers
118 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, ...
1
vote
2answers
2k 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, ...
5
votes
1answer
116 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 ...
0
votes
2answers
125 views
Nédélec Elements and Newton-Methods
If you want to develop numerical algorithms for variational inequalities, you often choose a Semismooth Newton Method. In many cases, this approach involves derivatives of $\max$ or $\min$ functions ...
5
votes
2answers
236 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 $$
...
1
vote
0answers
202 views
Vectorised root finding in Python
I have an array of size (254, 80) which I am trying to use Scipy's fsolve on. I have found that the speed of using fsolve on a vector is quicker than it is in a for loop but only for vectors upto ...
1
vote
0answers
178 views
Newton - Raphson method : maxima of function in 2 variables
I am computing the maximum of a function (with two-variables) using Newton-Raphson method. The function is : $e^{-(x \ - x_0)^2 - (y \ - y_0)^2}$, whose maxima exists at $(x_0,y_0)$.
The Jacobian ...
4
votes
3answers
165 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}^{...
1
vote
0answers
72 views
Successive iteration method for solving eigenvalue ploblem
I have a question concerning the branch of successive iteration methods (Newton, Runge-Kutta). I definitely know (or can read in Wikipedia) the implementation of these methods. But I was wondering ...
1
vote
0answers
98 views
Jacobian of the electron and hole drift diffusion equations with respect to potential in semiconductors
These are the discretized drift diffusion equations as taken from the book "Analysis and Simulation of Semiconductor Devices". The electron continuity equation is:
$$((\Delta_{j-1}^y+\Delta_j^y)/2\...
3
votes
1answer
113 views
Newton's method stagnates at small error
I have a system of the form
$$A(u)f(u)=b$$
where $A$ is basically a matrix originating from the Finite Element Method.
I try to solve it using the Newton method:
$$R = A(u_{i}) f(u_{i}) - b $$
$$...
1
vote
0answers
81 views
Using Newton-Raphson method to solve the hydrostatic equation
I'm trying to use newton-raphson method for nonlinear systems of equations as described in 'Numerical recipies' book in chapter 9.6 to solve the hydrostatic equation for a polytropic star.
For each ...
6
votes
1answer
736 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<...
3
votes
0answers
94 views
Optimization based integration for MPM
I'm considering implementing (just for simplicity) the unconstrained implicit optimization based integration for Material Point Method as described in Chenfanfu Jiang's thesis on MPM (the minimization ...
2
votes
0answers
149 views
Does applying the Newton-Raphson iteration for matrix reciprocal refine a matrix inverse from LU/GE?
This is a follow-up to this answer.
Suppose you have a possibly very ill-conditioned matrix $A$, and you compute its inverse with LU/GE to get $X_{\text{lu}}\approx A^{-1}$.
The Newton-Raphson ...
7
votes
1answer
176 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 ...
3
votes
2answers
414 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 ...
2
votes
1answer
58 views
Doubt regarding principled approach towards approximating the Hessian
In my optimization problem, the hessian has a structure such that it can be written as the sum of two matrices. Populating the first of the matrices is efficient. Populating the second one is ...
8
votes
1answer
283 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. ...
6
votes
1answer
127 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 \...
1
vote
0answers
90 views
Quasi Newton taking very small steps
I have implemented a Quasi-Newton method based on the Hessian approximation. I am noticing that the algorithm takes too many iterations to converge, even though it does converge. What I am not able to ...
1
vote
1answer
94 views
The linear system in Quasi Newton method
I have implemented a Quasi Newton method for my problem, where I use the Hessian matrix approximation based approach. Hence, there is a linear system solve in every iteration. I solve the linear ...
1
vote
0answers
109 views
Solving a large system of nonlinear equations, where timeseries are the unknown
I am trying to solve a problem, which I find quite hard, like, headache-hard. I have to solve the following set of $M$ nonlinear equations:
$$F(X)=\begin{bmatrix}f_1 (X)\\f_2 (X)\\...\\f_M (X)\\ \end{...
8
votes
1answer
101 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 ...
10
votes
3answers
607 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 ...
3
votes
0answers
237 views
Quasi Newton method for block diagonal Hessian
I am having an unconstrained optimization problem, where the Hessian is positive semidefinite and block diagonal. The function is strictly convex, hence, the curvature condition ($ s^{T}_{k}y_{k} > ...
2
votes
0answers
260 views
Applying Newton-Raphson method to system of two differential equations, one time independent, one time dependent
The goal is to couple system of two nonlinear differential equations by applying appropriate space and time discretization and Newton-Raphson scheme.
The equations system is
$$\left[
\begin{array}{c}
...
2
votes
2answers
194 views
Why do Newton-Krylov iterations stagnate in this problem? [closed]
Consider this integro-differential heat equation taken from SciPy documentation page:
$
\nabla^2 P = \alpha \left(\iint_\Omega \cosh(P)dx dy \right)^2
$
which was found in this question.
In the ...
4
votes
1answer
190 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 ...
5
votes
1answer
258 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{...
3
votes
1answer
440 views
Implementation of Backward-Euler scheme, Newton-Raphson iteration scheme to time dependent nonlinear differential equation
I just knew how to do Newton-Raphson iteration in time-independent 1D nonlinear differential equation. Then I applied to time-dependent 1D nonlinear differential equation, and I got confused.
Below ...
4
votes
0answers
360 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}^...
1
vote
2answers
649 views
How to implement Newton method in solving 1D PDE system? (ie. Poisson eq, continuity eq, drift-diffusion eq.)
I want to solve PDE system, which consists of Poisson equation, continuity equations for electron and hole with drift-diffusion equation numerically, by using method called Newton's method.
This ...
4
votes
1answer
1k 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 ...
5
votes
1answer
2k 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?
...
