User:Detalse

թվային գծային հանրահաշիվը, Առնոլդի բազմակրկնությունը հանդիսանում է ութվալենտական ​​ալգորիթմ որի կարեւոր օրինակներից է կրկնողական մեթոդը. Առնոլդը գտնում է, որ ութվալենտականությունը գլխավորապես (անհնար է համարվի -հերմետիկ) մատրիցներ; հերմետիկ մատրիցների համար համանման մեթոդ է Լենքզոսի կրկնողականությունը. Առնոլդի կրկնողականությունը հայտնաբերվել է Վ.Է.Առնոլդի կողմից 1951թ.

կրկնողական մեթոդ տերմինը, որն օգտագործվում է նկարագրելու Առնոլդինը, կարող է լինել, թերեւս փոքր - ինչ շփոթեցնող. Նշենք, որ բոլոր գլխավոր ութվալենտական ​​ալգորիթմերը պետք է լինեն կրկնողական. Սա այն չէ ինչը վերաբերվում է երբ մենք ասում ենք Առնոլդինը կրկնողական մեթոդ է. Փոխարենը, Առնոլդինը պատկանում է տվյալ դասի գծային հանրահաշվի ալգորիթմերին (հիմնված Կռիլովի միջակայքերին) որոնք տալիս են մասնակի արդյունք կրկնողականության փոքր թվերի համեմատությունից հետո. Սրանք տարբեր են այսպես կոչված ուղղակի մեթոդները, որոնք պետք է ավարտվեն տալով որեւէ օգտակար արդյունքներ.

Առնոլդի բազմակրկնությունը լայն նոսր փակուղային մատրիցա ալգորիթմ է: Այն ուղղակիորեն չի օգտվում մատրիցայի էլեմենտներից, սակայն մատրիցայի քարտեզի վեկտորների եզրակացությունները ի զորու է դարձնել պատկերներ. Սա շարժառիթ է կառուցելու Կռիլովի միջակայքերը.

Կռիլովի միջակայքերը եւ գլխավոր բազմակրկնությունը

ՈՒթվալենտականության գտնելու մեթոդը (մասնավորապես խոշորագույն ութվալենտականությունը) որպես տվյալ m × m մատրից $A$ հանդիսանում է գլխավոր բազմակրկնություն. Սկսելով նախնական պատահական վեկտոր b, այս մեթոդը հաշվարկում է Ab, A²b, A³b,… բազմակրկնության պահպանման եւ նորմալացման արդյունքը b ամեն հերթին. Այս հաջորդականությունը համնկնում է ութվեկտորի համապատասխան ութվալենտականության հետ, $\lambda _{1}$. Սակայն միայն վերջնական արդյունքը օգտագործելիս հնարավոր է օգտակար հաշվարկը ապարդյուն լինի, $A^{n-1}b$. ենթադրվում է, որ փոխարենը, ձևավորենք այսպես կոչված Կռիլովի մատրիցը:

$K_{n}={\begin{bmatrix}b&Ab&A^{2}b&\cdots &A^{n-1}b\end{bmatrix}}.$

Մատրիցի սյուները օրթոգոնալ չեն,բայց սկզբունքորեն,մենք կարող ենք գտնել օրթոգոնալ հիմքը,մեթոդի միջոցով ինչպիսիք են Gram–Schmidt orthogonalization. արդյունքային վեկտորները հիմք են հանդիսանում Կռիլովի միջակայքերը, ${\mathcal {K}}_{n}$. Մենք կարող ենք ակնկալել, որ վեկտորները այս սկզբունքով են տալիս լավ մոտեցումներ ութվեկտորներին համապատասխանող $n$ խոշորագույն ութվեկտորներ, նույն պատճառով որ $A^{n-1}b$ մոտեցուման գերակշռողը ութվեկտորն է.

Առնոլդի բազմակրկնությունը

Գործընթացը նկարագրված է վերը ինտուիտիվ կերպով. Ցավոք, դա նաեւ անկայուն է. սա այն վայրն է որտեղ մուտք է գործել Առնոլդի բազմակրկնությունը.

Առնոլդի բազմակրկնությունը օգտագործում է կայունացելու Gram–Schmidt գործընթացը արտադրելու օրթնորմալացված վեկտորների հաջորդականությունը , q₁, q₂, q₃, …, որը կոչվում է Առնոլդի վեկտոր, օրինակ, որ ամեն n, վեկտոր q₁, …, q_n ներառում է Կռիլովի միջակայքը ${\mathcal {K}}_{n}$. Հստակ է, որ ալգորիթմը հետեւյալն է:

• Սկսել կամայական q₁ վեկտորից կապնված 1 նորմայից.
• Կրկնել k = 2, 3, համար …
  • $q_{k}\leftarrow Aq_{k-1}\,$
  • j համար 1-ից դեպի k − 1
    • $h_{j,k-1}\leftarrow q_{j}^{*}q_{k}\,$
    • $q_{k}\leftarrow q_{k}-h_{j,k-1}q_{j}\,$
  • $h_{k,k-1}\leftarrow \|q_{k}\|\,$
  • $q_{k}\leftarrow {\frac {q_{k}}{h_{k,k-1}}}\,$

j-հանգույցի ծրագրերը դուրս են  $q_{k}$  բաղադրիչից  $q_{1},\dots ,q_{k-1}$ ուղղություններով.  Սա ապահովում են  բոլոր առաջացած վեկտորների օրթոգենությունը.

Ալգորիթմը խախտվում է երբ q_k զրոյական վեկտոր է. Դա պատահում է, երբ նվազագույն պոլինամինալ A-ի k աստիճանն է. Շատ դիմումների վերաբերյալ Առնոլդի բազմակրկնությունը, այդ թվում ութվալենտական ​​ալգորիթմի ներքեւինը GMRES, ալգորիթմը այս պահին համնկնում է.

k հանգույցի ամեն քայլը  տեւում է մեկ մատրից-վեկտորը ապրանքների եւ մոտ 4mk լողացող միավոր գործողություններ.

Առնոլդի բազմակրկնության Հատկությունները

Նշենք Q_n ենթակետի m-by-n մատրից ձեւավորում առաջին n եթե, եւ միայն եթե Arnoldi բազմակրկնություն չի կոտրել ներքեւ. մատրից q₁, q₂, …, q_n, եւ թող H_n (վերին Hessenberg) մատրից ձեւավորվում է ըստ համարների h_j,k հաշվարկվում է ի ալգորիթմը:

$H_{n}={\begin{bmatrix}h_{1,1}&h_{1,2}&h_{1,3}&\cdots &h_{1,n}\\h_{2,1}&h_{2,2}&h_{2,3}&\cdots &h_{2,n}\\0&h_{3,2}&h_{3,3}&\cdots &h_{3,n}\\\vdots &\ddots &\ddots &\ddots &\vdots \\0&\cdots &0&h_{n,n-1}&h_{n,n}\end{bmatrix}}.$

Ապա մենք ունենք

$H_{n}=Q_{n}^{*}AQ_{n}.\,$

Այս զիջում այլընտրանքային մեկնաբանության է Առնոլդի կրկնողականությունը որպես (մասնակի) orthogonal կրճատման A Hessenberg ձեւով.. մատրիցը H_n կարելի է դիտարկել որպես ներկայացուցչության հենքի վրա ձեւավորված Առնոլդի վեկտորի կողմից օրթոգոնալ նախագծումը A ապա Կռիլովի միջակայքերը ${\mathcal {K}}_{n}$.

մատրից H_n արելի է բնութագրել հետեւյալ պայմանով. The օպտիմալ բնորոշում H_n ||p(A)q₁||₂ ենթակետի monic polynomials of degree n. Այս խնդիրը յուրօրինակ լուծում է եթե, եւ միայն եթե Առնոլդի բազմակրկնություն չի կոտրել ներքեւ.

նա հարաբերությունը միջեւ Q matrices հետագա iterations տրված է

$AQ_{n}=Q_{n+1}{\tilde {H}}_{n}$

where

${\tilde {H}}_{n}={\begin{bmatrix}h_{1,1}&h_{1,2}&h_{1,3}&\cdots &h_{1,n}\\h_{2,1}&h_{2,2}&h_{2,3}&\cdots &h_{2,n}\\0&h_{3,2}&h_{3,3}&\cdots &h_{3,n}\\\vdots &\ddots &\ddots &\ddots &\vdots \\\vdots &&0&h_{n,n-1}&h_{n,n}\\0&\cdots &\cdots &0&h_{n+1,n}\end{bmatrix}}$

is an (n+1)-by-n matrix formed by adding an extra row to H_n.

Category:Numerical linear algebra