Schnellster Algorithmus zur Berechnung der Bedingungsnummer einer großen Matrix in Matlab / Octave

9

Aus der Definition der Bedingungsnummer geht hervor, dass eine Matrixinversion erforderlich ist, um sie zu berechnen. Ich frage mich, ob für eine generische quadratische Matrix (oder besser, wenn eine symmetrische positive Bestimmtheit möglich ist) eine Matrixzerlegung ausgenutzt werden kann, um die Bedingungsnummer in a zu berechnen schneller Weg.

linear-algebra matrix condition-number Linello
quelle

7

Die Berechnung der Bedingungszahl (auch wenn sie innerhalb eines Faktors von 2 angenähert wird) scheint dieselbe Komplexität zu haben wie die Berechnung einer Faktorisierung, obwohl es in dieser Richtung keine Theoreme gibt.

Aus einem spärlichen Cholesky-Faktor einer symmetrischen positiven bestimmten Matrix oder aus einer spärlichen -Faktorisierung (mit implizitem ) einer allgemeinen quadratischen Matrix kann man die Bedingungsnummer in der Frobenius-Norm erhalten, indem man die spärliche inverse Teilmenge von berechnet , was viel schneller ist als die Berechnung der vollständigen Inversen. (Im Zusammenhang damit steht meine Arbeit: Hybride Normen und Grenzen für überbestimmte lineare Systeme, Linear Algebra Appl. 216 (1995), 257-266. Http://www.mat.univie.ac.at/~neum/scan/74 .pdf ) $R$ $QR$ $Q$ $(R^TR)^{-1}$

Bearbeiten: Wenn dann ist in Bezug auf ein einheitlich invariantes Norn $A=QR$ Zur Berechnung spärlicher QR-Faktorisierungen siehe z.B.http://dl.acm.org/citation.cfm?id=174408. Zur Berechnung der spärlichen Inversen siehe z. B. meine Arbeit: Eingeschränkte Maximum-Likelihood-Schätzung von Kovarianzen in spärlichen linearen Modellen, Genetics Selection Evolution 30 (1998), 1-24. https://www.mat.univie.ac.at/~neum/ms/reml.pdf Die Kosten betragen etwa das Dreifache der Kosten für die Faktorisierung.

c Ö n d (EIN) = c Ö n d (R.) = \sqrt{c Ö n d ({R.}^{T.} R.)} .

$cond(A)=cond(R)=\sqrt{cond(R^TR)}.$

Arnold Neumaier
quelle

Sie schlagen also Folgendes vor: Wenn eine Matrix

berechnen Sie ihren QR in der Form

wobei

eine obere Dreiecksmatrix und

eine orthogonale Matrix ist und die Bedingungsnummer durch

Hier geht es darum, eine schnelle Methode zur Berechnung einer QR-Faktorisierung zu finden. Habe ich recht?

A

$\mathbf{A}$

A = Q R

$\mathbf{A}=\mathbf{Q}\mathbf{R}$

R

$\mathbf{R}$

Q

$\mathbf{Q}$

cond (A) = | | A | | | | A^{- 1} | | (R^{T} R)^{- 1}

$\textrm{cond}(\mathbf{A})=||A|| ||A^{-1}|| (\mathbf{R}^T\mathbf{R})^{-1}$

Linello

@linello: nicht ganz; siehe meine Bearbeitung.

Arnold Neumaier

Vielen Dank! Ich werde es überprüfen, übrigens, was kostet dieser Schritt?

Linello

O (n^{3})

$O(n^3)$

4

Es ist sicherlich einfach, die Eigenwert / Eigenvektor-Zerlegung einer symmetrischen Matrix oder die SVD einer allgemeinen Matrix zur Berechnung der Bedingungsnummer zu verwenden, aber dies sind keine besonders schnellen Methoden, um fortzufahren.

$A^{-1}$ condest

Brian Borchers
quelle

Aber die Schätzung ist manchmal deutlich zu klein. Die Berechnung der Bedingungszahl (auch wenn sie innerhalb eines Faktors von 2 angenähert wird) scheint dieselbe Komplexität zu haben wie die Berechnung einer Faktorisierung, obwohl es in dieser Richtung keine Theoreme gibt.

Arnold Neumaier

1

$H$ $H$ $H^TH$

Da die größten und kleinsten Eigenwerte / Singularwerte sehr schnell gefunden werden können (lange bevor die Tridiagonalisierung abgeschlossen ist), ist die Lanczos-Methode besonders nützlich, um die Bedingungsnummer zu berechnen.

Chaohuang
quelle

Ich habe mich immer gefragt, wo ich einen lesbaren Matlab-Code für die Lanczos-Iteration finden kann, der verdeutlicht, wie man den kleinsten oder größten Eigenwert erhält. Kannst du mir einen vorschlagen?

Linello

Ich habe keine MATLAB-Codes für den Lanczos-Algorithmus.

Chaohuang

Schnellster Algorithmus zur Berechnung der Bedingungsnummer einer großen Matrix in Matlab / Octave

Antworten: