Faddeev–LeVerrier algorithm: Difference between revisions

Revision as of 06:23, 1 March 2016

Revision as of 12:03, 1 March 2016

Line 1:

In mathematics ([[linear algebra]]), the '''Faddeev–LeVerrier algorithm''' is a [[Recurrence relation|recursive]] method to calculate the coefficients of the [[characteristic polynomial]] <math>p(\lambda)=\det (\lambda I_n - A)</math> of a square [[Matrix (mathematics)|matrix]], {{mvar|A}}, named after [[Dmitry Konstantinovich Faddeev]] and [[Urbain Le Verrier]]. Calculation of this polynomial yields the [[eigenvalueseigenvalue]]s of {{mvar|A}} as its roots; as a matrix polynomial in the matrix {{mvar|A}} itself, it vanishes by the fundamental [[Cayley–Hamilton theorem]]. Calculating determinants, however, is computationally cumbersome, whereas this efficient algorithm is computationally significantly more efficient (in [[NC (complexity)|NC complexity class]]).

The algorithm has been independently rediscovered several times, in some form or another. It was first published in 1840 by [[Urbain Le Verrier]],<ref>[[Urbain Le Verrier]]: ''Sur les variations séculaires des éléments des orbites pour les sept planètes principales'', ''J. de Math.'' (1) '''5''', 230 (1840), [http://gallica.bnf.fr/ark:/12148/bpt6k163849/f228n35.capture# Online]</ref> subsequently redeveloped by