Please enable JavaScript.
Coggle requires JavaScript to display documents.
LR TRANSZFORMÁCIÓ - Coggle Diagram
LR TRANSZFORMÁCIÓ
LR Felbontáson alapulva olyan mátrixsorozatot határoz meg amivel meghatározhatók A saját értékei
Az eljárás \(A_1 = A\) ból indul
Lépései:
\(A_k = L_k R_k\)
\(A_{k+1} = R_k L_k\)
A mátrixot felbontjuk egy alsó és egy felső háromszög mátrixra.
A következő iterált mátrixot ezek fordított srrendben vett összeszorzásával kapjuk
SEGÉDTÉTEL:
Legyen
\(T_k = L_1 L_2 ... L_{k-1}\)
és
\(U_k=R_k R_{k-1} ... R_1\)
Ha minden k = 1,2 ... indexre létezik a definiált \(A_k\) mátrix akkor
A mátrix hasonló \(A_k\) hoz
\(A_k = (L_1 L_2 ... L_{k-1})^{-1}*A_1(L_1 L_2 ... L_{k-1})L_k = T^{-1}_{k-1}A_1T_{k-1}\)
\(A^k_1 = T_kU_k\)
BIZONYÍTÁS:
Az 1. állítás adódik a 2. ból. A többire alkalmazzuk a teljes indukciót.
\(L_k\) reguláris, ezért \(A_{k+1} = L^{-1}_k A_k L_k\), az indukciós feltevés miatt :
\( A_{k+1} =L_{k}^{-1}\left(L_{1} L_{2} \cdots L_{k-1}\right)^{-1} A_{1}\left(L_{1} L_{2} \cdots L_{k-1}\right) L_{k} \)
\(=\left(L_{1} L_{2} \cdots L_{k}\right)^{-1} A_{1}\left(L_{1} L_{2} \cdots L_{k}\right) \)
\(=T_{k}^{-1} A_{1} T_{k} \)
Második állítást igazolja k+1 esetre is
Harmadik állítást is hasonlóan igazolhatjuk:
\(A_{1}^{k+1} =A_{1} A_{1}^{k}=A_{1} T_{k} U_{k}=A_{1}\left(L_{1} L_{2} \cdots L_{k}\right)\left(R_{k} R_{k-1} \cdots R_{1}\right) \)
\(=\left(L_{1} L_{2} \cdots L_{k}\right) A_{k+1}\left(R_{k} R_{k-1} \cdots R_{1}\right) \)
\(=\left(L_{1} L_{2} \cdots L_{k}\right) L_{k+1} R_{k+1}\left(R_{k} R_{k-1} \cdots R_{1} \right)=T_{k+1} U_{k+1} \)
LR ALGORITMUS KONVERGENCIA TÉTELE:
Ha A valós négyzetes mátrixra érvényesek ezek a feltételek:
A sajátértékeit alkalmasan indexelve érvényes az
\(|\lambda_1| >|\lambda_2| > \cdots |\lambda_n| >0\)
Megadható A mátrixot diagonáló olyan X mátrix amellyel egyrészt
\(X^{-1} A_1 X = D = diag(\lambda_1, \lambda2 \cdots \lambda_n) \)
Másrészt létezik mind az \(X = \check{L} \check{R}\) és az \( X^{-1} = \check{L} \check{R}\)
Az \(A_k = L_k R_k\) felbontás létezik minden \(k \geq 1\) re
Akkor az \( {A_k} {R_k} és {L_k} \) mátrix sorozatok mind konvergensek
\(\lim _{k \rightarrow \infty} A_{k}=\lim _{k \rightarrow \infty} R_{k}=\left(\begin{array}{cccc} \lambda_{1} & \mathrm{x} & \cdots & \mathrm{x} \\ 0 & \lambda_{2} & \cdots & \mathrm{x} \\ 0 & 0 & \ddots & \vdots \\ 0 & 0 & \cdots & \lambda_{n} \end{array}\right)\)
És \(\lim _{k \rightarrow \infty} L_{k}=I\)
Olyan Mátrixhoz tart ami az \(A_1\) mátrix sajátértékeit tárolja növekvő sorrendben a főátlóban
Az iteráció megállási feltétele lehet az iterált \(A_k\) mátrix főátló alatti elemeinek négyzetösszege kisebb egy tetszőlegesen kicsi \(\epsilon >0\) számnál
LR algoritmus legfőbb hátránya, hogy erős feltételek teljesülése esetén is előfordulhat valamelyik k -ra, hogy az \(A_k\) iterált mátrix nem bontható fel \(L_k R_k\) alakban
LR algoritmus műveletigénye:
Általános mátrixra: \(O(n^3)\)
Felső Hessenberg alakú mátrixra: \(O(n^2)\)
Tridiagonális mátrixra: \(O(n)\)