Załóżmy b.s.o., że to macierz trójkątna górna.
AB=C
a_{i,j} = 0 dla i>j
a_{i,j} = a_{i,j} w p.p.
b_{i,j} = 0 dla i>j
b_{i,j} = b_{i,j} w p.p.
c_{i,j} = \sum_{k=0}^n a_{i,k}b_{k,j}
Rozważmy tylko elementy i>j i sprawdzmy, czy są równe 0.
c_{i,j} = \sum_{k=0}^i 0\cdot b_{k,j} + \sum_{k=i+1}^n a_{i,k}\cdot 0 = 0
Macierz [x_{i,j}] macierz wejściowa {y_{i,j}} wyjściowa, elementy [y_{i,j}] liczymy po kolei dla i=(1,2,3,4, … n) j=(i,i-1,i-2, … 1)
[y_{i,i}]=1/x_{i,i}
[y_{i,j}]=(-x_{i,j}/x_{j,j} -\sum_{k=j+i}^{i-1} x_{i,k}\cdot y_{k,j})/x_{i,i}
A \cdot A^{-1} = I. Macierz A jest trójkątna, więc do obliczania wystarczy tylko zsumować tak: i_{i,j} = \sum_{k=j}^i x_{i,k} \cdot y_{k,j}, gdzie i_{i,j} jest elementem macierzy I, x_{i,j} – macierzy A, a y_{i,j} – macierzy A^{-1}. Przekształćmy, żeby otrzymać y_{i,j}:
\displaystyle i_{i,j} = \sum_{k=j}^i x_{i,k} \cdot y_{k,j}
\displaystyle i_{i,j} = \sum_{k=j}^{i-1} x_{i,k} \cdot y_{k,j} \quad + x_{i,i} \cdot y_{i,j}
\displaystyle y_{i,j} = x_{i,i}^{-1} \cdot \left(i_{i,j} - \sum_{k=j}^{i-1} x_{i,k} \cdot y_{k,j} \right)
Teraz można obliczać y_{i,j} iterując po kolei po i, a potem po j, podstawiając za i_{i,j} zero lub jeden.
wiemy, że:
l_{i,j} = l^T_{j,i}
a_{i,j} = a_{j,i}
\displaystyle a_{i,j} = \sum_{k=0}^n l_{i,k}l^T_{k,j} = \sum_{k=0}^n l_{i,k}l_{j,k}
Czyli w szczególności:
\displaystyle a_{i,i} = \sum_{k=0}^n l_{i,k}^2 = \sum_{k=0}^i l_{i,k}^2 = \sum_{k=0}^{i-1} l_{i,k}^2 + l_{i,i}^2
l_{i,i} = \sqrt {a_{i,i} - \sum_{k=0}^{i-1} l_{i,k}^2}
Dla i>j:
a_{i,j} = \sum_{k=0}^n l_{i,k}l_{j,k} = \sum_{k=0}^j l_{i,k}l_{j,k} = \sum_{k=0}^{j-1} l_{i,k}l_{j,k} + l_{i,j}l_{j,j}
I z tego juz wynika drugi wzrór.
Doprowadzamy eliminacja macierz do samej przekatnej i wtedy obliczenie wyniku to n dzielen. Wystarczy policzyc ile operacji jest przy doprowadzaniu do diagonali.
Doprowadzenie do schodkowej:
\sum_{k=1}^n k^2 - w k elementach k wierzszy odejmujemy wartości.
Schodkowa → diagonalna:
\sum_{k=1}^n k \cdot (n-k)