3
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Is this question a homework problem? $\endgroup$ – Geoff Oxberry Jan 10 '14 at 1:52
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I don't think that the two Newton methods for the old and new system are easily related to each other. $\endgroup$ – Federico Poloni Jun 14 '14 at 13:18
  • $\begingroup$ No, that not. But if polynomial systems were easily solvable by transforming them into quadratic systems (that would even be sparse), then all the world would do it. $\endgroup$ – LutzL Jun 14 '14 at 16:20
1
$\begingroup$

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.

$\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.