5
$\begingroup$

$$ x_1 + x_2 + \cdots +x_n = c_1 $$ $$ \frac{x_1^2}{2} + \frac{x_2^2}{2} + \cdots +\frac{x_n^2}{2} = c_2 $$
$$ \cdots $$ $$ \frac{x_1^n}{n!} + \frac{x_2^n}{n!} + \cdots +\frac{x_n^n}{n!} = c_n $$

$c_1,\cdots,c_n$ are known constants. $x_1 \cdots x_n$ are the unknown variables to solve.

$\endgroup$
3
  • $\begingroup$ What have you tried ? BTW, using the word algorithm does not make it Computer Science. Solving such equations seems straight math to me. $\endgroup$ – babou Nov 24 '14 at 1:30
  • $\begingroup$ I am wondering some iteration techniques, but have no experience. Please let me known what kind of mathematics approaciate, I am not sure if numerical mathematics is suitable for math exchange. If necessary i will post it there. $\endgroup$ – user26143 Nov 24 '14 at 1:34
  • $\begingroup$ Cross-posted on math.se: math.stackexchange.com/questions/1036219/…. $\endgroup$ – Yuval Filmus Nov 24 '14 at 6:33
7
$\begingroup$

One way, which is numerically probably a bad idea, is to use Newton's identities. They give the value of the elementary symmetric functions given the power sums, and from the elementary symmetric functions you can construct a polynomial whose roots are the answers to your problem. Let $p_k = k! c_k$, and let $e_k$ be the sum of all $\binom{n}{k}$ products of $k$ variables out of $x_1,\ldots,x_n$. Newton's identities state that $$ ke_k = (-1)^{k-1} p_k + \sum_{i=1}^{k-1} (-1)^{i-1} e_{k-i} p_i. $$ Using these identities, you can compute $e_1,\ldots,e_n$. Now consider the polynomial $$ P = x^n + \sum_{i=1}^n (-1)^i e_i x^{n-i}. $$ The unique solution to your equations are the $n$ roots of $P$.

As an example, let's do the case $n = 2$. We have $e_1 = p_1$ and $$ 2e_2 = -p_2 + e_1 p_1 = p_1^2 - p_2. $$ The polynomial $P$ is therefore $$ x^2 - p_1 x + \frac{p_1^2-p_2}{2}. $$

For $n=3$ we calculate additionally $$ 3e_3 = p_3 - e_1 p_2 + e_2 p_1 = p_3 - p_1 p_2 + \frac{p_1^2-p_2}{2} p_1 = \frac{2p_3 - 3p_1p_2 + p_1^3}{2}. $$ The polynomial $P$ is therefore $$ x^3 - p_1 x^2 + \frac{p_1^2-p_2}{2}x - \frac{2p_3 - 3p_1p_2 + p_1^3}{6}. $$

$\endgroup$
2
  • $\begingroup$ Sorry for late response, excuse me, why the roots of $P$ give the solutions to the eqns above, i.e. $\sum_i^n x_i^k /k!= c_k, k=1,2,\cdots, n$? $\endgroup$ – user26143 Jan 10 '15 at 13:54
  • 1
    $\begingroup$ If we write $P = (x-x_1)(x-x_2)\cdots(x-x_n)$ then we can read off the coefficients of $x^m$ to deduce that $e_1=x_1+\cdots+x_n$, $e_2=x_1x_2+\cdots+x_{n-1}x_n$, and so on. Therefore the roots $x_1,\ldots,x_n$ of $P$ satisfy these equations on $e_1,\ldots,e_n$. We conclude that the roots of $P$ are solutions of the system of equations $e_1=x_1+\cdots+x_n$, $e_2=x_1x_2+\cdots+x_{n-1}x_n$, ..., $e_n = x_1x_2\cdots x_n$. A priori there could be other solutions, but this is not the case here. $\endgroup$ – Yuval Filmus Jan 10 '15 at 17:25

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.