scipy.sparse.linalg.

lsmr

scipy.sparse.linalg.lsmr(A, b, damp=0.0, atol=1e-06, btol=1e-06, conlim=100000000.0, maxiter=None, show=False, x0=None)

Iterativer Löser für Kleinstquadratprobleme.

lsmr löst das System linearer Gleichungen Ax = b. Wenn das System inkonsistent ist, löst es das Kleinstquadratproblem min ||b - Ax||_2. A ist eine rechteckige Matrix der Dimension m-mal-n, wobei alle Fälle erlaubt sind: m = n, m > n oder m < n. b ist ein Vektor der Länge m. Die Matrix A kann dicht oder dünn besetzt (üblicherweise dünn besetzt) sein.

Parameter:

A{sparse array, ndarray, LinearOperator}

Matrix A im linearen System. Alternativ kann A ein linearer Operator sein, der Ax und A^H x erzeugen kann, z.B. mit scipy.sparse.linalg.LinearOperator.

barray_like, shape (m,)

Vektor b im linearen System.

dampfloat

Dämpfungsfaktor für regularisierte Kleinstquadrate. lsmr löst das regularisierte Kleinstquadratproblem

min ||(b) - (  A   )x||
    ||(0)   (damp*I) ||_2

wobei damp eine Skalare ist. Wenn damp None oder 0 ist, wird das System ohne Regularisierung gelöst. Standard ist 0.

atol, btolfloat, optional

Abbruchtoleranzen. lsmr setzt die Iterationen fort, bis ein bestimmter Rückwärtsfehlerschätzer kleiner ist als eine bestimmte Größe, die von atol und btol abhängt. Sei r = b - Ax der Residuenvektor für die aktuelle Näherungslösung x. Wenn Ax = b konsistent zu sein scheint, endet lsmr, wenn norm(r) <= atol * norm(A) * norm(x) + btol * norm(b). Andernfalls endet lsmr, wenn norm(A^H r) <= atol * norm(A) * norm(r). Wenn beide Toleranzen 1.0e-6 (Standard) sind, sollte das finale norm(r) auf etwa 6 Stellen genau sein. (Das finale x wird normalerweise weniger korrekte Stellen haben, abhängig von cond(A) und der Größe von LAMBDA.) Wenn atol oder btol None ist, wird ein Standardwert von 1.0e-6 verwendet. Idealerweise sollten sie Schätzungen des relativen Fehlers in den Einträgen von A und b sein. Wenn beispielsweise die Einträge von A 7 korrekte Stellen haben, setzen Sie atol = 1e-7. Dies verhindert, dass der Algorithmus unnötige Arbeit über die Unsicherheit der Eingabedaten hinaus leistet.

conlimfloat, optional

lsmr bricht ab, wenn ein Schätzer von cond(A) conlim überschreitet. Für kompatible Systeme Ax = b kann conlim bis zu 1.0e+12 (z.B.) betragen. Für Kleinstquadratprobleme sollte conlim kleiner als 1.0e+8 sein. Wenn conlim None ist, beträgt der Standardwert 1e+8. Maximale Genauigkeit kann durch Setzen von atol = btol = conlim = 0 erreicht werden, aber die Anzahl der Iterationen kann dann übermäßig sein. Standard ist 1e8.

maxiterint, optional

lsmr bricht ab, wenn die Anzahl der Iterationen maxiter erreicht. Der Standardwert ist maxiter = min(m, n). Für schlecht konditionierte Systeme kann ein größerer Wert für maxiter erforderlich sein. Standard ist False.

showbool, optional

Protokolliert Iterationen, wenn show=True. Standard ist False.

x0array_like, shape (n,), optional

Anfangsschätzung von x, wenn None werden Nullen verwendet. Standard ist None.

Hinzugefügt in Version 1.0.0.

Rückgabe:

xndarray of float

Zurückgegebene Kleinstquadratlösung.

istopint

istop gibt den Grund für den Abbruch an

istop   = 0 means x=0 is a solution.  If x0 was given, then x=x0 is a
            solution.
        = 1 means x is an approximate solution to A@x = B,
            according to atol and btol.
        = 2 means x approximately solves the least-squares problem
            according to atol.
        = 3 means COND(A) seems to be greater than CONLIM.
        = 4 is the same as 1 with atol = btol = eps (machine
            precision)
        = 5 is the same as 2 with atol = eps.
        = 6 is the same as 3 with CONLIM = 1/eps.
        = 7 means ITN reached maxiter before the other stopping
            conditions were satisfied.

itnint

Verwendete Iterationsanzahl.

normrfloat

norm(b-Ax)

normarfloat

norm(A^H (b - Ax))

normafloat

norm(A)

condafloat

Konditionszahl von A.

normxfloat

norm(x)

Hinweise

Hinzugefügt in Version 0.11.0.

Referenzen

[1]

D. C.-L. Fong und M. A. Saunders, „LSMR: An iterative algorithm for sparse least-squares problems“, SIAM J. Sci. Comput., Bd. 33, S. 2950-2971, 2011. arXiv:1006.0758

[2]

LSMR-Software, https://web.stanford.edu/group/SOL/software/lsmr/

Beispiele

Probieren Sie es in Ihrem Browser aus!

>>> import numpy as np
>>> from scipy.sparse import csc_array
>>> from scipy.sparse.linalg import lsmr
>>> A = csc_array([[1., 0.], [1., 1.], [0., 1.]], dtype=float)

Das erste Beispiel hat die triviale Lösung [0, 0]

>>> b = np.array([0., 0., 0.], dtype=float)
>>> x, istop, itn, normr = lsmr(A, b)[:4]
>>> istop
0
>>> x
array([0., 0.])

Der Abbruchcode istop=0 zeigt an, dass ein Nullvektor als Lösung gefunden wurde. Die zurückgegebene Lösung x enthält tatsächlich [0., 0.]. Das nächste Beispiel hat eine nicht-triviale Lösung

>>> b = np.array([1., 0., -1.], dtype=float)
>>> x, istop, itn, normr = lsmr(A, b)[:4]
>>> istop
1
>>> x
array([ 1., -1.])
>>> itn
1
>>> normr
4.440892098500627e-16

Wie durch istop=1 angezeigt, hat lsmr eine Lösung gefunden, die den Toleranzgrenzen entspricht. Die gegebene Lösung [1., -1.] löst offensichtlich die Gleichung. Die restlichen Rückgabewerte enthalten Informationen über die Anzahl der Iterationen (itn=1) und die verbleibende Differenz zwischen linker und rechter Seite der gelösten Gleichung. Das letzte Beispiel demonstriert das Verhalten im Fall, dass keine Lösung für die Gleichung existiert

>>> b = np.array([1., 0.01, -1.], dtype=float)
>>> x, istop, itn, normr = lsmr(A, b)[:4]
>>> istop
2
>>> x
array([ 1.00333333, -0.99666667])
>>> A.dot(x)-b
array([ 0.00333333, -0.00333333,  0.00333333])
>>> normr
0.005773502691896255

istop zeigt an, dass das System inkonsistent ist und x somit eher eine ungefähre Lösung des entsprechenden Kleinstquadratproblems ist. normr enthält die minimal gefundene Distanz.

ZurückIn Tab öffnen