LU декомпозиција

Из Википедије, слободне енциклопедије

У линеарној алгебри, LU декомпозиција или LU факторизација (од енглеских речи lower - доње и upper - горње) је декомпозиција матрице која записује матрицу као производ доње троугаоне и горње троугаоне матрице. Производ некада укључује и пермутациону матрицу. Ова декомпозиција се користи у нумеричкој анализи да се реши систем линеарних једначина или да се израчуна детерминанта матрице. LU декомпозиција семоже сматрати и као матрични облик Гаусове елиминације. LU декомпозицију је увео Алан Тјуринг.[1]

Дефиниција[уреди]

Нека је A квадратна матрица. LU декомпозиција је разлагање облика

 A = LU, \,

где су L и U доње и горње троугаоне матрице истих димензија. То значи да L има нуле само изнад главне дијагонале, док U има нуле испод главне дијагонале. За матрицу 3 \times 3 , ово постаје:


        \begin{bmatrix}
           a_{11} & a_{12} & a_{13} \\
           a_{21} & a_{22} & a_{23} \\
           a_{31} & a_{32} & a_{33} \\
        \end{bmatrix} =
      \begin{bmatrix}
           l_{11} & 0 & 0 \\
           l_{21} & l_{22} & 0 \\
           l_{31} & l_{32} & l_{33} \\
        \end{bmatrix}
        \begin{bmatrix}
           u_{11} & u_{12} & u_{13} \\
           0 & u_{22} & u_{23} \\
           0 & 0 & u_{33} \\
        \end{bmatrix}.
LDU декомпозиција Волшове матрице

LDU декомпозиција је декомпозиција облика

 A = LDU, \,

где је D дијагонална матрица а L и U су јединичне троугаоне матрице, што значи да су све вредности на главним дијагоналама L и U једнаке јединици.

LUP декомпозиција (такође се назива LU декомпозиција са парцијалним пивотирањем) је декомпозиција облика

 PA = LU, \,

где су L и U опет доње и горње троугаоне матрице, а P је пермутациона матрица, тј, матрица од нула и јединица где се налази тачно једна јединица у свакој врсти и колони.

LU декомпозиција са потпуним пивотирањем је облика

 PAQ = LU, \,

Горе је претпостављено да је A квадратна матрица, али ове декомпозиције се могу генерализовати и на правоугаоне матрице. У том случају, L и P су квадратне матрице које имају исти број врста као и A, док је U истог облика као A. Горња троугаона форма се интерпетира као постојање нултих елемената испод главне дијагонале, која почиње у горњем левом углу.

Постојање и јединственост[уреди]

Регуларна матрица дозвољава LU факторизацију ако и само ако су сви њени водећи главни минори различити од нуле. Факторизација је јединствена ако захтевамо да се дијагонале од L (или U) састоје од јединица. Матрица има јединствену LDU факторизацију под истим условима.

Ако је матрица сингуларна, LU факторизација може опет постојати. Заправо, квадратна матрица ранга k има LU факторизацију ако је k главних водећих минора различит од нуле, мада не важи обрнуто.

Довољни и потребни услови под којима нека не обавезно регуларна матрица над неким пољем има LU су познати. Ови услови су изражени преко ранга одређених подматрица. Гаусов елиминациони алгоритам за добијање LU факторизације је такође проширен на овај најопштији случајOkunev & Johnson 1997.

Свака регуларна матрица дозвољава LUP факторизацију.

Позитивно дефинитне матрице[уреди]

Ако је матрица A самоајдунгована и позитивно-дефинититна, онда можемо да организовати ствари тако да је U конјуговани транспонент од L. У том случају, можемо написати A као

 A = L L^{*}. \,

Ова декомпозиција се назива метод Холеског. Метод Холеског увек постоји и јединствен је. Даље, рачунањем метода Холекског је ефикасније и нумерички стабилније од рачунања неких других LU декомпозиција.

Експлицитна формулација[уреди]

Када постоји LDU факторизација и када је она јединствена, тада постоји затоврена (експлицинта формула) за елементе матрица L, D, и U у виду количника детерминанти одређених подматрица оригиналне матрице A (Householder 1975). На пример, D_1 = A_{1,1} и за i = 2, \ldots, n, D_i је количник i-те главне подматрице и (i-1)-те главне подматрице.

Алгоритми[уреди]

LU декомпозиција је у основи модификовани облик Гаусове елиминације. Матрица A се трансформише у горњу троугаону матрицу U елиминисањем вредности испод главне дијагонале. Дулитлов алгоритам врши елиминацију колоне по колоне, идући са лева, множењем A са леве стране атомском доњем троугаоном матрицом. Резултат овога је јединична доња троугаона матрица и горња троугаона матрица. Крутов алгоритам је мало другачији и даје доњу троугаону матрицу и јединичну горњу троугаону матрицу.

Рачунање LU факторизације коришћењем било ког од ова два алгоритма захтева 2n3 / 3 операција са покретним зарезом, ако се игноришу чланови нижег реда. Парцијално пивотирање додаје само квадратни члан; ово није случај код пуног пивотирања.[2]

Дулитлов алгоритам[уреди]

Ако имамо матрицу димензија N × N


A= (a_{n,n})

дефинишемо почетно стање

 A^{(0)} := A

и затим следи n итерација (n = 1,...,N-1).

Елементи матрице испод главне дијагонале у n-ој колони од A(n-1) се елиминишу сабирањем i-те врсте ове матрице помножене са

l_{i,n} := -\frac{a_{i,n}^{(n-1)}}{a_{n,n}^{(n-1)}}

за i = n+1,\ldots,N. Ово се може урадити множењем A(n-1) са доњом троугаоном матрицом


L_n =
\begin{pmatrix}
     1 &        &           &         &         & 0 \\
       & \ddots &           &         &         &   \\
       &        &         1 &         &         &   \\
       &        & l_{n+1,n} &  \ddots &         &   \\
       &        &    \vdots &         &  \ddots &   \\
     0 &        &   l_{N,n} &         &         & 1 \\
\end{pmatrix}.

Одређујемо

 A^{(n)} := L_n A^{(n-1)}.

После N-1 корака, елиминисани су сви елементи матрице испод главне дијагонале, па се добија горња троугаона матрица A(N-1). Добија се факторизација


A = L_{1}^{-1} L_{1} A^{(0)}
= L_{1}^{-1} A^{(1)} = L_{1}^{-1} L_{2}^{-1} L_{2} A^{(1)} = 
L_{1}^{-1}L_{2}^{-1} A^{(2)} =\ldots = L_{1}^{-1} \ldots L_{N-1}^{-1} A^{(N-1)}.

Ако се горња троугаона матрица A(N-1) означи са U, и L=L_{1}^{-1} \ldots L_{N-1}^{-1}. Пошто је инверзна вредност доње троугаоне матрице Ln опет доња троугаона матрица, а производ две доње троугаоне матрице је опет доња троугаона матрица, добија се да је L такође доња троугана матрица. Штавише, може се видети да је


L =
\begin{pmatrix}
       1 &        &            &        &            & 0 \\
-l_{2,1} & \ddots &            &        &            &   \\
         &        &          1 &        &            &   \\
  \vdots &        & -l_{n+1,n} & \ddots &            &   \\
         &        &     \vdots &        &       1    &   \\
-l_{N,1} &        & -l_{N,n}   &        & -l_{N,N-1} & 1 \\
\end{pmatrix}.

Добијамо A=LU.

Јасно је да би овај алгоритам правилно радио, потребно је имати a_{n,n}^{(n-1)}\not=0 у сваком кораку (погледати дефиницију l_{i,n}). Ако овај услов није задовољен у неком тренутку, само је потребно заменити n-ту врсту са другом врстом испод ње пре него што алгоритам настави даље. То је разлог зашто LU декомпозиција у општем случају пише као P^{-1}A = L U .

Крутов и LUP алгоритми[уреди]

LUP факторизациони алгоритам уопштава Крутову декомпозицију матрице. Може се описати у следећим корацима.

  1. Ако A има ненулти елемент у својој првој врсти, онда узети пермутациону матрицу P_1 тако да A P_1 има ненулти елемент у свом горњем левом углу. У супротном случају, за P_1 се узима јединична матрица. Нека је A_1 = A P_1.
  2. Нека је A_2 матрица која се добија од матрице A_1 брисањем прве врсте и прве колоне. Факторизовати A_2 = L_2 U_2 P_2 рекурзивно. Добити L од L_2 прво додавањем нултог реда горе, а затим додавањем прве колоне A_1 слева.
  3. Добити U_3 од U_2 прво додавањем нултог реда горе и нулте колоне са лева, а затим заменом горње леве вредности (која је једнака 0 у овом тренутку) јединицом. Добити P_3 од P_2 на сличан начин и дефинисати A_3 = A_1 / P_3 = A P_1 / P_3. Нека је P инверзна матрица P_1 / P_3.
  4. У овом тренутку, A_3 је исто као и L U_3, осим (можда) у првој врсти. Ако је прва врста A једнака нули, онда A_3 =  L U_3, пошто обе имају нулту прву колону, а A = L U_3 P следо, као жељено. У супротном случају, A_3 и L U_3 имају исте ненулте вредности у горњем левом углу, и A_3 = L U_3 U_1 за неку горње-троугаону квадратну матрицу U_1 са јединицама на дијагонали (U_1 брише елементе L U_3 и додаје елементе A_3 помоћу горњег левог угла). Сада је A = L U_3 U_1 P декомпозиција жељеног облика.

Теоријска сложеност[уреди]

Ако се две матрице реда n могу помножити за време M(n), где је M(n)≥na за неко a>2, онда се LU декомпозиција може израчунати за време O(M(n)).[3] Ово на пример значи да O(n2.376) алгоритам постоји заснован на Коперсмит-Виноградовом алгоритму.

Пример[уреди]


        \begin{bmatrix}
           4 & 3 \\
           6 & 3 \\
        \end{bmatrix} =
      \begin{bmatrix}
           l_{11} & 0 \\
           l_{21} & l_{22} \\
        \end{bmatrix}
        \begin{bmatrix}
           u_{11} & u_{12} \\
           0 & u_{22} \\
        \end{bmatrix}.

Један начин за проналажење LU факторизације ове просте матрице је да се просто инспекцијом реше линеарне једначине. Из операције множења матрица добија се:

l_{11} \cdot u_{11} + 0 \cdot 0 = 4
l_{11} \cdot u_{12} + 0 \cdot u_{22} = 3
l_{21}\cdot u_{11} + l_{22} \cdot 0 = 6
l_{21}\cdot u_{12} + l_{22} \cdot u_{22} = 3.

Такав систем једначина је неодређен. У овом случају било који од два ненулта елемента матрица L и U су параметри решења и могу се произвољно поставити на неку ненулту вредност. Стога, да би нашли јединствену LU факторизацију, неопходно је да се поставе нека ограничења на матрице L и U. На пример, можемо захтевати да је доња троугаона матрица L јединична (има све јединице на главној дијагонали). Онда систем једначина има следећа решења:

l_{21} = 1.5
u_{11} = 4
u_{12} = 3
u_{22} = -1.5.

Заменов ових вередности у LU декомпозицију изнад добијамо:


        \begin{bmatrix}
           4 & 3 \\
           6 & 3 \\
        \end{bmatrix} =
      \begin{bmatrix}
           1 & 0 \\
           1.5 & 1 \\
        \end{bmatrix}
        \begin{bmatrix}
           4 & 3 \\
           0 & -1.5 \\
        \end{bmatrix}.

Факторизација ретких матрица[уреди]

Развијени су специјални алгоритми за факторизацију великих ретких матрица. Ови алгоритми покушавају да пронађу ретке факторе L и U. У идеалном случају, цена њиховог израчунавања (меморијамемориско заузеће и број операција) је одређен бројем ненултих елемената, а не величином матрице.

Ови алгоритми користе слободу замене врста и колона да минимализују генерисање ненултих елемената на месту нултих током извршавања алгоритма.

Уопштени поступак ређања који смањује генерисање ненултих елемената се моће одредити коришћењем теорије графова.

Примене[уреди]

Решавање система линеарних једначина[уреди]

Имајући у виду матричну једначину

A x = L U x = b \,

желимо да одредимо x за одређено A и b. У овом случају решење ће бити одређено у два логичка корака:

  1. прво је потребно решити једначину  Ly = b за y
  2. друго, потребно је решити једначину  Ux = y за x.

Приметити да у оба случаја постоје троугаоне матрице (доња и горња) које се могу решити директном користећи замене унапред и уназад бет коришћења Гаусове елиминације (ипак, Гаусова елиминације или неки њен еквивалент је потребан да се израчуна сама LU факторизација). Стога LU факторизација је рачунски ефикасна само када је потребно решавати матричне једначине за различите вредности b; брже је једном урадити LU декомпозицију матрице A, и затим решавати троугаоне матрице за свако b, него користити Гаусову елиминацију сваки пут.

Инверзна матрица[уреди]

Када се решава систем једначина, b се обично сматра као вектор-колона дугачка као висина матрице A. Уместо вектор-колоне b, можемо имати матрицу B, где је B матрица типа nxp, па покушавамо наћи матрицу X (која је исто типа n-x-p):

A X = L U X = B

Исти аглоритам раније показан се може користити да се реши свака колона матрице X. Може се претпоставити да је B јединична матрица димензија n. Из тога би следило да је решење X инверзна вредност матрице A.[4]

Детерминанта[уреди]

Матрице L и U се могу искористи да се врло брзо израчуна детерминанта матрице A, пошто је det(A) = det(L) det(U) а детерминанта троугаоних матрица је прост производ њених дијагоналних елемената. На пример, ако је L јединична троугаона матрица, онда је

 \det(A) = \det(L) \det(U) = 1 \cdot \det(U) = \prod_{i=1}^n u_{ii}.

Исти приступ важи и за LUP факторизацију. Детерминанта пермутационе матрице P је (−1)S, где је S број замена врста у декомпозицији.

Види још[уреди]

Референце[уреди]

  1. ^ Poole, David (2006), Linear Algebra: A Modern Introduction (2nd ed.), Canada: Thomson Brooks/Cole, ISBN 0-534-99845-3 
  2. ^ Golub, Gene H.; Van Loan, Charles F. (1996), Matrix Computations (3rd ed.), Baltimore: Johns Hopkins, ISBN 978-0-8018-5414-9 
  3. ^ J.R. Bunch and J.E. Hopcroft, Triangular factorization and inversion by fast matrix multiplication, Mathematics of Computation, 28 (1974) 231–236.
  4. ^ Matrix Computations. 3rd Edition, 1996., pp. 121.

Литература[уреди]

Спољашње везе[уреди]

Референце

Програмски код

Онлајн ресурси