System of quadratic algebraic equations

Question

I have this problem

$H_i(x_1,x_2,\dots, x_N) = a_{ijk} x_j x_k + b_{ij} x_j + c_i = 0 \quad 1\leq i \leq N$

And I need to show that applying Newton-Raphson can fail to find even one real solution of this system for any N.

Well if I apply Newton-Raphon, first I calculate the gradient:

$\frac{\partial H_i}{\partial x_l} = a_{ilk} x_k + a_{ijl} x_j + b_{il} = 0$

and solve for

$\boldsymbol{\Delta x} = -( \frac{\partial \boldsymbol{H}}{\partial \boldsymbol{x}})^{-1} \boldsymbol{H} $

Evaluating the gradient and the function at the initial estimation. The gradient is a second-order tensor. I do not know how this could fail. Maybe if the initial estimation did not converge, but that's a matter of choosing a good one. I assume the system has a solution, since the question focuses on finding the solutions, not on whether these exist or not. Thanks in advance.

Answer 1

You can show that any system of polynomial equations can be written as a larger system of quadratic equations by introducing new variables for intermediate terms. Now it is known that global convergence of Newtons method gets worse the higher the degree and dimension, so there should be many examples that show this property.

Answer 2

This is a generalization of the scalar case $f(x) = a x^2 + b x + c = 0$. The derivative $f'(x) = 2 a x + b$ may be zero at a solution, which happens if and only if $b^2 = 4 a c$ (in which case the graph of $f$ only touches the $x$-axis but does not cross it).

Likewise, in your quadratic system the Jacobian may be singular (i. e. not invertible) at a solution under some conditions. In this case Newton's method will fail to converge.