Gauss-Jordan Elimination

Denne artikel indeholder:

Har man flere ligninger med flere ubekendte, kan det hurtigt blive et stort arbejde at løse ligningssystemet vha. f.eks. substitution.

Derfor kan man med fordel anvende Gauss-Jordan elimination til at løse systemet.

Lad os forestille os, at vi har følgende ligninger, hvor \(a_{ij}\) og \(b_i\) er reelle tal:

\begin{align} a_{11}x + a_{12}y + a_{13}z = b_1 \\ a_{21}x + a_{22}y + a_{23}z = b_2 \\ a_{31}x + a_{32}y + a_{33}z = b_3 \end{align}

Det vil være besværligt at løse dette system vha. substitution (og endnu værre hvis vi havde flere ligninger og flere ubekendte), så vi kan i stedet vælge at omskrive ligningssystemet til følgende:

\begin{equation} \begin{pmatrix}a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33}\end{pmatrix} \begin{pmatrix} x \\ y \\ z \end{pmatrix} = \begin{pmatrix} b_1 \\ b_2 \\ b_3 \end{pmatrix} \end{equation}

Hvis man anvender regnereglerne for matrixmultiplikation kan man se, at dette giver de tre ligninger ovenfor.

Vi kan nu samle koefficienterne (\(a_{ij}\)) og resultaterne (\(b_i\)) i en ny form for matrix (på engelsk kaldet en augmented matrix):

\begin{equation} \left( \begin{array}{ccc|c} a_{11} & a_{12} & a_{13} & b_1 \\ a_{21} & a_{22} & a_{23} & b_2 \\ a_{31} & a_{32} & a_{33} & b_3 \end{array} \right) \end{equation}

Vi skal nu se på, hvordan denne matrix kan anvendes til at løse ligningssystemet.

Rækkeoperationer og Rækkeækvivalens

For at løse vores ligningsystem, har vi tre operationer vi kan udføre på vores matrix. De er følgende:

Vi kan hurtigt se, at vi gerne må udføre disse tre operationer - en række i vores matrix svarer jo til en af de tre ligninger ovenfor, og det er jo ligegyldigt hvilken rækkefølge vi skriver vores ligninger op i. Desuden må vi jo gerne gange med et tal på hver side af lighedstegnet (altså skalere), og vi må gerne lægge en ligning til en anden ligning.

Disse tre operationer kaldes elementære rækkeoperationer, og hvis man kan få en matrix \(A\) til at blive en matrix \(B\) ved at udføre rækkeoperationer på den, kaldes \(A\) og \(B\) for rækkeækvivalente matricer, hvilket skrives som \(A\sim B\).

Løsning af Lineære Ligningssystemer

Hvis vi skal løse et ligningssystem vha. rækkeoperationer, skal ligningssystemet være lineært. Dvs. alle de ubekendte skal være i første potens (dette er dog ikke hele definitionen på at være lineær - læs grundlæggende lineær algebra for mere om dette).

Lad os se på et eksempel - vi har følgende ligninger:

\begin{align} x + 2y - z = 1 \\ 2x - y + z = 3 \\ -x + 2y + 3z = 7 \end{align}

Ud fra disse kan vi opstille følgende matrix:

\begin{equation} \left( \begin{array}{ccc|c} 1 & 2 & -1 & 1 \\ 2 & -1 & 1 & 3 \\ -1 & 2 & 3 & 7 \end{array} \right) \end{equation}

Vi kan nu lægge række 1 til række 3, og trække række 1 to gange fra række 2, hvormed vi får følgende:

\begin{equation} \left( \begin{array}{ccc|c} 1 & 2 & -1 & 1 \\ 0 & -5 & 3 & 1 \\ 0 & 4 & 2 & 8 \end{array} \right) \end{equation}

Vi kan nu dividere række tre med 4 (altså skalere med \(1/4\)), og lægge resultatet af række tre fem gange til række to:

\begin{equation} \left( \begin{array}{ccc|c} 1 & 2 & -1 & 1 \\ 0 & 0 & 11/2 & 11 \\ 0 & 1 & 1/2 & 2 \end{array} \right) \end{equation}

Vi kan nu skalere række to med \(2/11\) og ombytte række to og tre:

\begin{equation} \left( \begin{array}{ccc|c} 1 & 2 & -1 & 1 \\ 0 & 1 & 1/2 & 2 \\ 0 & 0 & 1 & 2 \end{array} \right) \end{equation}

Vores matrix er nu på række echelon-form, dvs. vi har en form for trappe af \(1\)-taller langs diagonalen, og vi har kun nuller under diagonalen. Vi kan nu opskrive tre ligninger ud fra vores matrix:

\begin{align} x + 2y - z = 1 \\ y + 1/2z = 2 \\ z = 2 \end{align}

Nu kan ligningerne meget lette løses - vi har \(z\), som vi blot kan indsætte i ligning 2, og dermed få \(y\), hvorefter vi kan indsætte begge i ligning 1 og få \(x\). Hele denne fremgangsmåde med vores matrix til at løse ligningssystemet kaldes Gauss elimination. Men vi kan gøre det endnu bedre! Vi fortsætter med at rækkereducere vores matrix:

\begin{equation} \left( \begin{array}{ccc|c} 1 & 2 & -1 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 2 \end{array} \right) \sim \left( \begin{array}{ccc|c} 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 2 \end{array} \right) \end{equation}

Nu har vi altså også lavet nuller over diagonalen, og har dermed opnået reduceret række echelon-form (og fremgangsmåden kaldes nu Gauss-Jordan elimination). Nu kan vi direkte aflæse løsningen til ligningssystemet, idet første række siger \(x = 1\), anden række \(y = 1\) og sidste række \(z = 2\).

Et eksempel

Lad os løse følgende ligningssystem:

\begin{align} x_2 + x_3 + x_4 = 0 \\ 3x_1 + 3x_3 - 4x_4 = 7 \\ x_1 + x_2 + x_3 + 2x_4 = 6 \\ 2x_1 + 3x_2 + x_3 + 3x_4 = 6 \end{align}

Vi kan opskrive følgende matrix ud fra dette:

\begin{align} \left( \begin{array}{cccc|c} 0 & 1 & 1 & 1 & 0 \\ 3 & 0 & 3 & -4 & 7 \\ 1 & 1 & 1 & 2 & 6 \\ 2 & 3 & 1 & 3 & 6 \end{array} \right) \end{align}

Nu skal vi blot rækkereducere denne matrix til reduceret række echelon-form (jeg laver ca. 2-3 rækkeoperationer ad gangen):

\begin{align} \sim \left( \begin{array}{cccc|c} 1 & 1 & 1 & 2 & 6 \\ 0 & 1 & 1 & 1 & 0 \\ 3 & 0 & 3 & -4 & 7 \\ 2 & 3 & 1 & 3 & 6 \end{array} \right) \sim \left( \begin{array}{cccc|c} 1 & 0 & 0 & 1 & 6 \\ 0 & 1 & 1 & 1 & 0 \\ 3 & 0 & 3 & -4 & 7 \\ 2 & 2 & 0 & 2 & 6 \end{array} \right) \sim \left( \begin{array}{cccc|c} 1 & 0 & 0 & 1 & 6 \\ 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 3 & -7 & -11 \\ 0 & 1 & 0 & 0 & -3 \end{array} \right) \end{align} \begin{align} \sim \left( \begin{array}{cccc|c} 1 & 0 & 0 & 1 & 6 \\ 0 & 1 & 0 & 0 & -3 \\ 0 & 0 & 1 & 1 & 3 \\ 0 & 0 & 3 & -7 & -11 \end{array} \right) \sim \left( \begin{array}{cccc|c} 1 & 0 & 0 & 1 & 6 \\ 0 & 1 & 0 & 0 & -3 \\ 0 & 0 & 1 & 1 & 3 \\ 0 & 0 & 0 & -10 & -20 \end{array} \right) \sim \left( \begin{array}{cccc|c} 1 & 0 & 0 & 0 & 4 \\ 0 & 1 & 0 & 0 & -3 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 2 \end{array} \right) \end{align}

Dvs. resultatet bliver \(x_1 = 4, x_2 = -3, x_3 = 1, x_4 = 2\).