Vieta's theorem

Vieta's theorem states that given a polynomial equation $$a_nx^n + \cdots + a_1x+a_0=0$$ the quantities \begin{align*}s_1&=r_1+r_2+\cdots\\ s_2&=r_1 r_2 +r_1 r_3 + \cdots \end{align*} etc., where $r_1,\dots, r_n$ are the roots of the polynomial equation are given by $$s_i = (-1)^i \frac{a_{n-i}}{a_n} .$$

So my question is: can we use this to find all the roots of the polynomial equation?

-
They are helpful in studying the roots of the equation, and are used in the derivations of formulas for the roots. But all that was done 100s of years ago. –  GEdgar Nov 20 '11 at 21:38
In some cases (especially with quadratic polynomials), it might help you guess the factorization (for example, try factoring $X^2-5X+6$ or $X^2 - 2 \cos(\theta) X + 1$ that way). But in general, finding the roots from this formula amounts to solving the same equation. However the formula is used in some theoretical arguments. –  Joel Cohen Nov 21 '11 at 0:08

Quick answer : you're not going to find the roots in any quicker way with this method. Remember that in general, for polynomials of degree 5 or more, you cannot find explicit formulas for the roots. You simply cannot. With this method or another.

Now, what is the Vieta's theorem? It is in fact just expanding the product $$a_n * \prod_{i=1}^n (x - r_i) = a_nx^n + \dots + a_1x+a_0$$

-
Aka as Vieta's formulas. Since Viète did pioneering work on algebra and algebraic notation, it's fine to call this observation a theorem. –  lhf Nov 21 '11 at 0:22
Absolutely! I did not meant any disrespect toward his work. It's just that stated like this, it seems that there is some "magic" involved (We don't know the roots, but we know something about some strange product involving them? Magic!) Explaining where the magic comes from helps understand why, in fact, we can't "magically" find the roots. –  Fezvez Nov 22 '11 at 6:10

Numerically, however, for a monic polynomial $p(x)=x^n+c_{n-1} x^{n-1}+\cdots+c_1 x+c_0$, one can treat the Vieta equations relating the $n$ roots $x_k$ and the $n$ remaining coefficients $c_j$ as a system of simultaneous nonlinear equations, and then apply the multivariate version of Newton-Raphson on them.

To wit, note that the Jacobian of the system (I use the quartic case here to keep things simple)

\begin{align*}x_1+x_2+x_3+x_4=&-c_3\\x_1 x_2+x_3 x_2+x_4 x_2+x_1 x_3+x_1 x_4+x_3 x_4=&c_2\\x_1 x_2 x_3+x_1 x_4 x_3+x_2 x_4 x_3+x_1 x_2 x_4=&-c_1\\x_1 x_2 x_3 x_4=&c_0\end{align*}

is

$$\begin{split}&\mathbf J(\mathbf x)=\mathbf J(x_1,x_2,x_3,x_4)=\\&\small\begin{pmatrix} 1 & 1 & 1 & 1 \\ x_2+x_3+x_4 & x_1+x_3+x_4 & x_1+x_2+x_4 & x_1+x_2+x_3 \\ x_2 x_3+x_4 x_3+x_2 x_4 & x_1 x_3+x_4 x_3+x_1 x_4 & x_1 x_2+x_4 x_2+x_1 x_4 & x_1 x_2+x_3 x_2+x_1 x_3 \\ x_2 x_3 x_4 & x_1 x_3 x_4 & x_1 x_2 x_4 & x_1 x_2 x_3\end{pmatrix}\end{split}$$

with inverse

$$\begin{split}&\mathbf J^{-1}(\mathbf x)=\mathbf J^{-1}(x_1,x_2,x_3,x_4)=\\&\tiny \begin{pmatrix}\frac{x_1^3}{(x_1-x_2) (x_1-x_3) (x_1-x_4)} &\frac{x_1^2}{(x_1-x_2) (x_1-x_3) (x_4-x_1)} &\frac{x_1}{(x_1-x_2) (x_1-x_3) (x_1-x_4)} & \frac1{(x_2-x_1)(x_1-x_3) (x_1-x_4)} \\ \frac{x_2^3}{(x_2-x_1) (x_2-x_3) (x_2-x_4)} &\frac{x_2^2}{(x_1-x_2) (x_2-x_3) (x_2-x_4)} &\frac{x_2}{(x_2-x_1) (x_2-x_3) (x_2-x_4)} & \frac1{(x_1-x_2) (x_2-x_3) (x_2-x_4)} \\\frac{x_3^3}{(x_1-x_3) (x_2-x_3) (x_3-x_4)} &\frac{x_3^2}{(x_1-x_3) (x_3-x_2) (x_3-x_4)} &\frac{x_3}{(x_1-x_3) (x_2-x_3) (x_3-x_4)} & \frac1{(x_1-x_3)(x_3-x_2) (x_3-x_4)} \\\frac{x_4^3}{(x_4-x_1) (x_4-x_2) (x_4-x_3)} &\frac{x_4^2}{(x_1-x_4) (x_4-x_2) (x_4-x_3)} &\frac{x_4}{(x_4-x_1) (x_4-x_2) (x_4-x_3)} & \frac1{(x_1-x_4)(x_4-x_2) (x_4-x_3)}\end{pmatrix}\end{split}$$

and thus the Newton-Raphson iteration function looks like this:

$$\mathbf x-\mathbf J^{-1}(\mathbf x)\begin{pmatrix}s_1+c_3\\s_2-c_2\\s_3+c_1\\s_4-c_0\end{pmatrix}$$

or explicitly,

\begin{align*}x_1-&\frac{c_3 x_1^3+c_2 x_1^2+c_1 x_1+c_0+x_1^4}{(x_1-x_2) (x_1-x_3)(x_1-x_4)}\\x_2-&\frac{c_3 x_2^3+c_2 x_2^2+c_1 x_2+c_0+x_2^4}{(x_2-x_1)(x_2-x_3) (x_2-x_4)}\\x_3-&\frac{c_3 x_3^3+c_2 x_3^2+c_1 x_3+c_0+x_3^4}{(x_3-x_1) (x_3-x_2) (x_3-x_4)}\\x_4-&\frac{c_3 x_4^3+c_2 x_4^2+c_1 x_4+c_0+x_4^4}{(x_4-x_1) (x_4-x_2) (x_4-x_3)}\end{align*}

This application of the multivariate Newton-Raphson method to the Vieta formulae is called the Durand-Kerner algorithm for simultaneously determining the roots of a polynomial:

$$x_i^{(k+1)}=x_i^{(k)}-\frac{p(x_i^{(k)})}{\prod\limits_{j\neq i} (x_i^{(k)}-x_j^{(k)})},\qquad i=1\dots n;\; k=0,1,\dots$$

where the $x_i^{(0)}$ are initial approximations (which, as with any Newton-Raphson method, are required). As with the usual Newton-Raphson method, it is quadratically convergent. It is however remarkable that the method is not as finicky with initial conditions as is usual with Newton-Raphson. (In practice, however, one usually takes equally spaced points around a circle in the complex plane as a starting point for the method, where the radius is determined from bounds for the roots.)

See Kerner's original paper for more details of the derivation.

The algorithm is also sometimes referred to as the Weierstrass-Durand-Kerner method, since Karl Weierstrass used this in his constructive proof of the fundamental theorem of algebra. See Weierstrass's paper for more on this.

-
It is just magic typing!! –  awllower Nov 22 '11 at 8:15
Huh? What are you on about? –  Ｊ. Ｍ. Nov 22 '11 at 8:19

You cannot use the symmetric functions to find the roots despite a natural urge to do so. It is instructive to try it and find yourself back where you started from. Try it with a quadratic equation.

-
My point is from $r_1=x_1+x_2$ and $r_2=x_1 x_2$, all you get by eliminating $x_2$ is $x_1^2 - r_1 x_1 + r_2=0$, which is the original equation. You need an idea to solve it. In this case, completing the square. You need other ideas for degrees 3 and 4 and there are none for higher degrees... –  lhf Nov 22 '11 at 11:13