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

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

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

Приклад 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 columnCount ≤ lead 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 i ≠ r then Swap rows i and r
        Divide row r by M[r, lead]
        for 0 ≤ i < rowCount do
            if i ≠ r 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 p ≤ c < 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

Див. також

Посилання

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.