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?

  • 3
    $\begingroup$ 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. $\endgroup$
    – Paul
    Nov 10, 2012 at 13:56
  • 1
    $\begingroup$ 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. $\endgroup$ Nov 10, 2012 at 20:40
  • $\begingroup$ Is the number of equations equal to the number of variables? Or what will guarantee that there is a solution at all? $\endgroup$ Nov 12, 2012 at 19:22
  • $\begingroup$ 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). $\endgroup$ Nov 13, 2012 at 20:00
  • $\begingroup$ Have you found a way to write it more in a matrix style notation? I think the structure of the problem would be more visible. Although I admit it will be tricky. Interesting side note, you have $\approx 2k+m^2/2$ unkowns and $\approx 2km$ knowns which means that you cannot choose freely $m$ and $k$ because otherwise you end up with an under determined system. $\endgroup$
    – Bort
    Jul 23, 2019 at 13:30

1 Answer 1


I am also using the Newton's method to solve a system of non linear equations, it's a simple 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,...)\delta x_1+\dfrac{\partial f_1}{\partial x_2}(x_1^0,x_2^0,...)\delta x_2 + ...=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,...)\delta x_1+\dfrac{\partial f_2}{\partial x_2}(x_1^0,x_2^0,...)\delta x_2 + ...=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,...)\delta x_1+\dfrac{\partial f_n}{\partial x_2}(x_1^0,x_2^0,...)\delta x_2 + ...=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 $

  • 3
    $\begingroup$ 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. $\endgroup$ Mar 26, 2015 at 19:29
  • $\begingroup$ at least I tried to help sir! the problem is not because I am new here, but you should ask what I am studying! $\endgroup$
    – Navaro
    Mar 29, 2015 at 0:51
  • 1
    $\begingroup$ 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! $\endgroup$
    – Navaro
    Mar 29, 2015 at 1:08
  • $\begingroup$ @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. $\endgroup$
    – nick
    Mar 30, 2015 at 1:50
  • 1
    $\begingroup$ @nick The answer is technically correct. I can't accept the answer; only the OP can. I take issue with the following, none of which are personal: 1) The explanation is verbose about a method taught in the 1st or 2nd year of university to most computational scientists. 2) It essentially states "use Newton's method", as in the comments. It focuses on implementation (already done in many libraries); why one would want to use this method over others is much more informative. 3) The question asks about exploiting structure, and what method would be best; this answer doesn't address either point. $\endgroup$ Mar 30, 2015 at 7:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.