basisalgoritmes

Basisalgoritmes zijn procedures die proberen een basis te vinden of te construeren voor een vectorruimte of een deelruimte, meestal gegeven door een verzameling generatoren of een matrix. Een basis is een verzameling vectoren die de ruimte genereren en lineair onafhankelijk zijn.

Een veelvoorkomend probleem is het vinden van een basis voor de kolomruimte of de nulruimte van een matrix. Gaussische eliminatie (row-reduction) tot rij-echelonvorm is een standaard methode. De kolommen van de oorspronkelijke matrix die overeenkomen met de pivots in de gereduceerde vorm vormen een basis voor de kolomruimte. De oplossingen van Ax = 0 geven een basis voor de nulruimte; deze basis ontstaat door vrije variabelen te kiezen en bijbehorende oplossingsvectoren te construeren.

Een andere belangrijke methode is het Gram-Schmidt-proces, waarmee uit een lineair onafhankelijke generating set een orthonormale basis kan worden gemaakt. Ook de QR-decompositie levert een orthonormale basis voor de kolomruimte en heeft brede toepassingen in numerieke lineaire algebra.

Voor ruimtes zoals polynoomruimten of functies kan men basisfuncties kiezen zoals monomen of orthogonale polynomen; in de praktijk kan men ook een basis verkrijgen door lineair onafhankelijke subsets te selecteren of door eliminatie te gebruiken op de bijbehorende coefficientmatrix.

Complexiteit: Gaussische eliminatie vereist typisch O(n^3) bewerkingen voor een n×n-matrix; met gedeeltelijke pivotering en structuur-samenhang kan dit variëren in praktische toepassingen.

Toepassingen omvatten het oplossen van lineaire systemen, projecties, datareductie, computergraphics en signaalverwerking.

Zie ook: lineaire algebra, Gauss-eliminatie, Gram-Schmidt, QR-decompositie, matroidtheorie.