# Zadanie 6


$M = \begin{bmatrix}
m_{11} & m_{12} & \dots & m_{1n} \\
m_{21} & m_{22} & \dots & m_{2n} \\
\vdots & \vdots & \ddots & \vdots \\
m_{n1} & m_{n2} & \dots & m_{nn} \end{bmatrix} =
\begin{bmatrix} a_{11} & 0 & \dots & 0 \\
a_{21} & a_{22} & \dots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
a_{n1} & a_{n2} & \dots & a_{nn}
\end{bmatrix}
\begin{bmatrix} a_{11} & a_{21} & \dots & a_{n1} \\
0 & a_{22} & \dots & a_{n2} \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \dots & a_{nn}
\end{bmatrix} = A^TA$

stąd wynika, że

$m_{11} = a_{11}^2 \implies a_{11} = \sqrt{m_{11}}$

$m_{21} = a_{21}a_{11} \implies a_{21} = \dfrac{m_{21}}{a_{11}}$

$m_{22} = a_{21}^2 + a_{22}^2 \implies a_{22} = \sqrt{m_{22} - a_{21}^2}$

$m_{32} = a_{31} a_{21} + a_{32} a_{22} \implies a_{32} = \dfrac{m_{32} - a_{31}a_{21}}{a_{22}}$

$\vdots$

bardziej ogólnie:

$a_{ii} = \sqrt{m_{ii} - \sum_{k=1}^{i-1} a_{ik}^2}$

$a_{ji} = \dfrac{m_{ji} - \sum_{k=1}^ {i-1}a_{jk}a_{ik}}{a_{ii}}$

algorytm

Wejście: macierz $M$ w postaci tablicy $n$ na $n$

; A - wyzerowana tablica n na n
j := 1
while j <= n                       (Wykonuje się n razy)
    i := 1
    while i <= j                   (Wykonuje się j razy, średnio (n+1)/2 razy)
        if i == j
            suma := 0
            k := 1
            while k <= i - 1       (Wykonuje się j-1 razy, czyli n/2 razy)
                suma += A[i][k] * A[i][k]
                k += 1
            A[i][i] := sqrt(M[i][i] - suma)
        else
            suma := 0
            k := 1
            while k <= i - 1       (Wykonuje się średnio j/2, czyli n/4 razy)
                suma += A[j][k] * A[i][k]
                k += 1
            A[j][i] := (M[j][i] - suma) / A[i][i]
        i += 1
    j += 1
return A

Wyjście: macierz dolnotrójkątna A

Czas działania to $O(n^3 / 4)$