Рядкова ступінчаста форма

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

У лінійній алгебрі матриця має рядкову ступінчасту форму якщо

  • Усі ненульові рядки (рядки, що мають хоча б один ненульовий елемент) знаходяться над нульовими рядками, і
  • Лідируючий коефіцієнт (перший ненульовий елемент зліва) ненульового рядка завжди строго справа від лідируючого коефіцієнта в рядку вище.

Приклад 3x3 матриці у рядковій ступінчастій формі:


\left[ \begin{array}{ccc|c}
1 & a_1 & a_2 & a_3 \\
0 & 1 & a_4 & a_5 \\
0 & 0 & 1 & a_6
\end{array} \right]

Матриця є у скороченій рядковій формі (також називається рядкова канонічна форма) якщо вона задовольняє наступну умову:

  • Кожен передній коефіцієнт є 1 і він є єдиним ненульовим елементом у відповідному стовпчику, наприклад:


\left[ \begin{array}{ccc|c}
1 & 0 & 0 & b_1 \\
0 & 1 & 0 & b_2 \\
0 & 0 & 1 & b_3
\end{array} \right]

Зауважимо, що це не завжди значить, що ми отримаємо одиничну матрицю. Наприклад, наступна матриця також у скороченій рядковій формі:


\left[ \begin{array}{cccc|c}
1 & 0 & 1/2  & 0 & b_1 \\
0 & 1 & -1/3 & 0 & b_2 \\
0 & 0 & 0    & 1 & b_3
\end{array} \right]

Неунікальність[ред.ред. код]

Кожна ненульова матриця може бути приведена до нескінченної кількості рядкових ступінчастих форм (вони можуть бути добутками інших ступінчастих форм, наприклад) з допомогою елементарних перетворень матриць. Однак, усі матриці та їхні рядкові ступінчасті форми відповідають одній матриці у скороченій рядковій ступінчастій формі.

Системи лінійних рівнянь[ред.ред. код]

Система лінійних рівнянь є у рядковій ступінчастій формі якщо її розширена матриця знаходиться в рядковій ступінчастій формі. Схожим чином, система рівнянь є у скороченій рядковій ступінчастій формі або канонічній формі якщо її розширена матриця є у скороченій рядковій ступінчастій формі.

Псевдокод[ред.ред. код]

Наступний псевдокод конвертує матриці у скорочену рядкову ступінчасту форму:

function ToReducedRowEchelonForm(Matrix M) is
    lead := 0
    rowCount := the number of rows in M
    columnCount := the number of columns in M
    for 0 ≤ r < rowCount do
        if columnCountlead then
            stop function
        end if
        i = r
        while M[i, lead] = 0 do
            i = i + 1
            if rowCount = i then
                i = r
                lead = lead + 1
                if columnCount = lead then
                    stop function
                end if
            end if
        end while
        if ir then Swap rows i and r
        Divide row r by M[r, lead]
        for 0 ≤ i < rowCount do
            if ir do
                Subtract M[i, lead] multiplied by row r from row i
            end if
        end for
        lead = lead + 1
    end for
end function

наступний псевдокод перетворює матрицю у рядкову ступінчасту форму (не скорочену):

function ToRowEchelonForm(Matrix M) is
    nr := number of rows in M
    nc := number of columns in M
    
    for 0 ≤ r < nr do
        allZeros := true
        for 0 ≤ c < nc do
            if M[r, c] != 0 then
                allZeros := false
                exit for
            end if
        end for
        if allZeros = true then
            In M, swap row r with row nr
            nr := nr - 1
        end if
    end for
    
    p := 0
    while p < nr and p < nc do
        label nextPivot:
            r := 1
            while M[p, p] = 0 do 
                if (p + r) <= nr then
                    p := p + 1
                    goto nextPivot
                end if
                In M, swap row p with row (p + r)
                r := r + 1
            end while
            for 1 ≤ r < (nr - p) do 
                if M[p + r, p] != 0 then
                    x := -M[p + r, p] / M[p, p]
                    for pc < nc do
                        M[p + r, c] := M[p , c] * x + M[p + r, c]
                    end for
                end if
            end for
            p := p + 1
    end while
end function

Див. також[ред.ред. код]

Посилання[ред.ред. код]