Page 206 - Matrices theory and applications

10.5. Leverrier’s Method
Elementary symmetric polynomials
:=
σ 1

:=
λ j λ k ,
σ 2
j<k
. . . λ 1 + ··· + λ n =Tr M, 189

σ r := λ j 1 ··· λ j r ,
j 1 <···<j r
.
.
.

σ n := λ j =det M.
j
Newton sums
m
s m := λ , 1 ≤ m ≤ n.
j
j
j
The numbers (−1) σ j are the coefficients of the characteristic polynomial
of M:
n
n
P M (X)= X − σ 1 X n−1 + σ 2 X n−2 − ··· +(−1) σ n .
m
Furthermore, the s m are the traces of the powers M . One can obtain
n
2
them by computing M ,... ,M . Each of these matrices is obtained in
α
O(n ) operations, with 2 ≤ α ≤ 3(α = 3, using the naive method for
the product of two matrices). In all, the computation of s 1 ,... ,s n needs
O(n α+1 ) operations, which is a lot, compared to iterative methods (QR ,
2
Jacobi), for which each iteration is made in O(n ) operations at worst.
The passage from Newton sums to elementary symmetric polynomials is
j
done through Newton’s formulas. If Σ j =(−1) σ j and Σ 0 := 1, we have
m

mΣ m + s k Σ m−k =0, 1 ≤ n.
k=1
One uses these formulas in increasing order, beginning with Σ 1 = −s 1 .
When Σ 1 ,... , Σ m−1 are known, one computes
1
Σ m = − (s 1 Σ m−1 + ··· + s m Σ 0 ).
m
2
This computation, which needs only O(n ) operations, has a negligible cost.
Besides the high cost of this method, its instability is unfortunate when
k
k = IR or k = CC:when n is large, s k increases like ρ(M) ,thus much
more rapidly than σ k . The eigenvalues of smaller modulus are thus much
perturbed by the round-off errors, and this is reinforced by the large number
of operations.