What does it mean when Newton's method encounters a non-invertible matrix?

Question

I'm trying to solve some systems of polynomials. I'm using Newton's method as described here. But my code breaks if my initial guess or any subsequent iteration lands on a point which is a solution for some but not all of the functions.

For example, say I want to find $(x,y,z)$ such that: $$ f_1(x,y,z)=x^2-z \\ f_2(x,y,z)=y^2-z \\ f_3(x,y,z)=z $$ are all zero. (The solution is $(0,0,0)$.) I believe the Jacobian and inverse are: $$ \boldsymbol{J}= \begin{pmatrix} 2x & 0 & -1 \\ 0 & 2y & -1 \\ 0 & 0 & 1 \\ \end{pmatrix} , \boldsymbol{J}^{-1}= \begin{pmatrix} \frac{1}{2x} & 0 & \frac{1}{2x} \\ 0 & \frac{1}{2y} & \frac{1}{2x} \\ 0 & 0 & 1 \\ \end{pmatrix} $$ If we happen to guess any starting point on $x=0$ or $y=0$, then the corresponding column of $\boldsymbol{J}$ becomes zero, and non-invertible. Or, $\boldsymbol{J}^{-1}$ would contain $\frac{1}{0}$.

Am I Doing It Wrong™? How should the algorithm proceed in this case? Or should I be using a different algorithm?

I found this question which seems to say that $\boldsymbol{J}$ should always be invertible, which I don't understand.

Answer 1

The Jacobian is invertible when there are several different directions you can travel which result in similar changes overall. Consider the one-dimensional problem of $f(x)=1-x^2$ starting from $x=0$. In such an instance, either direction is valid, so Newton's method cannot pick a direction to go.

Another situation is when the derivative is vanishing at a point even though the function is monotone, such as with $f(x)=1-x^3$.

There are a lot of different ways these situations can be tackled.

• Line search let's you continue as long as you have a direction to go in. If Newton's method can't give you a direction, you can try choosing random ones.
• Using a pseudoinverse may help. You could try estimating $\mathbf J^{-1}\mathbf f(\vec x)$ iteratively this way using something like the Gauss-Seidel method.
• Move a small random amount when the Jacobian is not invertible, or perhaps if its determinant is sufficiently small. Intuitively, you can see from the above examples that this should help Newton's method "get away" from the troublesome point and be able to start progressing again.

Answer 2

One thing you might try is to use the Moore-Penrose pseudoinverse of $J$ rather than the inverse.