I am looking for a numerical method that can solve a system of non-linear equations. The non-linear equations are polynomials that are in one of the following forms:

$$ c_1x_1+c_2x_2+\ldots+c_nx_n=C \\ d_1x_1^2+d_2x_2^2+\ldots+d_nx_n^2=D $$

(The variables are $x_1,x_2,\ldots x_n$.)

I can't get initial guesses that are close to the root. Is there a good numerical method to solve the system of equations?

Thank you in advance

  • $\begingroup$ Have you tried MATLab or SAGE? You'll have to do a little scripting magic, but it's nothing too complicated ;-) If you need help with that, though, edit your question to reflect that and/or ask on StackOverflow. $\endgroup$ – ThisIsNotAnId May 28 '12 at 17:58

So if I understood your question correctly you are trying to solve a non-linear system of equations of the form

$$ Ax + x^{T}Bx = b .$$

Restating it as

$$ ( A + x^{T}B ) x = b $$ $$ \Leftrightarrow x = (A + x^{T}B)^{-1}b = f(x) $$ $$ \Leftrightarrow x - f(x) = 0 $$

a fixed point is found. Any root-finding method can now be used. For example, the simplest approach would be a fixed-point iteration of the form

$$ x_{i+1} = (A + x_{i}^{T}B)^{-1}b ,$$

but alternatives include Newton's or any other higher order method of the Housholder family.

Note 1: In $x_{i+1} = (A + x_{i}^{T}B)^{-1}b$ the matrix $(A + x_{i}^{T}B)^{-1}$ should not be interpeted as computing the inverse but as solving the linear system of equations $(A + x_{i}^{T}B)x_{i+1} = b$. This system of equations will be solved multiple times until some criterion is met (e.g. the residual $r = \lvert ( A + x^{T}B ) x - b \rvert $ being smaller than some prescribed tolerance $\epsilon_{tol}$).

Note 2: this works assuming an unique solution exists. The closer your initial guess $x_0$ is to the "exact" solution, the less number of iterations you will need. As such a first step towards improving your method is to get a better initial guess. Another possibility is to use a method with a larger convergence radious first (e.g. a fix-point iteration), and then switch to a method with better convergence properties when some residual criterion is met (e.g. switch to Newton's method if $r<10^{-2}$).


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.