Den Faddeev-Leverrier-algoritmen er en metode for å beregne karakteristiske polynom av en matrise . Den er oppkalt etter den russiske matematikeren Dmitrii Konstantinovich Faddeev (ru) . Først utgitt av Urbain Le Verrier (1840), ble den gjenoppdaget mange ganger: Horst (1935), Souriau (1948), Frame (1949), Faddeev (en) og Sominskii (1949).
Å beregne det karakteristiske polynomet til en kvadratmatrise M i orden n er av grunnleggende praktisk betydning, siden det er et middel for å få tilgang til egenverdiene til M eller et polynom som avbrytes i M ( Cayley-Hamilton-setning ). Dette problemet er imidlertid svært beregningsmessig, og den naive algoritmen, som vil bestå i direkte beregning av determinanten , er ekstremt tung når det gjelder algoritmisk kompleksitet : den er en determinant som skrives som summen av n ! termer, hvor n betegner størrelsen på matrisen M ; imidlertid svingemetoden gjør det mulig for denne beregningen for å bli redusert til en tid av orden O ( n- 3 ).
Faddeevs algoritme er en del av en effektivitetsmetode. La oss starte fra matrisen M , som vi leter etter det karakteristiske polynomet .
Vi definerer ved induksjon den endelige sekvensen av matriser med:
tilSå viser vi at det karakteristiske polynomet til M er verdt:
Koeffisientene til det karakteristiske polynomet uttrykkes i form av spor , produkter og sum av matriser, noe som gjør dem lette å beregne, i det minste for en maskin. Kompleksiteten til Faddeevs algoritme er polynom, og vi kan vise at den i mange tilfeller er mer effektiv enn beregningen av determinanten ved hjelp av pivotmetoden. I tillegg ble en rask parallell implementering av Faddeevs algoritme oppnådd av Lazslo Csanky i 1975; det viser at denne algoritmen er i NC- kompleksitetsklassen .
Samuelson-Berkowitz-algoritme (de)
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">