Gauss-eliminatie: een methode om stelsels vergelijkingen op te lossen

Gauss-eliminatie is een van de meest fundamentele algoritmen in de lineaire algebra voor het oplossen van stelsels lineaire vergelijkingen. Genoemd naar de Duitse wiskundige Carl Friedrich Gauss, zet deze methode een stelsel vergelijkingen om in een equivalent, eenvoudiger formaat door een reeks bewerkingen uit te voeren op de matrixrepresentatie.

In dit artikel leggen we uit hoe Gauss-eliminatie werkt, implementeren we het in Python en onderzoeken we de toepassingen in data science en numerieke berekeningen. Door dit algoritme te begrijpen, krijgen we inzicht in een basistechniek die ten grondslag ligt aan veel rekenmethoden die in data-analyse worden gebruikt.

Wat is Gauss-eliminatie?

Gauss-eliminatie is een algoritme om stelsels lineaire vergelijkingen op te lossen door de aangevulde matrix van het stelsel systematisch om te vormen naar rij-echelonvorm (REF). Deze transformatie behoudt de oplossingsverzameling en maakt het eenvoudiger om de waarden van de variabelen te vinden.

Een matrix staat in rij-echelonvorm wanneer:

• Alle rijen die volledig uit nullen bestaan onderaan in de matrix staan
• Het leidende element (eerste niet-nul element) van elke niet-nul rij rechts van het leidende element van de rij erboven staat
• Alle elementen onder een leidend element nul zijn

Om rij-echelonvorm te bereiken, gebruiken we drie typen elementaire rijoperaties:

• Rijen verwisselen: Wissel twee rijen om
• Rijschaalvergroting: Vermenigvuldig alle elementen in een rij met een niet-nul constante
• Rijoptelling: Vervang een rij door de som van zichzelf en een veelvoud van een andere rij

Daarnaast is het belangrijk onderscheid te maken tussen Gauss-eliminatie en Gauss–Jordan-eliminatie:

• Gauss-eliminatie zet de matrix om naar rij-echelonvorm en vereist terugsubstitutie om de variabelen te vinden
• Gauss–Jordan-eliminatie gaat door tot gereduceerde rij-echelonvorm (RREF), waarbij alle leidende elementen 1 zijn en alle andere elementen in de kolom van elk leidend element 0 zijn

Hoewel Gauss–Jordan-eliminatie een directere oplossing geeft, is Gauss-eliminatie over het algemeen efficiënter voor grote stelsels, zeker in combinatie met terugsubstitutie en technieken zoals LU-decompositie.

Stapsgewijze uitleg van het Gauss-eliminatie-algoritme

Laten we het Gauss-eliminatieproces doorlopen met een eenvoudig voorbeeld. Beschouw het volgende stelsel lineaire vergelijkingen:

Stelsel van lineaire vergelijkingen. Afbeelding door de auteur.

Stap 1: Maak de aangevulde matrix

We representeren het stelsel eerst als een aangevulde matrix, waarbij we de coëfficiëntenmatrix combineren met de constanten:

Aangevulde matrix. Afbeelding door de auteur.

Stap 2: Voorwaartse eliminatie

We voeren nu elementaire rijoperaties uit om de matrix om te vormen naar rij-echelonvorm.

Maak het eerste element van de eerste kolom een pivot en elimineer alle elementen eronder:

• Tel 3/2 × rij 1 op bij rij 2:

Tel 3/2 × rij 1 op bij rij 2. Afbeelding door de auteur.

• Tel rij 1 op bij rij 3:

Tel rij 1 op bij rij 3. Afbeelding door de auteur.

Ga naar de tweede kolom en elimineer alle elementen onder de pivot:

• Vermenigvuldig rij 2 met 2 om de pivot 1 te maken:

Vermenigvuldig rij 2 met 2. Afbeelding door de auteur.

• Trek 2 × rij 2 af van rij 3:

Trek 2 × rij 2 af. Afbeelding door de auteur.

Maak de pivot in de derde rij positief:

• Vermenigvuldig rij 3 met -1:

Vermenigvuldig rij 3 met -1. Afbeelding door de auteur.

De matrix staat nu in rij-echelonvorm.

Stap 3: Terugsubstitutie

Nu kunnen we de waarden van onze variabelen vinden via terugsubstitutie:

Uit rij 3: 

          z = -1

Uit rij 2: 

          y + z = 2,

          dus y + (-1) = 2,

          wat geeft y = 3

Uit rij 1: 

          2x + y - z = 8,

          dus 2x + 3 - (-1) = 8,

          wat geeft 2x = 4,

          dus x = 2

Daarom is de oplossing x = 2, y = 3, z = -1.

Hoewel we de Gauss-eliminatie op dit voorbeeld toepassen, blijven de stappen hetzelfde voor een ander lineair stelsel vergelijkingen.

Implementatie van Gauss-eliminatie in Python

Hoewel we het algoritme met basis-Python kunnen schrijven, maken de gevectoriseerde bewerkingen van NumPy de implementatie zowel overzichtelijker als aanzienlijk sneller. 

Voor educatieve doeleinden is het waardevol om het onderliggende algoritme te begrijpen, maar voor productiegebruik is het aan te raden geoptimaliseerde bibliotheken te benutten. Nu we het onderliggende algoritme in de vorige sectie al hebben begrepen, gaan we in op de implementatie met geoptimaliseerde bibliotheken in Python.

Implementatie op basis van NumPy

NumPy biedt de functie numpy.linalg.solve(), die een sterk geoptimaliseerde oplossing voor stelsels lineaire vergelijkingen implementeert:

import numpy as np

# Define the coefficient matrix A and constant vector b
A = np.array([[2, 1, -1],
             [-3, -1, 2],
             [-2, 1, 2]], dtype=float)
b = np.array([8, -11, -3], dtype=float)

# Solve the system Ax = b
x = np.linalg.solve(A, b)

print("Solution:", x)Mogelijk gemaakt door

In de bovenstaande code definiëren we de coëfficiëntenmatrix A en de constante vector b, die hetzelfde zijn als de aangevulde matrix die we in stap 1 van het bovenstaande Gauss-eliminatievoorbeeld hebben gemaakt. 

We gebruiken de functie numpy.linalg.solve() om tot de oplossing te komen en printen de uitvoer zoals hieronder te zien:

Oplossing met code-implementatie. Afbeelding door de auteur.

Deze implementatie gebruikt onder de motorkap LAPACK, dat LU-decompositie toepast (een variant van Gauss-eliminatie) geoptimaliseerd voor numerieke stabiliteit en prestaties.

Omgaan met bijzondere gevallen

Bij het implementeren van Gauss-eliminatie kom je verschillende bijzondere gevallen tegen die zorgvuldige afhandeling vereisen:

• Singuliere matrices: Als de determinant van je coëfficiëntenmatrix nul is of zeer dicht bij nul ligt, heeft het stelsel geen oplossing of oneindig veel oplossingen. NumPy’s linalg.solve() functie werpt in dit geval een LinAlgError.

• Numerieke stabiliteit: Bij drijvende-komma-aritmetiek kunnen afrondingsfouten zich opstapelen en tot onnauwkeurige resultaten leiden. Gedeeltelijke pivotering, waarbij het grootste element in een kolom als pivot wordt gekozen, helpt dit te beperken.

• Over- of onderbepaalde stelsels: Wanneer het aantal vergelijkingen niet overeenkomt met het aantal variabelen, kun je in plaats daarvan numpy.linalg.lstsq() gebruiken, dat de kleinste-kwadratenoplossing vindt.

Voor grote stelsels met veel nullen kunnen de sparse-matrixoplossers van SciPy orders van grootte sneller zijn dan dense oplossers:

from scipy.sparse import csr_matrix
from scipy.sparse.linalg import spsolve

# For large sparse matrices
A_sparse = csr_matrix(A)
x = spsolve(A_sparse, b)Mogelijk gemaakt door

Hoewel het begrijpen van de werking van het algoritme waardevol is, kun je in de praktijk met de geoptimaliseerde implementaties van NumPy en SciPy stelsels lineaire vergelijkingen efficiënt en betrouwbaar oplossen zonder het wiel opnieuw uit te vinden.

Waar Gauss-eliminatie wordt gebruikt

Gauss-eliminatie gaat veel verder dan de theoretische wiskunde en kent talloze praktische toepassingen in diverse domeinen van wetenschap, techniek en data-analyse. 

Hier zijn enkele van de belangrijkste realistische toepassingen van dit fundamentele algoritme:

• Lineaire regressie: In data science wordt Gauss-eliminatie gebruikt om de normale vergelijkingen op te lossen die ontstaan bij het vinden van best-fit parameters in lineaire regressiemodellen. Dit stelt analisten in staat voorspellingen te doen op basis van historische data.
• Netwerkanalyse: Ingenieurs gebruiken Gauss-eliminatie om onbekende stromen of spanningen in elektrische schakelingen op te lossen door wetten van Kirchhoff toe te passen, die stelsels lineaire vergelijkingen genereren die gelijktijdig moeten worden opgelost.
• Matrixinversie: Gauss-eliminatie vormt de basis voor het berekenen van matrixinversen, essentieel bij transformaties, statistische analyses en het oplossen van complexe wiskundige problemen in machinelearning-algoritmen.
• Numerieke integratie: Bij het implementeren van geavanceerde numerieke methoden zoals impliciete Euler of Runge–Kutta-integratie wordt Gauss-eliminatie gebruikt om de resulterende stelsels vergelijkingen op te lossen en zo stabiliteit te waarborgen in simulaties van dynamische systemen.

Door deze toepassingen te begrijpen, zien we hoe één wiskundige techniek de ruggengraat vormt van veel tools die data scientists, ingenieurs en onderzoekers dagelijks gebruiken.

Conclusie

Dit artikel besprak het fundamentele algoritme van Gauss-eliminatie voor het oplossen van stelsels lineaire vergelijkingen door matrices om te vormen naar rij-echelonvorm. We leerden ook hoe we deze techniek in Python kunnen implementeren met de geoptimaliseerde functies van NumPy, en we begrepen de praktische toepassingen in lineaire regressie, netwerkanalyse, matrixinversie en numerieke methoden. 

Wil je je kennis van lineaire algebra en de toepassingen in data science verdiepen, overweeg dan om je in te schrijven voor onze cursus Linear Algebra, waarin je meer geavanceerde concepten en implementaties van deze basistechnieken verkent.