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
    Commented Nov 24, 2014 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
    Commented Nov 24, 2014 at 1:34
  • $\begingroup$ Cross-posted on math.se: math.stackexchange.com/questions/1036219/…. $\endgroup$ Commented Nov 24, 2014 at 6:33

1 Answer 1

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
    Commented Jan 10, 2015 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$ Commented Jan 10, 2015 at 17:25

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.