Metoda e eigenvlerave të Krylovit.

1.2 Metoda Krylov

Metoda e Krylovit bazohet në vetinë e një matrice katrore M për të zhdukur polinomin e saj karakteristik. Në këtë punim, matrica M është një matricë e koeficientëve të lidhjes teknologjike, e cila ka formën:

Sipas teoremës Hamilton-Cali, çdo matricë katroreështë rrënja e polinomit të tij karakteristik dhe, për rrjedhojë, e kthen atë në zero. Le të jetë (1.2.1) polinomi karakteristik

Duke zëvendësuar vlerën e λ në shprehje me M, marrim

Duke marrë një vektor arbitrar jozero Y 0 dhe duke shumëzuar të dyja anët e shprehjes (1.2.2) me të, marrim:

Ose në formë

Nëse ky sistem ka e vetmja zgjidhje, atëherë rrënjët e tij p 1, p 2 .....p n janë koeficientë të polinomit karakteristik (1.2.1).

Nëse njihen koeficientët р 1, р 2…..р n, dhe rrënjët λ 1, λ 2,….λ n të polinomit karakteristik, atëherë metoda Krylov bën të mundur gjetjen e vektorëve përkatës duke përdorur formulën e mëposhtme :

Këtu y (n -1), y (n -2), .... y (0) janë vektorët e përdorur për të gjetur koeficientët p 1, p 2 .....p n me metodën Krylov, dhe koeficientët q ij () përcaktohen duke përdorur skemën e Hornerit

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

Për të përcaktuar eigenvlerat matrica M, është e nevojshme të zgjidhet ekuacioni karakteristik që rezulton. Për matricën M, ky ekuacion do të jetë i shkallës së pestë në këtë punë do ta zgjidhim një ekuacion të tillë duke përdorur metodën tangjente ose ndryshe metodën e Njutonit.

1.3 Metoda e Njutonit (metoda tangjente)

Metoda e Njutonit (e njohur edhe si metoda tangjente) është një përsëritëse metodë numerike gjetja e rrënjës (zero) të një funksioni të caktuar. Kërkimi i zgjidhjes kryhet duke ndërtuar përafrime të njëpasnjëshme dhe bazohet në parimet e përsëritjes së thjeshtë. Metoda ka konvergjencë kuadratike. Një përmirësim i metodës është metoda e kordave dhe tangjenteve. Metoda e Njutonit mund të përdoret gjithashtu për të zgjidhur problemet e optimizimit në të cilat është e nevojshme të përcaktohet zeroja e derivatit të parë ose gradientit në rastin. hapësirë ​​shumëdimensionale.

Për të zgjidhur ekuacionin f(x) = 0 në mënyrë numerike duke përdorur metodën e thjeshtë të përsëritjes, ai duhet të reduktohet në formën e mëposhtme: x = f(x), ku f(x) është një pasqyrim i tkurrjes.

Për konvergjencën më të mirë të metodës, kushti duhet të plotësohet në pikën e përafrimit tjetër. Zgjidhje ekuacioni i dhënë kërkoni në formën, pastaj:

Duke supozuar se pika e afrimit është "mjaft afër" me rrënjën, dhe kjo funksioni i dhënëështë e vazhdueshme, formula përfundimtare për është:

(1.3.2)

Duke marrë parasysh këtë, funksioni përcaktohet nga shprehja

(1.3.3)

Ky funksion kryen një hartë kompresive në afërsi të rrënjës dhe algoritmin për gjetjen zgjidhje numerike ekuacioni reduktohet në një procedurë llogaritëse përsëritëse:

(1.3.4)

Sipas teoremës së Banach-ut, sekuenca e përafrimeve priret në rrënjën e ekuacionit.

Figura 1.1- Paraqitja grafike Metoda e Njutonit

Ideja kryesore e metodës është si më poshtë: e dhënë përafrimi fillestar pranë rrënjës hipotetike, pas së cilës në pikën e përafrimit ndërtohet një tangjente me funksionin në studim, për të cilën gjendet kryqëzimi me boshtin e abshisës. Kjo pikë merret si përafrim tjetër. Dhe kështu me radhë derisa të arrihet saktësia e kërkuar.

Përparësitë e metodës së Njutonit:

1) nëse funksioni që minimizohet është kuadratik, atëherë metoda do t'ju lejojë të gjeni minimumin në një hap;

2) nëse funksioni që minimizohet i përket klasës së sipërfaqeve të rrotullimit, atëherë metoda gjithashtu siguron konvergjencë në një hap;

3) nëse funksioni është asimetrik, atëherë metoda nuk siguron konvergjencë në numri përfundimtar hapat. Por për shumë funksione, arrihet një shkallë shumë më e lartë e konvergjencës sesa kur përdoren modifikime të tjera të metodës së zbritjes më të pjerrët.

Përdorimi i metodës Krylov dhe metodës së Njutonit janë dhënë në shtojcat. Metodat u implementuan në mjedisin MathCAD dhe VB.Net.

Zhvillimi dhe kostot materiale. Kështu, qëllimi i dizajnit të diplomës është të zhvillohet paketë softuerike për të simuluar situatën e radarit në një kompjuter personal, duke ju lejuar të simuloni situatën e radarit sipas parametrave të specifikuar, të krijoni një skedar dalës që përmban modelin e llogaritur, të përdorni skedarin që rezulton për të testuar pajisjet reale të përpunimit...

1. Nëse është dhënë një matricë, atëherë ekuacioni i saj karakteristik (sekular) shkruhet në formën

. (81)

Në anën e majtë të këtij ekuacioni është një polinom karakteristik i shkallës. Për të llogaritur drejtpërdrejt koeficientët e këtij polinomi, është e nevojshme të zbulohet përcaktori karakteristik, dhe kjo shoqërohet me një sasi të madhe pune llogaritëse për ato të mëdha, pasi përfshihet në elementët diagonale të përcaktorit.

Akademiku A. N. Krylov në 1937 propozoi një transformim të përcaktuesit karakteristik, si rezultat i të cilit ai hyn vetëm në elementët e një kolone (ose rreshti). Transformimi Krylov thjeshton ndjeshëm llogaritjen e koeficientëve të ekuacionit karakteristik.

Në këtë pjesë do të japim një derivim algjebrik të ekuacionit karakteristik të transformuar, disi të ndryshëm nga derivimi i vetë Krylovit.

Le të paraqesim në konsideratë një hapësirë ​​vektoriale -dimensionale me një bazë dhe një operator linear në , të përcaktuar nga një matricë e dhënë nën këtë bazë. Le të zgjedhim një vektor arbitrar dhe të hartojmë një seri vektorësh

Lërini vektorët e parë të kësaj serie janë linearisht të pavarur, dhe vektori i th është një kombinim linear i këtyre vektorëve:

Të gjithë vektorët e mëtejshëm të serisë (82) shprehen gjithashtu në mënyrë lineare përmes vektorëve të parë të kësaj serie. Kështu, në serinë (82) ka një lineare vektorë të pavarur, dhe ky numër maksimal i vektorëve linearisht të pavarur të serisë (82) mund të realizohet gjithmonë në vektorët e parë të serisë.

Një polinom është një polinom minimal (anulues) i një vektori në lidhje me një operator (shih § 1). Metoda e A. N. Krylov është një metodë përcaktim efektiv polinomi vektorial minimal.

Ne do të shqyrtojmë dy raste veç e veç: rastin e rregullt, kur , dhe rastin e veçantë, kur .

Një polinom është një pjesëtues i polinomit minimal të të gjithë hapësirës, ​​dhe nga ana tjetër është një pjesëtues i polinomit karakteristik. Prandaj është gjithmonë pjesëtues.

Në rastin e rregullt, dhe kanë të njëjtën shkallë, dhe meqenëse koeficientët kryesorë të tyre janë të barabartë, këto polinome përkojnë. Kështu, në rastin e rregullt

,

prandaj metoda e Krylovit në rastin e rregullt është metodë për llogaritjen e koeficientëve të polinomit karakteristik.

NË rast i veçantë, siç do të shohim më poshtë, metoda e Krylovit nuk bën të mundur përcaktimin dhe në këtë rast përcakton vetëm polinomin që është pjesëtues.

Kur paraqesim transformimin e Krylovit, ne do t'i shënojmë koordinatat e vektorit në një bazë të caktuar me , dhe koordinatat e vektorit me .

2. Rasti i rregullt: . Në këtë rast, vektorët janë linearisht të pavarur dhe barazitë (83), (84), (85) marrin formën

Kushti për pavarësinë e zambakut të vektorëve mund të shkruhet në mënyrë analitike si më poshtë (shih Kapitullin III, § 1):

. (89)

Konsideroni një matricë të përbërë nga koordinata vektoriale:

. (90)

Në rastin e rregullt, grada e kësaj matrice është e barabartë me . Rreshtat e parë të kësaj matrice janë linearisht të pavarura, dhe rreshti i fundit, i, është një kombinim linear i atyre të mëparshme.

Ne marrim varësinë midis rreshtave të matricës (90) duke zëvendësuar barazinë vektoriale (86) me një sistem ekuivalent barazish skalare

(91)

Nga ky sistem ekuacionesh lineare ne mund të përcaktojmë në mënyrë unike koeficientët e kërkuar dhe t'i zëvendësojmë vlerat që rezultojnë në (88). Ky përjashtim nga (88) dhe (91) mund të kryhet në një formë simetrike. Për ta bërë këtë, ne rishkruajmë (88) dhe (91) si më poshtë:

Meqenëse ky sistem ekuacionesh me të panjohura ka një zgjidhje jo zero, përcaktorja e këtij sistemi duhet të jetë e barabartë me zero:

. (92)

Nga këtu ne përcaktojmë , pasi kemi transpozuar më parë përcaktorin (92) në lidhje me diagonalen kryesore:

, (93)

ku faktori konstant përcaktohet me formulën (89) dhe është i ndryshëm nga zero.

Identiteti (93) është transformimi i Krylovit. Në përcaktorin Krylov, i cili është në anën e djathtë të këtij identiteti, ai përfshihet vetëm në elementet e kolonës së fundit; elementet e mbetur të këtij përcaktori nuk varen nga.

Komentoni. Në rastin e rregullt, e gjithë hapësira është ciklike (në lidhje me operatorin). Nëse zgjedhim vektorët si bazë, atëherë në këtë bazë operatori korrespondon me një matricë që ka një formë normale natyrore

. (94)

Kalimi nga baza kryesore në bazë kryhet duke përdorur një matricë transformimi jo të veçantë

. (95)

3. Rast i veçantë: . Në këtë rast, vektorët janë të varur linearisht, dhe për këtë arsye

.

Barazia (93) u nxor nën kushtin . Por të dyja anët e kësaj barazie janë të plota funksionet racionale nga dhe parametrat. Prandaj, "nga konsideratat e vazhdimësisë" rrjedh se barazia (93) vlen edhe për . Por atëherë në përcaktuesin Krylov (93), pas zgjerimit të tij, të gjithë koeficientët do të jenë të barabartë me zero. Kështu, në një rast të veçantë, formula (93) bëhet identiteti i parëndësishëm.

Konsideroni një matricë të përbërë nga koordinata vektoriale

. (97)

Kjo matricë ka një renditje dhe rreshtat e parë në të janë linearisht të pavarur, rreshti i fundit është një kombinim linear i rreshtave të parë me koeficientë [cm. (83)]. Nga koordinatat mund të zgjedhim koordinata të tilla që përcaktorja e përbërë nga këto koordinata vektoriale , ishte ndryshe nga zero:

. (98)

(99)

Nga ky sistem ekuacionesh përcaktohen në mënyrë unike koeficientët e polinomit (polinomi minimal i vektorit). Në mënyrë krejt analoge me rastin e rregullt (vetëm me shkronjat e zëvendësuara me dhe ) mund të eliminojmë nga (85) dhe (99) dhe të marrim formulën e mëposhtme për:

. (100)

4. Le të ndalemi në sqarimin e pyetjes për cilat matrica dhe me çfarë zgjedhje të vektorit fillestar ose, çfarë është e njëjtë, me çfarë zgjedhje të parametrave fillestarë ndodh rasti i rregullt.

Këtë e kemi parë tashmë në rastin e rregullt

.

Koincidenca e polinomit karakteristik me polinomin minimal do të thotë që matrica nuk ka dy pjesëtues elementarë me të njëjtin numër karakteristik, d.m.th., të gjithë pjesëtuesit elementar janë dyfish të dyfishtë. Në rastin kur është një matricë me strukturë të thjeshtë, kjo kërkesë është ekuivalente me kushtin që ekuacioni karakteristik i matricës të mos ketë rrënjë të shumta.

Koincidenca e polinomit me do të thotë se vektori i zgjedhur si vektor është ai që gjeneron (duke përdorur operatorin) të gjithë hapësirën. Sipas Teoremës 2 § 2, një vektor i tillë ekziston gjithmonë.

Nëse kushti nuk plotësohet, atëherë sido që ta zgjedhim vektorin, nuk do të fitojmë polinom, pasi polinomi i marrë me metodën Krylov është pjesëtues, i cili në rastin në shqyrtim nuk përkon me polinomin, por është vetëm pjesëtuesin e saj. Duke ndryshuar vektorin, ne mund të marrim çdo pjesëtues si vlerë.

Konkluzionet e marra mund t'i formulojmë në formën e teoremës së mëposhtme:

Teorema 14. Transformimi i Krylovit jep një shprehje për polinomin karakteristik të matricës në formën e përcaktorit (93) nëse dhe vetëm nëse plotësohen dy kushte:

1. Pjesëtuesit elementarë të një matrice janë dyshe të dyfishta.

2. Parametrat fillestarë janë koordinatat e vektorit që gjeneron (duke përdorur operatorin që i përgjigjet matricës) të gjithë hapësirën -dimensionale.

Në rastin e përgjithshëm, transformimi Krylov çon në një pjesëtues të caktuar të polinomit karakteristik. Ky pjesëtues është polinomi minimal për një vektor me koordinata ( – parametrat fillestarë në transformimin Krylov).

5. Do të tregojmë se si të gjejmë koordinatat e vektorit vetjak për çdo numër karakteristik, i cili është rrënja e polinomit të përftuar me metodën e Krylovit.

Ne do të kërkojmë vektorin në formë

Zëvendësimi i kësaj shprehjeje në barazinë vektoriale

dhe duke përdorur (101) marrim:

Nga këtu, meqë ra fjala, rrjedh se, pasi barazia në bazë të (102) do të jepte varësia lineare ndërmjet vektorëve . Në të ardhmen ne besojmë. Pastaj nga (102) marrim:

E para prej këtyre barazive përcakton për ne në mënyrë sekuenciale sasitë (koordinatat e vektorit në bazën "e re" ); barazia e fundit është pasojë e të mëparshmeve dhe nga relacioni .

Koordinatat e vektorit në bazën origjinale mund të gjenden duke përdorur formulat e mëposhtme, të cilat vijojnë nga (101):

(104)

Nën këtë matricë shkruajmë një vijë nga koordinatat e vektorit. Ne i caktojmë këta numra në mënyrë arbitrare (me vetëm një kufizim: të paktën njëri prej këtyre numrave është i ndryshëm nga zero). Nën rreshtin shkruajmë vijën, pra koordinatat e vektorit. Numrat fitohen duke shumëzuar në mënyrë sekuenciale një rresht me rreshtat e një matrice të caktuar. Kështu, për shembull, etj. Nën rreshtin shkruajmë rreshtin, etj. Secili prej rreshtave të caktuar, duke filluar nga i dyti, përcaktohet duke shumëzuar në mënyrë sekuenciale rreshtin e mëparshëm me rreshtat e kësaj matrice.

Mbi rreshtat e kësaj matrice shkruajmë një rresht total kontrolli

.

Në këtë rast kemi një rast të rregullt, pasi

.

Përcaktorja Krylov ka formën

.

Duke e zgjeruar këtë përcaktor dhe duke e zvogëluar me , gjejmë:

Le të shënojmë me vetvektorin e matricës që i korrespondon numrit karakteristik. Le të gjejmë numrat sipas formulave (103):

, , , .

Barazia e kontrollit, natyrisht, është e kënaqur.

Ne vendosim numrat që rezultojnë në një kolonë vertikale paralele me kolonën e vektorëve . Duke shumëzuar kolonën për kolonë, marrim koordinatën e parë të vektorit në bazën origjinale; në mënyrë të ngjashme marrim. Gjeni koordinatat (pas reduktimit me 4) të vektorit. Në mënyrë të ngjashme, ne përcaktojmë koordinatat e vektorit vetjak për numrin karakteristik.

, (105)

ju duhet të monitoroni rangun e matricës që rezulton në mënyrë që të ndaleni në rreshtin e parë [të nga lart], i cili është një kombinim linear i atyre të mëparshme. Përcaktimi i renditjes përfshin llogaritjen e përcaktuesve të njohur. Për më tepër, pasi të keni marrë përcaktorin Krylov në formën (93) ose (100), për ta zgjeruar atë nga elementët e kolonës së fundit, duhet llogaritur një numër i njohur përcaktorësh të rendit të th [në rastin e rregullt të th porosi].

Në vend që të zbulohet përcaktori Krylov, mund të përcaktohen koeficientët drejtpërdrejt nga sistemi i ekuacioneve (91) [ose (99)], duke aplikuar në këtë sistem një metodë efektive zgjidhjeje, për shembull, metodën e eliminimit. Kjo metodë mund të aplikohet drejtpërdrejt në matricë

Ne i kthejmë elementet në zero - rreshti i parë i kësaj matrice pas transformimit do të ketë formën (dhe jo rreshtin origjinal ) në rreshtat e kësaj matrice.

Pastaj do të gjejmë rreshtin e th në formë

dhe pasi zbresim rreshtat e mëparshëm marrim:

.

Modifikimi ynë i lehtë i rekomanduar i metodës Krylov (duke e kombinuar atë me metodën e eliminimit) na lejon të marrim menjëherë polinomin që na intereson [rasti i rregullt] pa llogaritur ndonjë përcaktues dhe pa zgjidhur një sistem ndihmës ekuacionesh.

Akademiku A.N. Krylov në 1931 ishte një nga të parët që propozoi një metodë mjaft të përshtatshme për zbulimin e përcaktuesit (2).

Thelbi i metodës së A.N. Krylov është shndërrimi i përcaktorit D() në formë

Barazia e përcaktorit D() me zero është e nevojshme dhe gjendje e mjaftueshme në mënyrë që të sistem homogjen lineare ekuacionet algjebrike

kishte një zgjidhje x1, x2, ..., xn, të ndryshme nga zero.

Le të transformojmë sistemin (2) si më poshtë. Le të shumëzojmë ekuacionin e parë me dhe të zëvendësojmë x1,...,xn me shprehjet e tyre (2) deri në x1,..., xn.

Duke e përsëritur këtë proces (n-1) herë, ne do të kalojmë nga sistemi (2) në sistem

koeficientët e të cilave do të përcaktohen me formula të përsëritura

Natyrisht, përcaktorja e sistemit (5) do të ketë formën (1).

Sistemi i ekuacioneve algjebrike lineare (5) ka një zgjidhje jo zero për të gjitha vlerat që plotësojnë ekuacionin D()=0. Kështu, D1()=0 për të gjithë që plotësojnë ekuacionin D()=0.

Le ta tregojmë atë

Le të jenë të gjitha rrënjët e D() të ndryshme. Meqenëse të gjitha rrënjët e D() janë rrënjë të D1(), atëherë D1() ndahet me D(). Meqenëse, përveç kësaj, fuqitë e D1 () dhe D () janë të njëjta, herësi duhet të jetë konstant. Duke krahasuar koeficientët për n, marrim

Nëse D() ka shumë rrënjë, barazia (8) mbetet e vërtetë.

Le të shqyrtojmë tani koeficientët bik që përcaktojnë D1(). Le të prezantojmë vektorët Bi me komponentët bi1, bi2, …, bin. Barazitë

tregojnë se Bi=ABi-1, ku A është matrica e transpozuar në atë të dhënë. Nga kjo rezulton se

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

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

Nëse C0, atëherë ekuacionet D1()=0 dhe D()=0 janë ekuivalente. Nëse C = 0, atëherë ky transformim nuk jep asgjë. A.N. Krylov ofron një teknikë të veçantë në këtë rast, të diskutuar më poshtë. Le të marrim një vektor arbitrar B0 = (bi1,bi2,…,bin) si vektor B0 dhe ta përdorim për të marrë vektorët Bi duke përdorur formulat (9).

Le të u=b01x1+b02x2+…+b0nxn (10)

ku x1,x2,...xn janë zgjidhje të sistemit (1/). Pastaj, duke përsëritur arsyetimin e mëparshëm, marrim:

Zgjidhja e këtij sistemi si sistem linear ekuacionet homogjene me n+1 të panjohura u,x1,x2,...xn, marrim se një zgjidhje jo zero është e mundur nëse dhe vetëm nëse

Duke përsëritur arsyetimin e mëparshëm, konstatojmë se

nëse C10, atëherë koeficientët pi të polinomit karakteristik përcaktohen si raportet ku Di janë plotësues algjebrikë elementet n-i në përcaktorin D().

Por thelbi i metodës së Krylovit është gjetja e këtyre koeficientëve pa numëruar të miturit.

Le të përdorim teoremën Hamilton-Cayley se një matricë është rrënja e ekuacionit të saj karakteristik, d.m.th.

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

ku pi janë koeficientët e polinomit karakteristik.

Duke shumëzuar barazinë (14) me b0, marrim:

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

Kjo barazi vektoriale jep një sistem ekuacionesh algjebrike lineare për përcaktimin e koeficientëve të polinomit karakteristik. Përcaktori i këtij sistemi është i barabartë me C1. Sistemi që rezulton mund të zgjidhet nga cilido prej metodat e njohura, për shembull, me metodën Gaussian.

Do të ishte e mundur të zbatohej teorema Hamilton-Cayley për vetë matricën A, dhe më pas do të merrnim sistemin

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

këtu ci=Aic0, c0

Vektor fillestar arbitrar.

Shembull. Le të ketë matricën A formën:

si vektor B0 marrim vektorin B0 = (1,0,0,0). Pastaj marrim vektorët

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

Sistemi i ekuacioneve algjebrike lineare për përcaktimin e koeficientëve të polinomit karakteristik ka formën:

Pasi e kemi zgjidhur këtë sistem, marrim: p1=-11, p2=7, p3=72, p4=-93. Prandaj, polinomi karakteristik do të marrë formën:

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

Në shembullin e dhënë, C10.

Nëse C = 0, një sistem i tillë nuk do të bëjë të mundur përcaktimin e koeficientëve të ekuacionit karakteristik. Matrica A dhe matrica A e transpozuar në të përmbushin të tyren ekuacioni karakteristik D(A)=0. Por mund të rezultojë se ka polinome () me shkallë më të vogël se n, për të cilët vlen edhe barazia (A)=(A)=0. Midis polinomeve të tillë, ekziston një polinom i vetëm me koeficient kryesor 1, i cili ka shkallën më të vogël. Ky polinom quhet minimal. Nëse polinomi minimal i matricës nuk përkon me polinomin karakteristik, atëherë C = 0 për çdo zgjedhje të vektorit fillestar. Në këtë rast, AC0=0 dhe vektorët C0, AC0, ..., Аn-1C0 janë të varur në mënyrë lineare.

Në praktikë, kur përdorni metodën Krylov, një situatë e tillë mund të lindë vetëm në rrethana të veçanta.