Lösen homogenes System Ax = 0 für jede m * n Matrix A in R (Nullraumbasis für A finden)

Question

Wie löst man ein homogenes System Ax = 0, wenn A irgendeine m * n Matrix (nicht unbedingt eine quadratische) in R?

# A=[-0.1 0.1]= 1x2 matrix; x=2x1 to be found; 0: 1x1 zero matrix 
A <- t(matrix(c(-0.1,0.1))) 

Diese Frage scheint zu finden, den Kernel (Nullraum) ein Rn -> Rm äquivalent zu sein (kann nicht Exponenten tun, sorry) lineare Transformation.

Answer 1

Wie auch immer, die Lösung für die obige spezifische Matrix A wird mir genügen.

Wir können es sehen, x = (a, a), wo a ist ein beliebiger Wert.

---

eine allgemeine Behandlung

Für allgemeine Lösung nehmen A ist n * p. (Leider ist dies die Schreibweise wir häufig in der Statistik verwenden.)

Sie müssen zuerst den Rang eines A durch eine QR-Zerlegung bestimmen:

QR <- qr.default(A) 
r <- QR$rank 
R <- QR$qr 

QR-Faktorisierung konvertiert rechtwinkliges System Ax = 0 zu Rx = 0 (unter orthogonal verwandeln).

• wenn n >= p, dann ist eine Rp * p obere Dreiecksmatrix;
• Wenn n < p, dann R ist eine p * n Trapezmatrix, wobei der linke p * p Block oben dreieckig ist.

Jetzt r Matrix Rang wird kommen

wenn n >= p

• wenn r = p Sie ein Full-Rang-System, so dass die Lösung zu x ist einzigartig. Nur ein Vektor von Nullen.
• Wenn r < p, gibt es (p - r) freie Variablen im NULL-Raum (ker(A)). Sie müssen die letzten (p - r) Werte in x auf einige willkürliche setzen, dann aktualisieren Sie die RHS b <- -(R[1:r, -(1:r)] %*% x[-(1:r)]) und lösen für die ersten r Werte von x eindeutig: x[1:r] <- backsolve(R, b, r).

wenn n < p

Dieses System hat immer freie Variablen in x, egal was r ist. Wir wenden die gleiche Berechnung wie oben in r < p an.Hier

ist eine Implementierung:

f <- function (A) { 
    n <- dim(A)[1] 
    p <- dim(A)[2] 
    QR <- qr.default(A) 
    R <- QR$qr 
    r <- QR$rank 
    x <- numeric(p) 
    if ((r < min(n, p)) || (n < p)) { 
    x[-(1:r)] <- runif(p - r) 
    b <- -(R[1:r, -(1:r), drop = FALSE] %*% x[-(1:r)]) 
    x[1:r] <- backsolve(R, b, r) 
    } 
    x 
    } 

Beachten Sie, dass, wenn Sie einen Vektor von Nullen erhalten, die Lösung eine zufällige ist. Sie können die Korrektheit durch A %*% f(A) überprüfen, vorbehaltlich eines Rundungsfehlers.

---

eine Erweiterung

Die f Funktion über nur eine Lösung gibt. Aber für diejenigen, die mit linearer Algebra vertraut sind, ist der Nullraum von A ein Vektorraum, und wir wollen wirklich eine Basis für diesen Raum. Also hier ist eine Verbesserung.

Jetzt, es sei denn, Sie erhalten einen Vektor von Nullen, ist die Lösung nicht eindeutig und es gibt einen Lösungsraum. In diesem Fall geben die Spalten x die Grundlage für diesen Raum. Jede lineare Kombination dieser Spalten ist eine Lösung. Beachten Sie auch, dass die zufällige Natur der vorherigen Funktion entfernt wird.

---

Warum QR-Faktorisierung?

Im linearen Algebra-Kurs wird die (reduzierte) Zeilenrangform verwendet, um den Nullraum von A zu finden. Der Rang A ist die Anzahl der Drehpunkte. Die Durchführung einer Gauß-Eliminierung zur Erzielung einer Echelon-Form ist jedoch nicht einfach in R zu codieren, so dass eine orthogonale Methode über QR-Faktorisierung verwendet wird. Ich glaube auch, dass dies numerisch stabiler ist.

---

was, wenn Sie Orthogonalbasis

Das obige Verfahren gibt nicht-orthogonale Basis wollen. Eine Alternative besteht darin, die QR-Faktorisierung auf t(A) (ja, es ist transponiert A) anzuwenden, den Rang zu bestimmen und die letzten freien Spalten der orthogonalen Matrix beizubehalten. Dies ergibt eine orthogonale Basis für den Lösungsraum.

Obwohl wir dies leicht codieren können, funktioniert nullspace Funktion von pracma Paket dies.

pracma::nullspace(A) 

Wenn es NULL zurückkehrt, dann bedeutet es, die Lösung ist einzigartig, nur ein Vektor von Nullen. Wenn sie eine Matrix zurückgibt, geben ihre Spalten eine orthogonale Basis.