A Faddeev-Leverrier algoritmus egy mátrix jellegzetes polinomjának kiszámítására szolgáló módszer . Nevét Dmitrii Konstantinovich Faddeev (ru) orosz matematikusról kapta . Először Urbain Le Verrier (1840) kiadta, és sokszor újra felfedezték: Horst (1935), Souriau (1948), Frame (1949), Faddeev (en) és Sominskii (1949).
Kiszámítása karakterisztikus polinomja egy négyzetes mátrix M rend n alapvető gyakorlati jelentősége, mivel ez egy módja hozzáférni az sajátértékek az M vagy polinom semlegesítette a M ( Cayley-Hamilton-tétel ). Ez a probléma azonban nagyon kiszámítható, és a naiv algoritmus, amely a determináns közvetlen kiszámításából állna , rendkívül nehéz az algoritmikus bonyolultság szempontjából : ez egy olyan determináns, amelyet n összegének írunk ! kifejezések, ahol n az M mátrix méretét jelöli ; a forgásmód azonban lehetővé teszi, hogy ezt a számítást O ( n 3 ) sorrendre redukáljuk .
Faddeev algoritmusa egy hatékonysági folyamat része. Kezdjük az M mátrixból , amelyhez a jellegzetes polinomot keressük .
Indukcióval definiáljuk a mátrixok véges szekvenciáját :
mertEzután megmutatjuk, hogy az M jellegzetes polinomja megér:
Az együtthatók a karakterisztikus polinom vannak kifejezve nyomok , termékek és összege mátrixok, ami számukra könnyen kiszámítható, legalábbis a gép. Faddeev algoritmusának bonyolultsága polinom, és megmutathatjuk, hogy sok esetben hatékonyabb, mint a determináns pivot módszerrel történő kiszámítása. Ezenkívül Faddeev algoritmusának gyors, párhuzamos megvalósítását Csanky Lazslo érte el 1975-ben; azt mutatja, hogy ez az algoritmus az NC komplexitási osztályba tartozik .
Samuelson-Berkowitz algoritmus (de)
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">