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

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

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

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

${\displaystyle \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 і він є єдиним ненульовим елементом у відповідному стовпчику, наприклад:

${\displaystyle \left[{\begin{array}{ccc|c}1&0&0&b_{1}\\0&1&0&b_{2}\\0&0&1&b_{3}\end{array}}\right]}$

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

${\displaystyle \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 

Див. також

• Метод Гауса
• Метод Гауса-Жордана

Посилання