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}\neq 0$, այդ դեպքում $l_{11}\neq 0$ և $u_{11}\neq 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)\times 1$, $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_{u}^{T},$

$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'-vw^{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'-vw^{T}/a_{11}$:

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

$A'-vw^{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}\neq 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$ չափի մատրիցի համար՝

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

Տես նաև

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