LU декомпозиција — разлика између измена

 
== Алгоритми ==
-{LU}- декомпозиција је у основи модификовани облик [[Гаусова елиминација|Гаусове елиминације]]. Матрица ''A'' се трансформише у горњу троугаону матрицу ''U'' елиминисањем вредности испод главне дијагонале. Дулитлов алгоритам врши елиминацију колоне по колоне, идући са лева, множењем ''A'' са леве стране атомском доњем троугаоном матрицом. Резултат овога је ''јединична доња троугаона'' матрица и горња троугаона матрица. Крутов алгиритамалгoритам је мало другачији и даје доњу троугаону матрицу и ''јединичну горњу троугаону '' матрицу.
 
Рачунање -{LU}- факторизације коришћењем било ког од ова два алгоритма захтева 2''-{n}-''<sup>3</sup> / 3 операција са покретним зарезом, ако се игноришу термичланови нижег реда. Парцијално [[пивотни елемент|пивотирање]] додаје само квадратни термчлан; ово није случај код пуног пивотирања.<ref>{{citation | first1=Gene H. | last1=Golub | author1-link=Gene H. Golub | first2=Charles F. | last2=Van Loan | author2-link=Charles F. Van Loan | year=1996 | title=Matrix Computations | edition=3rd | publisher=Johns Hopkins | place=Baltimore | isbn=978-0-8018-5414-9}}.</ref>
 
=== Дулитлов алгоритам ===
 
Јасно је да би овај алгоритам правилно радио, потребно је имати <math>a_{n,n}^{(n-1)}\not=0</math>
у сваком кораку (погледати дефиницију <math>l_{i,n}</math>). Ако овај услов није задовољен у неком тренутку, само је потребно заманитизамeнити ''n''-ту врсту са другом врстом испод ње пре него што алгоритам настави даље. То је разлог зашто -{LU}- декомпозиција у општенопштем случају пише као <math>P^{-1}A = L U </math>.
 
=== Крутов и LUP алгоритми ===
LUP факторизациони алгоритам уопштава [[Крутова декомпозиција матрице|Крутову декомпозицију матрице]]. Може се описати у следећим корацима.
 
# Ако <math>A</math> има ненулти елемент у својој првој врсти, онда узети пермутациону матрицу <math>P_1</math> тако да <math>A P_1</math> има ненулти елемнетелемент у свом горњем левом углу. У супротном случају, за <math>P_1</math> се узима [[јединична матрица]]. Нека је <math>A_1 = A P_1</math>.
# Нека је <math>A_2</math> матрица која се добија од матрице <math>A_1</math> брисањем прве врсте и прве колоне. Факторизовати <math>A_2 = L_2 U_2 P_2</math> рекурзивно. Добити <math>L</math> од <math>L_2</math> прво додавњемдодавањем нултог реда горе, а затим додавањем прве колоне <math>A_1</math> слева.
# Добити <math>U_3</math> од <math>U_2</math> прво додавањем нултенултог колонереда горе и нулте колоне са лева, а затим замењивањемзаменом горње леве вредности (која је једнака 0 у овом тренуткуtтренутку) јединицом. Добити <math>P_3</math> од <math>P_2</math> на сличан начин и дефинисати <math>A_3 = A_1 / P_3 = A P_1 / P_3</math>. Нека је <math>P</math> инверзна матрица <math>P_1 / P_3</math>.
# У овом тренутку, <math>A_3</math> је исто као и <math>L U_3</math>, осим (можда) у првој врсти. Ако је прва врста <math>A</math> једнака нули, онда <math>A_3 = L U_3</math>, пошто обе имају нулту прву колону, а <math>A = L U_3 P</math> следо, као жељено. У супротном случају, <math>A_3</math> и <math>L U_3</math> имају исте ненулте вредности у горњем левом углу, и <math>A_3 = L U_3 U_1</math> за неку горње-троугаону квадратну матрицу <math>U_1</math> са јединицама на дијагонали (<math>U_1</math> брише елементе <math>L U_3</math> и додаје елементе <math>A_3</math> помоћу горњег левог угла). Сада је <math>A = L U_3 U_1 P</math> декомпозиција жељеног облика.
 
Анониман корисник