Krylov sajátérték-módszere.

1.2 Krylov-módszer

Krylov módszere egy M négyzetmátrix azon tulajdonságán alapul, hogy eltünteti jellegzetes polinomját. Ebben a munkában az M mátrix technológiai kapcsolódási együtthatók mátrixa, amelynek alakja:

A Hamilton-Cali tétel szerint minden négyzetmátrix a karakterisztikus polinom gyöke, és ezért nullára fordítja. Legyen (1.2.1) a karakterisztikus polinom

A kifejezésben a λ értékét M-re cserélve megkapjuk

Ha veszünk egy tetszőleges Y 0 nem nulla vektort, és megszorozzuk vele az (1.2.2) kifejezés mindkét oldalát, a következőt kapjuk:

Vagy formában

Ha ez a rendszer rendelkezik egyetlen döntés, akkor p 1, p 2 .....p n gyökei a karakterisztikus polinom (1.2.1) együtthatói.

Ha ismertek a karakterisztikus polinom р 1, р 2…..р n együtthatói és λ 1, λ 2,….λ n gyökei, akkor a Krylov-módszer lehetővé teszi a megfelelő vektorok megtalálását a következő képlet segítségével :

Itt y (n -1), y (n -2), …. y (0) – a р 1 , р 2 .....р n együtthatók Krylov-módszerrel történő meghatározásához használt vektorok, a q ij () együtthatók Horner-séma segítségével kerülnek meghatározásra.

q 0i = 1, q ij = λ i q i-1,i +p i (1.2.7)

Meghatározására sajátértékek M mátrix, meg kell oldani a kapott karakterisztikus egyenletet. Az M mátrix esetében ez az egyenlet ötödik fokú lesz, ebben a munkában egy ilyen egyenletet fogunk megoldani a tangens módszerrel vagy más módon Newton módszerével.

1.3 Newton-módszer (tangens módszer)

A Newton-módszer (más néven tangens módszer) iteratív numerikus módszer egy adott függvény gyökének (nulla) megtalálása. A megoldás keresése egymást követő közelítések megszerkesztésével történik, és az egyszerű iteráció elvein alapul. A módszer másodfokú konvergenciával rendelkezik. A módszer továbbfejlesztése az akkordok és érintők módszere. A Newton-módszer felhasználható olyan optimalizálási feladatok megoldására is, amelyeknél meg kell határozni az első derivált vagy gradiens nulláját abban az esetben többdimenziós tér.

Az f(x) = 0 egyenlet egyszerű iterációs módszerrel történő numerikus megoldásához redukálni kell következő űrlapot: x = f(x), ahol f(x) egy összehúzódási leképezés.

A módszer legjobb konvergenciája érdekében a feltételnek a következő közelítés pontjában teljesülnie kell. Megoldás adott egyenlet keressen az űrlapon, majd:

Feltéve, hogy a megközelítési pont "elég közel" van a gyökérhez, és ez adott funkciót folyamatos, a végső képlet a következő:

(1.3.2)

Ezt figyelembe véve a függvényt a kifejezés határozza meg

(1.3.3)

Ez a függvény tömörítő leképezést hajt végre a gyökér szomszédságában, és a keresés algoritmusát numerikus megoldás az egyenlet egy iteratív számítási eljárásra redukálódik:

(1.3.4)

A Banach-tétel szerint a közelítések sorozata az egyenlet gyökeréig tart.

1.1 ábra- Grafikus ábrázolás Newton módszere

A módszer fő gondolata a következő: adott kezdeti közelítés a hipotetikus gyök közelében, ami után a közelítési pontban megszerkesztjük a vizsgált függvény érintőjét, amelyre az abszcissza tengellyel való metszéspontot találjuk. Ezt a pontot tekintjük a következő közelítésnek. És így tovább, amíg el nem éri a kívánt pontosságot.

A Newton-módszer előnyei:

1) ha a minimalizálandó függvény másodfokú, akkor a módszer lehetővé teszi, hogy egy lépésben megtalálja a minimumot;

2) ha a minimalizálandó függvény a forgásfelületek osztályába tartozik, akkor a módszer egy lépésben biztosítja a konvergenciát is;

3) ha a függvény aszimmetrikus, akkor a módszer nem biztosítja a konvergenciát végső szám lépések. De sok függvénynél sokkal nagyobb a konvergencia mértéke, mint a legmeredekebb ereszkedési módszer egyéb módosításaival.

A Krylov-módszer és a Newton-módszer alkalmazását a mellékletek tartalmazzák. A módszerek MathCAD és VB.Net környezetben kerültek implementálásra.

Fejlesztési és anyagköltségek. Így a diplomaterv célja a fejlesztés Szoftver csomag személyi számítógépen szimulálni a radarhelyzetet, lehetővé téve a radarhelyzet szimulációját a megadott paraméterek szerint, a számított modellt tartalmazó kimeneti fájl létrehozását, a kapott fájl felhasználásával valós feldolgozó eszközök tesztelésére...

1. Ha egy mátrixot adunk meg, akkor a karakterisztikus (világi) egyenletét a következő formában írjuk fel

. (81)

Ennek az egyenletnek a bal oldalán található egy jellemző fokszámú polinom. Ennek a polinomnak az együtthatóinak közvetlen kiszámításához fel kell tárni a karakterisztikus determinánst, és a nagyok esetében ez nagy számítási munkával jár, mivel a determináns átlós elemei között szerepel.

A. N. Krylov akadémikus 1937-ben javasolta a karakterisztikus determináns átalakítását, amelynek eredményeként az csak egy oszlop (vagy sor) elemeibe lép be. A Krylov-transzformáció jelentősen leegyszerűsíti a karakterisztikus egyenlet együtthatóinak számítását.

Ebben a részben a transzformált karakterisztikus egyenlet algebrai levezetését adjuk meg, amely némileg eltér magának Krylov levezetésétől.

Vegyünk figyelembe egy -dimenziós vektorteret egy bázissal és egy lineáris operátorral -ben, amelyet egy adott mátrix definiál ezen a bázison. Válasszunk egy tetszőleges vektort, és alkossunk vektorsorozatot

Legyen ennek a sorozatnak az első vektorai lineárisan függetlenek, és a th vektor ezeknek a vektoroknak a lineáris kombinációja:

A (82) sorozat minden további vektora szintén lineárisan fejeződik ki ennek a sorozatnak az első vektorain keresztül. Így a (82) sorozatban van egy lineáris független vektorok, és a sorozatnak ez a maximális számú lineárisan független vektora (82) mindig megvalósítható a sorozat első vektorain.

A polinom egy vektor minimális (törlő) polinomja egy operátorhoz képest (lásd 1. §). A. N. Krylov módszere egy módszer hatékony meghatározás minimális vektorpolinom.

Két esetet fogunk külön vizsgálni: a normál esetet, amikor , és a speciális esetet, amikor .

A polinom a teljes tér minimális polinomjának osztója, és viszont a karakterisztikus polinom osztója. Ezért ez mindig osztó.

Normál esetben, és azonos fokuk van, és mivel a vezető együtthatók egyenlők, ezek a polinomok egybeesnek. Így normál esetben

,

és ezért a Krylov-módszer normál esetben a karakterisztikus polinom együtthatóinak számítására szolgáló módszer.

BAN BEN különleges eset, amint alább látni fogjuk, a Krylov-módszer nem teszi lehetővé a meghatározását, és ebben az esetben csak azt a polinomot határozza meg, amely osztó.

A Krylov-transzformáció bemutatásakor a vektor koordinátáit egy adott bázisban -vel, a vektor koordinátáit pedig -vel jelöljük.

2. Szokásos eset: . Ebben az esetben a vektorok lineárisan függetlenek, és a (83), (84), (85) egyenlőségek a következő alakot öltik:

A vektorok liliomfüggetlenségének feltétele analitikusan a következőképpen írható fel (lásd III. fejezet 1. §):

. (89)

Tekintsünk egy vektorkoordinátákból álló mátrixot:

. (90)

Normál esetben ennek a mátrixnak a rangja egyenlő a -val. Ennek a mátrixnak az első sorai lineárisan függetlenek, az utolsó, i sor pedig az előzőek lineáris kombinációja.

A (90) mátrix sorai közötti függőséget úgy kapjuk meg, hogy a (86) vektoregyenlőséget egy ekvivalens skaláris egyenlőségrendszerre cseréljük.

(91)

Ebből a lineáris egyenletrendszerből egyedileg meghatározhatjuk a szükséges együtthatókat, és a kapott értékeket behelyettesíthetjük (88)-ba. Ez a kivétel a (88) és (91) alól szimmetrikus formában is végrehajtható. Ehhez átírjuk (88) és (91) a következőképpen:

Mivel ennek az ismeretlenekkel rendelkező egyenletrendszernek nincs nullától eltérő megoldása, ennek a rendszernek a determinánsának nullával kell egyenlőnek lennie:

. (92)

Innen meghatározzuk, miután előzőleg transzponáltuk a (92) determinánst a főátlóhoz képest:

, (93)

ahol az állandó tényezőt a (89) képlet határozza meg, és különbözik nullától.

Az identitás (93) a Krylov-transzformáció. A Krilov-determinánsban, amely ennek az azonosságnak a jobb oldalán található, csak az utolsó oszlop elemei között szerepel; ennek a determinánsnak a többi eleme nem függ attól.

Megjegyzés. Normál esetben a teljes tér ciklikus (az operátorhoz képest). Ha vektorokat választunk bázisnak, akkor ebben a bázisban az operátor egy természetes normál alakú mátrixnak felel meg

. (94)

A fő bázisról az alapra történő átmenet nem speciális transzformációs mátrix segítségével történik

. (95)

3. Speciális eset: . Ebben az esetben a vektorok lineárisan függőek, ezért

.

Az egyenlőséget (93) a feltétel alapján vezették le. De ennek az egyenlőségnek mindkét oldala egész racionális függvények-tól és paraméterektől. Ezért „a folytonossági megfontolásokból” az következik, hogy a (93) egyenlőség a -ra is érvényes. De ekkor a Krylov-determinánsban (93) annak kiterjesztése után minden együttható nulla lesz. Így egy speciális esetben a (93) képlet triviális azonossággá válik.

Tekintsünk egy vektorkoordinátákból álló mátrixot

. (97)

Ennek a mátrixnak van egy rangja, és az első sorok lineárisan függetlenek, az utolsó sor az első sorok lineáris kombinációja együtthatókkal [cm. (83)]. A koordináták közül választhatunk olyan koordinátákat, hogy a determináns ezekből a vektorkoordinátákból álljon össze , különbözött a nullától:

. (98)

(99)

Ebből az egyenletrendszerből a polinom (a vektor minimális polinomja) együtthatói egyértelműen meghatározhatók. A szokásos esethez teljesen analóg módon (csak és betűkkel helyettesítve) kiküszöbölhetjük (85) és (99) közül, és megkapjuk a következő képletet:

. (100)

4. Maradjunk annak a kérdésnek a tisztázásánál, hogy mely mátrixokra és milyen kezdővektor-választással, vagy mi ugyanaz, milyen kezdeti paraméterek megválasztásával fordul elő a szabályos eset.

Ezt már láthattuk a normál esetben

.

A karakterisztikus polinom és a minimális polinom egybeesése azt jelenti, hogy a mátrixnak nincs két azonos karakterisztikus számú elemi osztója, azaz minden elemi osztó páronkénti koprím. Abban az esetben, ha egy egyszerű szerkezetű mátrix, ez a követelmény egyenértékű azzal a feltétellel, hogy a mátrix karakterisztikus egyenletének nincs több gyöke.

A polinom egybeesése azt jelenti, hogy a vektorként kiválasztott vektor generálja (az operátor segítségével) a teljes teret. A 2. Tétel 2. §-a szerint ilyen vektor mindig létezik.

Ha a feltétel nem teljesül, akkor akárhogyan is választjuk ki a vektort, nem kapunk polinomot, mivel a Krylov-módszerrel kapott polinom osztó, ami a vizsgált esetben nem esik egybe a polinommal, hanem csak az osztója. A vektor változtatásával bármilyen osztót kaphatunk értékként.

A kapott következtetéseket a következő tétel formájában fogalmazhatjuk meg:

14. Tétel. A Krylov-transzformáció akkor és csak akkor ad kifejezést (93) determináns formájában a mátrix karakterisztikus polinomjára, ha két feltétel teljesül:

1. A mátrix elemi osztói páronkénti koprímek.

2. A kezdeti paraméterek annak a vektornak a koordinátái, amely a teljes -dimenziós teret generálja (a mátrixnak megfelelő operátor segítségével).

Általános esetben a Krylov-transzformáció a karakterisztikus polinom egy bizonyos osztójához vezet. Ez az osztó a minimális polinom egy koordinátákkal rendelkező vektorhoz ( – kezdeti paraméterek a Krylov-transzformációban).

5. Megmutatjuk, hogyan lehet megtalálni a sajátvektor koordinátáit bármely karakterisztikus számhoz, amely a Krylov-módszerrel kapott polinom gyöke.

A vektort az alakban fogjuk keresni

Ezt a kifejezést behelyettesítve a vektoregyenlőségbe

és a (101) használatával kapjuk:

Innen egyébként az következik, hogy mivel a (102) szerinti egyenlőség adná lineáris függőség vektorok között . Hiszünk a jövőben. Ekkor a (102)-ből kapjuk:

Ezen egyenlőségek közül az első szekvenciálisan határozza meg számunkra a mennyiségeket (a vektor koordinátáit az „új” bázisban ); az utolsó egyenlőség az előzőek és a reláció következménye .

A vektor koordinátáit az eredeti bázisban a következő képletekkel találhatjuk meg, amelyek a (101)-ből következnek:

(104)

E mátrix alá írunk egy sort a vektor koordinátáiból. Ezeket a számokat tetszőlegesen rendeljük hozzá (egyetlen megkötéssel: ezek közül a számok közül legalább egy különbözik a nullától). A vonal alá írjuk a vonalat, azaz a vektor koordinátáit. A számokat úgy kapjuk meg, hogy egy sort szekvenciálisan megszorozunk egy adott mátrix soraival. Így például, stb. A sor alá írjuk a sort stb. A hozzárendelt sorok mindegyikét a másodiktól kezdve úgy határozzuk meg, hogy az előző sort szekvenciálisan megszorozzuk ennek a mátrixnak a soraival.

Ennek a mátrixnak a sorai fölé írunk egy check total sort

.

Ebben az esetben rendes esetünk van, hiszen

.

A Krilov-determinánsnak megvan a formája

.

Ezt a determinánst kibővítve és -vel csökkentve azt kapjuk, hogy:

Jelöljük a karakterisztikus számnak megfelelő mátrix sajátvektorával. Keressük a számokat a (103) képlet szerint:

, , , .

Az ellenőrzési egyenlőség természetesen teljesül.

A kapott számokat a vektorok oszlopával párhuzamos függőleges oszlopba helyezzük . Oszlopról oszlopra szorozva megkapjuk a vektor első koordinátáját az eredeti bázisban; hasonlóan kapjuk . Keresse meg a vektor koordinátáit (4-es kicsinyítés után). Hasonlóképpen meghatározzuk a karakterisztikus szám sajátvektorának koordinátáit.

, (105)

figyelnie kell az eredményül kapott mátrix rangját, hogy megálljon az első [th from top] sorban, ami az előzőek lineáris kombinációja. A rang meghatározása magában foglalja az ismert determinánsok kiszámítását. Ezen túlmenően, miután megkaptuk a Krilov-determinánst (93) vagy (100) formában, az utolsó oszlop elemeiből való kibontáshoz ki kell számítani ismert számú harmadrendű determinánst [a th normál esetben rendelés].

A Krilov-determináns feltárása helyett az együtthatókat közvetlenül a (91) [vagy (99)] egyenletrendszerből határozhatjuk meg, erre a rendszerre valamilyen hatékony megoldási módszert alkalmazva, például az eliminációs módszert. Ez a módszer közvetlenül alkalmazható a mátrixra

Az elemeket nullára fordítjuk - ennek a mátrixnak az első sora lesz a transzformáció után alakja (és nem az eredeti sor ) ennek a mátrixnak a soraihoz.

Ezután megtaláljuk az űrlapon a th sort

és az előző sorok kivonása után kapjuk:

.

A Krylov-módszer javasolt enyhe módosítása (az eliminációs módszerrel kombinálva) lehetővé teszi, hogy azonnal megkapjuk a minket érdeklő polinomot [normál eset] anélkül, hogy determinánsokat számolnánk és egy segédegyenletrendszert megoldanánk.

A. N. Krylov akadémikus 1931-ben az elsők között javasolta egy meglehetősen kényelmes módszert a determináns feltárására (2).

A. N. Krylov módszerének lényege, hogy a D() determinánst formává alakítja

A D() determináns nullával való egyenlősége szükséges és elégséges állapot azért, hogy homogén rendszer lineáris algebrai egyenletek

nullától eltérő x1, x2, ..., xn megoldása volt.

Alakítsuk át a rendszert (2) a következő módon. Szorozzuk meg az első egyenletet és cseréljük ki az x1,...,xn helyeket a (2) – x1,..., xn kifejezésekkel.

Ezt a folyamatot (n-1) alkalommal megismételve a (2) rendszerről a rendszerre lépünk

amelyek együtthatóit ismétlődő képletek határozzák meg

Nyilvánvalóan az (5) rendszer determinánsának alakja (1) lesz.

Az (5) lineáris algebrai egyenletrendszer minden olyan értékre rendelkezik nullától eltérő megoldással, amely kielégíti a D()=0 egyenletet. Így D1()=0 mindazokra, akik kielégítik a D()=0 egyenletet.

Mutassuk meg

Legyen D() minden gyöke különböző. Mivel a D() minden gyöke a D1() gyöke, ezért D1() osztva D()-vel. Mivel ezen felül a D1() és a D() hatványai azonosak, a hányadosnak állandónak kell lennie. Összehasonlítva az n együtthatóit, azt kapjuk

Ha D()-nek több gyöke van, akkor a (8) egyenlőség igaz marad.

Tekintsük most a D1()-t meghatározó bik együtthatókat. Vezessünk be Bi vektorokat bi1, bi2, …, bin komponensekkel. Egyenlõségek

mutassuk meg, hogy Bi=ABi-1, ahol A az adott mátrixra transzponált mátrix. Ebből következik, hogy

Bi=A i-1B1, B1=AB0, (9)

ahol B0=(1,0,…,0)

Ha C0, akkor a D1()=0 és D()=0 egyenletek ekvivalensek. Ha C = 0, akkor ez a transzformáció nem ad semmit. A.N. Krylov ebben az esetben egy speciális technikát kínál, amelyet alább tárgyalunk. Vegyünk egy tetszőleges B0 = (bi1,bi2,…,bin) vektort B0 vektornak, és használjuk fel a Bi vektorok előállítására a (9) képlet segítségével.

Legyen u=b01x1+b02x2+…+b0nxn (10)

ahol x1,x2,…xn az (1/) rendszer megoldásai. Ezután az előző érvelést megismételve a következőket kapjuk:

Ennek a rendszernek a megoldása lineáris rendszerként homogén egyenletek n+1 u,x1,x2,…xn ismeretlennel azt kapjuk, hogy akkor és csak akkor lehetséges a nullától eltérő megoldás

Az előző érvelést megismételve azt találjuk

ha C10, akkor a karakterisztikus polinom pi együtthatói olyan arányokként vannak definiálva, ahol Di algebrai komplementerek elemek n-i a D() determinánsban.

De Krylov módszerének lényege, hogy megtalálja ezeket az együtthatókat a kiskorúak számítása nélkül.

Használjuk a Hamilton-Cayley tételt, miszerint a mátrix a karakterisztikus egyenletének gyökere, pl.

(A) n+p1(A)n-1+…+pn-1A+pnE=0, (14)

ahol pi a karakterisztikus polinom együtthatói.

A (14) egyenlőséget b0-val megszorozva a következőt kapjuk:

bn+p1bn-1+p2bn-2+…+pn-1b1+pnb0=0 (15)

Ez a vektoregyenlőség egy lineáris algebrai egyenletrendszert ad a karakterisztikus polinom együtthatóinak meghatározására. Ennek a rendszernek a determinánsa egyenlő C1-gyel. A kapott rendszer bármelyikével megoldható ismert módszerek például a Gauss-módszerrel.

Alkalmazhatnánk a Hamilton-Cayley tételt magára az A mátrixra, és akkor megkapnánk a rendszert

сn+p1сn-1+p2сn-2+…+pn-1с1+pnc0=0 (15/)

itt ci=Aic0, c0

Önkényes kezdővektor.

Példa. Legyen az A mátrix alakja:

B0 vektornak vesszük a B0 = (1,0,0,0) vektort. Ezután megkapjuk a vektorokat

B1=AB0, B2=A2B0=AB1, B3=A3B0=AB2, B4=A4B0=AB3:

A karakterisztikus polinom együtthatóinak meghatározására szolgáló lineáris algebrai egyenletrendszer a következő:

Ezt a rendszert megoldva a következőket kapjuk: p1=-11, p2=7, p3=72, p4=-93. Ezért a karakterisztikus polinom a következő formában lesz:

D()= 4 -113 + 72 +72 -93.

A megadott példában C10.

Ha C = 0, egy ilyen rendszer nem teszi lehetővé a karakterisztikus egyenlet együtthatóinak meghatározását. Az A mátrix és a rá transzponált A mátrix kielégíti a sajátjukat karakterisztikus egyenlet D(A)=0. De kiderülhet, hogy vannak n-nél kisebb fokú () polinomok, amelyekre az (A)=(A)=0 egyenlőség is fennáll. Az ilyen polinomok között van egyetlen 1-es vezető együtthatójú polinom, amelynek a legkisebb foka. Ezt a polinomot minimálisnak nevezzük. Ha a mátrix minimális polinomja nem esik egybe a karakterisztikus polinommal, akkor C = 0 a kezdeti vektor bármely választására. Ebben az esetben AC0=0 és a C0, AC0, ..., Аn-1C0 vektorok lineárisan függőek.

A gyakorlatban a Krylov-módszer alkalmazásakor ilyen helyzet csak különleges körülmények között állhat elő.