LU-մասնատում

LU-մասնատում (LU-դեկոմպոզիցիա, LU-ֆակտորիզացիա) - 
  
    
      
        A
      
    
    {\displaystyle A}
   մատրիցի ներկայացումը երկու մատրիցների արտադրյալի տեսքով՝ 
  
    
      
        A
        =
        L
        U
      
    
    {\displaystyle A=LU}
  , որտեղ 
  
    
      
        L
      
    
    {\displaystyle L}
  -ը ներքևի եռանկյուն մատրիցն է, իսկ 
  
    
      
        U
      
    
    {\displaystyle U}
  -ն՝ վերևի եռանկյուն մատրիցը։
LU-մասնատում օգտագործվում է գծային հանրահաշվական հավասարումների համակարգերի լուծման, մատրիցի հակադարձման և որոշիչի հաշվման համար։ LU-մասնատումը գոյություն ունի միայն այն ժամանակ, երբ 
  
    
      
        A
      
    
    {\displaystyle A}
   մատրիցն հակադարձելի է, իսկ 
  
    
      
        A
      
    
    {\displaystyle A}
   մատրիցի բոլոր գլխավոր անկյունագծային մինորները ոչհատուկ են]]։ 


== Կիրառությունը ==


=== Գծային հավասարումների համակարգի լուծում ===

  
    
      
        A
      
    
    {\displaystyle A}
   (համակարգի գործակիցների մատրից) մատրիցի ստացված LU-մասնատումը գծային հավասարումների համակարգի ընտանիքի լուծման համար կարող է օգտագործվել աջ մասի 
  
    
      
        b
      
    
    {\displaystyle b}
   տարբեր վեկտորներով՝

  
    
      
        A
        x
        =
        b
      
    
    {\displaystyle Ax=b}
  ։Եթե հայտնի է 
  
    
      
        A
      
    
    {\displaystyle A}
   մատրիցի LU-մասնատումը՝ 
  
    
      
        A
        =
        L
        U
      
    
    {\displaystyle A=LU}
  , սկզբնական համակարգը կարելի է գրել հետևյալ տեսքով՝

  
    
      
        L
        U
        x
        =
        b
      
    
    {\displaystyle LUx=b}
  ։Այս համակարգը կարող է լուծվել երկու քայլով։
Առաջին քայլում լուծվում է հետևյալ համակարգը՝

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

  
    
      
        U
        x
        =
        y
      
    
    {\displaystyle Ux=y}
  ։Քանի որ 
  
    
      
        U
      
    
    {\displaystyle U}
  -ն վերևի եռանկյուն մատրիցն է, այս համակարգը լուծվում է անմիջականորեն հակադարձ տեղադրմամբ։


=== Մատրիցի ձևափոխում ===

  
    
      
        A
      
    
    {\displaystyle A}
   մատրիցի ձևափոխումը համարժեք է հետևյալ հավասարումների համակարգի լուծմանը՝

  
    
      
        A
        X
        =
        I
      
    
    {\displaystyle AX=I}
  ,որտեղ 
  
    
      
        X
      
    
    {\displaystyle X}
  -ը անհայտ մատրից է, իսկ 
  
    
      
        I
      
    
    {\displaystyle I}
  -ն՝ միավոր մատրից։ Այս համակարգի 
  
    
      
        X
      
    
    {\displaystyle X}
   լուծումը հանդիսանում է 
  
    
      
        
          A
          
            −
            1
          
        
      
    
    {\displaystyle A^{-1}}
   հակադարձ մատրիցը։
Համակարգը կարելի է լուծել վերևում նկարագրված LU-մասնատման մեթոդով։


=== մատրիցի որոշիչի հաշվում ===
Ունենալով 
  
    
      
        A
      
    
    {\displaystyle A}
   մատրիցի LU-մասնատումը՝

  
    
      
        A
        =
        L
        U
      
    
    {\displaystyle A=LU}
  ,կարելի է անմիջականորեն հաշվել նրա որոշիչը՝

  
    
      
        det
        (
        A
        )
        =
        det
        (
        L
        U
        )
        =
        det
        (
        L
        )
        det
        (
        U
        )
        =
        
          (
          
            
              ∏
              
                i
                =
                1
              
              
                n
              
            
            
              L
              
                i
                i
              
            
          
          )
        
        
          (
          
            
              ∏
              
                i
                =
                1
              
              
                n
              
            
            
              U
              
                i
                i
              
            
          
          )
        
      
    
    {\displaystyle \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
      
    
    {\displaystyle n}
  -ը 
  
    
      
        A
      
    
    {\displaystyle A}
   մատրիցի չափն է, 
  
    
      
        
          L
          
            i
            i
          
        
      
    
    {\displaystyle L_{ii}}
  -ն և 
  
    
      
        
          U
          
            i
            i
          
        
      
    
    {\displaystyle U_{ii}}
  -ն 
  
    
      
        L
      
    
    {\displaystyle L}
   և 
  
    
      
        U
      
    
    {\displaystyle U}
   մատրիցների անկյունագծերի էլեմենտներն են։


== Բանաձևի դուրսբերումը ==
Ելնելով կիրառման ոլորտից LU-մասնատումը կարող է կիրառվել միայն ոչհատուկ մատրիցի համար, որի համար մենք հետագայում կընդունենք, որ 
  
    
      
        A
      
    
    {\displaystyle A}
   մատրիցն ոչհատուկ է։
Քանի որ 
  
    
      
        L
      
    
    {\displaystyle L}
   մատրիցի և առաջին տողում, և 
  
    
      
        U
      
    
    {\displaystyle U}
   մատրիցի առաջին սյունում բոլոր էլեմենտները, հնարավոր է բացի առաջինից, հավասար են զրոյի, ունենք՝

  
    
      
        
          a
          
            11
          
        
        =
        
          l
          
            11
          
        
        
          u
          
            11
          
        
      
    
    {\displaystyle a_{11}=l_{11}u_{11}}
  ։Եթե 
  
    
      
        
          a
          
            11
          
        
        =
        0
      
    
    {\displaystyle a_{11}=0}
  , ապա 
  
    
      
        
          l
          
            11
          
        
        =
        0
      
    
    {\displaystyle l_{11}=0}
   կամ 
  
    
      
        
          u
          
            11
          
        
        =
        0
      
    
    {\displaystyle u_{11}=0}
  ։ Առաջին դեպքում 
  
    
      
        L
      
    
    {\displaystyle L}
   մատրիցի առաջին տողը ամբողջությամբ կազմված է զրոներից, իսկ երկրորդ դեպքում՝ 
  
    
      
        U
      
    
    {\displaystyle U}
   մատրիցի առաջին սյունը։ Հետևաբար, 
  
    
      
        L
      
    
    {\displaystyle L}
   և 
  
    
      
        U
      
    
    {\displaystyle U}
   մատրիցները ոչհատուկ են, իսկ դա նշանակում է 
  
    
      
        A
      
    
    {\displaystyle A}
  -ն նույնպես ոչհատուկ է, որը բերում է հակասության։ Այսպիսով, եթե 
  
    
      
        
          a
          
            11
          
        
        =
        0
      
    
    {\displaystyle a_{11}=0}
  , ապա ոչհատուկ 
  
    
      
        A
      
    
    {\displaystyle A}
   մատրիցը չունի LU-մասնատում։
Դիցուկ 
  
    
      
        
          a
          
            11
          
        
        ≠
        0
      
    
    {\displaystyle a_{11}\neq 0}
  , այդ դեպքում 
  
    
      
        
          l
          
            11
          
        
        ≠
        0
      
    
    {\displaystyle l_{11}\neq 0}
   և 
  
    
      
        
          u
          
            11
          
        
        ≠
        0
      
    
    {\displaystyle u_{11}\neq 0}
  ։ Քանի որ 
  
    
      
        L
      
    
    {\displaystyle L}
  -ը և 
  
    
      
        U
      
    
    {\displaystyle U}
  -ն որոշված են 
  
    
      
        U
      
    
    {\displaystyle U}
  -ն հաստատունի վրա բազմապատկման ճշտությամբ և նույն հաստատունի վրա 
  
    
      
        L
      
    
    {\displaystyle L}
  -ի բաժանման ճշտությամբ, մենք կարող ենք պահանջել, որ 
  
    
      
        
          l
          
            11
          
        
        =
        1
      
    
    {\displaystyle l_{11}=1}
  ։ Այդ դեպքում 
  
    
      
        
          u
          
            11
          
        
        =
        
          a
          
            11
          
        
      
    
    {\displaystyle u_{11}=a_{11}}
  ։
Բաժանենք 
  
    
      
        A
      
    
    {\displaystyle A}
   մատրիցը վանդակների՝

  
    
      
        A
        =
        
          
            (
            
              
                
                  
                    a
                    
                      11
                    
                  
                
                
                  
                    w
                    
                      T
                    
                  
                
              
              
                
                  v
                
                
                  
                    A
                    ′
                  
                
              
            
            )
          
        
      
    
    {\displaystyle A={\begin{pmatrix}a_{11}&w^{T}\\v&A'\\\end{pmatrix}}}
  ,որտեղ 
  
    
      
        v
        ,
        
          w
          
            T
          
        
        ,
        
          A
          ′
        
      
    
    {\displaystyle v,w^{T},A'}
   ունի համապատասխանաբար 
  
    
      
        (
        N
        −
        1
        )
        ×
        1
      
    
    {\displaystyle (N-1)\times 1}
  , 
  
    
      
        1
        ×
        (
        N
        −
        1
        )
      
    
    {\displaystyle 1\times (N-1)}
  , 
  
    
      
        (
        N
        −
        1
        )
        ×
        (
        N
        −
        1
        )
      
    
    {\displaystyle (N-1)\times (N-1)}
   չափեր։
Նույն ձևով բաժանենք վանդակների 
  
    
      
        L
      
    
    {\displaystyle L}
   և 
  
    
      
        U
      
    
    {\displaystyle U}
   մատրիցները՝

  
    
      
        L
        =
        
          
            (
            
              
                
                  1
                
                
                  0
                
              
              
                
                  
                    v
                    
                      l
                    
                  
                
                
                  
                    L
                    ′
                  
                
              
            
            )
          
        
        ,
         
        U
        =
        
          
            (
            
              
                
                  
                    a
                    
                      11
                    
                  
                
                
                  
                    w
                    
                      u
                    
                    
                      T
                    
                  
                
              
              
                
                  0
                
                
                  
                    U
                    ′
                  
                
              
            
            )
          
        
        :
      
    
    {\displaystyle L={\begin{pmatrix}1&0\\v_{l}&L'\\\end{pmatrix}},\ U={\begin{pmatrix}a_{11}&w_{u}^{T}\\0&U'\\\end{pmatrix}}:}
  
  
    
      
        A
        =
        L
        U
      
    
    {\displaystyle A=LU}
   հավասարումը կընդունի այսպիսի տեսք՝

  
    
      
        
          w
          
            T
          
        
        =
        
          w
          
            u
          
          
            T
          
        
        ,
      
    
    {\displaystyle w^{T}=w_{u}^{T},}
  

  
    
      
        v
        =
        
          a
          
            11
          
        
        
          v
          
            l
          
        
        ,
      
    
    {\displaystyle v=a_{11}v_{l},}
  

  
    
      
        
          A
          ′
        
        =
        
          v
          
            l
          
        
        
          w
          
            u
          
          
            T
          
        
        +
        
          L
          ′
        
        
          U
          ′
        
      
    
    {\displaystyle A'=v_{l}w_{u}^{T}+L'U'}
  :Լուծելով հավասարումների համակարգը 
  
    
      
        
          v
          
            l
          
        
      
    
    {\displaystyle v_{l}}
  , 
  
    
      
        
          w
          
            u
          
        
      
    
    {\displaystyle w_{u}}
  , 
  
    
      
        
          L
          ′
        
      
    
    {\displaystyle L'}
  , 
  
    
      
        
          U
          ′
        
      
    
    {\displaystyle U'}
   նկատմամբ, կստանանք՝

  
    
      
        
          w
          
            u
          
        
        =
        w
        ,
      
    
    {\displaystyle w_{u}=w,}
  

  
    
      
        
          v
          
            l
          
        
        =
        v
        
          /
        
        
          a
          
            11
          
        
        ,
      
    
    {\displaystyle v_{l}=v/a_{11},}
  

  
    
      
        
          L
          ′
        
        
          U
          ′
        
        =
        
          A
          ′
        
        −
        v
        
          w
          
            T
          
        
        
          /
        
        
          a
          
            11
          
        
      
    
    {\displaystyle L'U'=A'-vw^{T}/a_{11}}
  :Վերջնականապես կունենանք՝

  
    
      
        L
        =
        
          
            (
            
              
                
                  1
                
                
                  0
                
              
              
                
                  v
                  
                    /
                  
                  
                    a
                    
                      11
                    
                  
                
                
                  
                    L
                    ′
                  
                
              
            
            )
          
        
        ,
      
    
    {\displaystyle L={\begin{pmatrix}1&0\\v/a_{11}&L'\\\end{pmatrix}},}
  

  
    
      
        U
        =
        
          
            (
            
              
                
                  
                    a
                    
                      11
                    
                  
                
                
                  
                    w
                    
                      T
                    
                  
                
              
              
                
                  0
                
                
                  
                    U
                    ′
                  
                
              
            
            )
          
        
        ,
      
    
    {\displaystyle U={\begin{pmatrix}a_{11}&w^{T}\\0&U'\\\end{pmatrix}},}
  

  
    
      
        
          L
          ′
        
        
          U
          ′
        
        =
        
          A
          ′
        
        −
        v
        
          w
          
            T
          
        
        
          /
        
        
          a
          
            11
          
        
      
    
    {\displaystyle L'U'=A'-vw^{T}/a_{11}}
  :Այսպիսով, մենք 
  
    
      
        N
        ×
        N
      
    
    {\displaystyle N\times N}
   չափի մատրիցն LU-մասնատմամբ բերեցինք 
  
    
      
        (
        N
        −
        1
        )
        ×
        (
        N
        −
        1
        )
      
    
    {\displaystyle (N-1)\times (N-1)}
   > չափի մատրիցի LU-մասնատման։

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


== Ալգորիթմ ==
LU-մասնատման հաշվարկի ալգորիթմներից մեկը բերենք ներքևում։
Կօգտագործենք հետևյալ նշանակումները մատրիցի էլեմենտների համար՝ 
  
    
      
        L
        =
        (
        
          l
          
            i
            j
          
        
        )
      
    
    {\displaystyle L=(l_{ij})}
  , 
  
    
      
        U
        =
        (
        
          u
          
            i
            j
          
        
        )
      
    
    {\displaystyle U=(u_{ij})}
  , 
  
    
      
        i
        ,
        j
        =
        1
        …
        n
      
    
    {\displaystyle i,j=1\dots n}
  , ընդ որում մատրիցների անկյունագծային էլեմենտներն են՝ 
  
    
      
        L
      
    
    {\displaystyle L}
  : 
  
    
      
        
          l
          
            i
            i
          
        
        =
        1
      
    
    {\displaystyle l_{ii}=1}
  , 
  
    
      
        i
        =
        1
        …
        n
      
    
    {\displaystyle i=1\dots n}
  ։ Այդ դեպքում, եթե հայտնի է LU-մասնատման մատրիցն, նրա որոշիչը կարելի է հաշվել հետևյալ բանաձևով՝

  
    
      
        det
        (
        A
        )
        =
        det
        (
        L
        U
        )
        =
        det
        (
        L
        )
        det
        (
        U
        )
        =
        det
        (
        U
        )
        =
        
          ∏
          
            i
            =
            1
          
          
            n
          
        
        
          U
          
            i
            i
          
        
      
    
    {\displaystyle \det(A)=\det(LU)=\det(L)\det(U)=\det(U)=\prod _{i=1}^{n}U_{ii}}
  :
  
    
      
        L
      
    
    {\displaystyle L}
   և 
  
    
      
        U
      
    
    {\displaystyle U}
   մատրիցները կարելի է գտնել հետևյալ ձևով (քայլերի կատարման հերթականությունը պետք է պահպանել խստորեն, քանի որ հաջորդ էլեմենտները գտնվում են նախորդների օգտագործմամբ)՝

  
    
      
        
          u
          
            1
            j
          
        
        =
        
          a
          
            1
            j
          
        
        ,
         
        j
        =
        1
        …
        n
      
    
    {\displaystyle u_{1j}=a_{1j},\ j=1\dots n}
  

  
    
      
        
          l
          
            j
            1
          
        
        =
        
          
            
              a
              
                j
                1
              
            
            
              u
              
                11
              
            
          
        
        ,
         
        j
        =
        1
        …
        n
         
        (
        
          u
          
            11
          
        
        ≠
        0
        )
      
    
    {\displaystyle l_{j1}={\frac {a_{j1}}{u_{11}}},\ j=1\dots n\ (u_{11}\neq 0)}
  
  
    
      
        i
        =
        2
        …
        n
      
    
    {\displaystyle i=2\dots n}
  -ի համար՝

  
    
      
        
          u
          
            i
            j
          
        
        =
        
          a
          
            i
            j
          
        
        −
        
          ∑
          
            k
            =
            1
          
          
            i
            −
            1
          
        
        
          l
          
            i
            k
          
        
        
          u
          
            k
            j
          
        
        ,
         
        j
        =
        i
        …
        n
      
    
    {\displaystyle u_{ij}=a_{ij}-\sum _{k=1}^{i-1}l_{ik}u_{kj},\ j=i\dots n}
  

  
    
      
        
          l
          
            j
            i
          
        
        =
        
          
            1
            
              u
              
                i
                i
              
            
          
        
        (
        
          a
          
            j
            i
          
        
        −
        
          ∑
          
            k
            =
            1
          
          
            i
            −
            1
          
        
        
          l
          
            j
            k
          
        
        
          u
          
            k
            i
          
        
        )
        ,
         
        j
        =
        i
        …
        n
      
    
    {\displaystyle l_{ji}={\frac {1}{u_{ii}}}(a_{ji}-\sum _{k=1}^{i-1}l_{jk}u_{ki}),\ j=i\dots n}
  Արդյունքում մենք կստանանք 
  
    
      
        L
      
    
    {\displaystyle L}
   և 
  
    
      
        U
      
    
    {\displaystyle U}
   մատրիցները։
Տվյալ մեթոդի ծրագրային իրականացման ժամանակ (Գաուսի կոմպակտ սխեմա) 
  
    
      
        L
      
    
    {\displaystyle L}
   և 
  
    
      
        U
      
    
    {\displaystyle U}
   մատրիցների ներկայացման համար կարելի է բավարարվել միայն մեկ մասիվով, որում 
  
    
      
        L
      
    
    {\displaystyle L}
   և 
  
    
      
        U
      
    
    {\displaystyle U}
   մատրիցները համակցվում են։ Այսպես, 
  
    
      
        3
        ×
        3
      
    
    {\displaystyle 3\times 3}
   չափի մատրիցի համար՝

  
    
      
        
          
            (
            
              
                
                  
                    u
                    
                      11
                    
                  
                
                
                  
                    u
                    
                      12
                    
                  
                
                
                  
                    u
                    
                      13
                    
                  
                
              
              
                
                  
                    l
                    
                      21
                    
                  
                
                
                  
                    u
                    
                      22
                    
                  
                
                
                  
                    u
                    
                      23
                    
                  
                
              
              
                
                  
                    l
                    
                      31
                    
                  
                
                
                  
                    l
                    
                      32
                    
                  
                
                
                  
                    u
                    
                      33
                    
                  
                
              
            
            )
          
        
      
    
    {\displaystyle {\begin{pmatrix}u_{11}&u_{12}&u_{13}\\l_{21}&u_{22}&u_{23}\\l_{31}&l_{32}&u_{33}\\\end{pmatrix}}}
  


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


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