Fordított iteráció - Inverse iteration

A numerikus elemzés során az inverz iteráció ( inverz teljesítmény módszerként is ismert ) iteratív sajátérték-algoritmus . Ez lehetővé teszi egy hozzávetőleges sajátvektor megtalálását, ha a megfelelő sajátértékhez való közelítés már ismert. A módszer fogalmilag hasonló a hatalmi módszerhez . Úgy tűnik, hogy eredetileg úgy fejlesztették ki, hogy kiszámítsa a rezonanciafrekvenciákat a szerkezeti mechanika területén.

Az inverz teljesítmény iterációs algoritmus kezdődik közelítő a sajátérték megfelel a kívánt sajátvektor és a vektor , vagy egy véletlenszerűen kiválasztott vektor, vagy egy közelítés a sajátvektor. A módszert az iteráció írja le ${\ displaystyle \ mu}$${\ displaystyle b_ {0}}$

${\ displaystyle b_ {k + 1} = {\ frac {(A- \ mu I) ^ {- 1} b_ {k}} {C_ {k}}},}$

ahol általában néhány állandót választunk, mivel a sajátvektorokat az állandóval való szorzásig határozzuk meg, az elméletben tetszőleges lehet; Az alábbiakban tárgyaljuk a választás gyakorlati szempontjait . ${\ displaystyle C_ {k}}$${\ displaystyle C_ {k} = \ | (A- \ mu I) ^ {- 1} b_ {k} \ |.}$${\ displaystyle C_ {k}}$${\ displaystyle C_ {k}}$

Minden iterációnál a vektort megszorozzuk a mátrixszal és normalizáljuk. Ez pontosan ugyanaz képlet, mint a Power Method , azzal az eltéréssel, helyettesítve a mátrix által Minél közelebb van a közelítés a sajátérték választjuk, a gyorsabb az algoritmus konvergál; a helytelen választás azonban lassú konvergenciához vagy a kívánt kiviteltől eltérő sajátvektorhoz való konvergenciához vezethet. A gyakorlatban ezt a módszert akkor alkalmazzák, amikor ismert a sajátérték jó közelítése, és ezért csak néhány (elég gyakran csak egy) iterációra van szükség. ${\ displaystyle b_ {k}}$${\ displaystyle (A- \ mu I) ^ {- 1}}$${\ displaystyle A}$${\ displaystyle (A- \ mu I) ^ {- 1}.}$${\ displaystyle \ mu}$${\ displaystyle \ mu}$

Elmélet és konvergencia

A teljesítmény iterációjának alapgondolata a kezdeti vektor kiválasztása (vagy egy sajátvektor közelítés, vagy egy véletlenszerű vektor) és az iteratív kiszámítás . A nulla mértékegység kivételével bármelyik kezdeti vektor esetén az eredmény konvergál a domináns sajátértéknek megfelelő sajátvektorral . ${\ displaystyle b}$${\ displaystyle Ab, A ^ {2} b, A ^ {3} b, ...}$

Az inverz iteráció ugyanezt teszi a mátrixra , tehát konvergál a mátrix domináns sajátértékének megfelelő sajátvektorral . Ennek a mátrixnak a sajátértékei vannak, ahol vannak a . Ezeknek a számoknak a legnagyobbja felel meg a legkisebbnek a és a sajátvektorai megegyeznek, mivel ${\ displaystyle (A- \ mu I) ^ {- 1}}$${\ displaystyle (A- \ mu I) ^ {- 1}}$${\ displaystyle (\ lambda _ {1} - \ mu) ^ {- 1}, ..., (\ lambda _ {n} - \ mu) ^ {- 1},}$${\ displaystyle \ lambda _ {i}}$${\ displaystyle A}$${\ displaystyle (\ lambda _ {1} - \ mu), ..., (\ lambda _ {n} - \ mu).}$${\ displaystyle A}$${\ displaystyle (A- \ mu I) ^ {- 1}}$

${\ displaystyle Av = \ lambda v \ Leftrightarrow (A- \ mu I) v = \ lambda v- \ mu v \ Leftrightarrow (\ lambda - \ mu) ^ {- 1} v = (A- \ mu I) ^ {-1} v}$

Következtetés : A módszer a mátrix sajátvektorához konvergál, amely a legközelebbi sajátértékhez tartozik ${\ displaystyle A}$${\ displaystyle \ mu.}$

Különösen, ha azt látjuk, hogy konvergál a sajátvektorhoz, amely megfelel a legkisebb abszolút értékű sajátértéknek . ${\ displaystyle \ mu = 0}$${\ displaystyle (A) ^ {- 1} b_ {k}}$${\ displaystyle A}$

A konvergencia sebessége

Elemezzük a módszer konvergencia-sebességét .

Az energiateljesítményről ismert, hogy lineárisan konvergál a határértékre, pontosabban:

${\ displaystyle \ mathrm {Távolság} (b ^ {\ mathrm {ideális}}, b _ {\ mathrm {Teljesítmény ~ módszer}} ^ {k}) = O \ balra (\ balra | {\ frac {\ lambda _ { \ mathrm {szubdomináns}}} {\ lambda _ {\ mathrm {domináns}}}} \ jobb | ^ {k} \ jobb),}$

így az inverz iterációs módszernél hasonló eredmény hangzik, mint:

${\ displaystyle \ mathrm {Távolság} (b ^ {\ mathrm {ideális}}, b _ {\ mathrm {Inverz ~ iteráció}} ^ {k}) = O \ balra (\ balra | {\ frac {\ mu - \ lambda _ {\ mathrm {a ~ -hoz legközelebb álló ~ {\ ma}} {\ mu - \ lambda _ {\ mathrm {második ~ a ~} -hoz legközelebb álló ~ ~}} jobbra | ^ {k} \ jobbra.)}$

Ez kulcsfontosságú formula a módszer konvergenciájának megértéséhez. Ez azt mutatja, hogy ha valamilyen sajátértékhez közel áll , akkor például minden iteráció javítja a pontossági időket. (Azt használjuk, hogy elég kicsinél a "legközelebb " és a "a legközelebb " ugyanaz.) Kicsit kicsinél körülbelül ugyanaz, mint a . Ennélfogva, ha valaki úgy talál , hogy az elég kicsi, akkor nagyon kevés iteráció lehet kielégítő. ${\ displaystyle \ mu}$${\ displaystyle \ lambda}$${\ displaystyle \ mu - \ lambda = \ epsilon}$${\ displaystyle | \ epsilon | / | \ lambda + \ epsilon - \ lambda _ {\ mathrm {legközelebb ~ ~} \ lambda} |}$${\ displaystyle \ epsilon}$${\ displaystyle \ mu}$${\ displaystyle \ lambda}$${\ displaystyle | \ epsilon |}$${\ displaystyle | \ epsilon | / | \ lambda - \ lambda _ {\ mathrm {legközelebb ~ a ~} -hez \ lambda} |}$${\ displaystyle \ mu}$${\ displaystyle \ epsilon}$

Bonyolultság

Az inverz iterációs algoritmus megköveteli egy lineáris rendszer megoldását vagy az inverz mátrix kiszámítását. Nem strukturált mátrixok esetén (nem ritka, nem Toeplitz, ...) ehhez műveleteket kell végrehajtani. ${\ displaystyle O (n ^ {3})}$

Végrehajtási lehetőségek

A módszert a következő képlet határozza meg:

${\ displaystyle b_ {k + 1} = {\ frac {(A- \ mu I) ^ {- 1} b_ {k}} {C_ {k}}},}$

Ennek végrehajtására azonban többféle lehetőség van.

Számítsa ki a fordított mátrixot vagy oldja meg a lineáris egyenletek rendszerét

A képletet a következő módon tudjuk átírni:

${\ displaystyle (A- \ mu I) b_ {k + 1} = {\ frac {b_ {k}} {C_ {k}}},}$

hangsúlyozva, hogy a következő közelítés megtalálásához megoldhatjuk a lineáris egyenletek rendszerét. Két lehetőség van: választhat egy algoritmust, amely egy lineáris rendszert old meg, vagy kiszámolhatja a fordított értéket , majd alkalmazhatja azt a vektorra. Mindkét opció bonyolult O (n ³ ) , a pontos szám a választott módszertől függ. ${\ displaystyle b_ {k + 1}}$${\ displaystyle (A- \ mu I) ^ {- 1}}$

A választás az iterációk számától is függ. Naiiván, ha minden iterációnál egy lineáris rendszert old meg, akkor a bonyolultság k * O (n ³ ) , ahol k iterációk száma; Hasonlóképpen, az inverz mátrix kiszámítása és minden iterációnál történő alkalmazása k * O (n ³ ) bonyolultságú . Vegye figyelembe azonban, hogy ha a sajátérték becslése állandó marad, akkor bármelyik módszerrel csökkenthetjük a bonyolultságot O (n ³ ) + k * O (n ² ) értékre. A fordított mátrix egyszeri kiszámítása és az iterációnál történő tárolása O (n ³ ) + k * O (n ² ) bonyolultságú . Tárolása egy LU bomlása a és használata előre és vissza helyettesítés , hogy megoldja az egyenletrendszert minden iteráció is a komplexitás O (n ³ ) + k * O (n ² ) . ${\ displaystyle \ mu}$${\ displaystyle (A- \ mu I)}$

A mátrix invertálása általában magasabb kezdeti költségekkel jár, de minden iterációnál alacsonyabb költségekkel jár. Ezzel szemben a lineáris egyenletek megoldása rendszerint alacsonyabb kezdeti költségekkel jár, de minden egyes iterációhoz több műveletet igényel.

Háromszög alakú alakítás , Hessenberg-forma

Ha sok iterációt kell elvégezni (vagy néhány iterációt kell elvégezni, de sok sajátvektorhoz szükséges), akkor bölcs dolog az, ha a mátrixot először a felső Hessenberg-formába hozza (szimmetrikus mátrix esetében ez háromszög alakú lesz ). Amely házszám-redukción alapuló technikával végzett aritmetikai műveleteket fizet ), az ortogonális hasonlóságok véges sorrendjével, kissé olyan, mint egy kétoldalas QR-bomlás. (A QR-bomláshoz a háztulajdonos-forgatások csak balra szorozódnak, a Hessenberg-eset esetén pedig balra és jobbra is.) Szimmetrikus mátrixok esetén ez az eljárás aritmetikai műveleteket igényel a háztulajdonos redukción alapuló módszer alkalmazásával.${\ displaystyle {\ kezdődik {mátrix} {\ frac {10} {3}} \ vége {mátrix}} n ^ {3} + O (n ^ {2})}$${\ displaystyle {\ kezdődik {mátrix} {\ frac {4} {3}} \ vége {mátrix}} n ^ {3} + O (n ^ {2})}$

A háromszögletű mátrix lineáris egyenletrendszerének megoldása költségeket okoz , tehát az összetettség növekszik , ahol az iterációs szám jobb, mint a közvetlen inverziónál. Néhány iterációnál azonban az ilyen átalakítás nem feltétlenül praktikus. ${\ displaystyle O (n)}$${\ displaystyle O (n ^ {3}) + kO (n)}$${\ displaystyle k}$

A Hessenberg formává történő átalakulás négyzetes gyökereket és az osztási műveletet is magában foglal, amelyeket a hardver nem általánosan támogat.

A normalizálási állandó megválasztása ${\ displaystyle C_ {k}}$

Általános célú (például az Intel által gyártott) processzorokon az összeadás, szorzás és osztás végrehajtási ideje megközelítőleg azonos. A beágyazott és / vagy alacsony energiaigényű hardverek ( digitális jelfeldolgozók , FPGA , ASIC ) megosztását azonban a hardver nem támogatja, ezért kerülendő. A választás lehetővé teszi a gyors osztást kifejezett hardver támogatás nélkül, mivel a 2-es teljesítménnyel történő osztást bit-eltolásként ( fixpontos aritmetika esetén ) vagy az exponenstől való kivonásként ( lebegőpontos aritmetika ) lehet végrehajtani. ${\ displaystyle C_ {k} = 2 ^ {n_ {k}}}$${\ displaystyle k}$

Ha az algoritmust fixpontos aritmetikai módszerrel valósítja meg , az állandó megválasztása különösen fontos. A kis értékek a normák gyors növekedéséhez és a túlcsorduláshoz vezetnek ; A nagy érték esetén a vektor nulla felé hajlik. ${\ displaystyle C_ {k}}$${\ displaystyle b_ {k}}$${\ displaystyle C_ {k}}$${\ displaystyle b_ {k}}$

Használat

A módszer fő alkalmazása az a helyzet, amikor egy sajátértékhez közelítést találunk, és meg kell találni a hozzávetőleges sajátvektort. Ilyen helyzetben a fordított iteráció a fő és valószínűleg az egyetlen használható módszer.

Hozzávetőleges sajátértékek meghatározásának módszerei

Tehát általában a módszert valamilyen más módszerrel kombinálva alkalmazzák, amely megközelítő sajátértékeket talál: a standard példa a felezési sajátérték algoritmus , egy másik példa a Rayleigh hányados iteráció , amely valójában ugyanaz az inverz iteráció a hozzávetőleges sajátérték kiválasztásával, mint a Az iteráció előző lépésében kapott vektornak megfelelő Rayleigh hányados .

Vannak olyan helyzetek, amikor a módszer önmagában is használható, ám ezek meglehetősen marginálisak.

A mátrix normája a domináns sajátértékhez való közelítésként

A domináns sajátérték bármely mátrixra könnyen becsülhető. Bármely indukált normára igaz, hogy minden sajátértékre . Tehát, ha a mátrix normáját megközelítő sajátértékként vesszük, akkor láthatjuk, hogy a módszer konvergál a domináns sajátvektorhoz. ${\ displaystyle \ left \ | A \ right \ | \ geq | \ lambda |,}$${\ displaystyle \ lambda}$

Becslések statisztikák alapján

Néhány valósidejű alkalmazásban meg kell találni a mátrixok sajátvektorát másodpercenkénti millió mátrix sebességgel. Az ilyen alkalmazásokban általában a mátrixok statisztikája előre ismert, és hozzávetőleges sajátértéken lehet venni egy nagy mátrixminta átlagos sajátértékét. Jobb, ha kiszámíthatjuk a sajátérték és a nyomvonal vagy a mátrix normájának átlagos arányát, és becsülhetjük meg az átlagos sajátérték értékét a nyomkövetéssel vagy a normával szorozva az arány átlagos értékével. Egyértelmű, hogy egy ilyen módszer csak diszkrécióval és csak akkor alkalmazható, ha a nagy pontosság nem kritikus. Az átlagos sajátérték becslésének ez a megközelítése más módszerekkel kombinálható a túlzott hiba elkerülése érdekében.

Lásd még

• Teljesítmény iteráció
• Rayleigh hányados iteráció
• Sajátérték-algoritmusok felsorolása

Irodalom

Külső linkek

• Inverz inerció sajátvektorok megtalálására , fizika.arizona.edu