Wiederholtes Lösen von

Ich verwende MATLAB, um ein Problem zu lösen, bei dem zu jedem Zeitpunkt gelöst wird, wobei sich mit der Zeit ändert. Im Moment mache ich das mit MATLABs :$\mathbf{A} \mathbf{x}=\mathbf{b}$$\mathbf{b}$mldivide

x = A\b

Ich habe die Flexibilität, so viele Vorberechnungen wie nötig durchzuführen, und frage mich, ob es eine schnellere und / oder genauere Methode als gibt mldivide. Was wird hier typischerweise gemacht? Vielen Dank an alle!

Das offensichtlichste, was Sie tun können, ist die Vorausberechnung

[L,U] = lu(A) ~ O (n ^ 3)

Dann rechnest du einfach

x = U \ (L \ b) ~ O (2 n ^ 2)

Dies würde die Kosten enorm senken und beschleunigen. Die Genauigkeit wäre gleich.

Zu diesem Thema haben wir in unseren Kursen zum wissenschaftlichen Rechnen einige umfangreiche Computerlabore durchgeführt. Für die "kleinen" Berechnungen, die wir dort durchgeführt haben, war der Backslash-Operator von Matlab immer schneller als alles andere, auch nachdem wir unseren Code so weit wie möglich optimiert und alle Matrizen zuvor neu angeordnet hatten (zum Beispiel mit der Bestellung von Reverse Cuthill McKee für dünne Matrizen). .

Sie können eine unserer Laboranweisungen lesen . Die Antwort auf Ihre Frage wird (in Kürze) auf Seite 4 behandelt.

Ein gutes Buch zu diesem Thema wurde zum Beispiel von Cheney geschrieben .

Angenommen, ist eine n × n dichte Matrix und Sie müssen A x i = b i , i = 1 … m lösen . Wenn m ist groß genug , dann gibt es nichts falsch in$A$$n\times n$ $Ax_i = b_i$$i=1\dots m$$m$

V = inv(A);
...
x = V*b;

Flops sind für und O ( n 2 ) für , daher sind einige Experimente erforderlich , um den Break-Even-Wert für m zu bestimmen ...$O(n^3)$inv(A)$O(n^2)$V*b$m$

>> n = 5000;
>> A = randn(n,n);
>> x = randn(n,1);
>> b = A*x;
>> rcond(A)
ans =
   1.3837e-06
>> tic, xm = A\b; toc
Elapsed time is 1.907102 seconds.
>> tic, [L,U] = lu(A); toc
Elapsed time is 1.818247 seconds.
>> tic, xl = U\(L\b); toc
Elapsed time is 0.399051 seconds.
>> tic, [L,U,p] = lu(A,'vector'); toc
Elapsed time is 1.581756 seconds.
>> tic, xp = U\(L\b(p)); toc
Elapsed time is 0.060203 seconds.
>> tic, V=inv(A); toc
Elapsed time is 7.614582 seconds.
>> tic, xv = V*b; toc     
Elapsed time is 0.011499 seconds.
>> [norm(xm-x), norm(xp-x), norm(xl-x), norm(xv-x)] ./ norm(x)
ans =
   1.0e-11 *
    0.1912    0.1912    0.1912    0.6183

$A^{-1}$$LU$$m>125$

Einige Notizen

Informationen zur Stabilität und Fehleranalyse finden Sie in den Kommentaren zu dieser anderen Antwort , insbesondere der von VictorLiu.

$m\ll n$

Das Timing wurde mit Matlab R2011b auf einem 12-Kern-Computer mit einem ziemlich konstanten UNIX-Lastdurchschnitt von 5 durchgeführt. beste tic, tocZeit von drei Sonden.

Werfen Sie einen Blick auf diese Frage , die Antworten zeigen, dass sie mldivideziemlich clever ist, und geben Sie auch Vorschläge, wie Sie sehen können, was Matlab zur Lösung verwendet A\b. Dies kann Ihnen einen Hinweis zu den Optimierungsoptionen geben.

Die Verwendung von Backslash ist mehr oder weniger gleichbedeutend mit inv(A)*Bder intuitiven Codierung. Sie sind ungefähr gleich (nur in der Art und Weise, wie die Berechnung durchgeführt wird), obwohl Sie die Matlab-Dokumentation zur Verdeutlichung überprüfen sollten.

Um Ihre Frage zu beantworten, ist Backslash im Allgemeinen in Ordnung, es hängt jedoch von den Eigenschaften der Massenmatrix ab.