LU-վերլուծություն

**LU-վերլուծություն**՝ A մատրիցի ներկայացումը երկու մատրիցների արտադրյալի տեսքով՝ A=LU, որտեղ L-ը ստորին եռանկյունաձև մատրից է, իսկ U-ն՝ վերին եռանկյունաձև մատրից։

LU-վերլուծությունն օգտագործվում է գծային հանրահաշվական հավասարումների համակարգերի լուծման, մատրիցի հակադարձի և որոշիչի հաշվման համար։ LU-վերլուծություն գոյություն ունի այն և միայն այն դեպքում, եթե A մատրիցը հակադարձելի է, իսկ A մատրիցի բոլոր գլխավոր անկյունային մինորները ոչ զրոյական են։ 
## Կիրառությունը
### Գծային հավասարումների համակարգի լուծում
A (համակարգի գործակիցների մատրից) մատրիցի ստացված LU-վերլուծությունը գծային հավասարումների համակարգի ընտանիքի լուծման համար կարող է օգտագործվել աջ մասի b տարբեր վեկտորներով՝
: Ax=b։
Եթե հայտնի է A մատրիցի LU-վերլուծությունը՝ A=LU, սկզբնական համակարգը կարելի է գրել հետևյալ տեսքով՝
: LUx=b ։
Այս համակարգը կարող է լուծվել երկու քայլով։

Առաջին քայլում լուծվում է հետևյալ համակարգը՝
: Ly=b ։
Քանի որ L-ն ներքևի եռանկյուն մատրիցն է, այս համակարգը լուծվում է անմիջականորեն ուղիղ տեղադրմամբ։

Երկրորդ քայլում լուծվում է հետևյալ համակարգը՝
: Ux=y ։
Քանի որ U-ն վերևի եռանկյուն մատրիցն է, այս համակարգը լուծվում է անմիջականորեն հակադարձ տեղադրմամբ։

### Մատրիցի ձևափոխում
A մատրիցի ձևափոխումը համարժեք է հետևյալ հավասարումների համակարգի լուծմանը՝
: AX=I,
որտեղ X-ը անհայտ մատրից է, իսկ I-ն՝ միավոր մատրից։ Այս համակարգի X լուծումը հանդիսանում է A^{-1} հակադարձ մատրիցը։

Համակարգը կարելի է լուծել վերևում նկարագրված LU-վերլուծության մեթոդով։

### մատրիցի որոշիչի հաշվում
Ունենալով A մատրիցի LU-վերլուծությունը՝
: A=LU,
կարելի է անմիջականորեն հաշվել նրա որոշիչը՝
: \det(A)=\det(LU)=\det(L)\det(U)=\left( \prod_{i=1}^n L_{ii} \right)  \left( \prod_{i=1}^n U_{ii} \right),
որտեղ n-ը A մատրիցի չափն է, L_{ii}-ն և U_{ii}-ն L և U մատրիցների անկյունագծերի էլեմենտներն են։

## Բանաձևի դուրսբերումը
Ելնելով կիրառման ոլորտից LU-վերլուծությունը կարող է կիրառվել միայն ոչհատուկ մատրիցի համար, որի համար մենք հետագայում կընդունենք, որ A մատրիցն ոչհատուկ է։

Քանի որ L մատրիցի և առաջին տողում, և U մատրիցի առաջին սյունում բոլոր էլեմենտները, հնարավոր է բացի առաջինից, հավասար են զրոյի, ունենք՝
: a_{11} = l_{11} u_{11}։
Եթե a_{11} = 0, ապա l_{11} = 0 կամ u_{11} = 0։ Առաջին դեպքում L մատրիցի առաջին տողը ամբողջությամբ կազմված է զրոներից, իսկ երկրորդ դեպքում՝ U մատրիցի առաջին սյունը։ Հետևաբար, L և U մատրիցները ոչհատուկ են, իսկ դա նշանակում է A-ն նույնպես ոչհատուկ է, որը բերում է հակասության։ Այսպիսով, եթե a_{11} = 0, ապա ոչհատուկ A մատրիցը չունի LU-վերլուծություն։

Դիցուկ a_{11} \ne 0, այդ դեպքում l_{11} \ne 0 և u_{11} \ne 0։ Քանի որ L-ը և U-ն որոշված են U-ն հաստատունի վրա բազմապատկման ճշտությամբ և նույն հաստատունի վրա L-ի բաժանման ճշտությամբ, մենք կարող ենք պահանջել, որ l_{11} = 1։ Այդ դեպքում u_{11} = a_{11}։

Բաժանենք A մատրիցը վանդակների՝
:  A = 
\begin{pmatrix}
     a_{11} & w^T \\
     v & A' \\
\end{pmatrix}
,
որտեղ v, w^T, A' ունի համապատասխանաբար (N-1)\times1, 1\times (N-1), (N-1)\times (N-1) չափեր։

Նույն ձևով բաժանենք վանդակների L և U մատրիցները՝
:
L = \begin{pmatrix}
     1 & 0 \\
     v_l & L' \\
\end{pmatrix},\ 
U = \begin{pmatrix}
     a_{11} & w_u^T \\
     0 & U' \\
\end{pmatrix}
:

A=LU հավասարումը կընդունի այսպիսի տեսք՝
:w^T=w^T_u, 
:v=a_{11}v_l, 
:A' = v_l w_u^T + L' U':

Լուծելով հավասարումների համակարգը v_l , w_u , L' , U'  նկատմամբ, կստանանք՝
:w_u = w, 
:v_l = v / a_{11}, 
:L'U' = A' - v w^T / a_{11}:
Վերջնականապես կունենանք՝
:
L = \begin{pmatrix}
     1 & 0 \\
     v/a_{11} & L' \\
\end{pmatrix}
, 
: U = \begin{pmatrix}
     a_{11} & w^T \\
     0 & U' \\
\end{pmatrix}
, 
:L'U' = A' - v w^T / a_{11}:
Այսպիսով, մենք N\times N չափի մատրիցն LU-մասնատմամբ բերեցինք (N-1)\times (N-1) > չափի մատրիցի LU-վերլուծության։

A' - v w^T / a_{11} արտահայտությունը կոչվում է a_{11} էլեմենտի Շուրի լրացում A մատրիցում։

## Ալգորիթմ
LU-վերլուծության հաշվարկի ալգորիթմներից մեկը բերենք ներքևում։

Կօգտագործենք հետևյալ նշանակումները մատրիցի էլեմենտների համար՝ L=(l_{ij}), U=(u_{ij}), i,j = 1\dots n, ընդ որում մատրիցների անկյունագծային էլեմենտներն են՝ L: l_{ii} = 1, i = 1\dots n։ Այդ դեպքում, եթե հայտնի է LU-վերլուծության մատրիցն, նրա որոշիչը կարելի է հաշվել հետևյալ բանաձևով՝
:\det(A) = \det(LU) = \det(L) \det(U) = \det(U) = \prod_{i=1}^n U_{ii}:
 
L և U մատրիցները կարելի է գտնել հետևյալ ձևով (քայլերի կատարման հերթականությունը պետք է պահպանել խստորեն, քանի որ հաջորդ էլեմենտները գտնվում են նախորդների օգտագործմամբ)՝
# u_{1j} = a_{1j},\ j = 1\dots n 
# l_{j1} = \frac {a_{j1}} {u_{11}},\  j = 1\dots n\  (u_{11} \ne 0) 

i = 2\dots n-ի համար՝
# u_{ij} = a_{ij} - \sum_{k=1}^{i-1} l_{ik}u_{kj},\  j = i\dots n 
# l_{ji} = \frac {1} {u_{ii}}(a_{ji} - \sum_{k=1}^{i-1} l_{jk}u_{ki}),\  j = i\dots n 

Արդյունքում մենք կստանանք L և U մատրիցները։

Տվյալ մեթոդի ծրագրային իրականացման ժամանակ (Գաուսի կոմպակտ սխեմա) L և U մատրիցների ներկայացման համար կարելի է բավարարվել միայն մեկ մասիվով, որում L և U մատրիցները համակցվում են։ Այսպես, 3\times 3 չափի մատրիցի համար՝

\begin{pmatrix}
  u_{11} & u_{12} & u_{13} \\
  l_{21} & u_{22} & u_{23} \\
  l_{31} & l_{32} & u_{33} \\
\end{pmatrix}


## Տես նաև
* Գաուս-Զեյդելի մեթոդ
* Կրամերի մեթոդ
* Ռելակսացիայի մեթոդ

## Ծանոթագրություններ

Կատեգորիա:Մաթեմատիկա
Կատեգորիա:Գծային հանրահաշիվ
Կատեգորիա:Թվային մեթոդներ
Կատեգորիա:Մատրից