0
$\begingroup$
I am trying to solve the following nonlinear equation for $f \in \mathbb{R}^3$ using the Newton-Raphson method, $$G(f) = {\sin{(||f||)} \over ||f|| }Jf + {1-\cos(||f||) \over ||f||^2} f \times Jf = g$$ where $g$ is a given vector in $\mathbb{R}^3$, $J \in \mathbb{R}^{3 \times 3}$ is a constant positive definite diagonal matrix and $||.||:\mathbb{R}^3 \rightarrow \mathbb{R}-\{\mathbb{R}^-\}$, represents Euclidean norm. The iterative equation obtained after applying this is the following, $$f_{i+1} = f_{i} + \nabla G (f_i)^{-1}(g-G(f_i))$$

Newton-Raphson method for an equation $f(x)=0$, where, $f:\mathbb{R}\rightarrow \mathbb{R}$, converges if the initial guess is very close to the root of the equation. We can roughly find a neighbourhood of the roots of such equations by plotting graphs or linearizing it but for equations like written above, I am not sure how would this work. I tried solving the above equation for different initial conditions, for some, it converges in at least $9$ iterations while for some other initial conditions it diverges badly. The measure of convergence is checked by computing the norm $||g-G(f_i)||$ in every iteration step.

Please find some iteration results below (performed in MATLAB):

Value of the matrix $J = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 5 & 0 \\ 0 & 0 & 3 \end{bmatrix}$ and $g = \begin{bmatrix} 6.13 \\ 1.73 \\ 3.20 \end{bmatrix}$

  1. For the initial condition $f_0 = \begin{bmatrix} 1 \\ 1 \\ 1\end{bmatrix}$, the value of the norm $||g-G(f_i)||$ converges to $10^{-14}$ in $10$ iterations. The solution of the equation comes out to be $\begin{bmatrix} 1.84 \\ 1.16 \\ 1.42 \end{bmatrix}$
  2. For the initial condition $f_0 = \begin{bmatrix} 2 \\ 2 \\ 1\end{bmatrix}$, the equation diverges as the value of the norm $||g-G(f_i)||$ grows to $10^{3}$. The value of the determinant of the matrix $\nabla G$ becomes very small with subsequent iterations (i.e. the matrix $\nabla G$ loses its invertibility in the iterative equation)

It seems an issue of finding a proper initial value to solve it numerically using the Newton-Raphson method. Any other method for solving such equations would also really be appreciated. Looking forward to your suggestions!

Thank you, Dhananjay.

$\endgroup$
0
$\begingroup$

If your functions is locally convex around a local minimizer, then Newton's method (and most of its variants) will converge quadratically in that "local" regime -- meaning, if you are close enough to a solution, then you will observe really fast convergence to a solution. If your function is nonconvex, however, there are no guarantees of convergence whatsoever unless you start your iteration close enough to a solution. As you have observed, it can be quite challenging to determine a reasonable first-iterate for this method. Some folks devote entire research papers to finding a reasonable first-iterate for a particular problem.

If no reasonable initial iterate can be inferred based on the problem structure, here are two standard choices for "initial iterates" (not just for Newton, for most fixed-point iterations):

  1. Initialize at zero.
  2. Initialize with a vector whose components are drawn from a standard normal distribution (iid at random). Some folks normalize this as well.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.