0
$\begingroup$

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

  • 0
    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.2012-05-28

1 Answers 1

4

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}$).