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=\left(\begin{array}{cc}{a}_{11}& w^T\\ v& A^{\prime }\end{array}\right)$,

որտեղ $v,w^T,A^{\prime }$ ունի համապատասխանաբար $(N-1)\times 1$, $1\times (N-1)$, $(N-1)\times (N-1)$ չափեր։

Նույն ձևով բաժանենք վանդակների $L$ և $U$ մատրիցները՝

$L=\left(\begin{array}{cc}1& 0\\ v_l& L^{\prime }\end{array}\right),U=\left(\begin{array}{cc}{a}_{11}& w_u^T\\ 0& U^{\prime }\end{array}\right):$

$A=LU$ հավասարումը կընդունի այսպիսի տեսք՝

$w^T=w_u^T,$

$v=a_{11}{v}_l,$

$A^{\prime }=v_l{w}_u^T+L^{\prime }{U}^{\prime }$:

Լուծելով հավասարումների համակարգը $v_l$, $w_u$, $L^{\prime }$, $U^{\prime }$ նկատմամբ, կստանանք՝

$w_u=w,$

$v_l=v/a_{11},$

$L^{\prime }{U}^{\prime }=A^{\prime }-v{w}^T/a_{11}$:

Վերջնականապես կունենանք՝

$L=\left(\begin{array}{cc}1& 0\\ v/a_{11}& L^{\prime }\end{array}\right),$

$U=\left(\begin{array}{cc}{a}_{11}& w^T\\ 0& U^{\prime }\end{array}\right),$

$L^{\prime }{U}^{\prime }=A^{\prime }-v{w}^T/a_{11}$:

Այսպիսով, մենք $N\times N$ չափի մատրիցն LU-մասնատմամբ բերեցինք $(N-1)\times (N-1)$ > չափի մատրիցի LU-վերլուծության։

$A^{\prime }-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$ մատրիցները կարելի է գտնել հետևյալ ձևով (քայլերի կատարման հերթականությունը պետք է պահպանել խստորեն, քանի որ հաջորդ էլեմենտները գտնվում են նախորդների օգտագործմամբ)՝

1. $u_{1j}=a_{1j},j=1\dots n$
2. $l_{j1}=\frac{a_{j1}}{u_{11}},j=1\dots n(u_{11}\ne 0)$

$i=2\dots n$-ի համար՝

1. $u_{ij}=a_{ij}-\sum _{k=1}^{i-1}{l}_{ik}{u}_{kj},j=i\dots n$
2. $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$ չափի մատրիցի համար՝

$\left(\begin{array}{ccc}{u}_{11}& u_{12}& u_{13}\\ l_{21}& u_{22}& u_{23}\\ l_{31}& l_{32}& u_{33}\end{array}\right)$

Տես նաև

• Գաուս-Զեյդելի մեթոդ
• Կրամերի մեթոդ
• Ռելակսացիայի մեթոդ