LU декомпозиција — разлика између измена
Садржај обрисан Садржај додат
Ред 58:
== Алгоритми ==
-{LU}- декомпозиција је у основи модификовани облик [[Гаусова елиминација|Гаусове елиминације]]. Матрица ''A'' се трансформише у горњу троугаону матрицу ''U'' елиминисањем вредности испод главне дијагонале. Дулитлов алгоритам врши елиминацију колоне по колоне, идући са лева, множењем ''A'' са леве стране атомском доњем троугаоном матрицом. Резултат овога је ''јединична доња троугаона'' матрица и горња троугаона матрица. Крутов
Рачунање -{LU}- факторизације коришћењем било ког од ова два алгоритма захтева 2''-{n}-''<sup>3</sup> / 3 операција са покретним зарезом, ако се игноришу
=== Дулитлов алгоритам ===
Ред 117:
Јасно је да би овај алгоритам правилно радио, потребно је имати <math>a_{n,n}^{(n-1)}\not=0</math>
у сваком кораку (погледати дефиницију <math>l_{i,n}</math>). Ако овај услов није задовољен у неком тренутку, само је потребно
=== Крутов и LUP алгоритми ===
LUP факторизациони алгоритам уопштава [[Крутова декомпозиција матрице|Крутову декомпозицију матрице]]. Може се описати у следећим корацима.
# Ако <math>A</math> има ненулти елемент у својој првој врсти, онда узети пермутациону матрицу <math>P_1</math> тако да <math>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>U_3</math> од <math>U_2</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> декомпозиција жељеног облика.
| |||