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

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

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

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

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

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

LDU декомпозиција Волшове матрице

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

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

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

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

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 као

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

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

Када постоји LDU факторизација и када је она јединствена, тада постоји затоврена (експлицинта формула) за елементе матрица L, D, и U у виду количника детерминанти одређених подматрица оригиналне матрице A (Householder 1975). На пример, и за , је количник -те главне подматрице и -те главне подматрице.

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

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

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

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

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

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

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

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

за . Ово се може урадити множењем A(n-1) са доњом троугаоном матрицом

Одређујемо

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

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

Добијамо .

Јасно је да би овај алгоритам правилно радио, потребно је имати у сваком кораку (погледати дефиницију ). Ако овај услов није задовољен у неком тренутку, само је потребно заменити n-ту врсту са другом врстом испод ње пре него што алгоритам настави даље. То је разлог зашто LU декомпозиција у општем случају пише као .

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

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

  1. Ако има ненулти елемент у својој првој врсти, онда узети пермутациону матрицу тако да има ненулти елемент у свом горњем левом углу. У супротном случају, за се узима јединична матрица. Нека је .
  2. Нека је матрица која се добија од матрице брисањем прве врсте и прве колоне. Факторизовати рекурзивно. Добити од прво додавањем нултог реда горе, а затим додавањем прве колоне слева.
  3. Добити од прво додавањем нултог реда горе и нулте колоне са лева, а затим заменом горње леве вредности (која је једнака 0 у овом тренутку) јединицом. Добити од на сличан начин и дефинисати . Нека је инверзна матрица .
  4. У овом тренутку, је исто као и , осим (можда) у првој врсти. Ако је прва врста једнака нули, онда , пошто обе имају нулту прву колону, а следо, као жељено. У супротном случају, и имају исте ненулте вредности у горњем левом углу, и за неку горње-троугаону квадратну матрицу са јединицама на дијагонали ( брише елементе и додаје елементе помоћу горњег левог угла). Сада је декомпозиција жељеног облика.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1. Poole, David (2006). Linear Algebra: A Modern Introduction (2nd изд.). Canada: Thomson Brooks/Cole. ISBN 0-534-99845-3. 
  2. Golub, Gene H.; Van Loan, Charles F. (1996). Matrix Computations (3rd изд.). 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.

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

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

Референце

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

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