Rijreductie van een matrix tot gereduceerde trapvorm

Stelsels lineaire vergelijkingen: Van stelsels naar matrices en rijreductie

Rijreductie van een matrix tot gereduceerde trapvorm

Bij rijreductie passen we elementaire rijoperaties toe; daarbij worden één of meer van de volgende bewerkingen toegepast:

een rij met een getal ongelijk aan nul vermenigvuldigen
een scalair veelvoud van een rij bij een andere rij optellen
het veranderen van de volgorde van de rijen

Dit zijn de toegestane handelingen. We hebben daarmee het proces van rijreductie nog niet vastgelegd. Doel van rijreductie is de matrix in gereduceerde trapvorm te brengen. We laten dat eerst aan de hand van enkele voorbeelden zien.

Breng de volgende matrix in gereduceerde trapvorm:

$A=\left(\,\begin{array}{rrrr} {1} & 2 & -4 & 8\\ -1 & -2 & 6 & -4\\ 1 & 4 & -2 & 0\end{array}\,\right)$

$\left(\,\begin{array}{rrrr} {1} & {0} &{0} & 28\\ {0} & {1} & {0} & -6\\ {0} & {0} &{1} & 2 \end{array}\,\right)$

We beginnen met de matrix:

$A=\left(\,\begin{array}{rrrr} \color{green}{1} & 2 & -4 & 8\\ -1 & -2 & 6 & -4\\ 1 & 4 & -2 & 0\end{array}\,\right)$ Groene elementen willen we onveranderd laten. We proberen eerst met de eerste rij zo veel mogelijk nullen in de eerste kolom te krijgen. Dat doen we door de eerste rij bij de tweede op te tellen en van de derde af te trekken. We krijgen dan:

$\left(\,\begin{array}{rrrr} \color{green}{1} & 2 & -\,4 & 8\\ \color{green}{0} & 0 & 2 & 4\\ \color{green}{0} & 2 & 2 & -8 \end{array}\,\right)$ Nu proberen we met de tweede rij de tweede kolom `schoon te vegen'. Dat gaat niet omdat het tweede element $0$ is. We verwisselen nu de tweede en derde rij (niet de tweede en eerste rij, want dan verstoren we het resultaat uit de eerste kolom!):

$\left(\,\begin{array}{rrrr} \color{green}{1} & 2 & -4 & 8\\ \color{green}{0} & 2 & 2 & -8\\ \color{green}{0} & \color{green}{0} & 2 & 4 \end{array}\,\right)$
en delen de tweede rij door $2$ :

$\left(\,\begin{array}{rrrr} \color{green}{1} & 2 & -4 & 8\\ \color{green}{0} & \color{green}{1} & 1 & -4\\ \color{green}{0} &\color{green}{0} & 2 & 4 \end{array}\,\right)$ Nu kunnen we met de tweede rij de tweede kolom schoonvegen. We trekken hem tweemaal van de eerste af; merk op dat daardoor de eerste kolom onveranderd blijft:

$\left(\,\begin{array}{rrrr} \color{green}{1} & \color{green}{0} & -6 & 16\\ \color{green}{0} & \color{green}{1} & 1 & -4\\ \color{green}{0} & \color{green}{0} & 2 & 4 \end{array}\,\right)$ Nu gaan we met de derde rij de derde kolom schoonvegen. Daartoe delen we hem eerst door $2$ :

$\left(\,\begin{array}{rrrr} \color{green}{1} & \color{green}{0} & -6 & 16\\ \color{green}{0} & \color{green}{1} & 1 & -4\\ \color{green}{0} & \color{green}{0} & \color{green}{1} & 2\end{array}\,\right)$ en tellen de nieuwe derde rij $6$ maal bij de eerste rij op en trekken hem ook van de tweede rij af; merk weer op dat hierdoor de eerste twee kolommen onveranderd blijven:

$\left(\,\begin{array}{rrrr} \color{green}{1} & \color{green}{0} & \color{green}{0} & 28\\ \color{green}{0} & \color{green}{1} & \color{green}{0} & -6\\ \color{green}{0} & \color{green}{0} & \color{green}{1} & 2 \end{array}\,\right)$
Nu kunnen we niet meer verder vegen; iedere veegpartij in de vierde kolom verstoort het resultaat in de eerste drie kolommen. Het verkregen resultaat is de rijgereduceerde trapvorm van $A$ , of kortweg de gereduceerde trapvorm van $A$ .

Uit het proces is het niet onmiddellijk duidelijk, maar rijreductie van een matrix levert een uniek resultaat op; we kunnen dus inderdaad spreken van de gereduceerde trapvorm van een matrix.

Nieuw voorbeeld

$\phantom{x}$

We beschrijven nu het algemene proces van rijreductie in de vorm van een algoritme. De lezer wordt aangeraden het zojuist gegeven voorbeeld te vergelijken met de volgende beschrijving.

Gauss-eliminatie

De Gauss-eliminatiemethode, of kortweg Gauss-eliminatie, is een methode om een matrix te reduceren tot een matrix in gereduceerde trapvorm door middel van elementaire rijbewerkingen.

Elke matrix kan gereduceerd worden tot een unieke gereduceerde trapvorm. De methode hieronder voert Gauss-eliminatie uit.

De eerste stap bestaat uit de volgende handelingen op een gegeven matrix met $m$ rijen en $n$ kolommen:

Laat $n_1$ het nummer van de eerste kolom zijn die niet uitsluitend uit nullen bestaat.
Verwissel eventueel twee rijen zodanig dat het eerste element van kolom $n_1$ niet nul is.
Deel de eerste rij door het eerste element van de kolom $n_1$ , zodat $a_{1n_1}=1$ .
De matrix heeft nu de volgende vorm gekregen: $\left(\,\begin{array}{cccccccc} 0 & \ldots & 0 & 1 & \ast & \ast & \ldots & \ast \\ 0 & \ldots & 0 & \alpha_2 & \ast & \ast & \ldots & \ast \\ 0 & \ldots & 0 & \alpha_3 & \ast & \ast & \ldots & \ast \\ \vdots & & \vdots & \vdots & \vdots & \vdots & & \vdots \\ 0 & \ldots & 0 & \alpha_m & \ast & \ast & \ldots & \ast \end{array}\,\right)$ Met $\ast$ noteren we de matrixelementen waarvan de waarde in de redenering niet belangrijk is.
Veeg met de eerste rij kolom $n_1$ verder schoon. We krijgen een matrix van de volgende vorm (met een omkaderde deelmatrix):
$\left(\,\begin{array}{cc} \begin{array}{cccc} 0 & \ldots & 0 & 1\end{array} & \begin{array}{cccc} \ast & \ast & \ldots & \ast \end{array} \\ \begin{array}{cccc} 0 & \ldots & 0 & 0 \\ 0 & \ldots & 0 & 0 \\ \vdots & & \vdots & \vdots \\ 0 & \ldots & 0 & 0\end{array} & \boxed{\begin{array}{cccc}\ast & \ast & \ldots & \ast\\ \ast & \ast & \ldots & \ast\\ \vdots & \vdots & & \vdots\\ \ast & \ast & \ldots & \ast\end{array}} \end{array}\,\right)$

De eerste stap is nu voltooid. In de vervolgstappen passen we dezelfde procedure toe op de omkaderde deelmatrix (maar wel met schoonvegen van hele kolommen in de laatste stap) en herhalen dit proces totdat we geen kader meer overhouden of een kader met enkel nullen, waarna het gehele proces van rijreductie is voltooid.

De genoemde vervolgstappen kunnen we als volgt formeler opschrijven: stel dat we $k$ stappen gedaan hebben. In de resulterende matrix zijn dan de eerste $k$ rijen al gebruikt om te vegen en de laatst geveegde kolom heeft nummer $n_k$ . We doen nu het volgende:

Laat $n_{k+1}$ het nummer van de eerste kolom zijn die vanaf het $(k+1)$ -ste element niet alleen uit nullen bestaat.
Verwissel eventueel rij $k+1$ met een volgende rij zodanig dat het $(k+1)$ -ste element van kolom $n_{k+1}$ ongelijk is aan nul.
Deel rij $k+1$ door dat element, zodat $a_{k+1,n_{k+1}}=1$ .
Veeg met rij $k+1$ de kolom $n_{k+1}$ verder schoon.

Het resultaat van dit veegproces kan er na bijvoorbeeld drie stappen als volgt uit zien:

$\left(\,\begin{array}{ccccccccccccccc} 0 & \ldots & 0 & 1 & \ast & \ldots & \ast & 0 & \ast & \ldots & \ast & 0 & \ast & \ldots & \ast\\ 0 & \ldots & 0 & 0 & 0 & \ldots & 0 & 1 & \ast & \ldots & \ast & 0 & \ast & \ldots & \ast\\ 0 & \ldots & 0 & 0 & 0 & \ldots & 0 & 0 & 0 & \ldots & 0 & 1 & \ast & \ldots & \ast\\ \vdots & & \vdots & \vdots & \vdots & & \vdots & \vdots & \vdots & & \vdots & 0 & \vdots & & \vdots\\ \vdots & & \vdots & \vdots & \vdots & & \vdots & \vdots & \vdots & & \vdots & \vdots & \vdots & & \vdots\\ 0 & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & 0 & \ast & \ldots & \ast \end{array}\,\right)$ Op de plaatsen met $\ast$ staan elementen die niet noodzakelijk $0$ of $1$ zijn.

Het proces stopt automatisch als alle rijen zijn gebruikt om te vegen of als de laatste rijen alleen nullen bevatten.

Pivoteren Via elementaire rijbewerking kunnen we een willekeurig geselecteerd niet-nul element van een matrix gelijk aan 1 maken en er tevens voor zorgen dat dit het enige niet-nul element in zijn kolom is. Dit proces heet het pivoteren van een matrix en het gekozen niet-nul matrixelement heet pivoteringselement, spilelement (of kortweg spil; in het Engels pivot) of scharnierelement. Rijreductie van een matrix tot zijn gereduceerde trapvorm is dus eigenlijk het zo lang mogelijk doorvoeren van pivoteringsoperaties.