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

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

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

${\displaystyle A=LU,\,}$

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

${\displaystyle {\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 декомпозиција је декомпозиција облика

${\displaystyle A=LDU,\,}$

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

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

${\displaystyle PA=LU,\,}$

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

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

${\displaystyle 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 као

${\displaystyle A=LL^{*}.\,}$

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

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

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

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

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

${\displaystyle A=(a_{n,n})}$

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

${\displaystyle A^{(0)}:=A}$

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

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

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

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

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

Одређујемо

${\displaystyle A^{(n)}:=L_{n}A^{(n-1)}.}$

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

${\displaystyle 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, и ${\displaystyle L=L_{1}^{-1}\ldots L_{N-1}^{-1}}$. Пошто је инверзна вредност доње троугаоне матрице L_n опет доња троугаона матрица, а производ две доње троугаоне матрице је опет доња троугаона матрица, добија се да је L такође доња троугана матрица. Штавише, може се видети да је

${\displaystyle 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}}.}$

Добијамо ${\displaystyle A=LU}$.

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

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

1. Ако ${\displaystyle A}$ има ненулти елемент у својој првој врсти, онда узети пермутациону матрицу ${\displaystyle P_{1}}$ тако да ${\displaystyle AP_{1}}$ има ненулти елемент у свом горњем левом углу. У супротном случају, за ${\displaystyle P_{1}}$ се узима јединична матрица. Нека је ${\displaystyle A_{1}=AP_{1}}$.
2. Нека је ${\displaystyle A_{2}}$ матрица која се добија од матрице ${\displaystyle A_{1}}$ брисањем прве врсте и прве колоне. Факторизовати ${\displaystyle A_{2}=L_{2}U_{2}P_{2}}$ рекурзивно. Добити ${\displaystyle L}$ од ${\displaystyle L_{2}}$ прво додавањем нултог реда горе, а затим додавањем прве колоне ${\displaystyle A_{1}}$ слева.
3. Добити ${\displaystyle U_{3}}$ од ${\displaystyle U_{2}}$ прво додавањем нултог реда горе и нулте колоне са лева, а затим заменом горње леве вредности (која је једнака 0 у овом тренутку) јединицом. Добити ${\displaystyle P_{3}}$ од ${\displaystyle P_{2}}$ на сличан начин и дефинисати ${\displaystyle A_{3}=A_{1}/P_{3}=AP_{1}/P_{3}}$. Нека је ${\displaystyle P}$ инверзна матрица ${\displaystyle P_{1}/P_{3}}$.
4. У овом тренутку, ${\displaystyle A_{3}}$ је исто као и ${\displaystyle LU_{3}}$, осим (можда) у првој врсти. Ако је прва врста ${\displaystyle A}$ једнака нули, онда ${\displaystyle A_{3}=LU_{3}}$, пошто обе имају нулту прву колону, а ${\displaystyle A=LU_{3}P}$ следо, као жељено. У супротном случају, ${\displaystyle A_{3}}$ и ${\displaystyle LU_{3}}$ имају исте ненулте вредности у горњем левом углу, и ${\displaystyle A_{3}=LU_{3}U_{1}}$ за неку горње-троугаону квадратну матрицу ${\displaystyle U_{1}}$ са јединицама на дијагонали (${\displaystyle U_{1}}$ брише елементе ${\displaystyle LU_{3}}$ и додаје елементе ${\displaystyle A_{3}}$ помоћу горњег левог угла). Сада је ${\displaystyle A=LU_{3}U_{1}P}$ декомпозиција жељеног облика.

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

${\displaystyle {\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 факторизације ове просте матрице је да се просто инспекцијом реше линеарне једначине. Из операције множења матрица добија се:

${\displaystyle l_{11}\cdot u_{11}+0\cdot 0=4}$

${\displaystyle l_{11}\cdot u_{12}+0\cdot u_{22}=3}$

${\displaystyle l_{21}\cdot u_{11}+l_{22}\cdot 0=6}$

${\displaystyle l_{21}\cdot u_{12}+l_{22}\cdot u_{22}=3.}$

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

${\displaystyle l_{21}=1.5}$

${\displaystyle u_{11}=4}$

${\displaystyle u_{12}=3}$

${\displaystyle u_{22}=-1.5.}$

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

${\displaystyle {\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. У идеалном случају, цена њиховог израчунавања (меморијамемориско заузеће и број операција) је одређен бројем ненултих елемената, а не величином матрице.

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

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

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

${\displaystyle Ax=LUx=b\,}$

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

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

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

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

${\displaystyle AX=LUX=B}$

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

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

${\displaystyle \det(A)=\det(L)\det(U)=1\cdot \det(U)=\prod _{i=1}^{n}u_{ii}.}$

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

• Блоковска LU декомпозиција
• Метод Холеског
• Декомпозиција матрице
• QR факторизација
• LU редукција

Референце

• LU декомпозиција на сајту MathWorld.
• LU декомпозиција Архивирано на сајту Wayback Machine (5. март 2013) на сајту Math-Linux.
• Модул за LU факторизацију са пивотирањем, проф. Џ. Х. Метјуз, Државни универзитет у Калифорнији, Фулертон
• LU декомпозиција на Институту за холистичке нумеричке методе

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

• LAPACK, колекција FORTRAN субрутина за решавање проблема из линеарне алгебре
• ALGLIB укључује делимичан порт за LAPACK у C++, C#, Delphi, итд.
• C++ код, проф. Џ. Лумис, Универзитет у Дејтону
• C код, Изворна математичка библиотека
• LU на X10

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

• Калкулатор за матрице, bluebit.gr
• Алат за LU декомпозицију, uni-bonn.de
• LU декомпозиција, Ед Пег, млађи, Волфрам демонстрациони пројекат, 2007.