# Numerical method for nonlinear system of algebraic equations of special type

I have a nonlinear system of algebraic equations of special kind: $$\begin{array}{rcl} x_{i}+y_{i}+z_{0,1}+c_{i,1}z_{1,1} & = & d_{i,1}, \\ x_{i}^2 + y_{i}^2 + z_{0,2} + c_{i,1} z_{1,2} + c_{i,2} z_{2,2} & = & d_{i,2} \\ \ldots & = & \ldots \\ x_{i}^{m} + y_{i}^{m} +z_{0,m}+c_{i,1} z_{1,m} + \ldots + c_{i,m} z_{m,m} & = & d_{i,m} \end{array}$$ where $i = 1,\ldots.k$ and number of equations is not less than number of unknowns. I have to find $(x_{i},y_{i},z_{i,j})$; $c_{i,j}$ and $d_{i,j}$ are known. Is there some numerical method that take in account specificity of this system? If not, please tell me which numerical method will work better with this system?

-
In general, for non-linear systems of equations, I would recommend newton's method. But I don't know of any specific method that can take advantage of your systems structure. Where do these equations come from? Perhaps others have researched this problem before and have come up with some recommendations. – Paul Nov 10 '12 at 13:56
Well, it's a polynomial system of equations, so that structure could potentially be exploited. Also, the linear part is almost lower-triangular, which is helpful. You could try looking at Gröbner basis methods, perhaps? Nevertheless, Newton's method can be a good first hack at it. – Geoff Oxberry Nov 10 '12 at 20:40
Is the number of equations equal to the number of variables? Or what will guarantee that there is a solution at all? – Arnold Neumaier Nov 12 '12 at 19:22
Apart from Gröbner basis methods (which are mostly symbolic methods), there are also specific numerical methods for systems of polynomial equations such as homotopy continuation methods (implemented in, e.g., PHCpack). – Christian Clason Nov 13 '12 at 20:00

I am also using the Newton's method to solve a system of non linear equations, it's a sample method, in fact it's a generalization of the known method for one variable. In the general case, we have the following system: $$f_1(x_1,x_2,x_3, ...,x_n)=0 \\ f_2(x_1,x_2,x_3, ...,x_n)=0 \\ \vdots \\ f_n(x_1,x_2,x_3, ...,x_n) = 0$$ Since the Newton's method is iterative, we guess the first vector of the solution then we search for correction to this last one and so on. Firstly, let's develop the functions in Taylor series (we neglect the terms of second and higher orders): $$f_1(x_1^0+\delta x_1^0,x_2^0+\delta x_2^0,...)=f_1(x_1^0,x_2^0,...)+\dfrac{\partial f_1}{\partial x_1}(x_1^0,x_2^0,...)+\dfrac{\partial f_1}{\partial x_2}(x_1^0,x_2^0,...) + ...=0 \\ f_2(x_1^0+\delta x_1^0,x_2^0+\delta x_2^0,...)=f_2(x_1^0,x_2^0,...)+\dfrac{\partial f_2}{\partial x_1}(x_1^0,x_2^0,...)+\dfrac{\partial f_2}{\partial x_2}(x_1^0,x_2^0,...) + ...=0 \\ \vdots \\ f_n(x_1^0+\delta x_1^0,x_2^0+\delta x_2^0,...)=f_n(x_1^0,x_2^0,...)+\dfrac{\partial f_n}{\partial x_1}(x_1^0,x_2^0,...)+\dfrac{\partial f_n}{\partial x_2}(x_1^0,x_2^0,...) + ...=0 \\$$ we can write it in matrix form:

$$\begin{bmatrix} \dfrac{\partial f_1}{\partial x_1}(x_1^0,x_2^0,...,x_n^0) & \dfrac{\partial f_1}{\partial x_2}(x_1^0,x_2^0,...,x_n^0) \dots \dfrac{\partial f_1}{\partial x_n}(x_1^0,x_2^0,...,x_n^0) \\ \\ \dfrac{\partial f_2}{\partial x_1}(x_1^0,x_2^0,...,x_n^0) & \dfrac{\partial f_2}{\partial x_2}(x_1^0,x_2^0,...,x_n^0) \dots \dfrac{\partial f_2}{\partial x_n}(x_1^0,x_2^0,...,x_n^0) \\ ~~~~\vdots & \vdots ~~~~~~~~~~\vdots \\ \\ \dfrac{\partial f_n}{\partial x_1}(x_1^0,x_2^0,...,x_n^0) & \dfrac{\partial f_n}{\partial x_2}(x_1^0,x_2^0,...,x_n^0) \dots \dfrac{\partial f_n}{\partial x_n}(x_1^0,x_2^0,...,x_n^0) \end{bmatrix} \begin{bmatrix} \delta x_1 \\ \\ \\ \delta x_2 \\ \vdots \\ \\ \\ \delta x_n \end{bmatrix} = \begin{bmatrix} -f_1(x_1^0,x_2^0,...,x_n^0) \\ \\ \\ -f_2(x_1^0,x_2^0,...,x_n^0) \\ \vdots \\ \\ \\ -f_n(x_1^0,x_2^0,...,x_n^0) \end{bmatrix}$$ or in a compact form: $J( \vec{x^i})\vec{\delta}x = -\vec{R}(\vec{x^i})$ where $J$ is called the jacobian matrix (

Now you give the initial guess: $$\vec{x^0} = \begin{bmatrix} x_1^0 \\ x_2^0 \\ x_3^0 \\ \vdots \\ x_n^0\\ \end{bmatrix}$$ Then you solve the system for the correction vector ($\vec{\delta}x$) when you obtain the values of $\vec{\delta}x$ you find the new vector $\vec{x^1}$ which is $\vec{x^1}$ = $\vec{x^0}$+$\vec{\delta^1}x$ and you repeat this to find

the new values in every iteration until it converges to the solution (you specify the convergence test), usually the convergence test is:

$\| \vec{\delta x }\| < \epsilon$ and $\|\vec{R}(\vec{x}^i)\| <\epsilon$

-
Welcome to SciComp! There are enough external resources describing Newton's method that I don't think including a detailed explanation of Newton's method is necessary for this post. Furthermore, the gist of your post was discussed in the comments of the original post, so this answer doesn't add anything new to the discussion. – Geoff Oxberry Mar 26 '15 at 19:29
at least I tried to help sir! the problem is not because I am new here, but you should ask what I am studying! – Navaro Mar 29 '15 at 0:51
Sir, if you are a Phd doesn't mean you are Einstein, please don't criticize people, we are here all searching for information don't make this personal! – Navaro Mar 29 '15 at 1:08
@GeoffOxberry With all due respect, this is a question and answer site. Comments might be helpful to the person who posed the question but they're pretty useless to other people who will come here looking for an answer. If Samir answered the question correctly, it should be marked as such. – nick Mar 30 '15 at 1:50