Monday, February 1, 2010

Faddeev-Leverrier Method

Let [Graphics:Images/FaddeevLeverrierMod_gr_1.gif] be an n × n matrix. The determination of eigenvalues and eigenvectors requires the solution of

(1) [Graphics:Images/FaddeevLeverrierMod_gr_2.gif]

where [Graphics:Images/FaddeevLeverrierMod_gr_3.gif] is the eigenvalue corresponding to the eigenvector [Graphics:Images/FaddeevLeverrierMod_gr_4.gif]. The values [Graphics:Images/FaddeevLeverrierMod_gr_5.gif] must satisfy the equation

(2) [Graphics:Images/FaddeevLeverrierMod_gr_6.gif].

Hence [Graphics:Images/FaddeevLeverrierMod_gr_7.gif] is a root of an nth degree polynomial [Graphics:Images/FaddeevLeverrierMod_gr_8.gif], which we write in the form

(3) [Graphics:Images/FaddeevLeverrierMod_gr_9.gif].

The Faddeev-Leverrier algorithm is an efficient method for finding the coefficients [Graphics:Images/FaddeevLeverrierMod_gr_10.gif] of the polynomial [Graphics:Images/FaddeevLeverrierMod_gr_11.gif]. As an additional benefit, the inverse matrix [Graphics:Images/FaddeevLeverrierMod_gr_12.gif] is obtained at no extra computational expense.

Recall that the trace of the matrix [Graphics:Images/FaddeevLeverrierMod_gr_13.gif], written [Graphics:Images/FaddeevLeverrierMod_gr_14.gif], is

(4) [Graphics:Images/FaddeevLeverrierMod_gr_15.gif].

The algorithm generates a sequence of matrices [Graphics:Images/FaddeevLeverrierMod_gr_16.gif] and uses their traces to compute the coefficients of [Graphics:Images/FaddeevLeverrierMod_gr_17.gif],

(5)

[Graphics:Images/FaddeevLeverrierMod_gr_18.gif]

[Graphics:Images/FaddeevLeverrierMod_gr_19.gif]

[Graphics:Images/FaddeevLeverrierMod_gr_20.gif]

[Graphics:Images/FaddeevLeverrierMod_gr_21.gif]

[Graphics:Images/FaddeevLeverrierMod_gr_22.gif]

[Graphics:Images/FaddeevLeverrierMod_gr_23.gif]

[Graphics:Images/FaddeevLeverrierMod_gr_24.gif]

[Graphics:Images/FaddeevLeverrierMod_gr_25.gif]

[Graphics:Images/FaddeevLeverrierMod_gr_26.gif]

[Graphics:Images/FaddeevLeverrierMod_gr_27.gif]

[Graphics:Images/FaddeevLeverrierMod_gr_28.gif]

[Graphics:Images/FaddeevLeverrierMod_gr_29.gif]

[Graphics:Images/FaddeevLeverrierMod_gr_30.gif]

[Graphics:Images/FaddeevLeverrierMod_gr_31.gif]

[Graphics:Images/FaddeevLeverrierMod_gr_32.gif]

[Graphics:Images/FaddeevLeverrierMod_gr_33.gif]

[Graphics:Images/FaddeevLeverrierMod_gr_34.gif]

[Graphics:Images/FaddeevLeverrierMod_gr_35.gif]

Then the characteristic polynomial is given by

(6) [Graphics:Images/FaddeevLeverrierMod_gr_36.gif].

In addition, the inverse matrix is given by

(7) [Graphics:Images/FaddeevLeverrierMod_gr_37.gif].

No comments:

Post a Comment

Introductory Methods of Numerical Analysis