Take the 2-minute tour ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.

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?

share|improve this question
3  
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
1  
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

1 Answer 1

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 $

share|improve this answer
2  
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 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! –  Samir Ouchene Mar 29 at 0:51
1  
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! –  Samir Ouchene Mar 29 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 at 1:50
    
@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. –  Geoff Oxberry Mar 30 at 7:01

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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