Praktyczny przykład, dlaczego odwracanie macierzy nie jest dobre

16

Zdaję sobie sprawę z tego, że odwrócenie matrycy w celu rozwiązania układu liniowego nie jest dobrym pomysłem, ponieważ nie jest tak dokładne i tak wydajne, jak bezpośrednie rozwiązywanie układu lub użycie rozkładu LU, Cholesky'ego lub QR.

Nie byłem jednak w stanie tego sprawdzić na praktycznym przykładzie. Próbowałem tego kodu (w MATLAB)

M   = 500;    
A   = rand(M,M);
A   = real(expm(1i*(A+A.')));
b   = rand(M,1);

x1  = A\b;
x2  = inv(A)*b;

disp(norm(b-A*x1))
disp(norm(b-A*x2))

a reszty są zawsze tego samego rzędu (10 ^ -13).

Czy ktoś mógłby podać praktyczny przykład, w którym inv (A) * b jest znacznie mniej niedokładne niż A \ b?

------ Aktualizacja pytania ------

Dziękuję Ci za Twoje odpowiedzi. Załóżmy jednak, że musimy rozwiązać n razy układ Ax=b , gdzie jest zawsze tą samą macierzą. Rozważ toA

- jest pełna, a tym samym wymaga tej samej pamięci w pamięci niż .AA1A

-Numer warunku jest niewielki, dlatego można obliczyć z dokładnością.AA1

Czy w takim przypadku obliczenie nie byłoby bardziej efektywne niż zastosowanie dekompozycji LU? Na przykład wypróbowałem ten kod Matlab:A1

%Set A and b:
M           = 1000; 
A           = rand(M,M);
A           = real(expm(1i*(A+A.')));
b           = rand(M,1);

%Times we solve the system:
n           = 3000;

%Performing LU decomposition:
disp('Performing LU decomposition')
tic
[L,U,P]     = lu(A);
toc
fprintf('\n')

%Solving the system n times with LU decomposition:
optsL.LT    = true;   %Options for linsolve
optsU.UT    = true;
disp('Solving the system n times using LU decomposition')
tic
for ii=1:n
    x1      = linsolve(U, linsolve(L,P*b,optsL) , optsU);
end
toc
fprintf('\n')

%Computing inverse of A:
disp('Computing inverse of A')
tic
Ainv        = inv(A);
toc
fprintf('\n')

%Solving the system n times with Ainv:
disp('Solving the system n times with A inv')
tic
for ii=1:n
    x2  = Ainv*b;
end
toc
fprintf('\n')

disp('Residuals')
disp(norm(b-A*x1))
disp(norm(b-A*x2))

disp('Condition number of A')
disp(cond(A))

Dla macierzy o liczbie warunków około 450 resztami sąO(1011) w obu przypadkach, ale rozwiązanie układu n razy przy użyciu rozkładu LU zajmuje 19 sekund, natomiast użycie odwrotności A zajmuje tylko 9 sekund.

Manu
źródło
8
strona pomocy MATLAB dla inv daje dobry przykład. Zajrzyj do sekcji zatytułowanej Rozwiąż układ liniowy .
GoHokies,
1
btw, jaki jest numer warunku macierzy ? Nie mam MATLAB na komputerze w pracy, więc nie mogę sprawdzić, ale zakładam, że jest wystarczająco mały, aby uzyskać dokładną odwrotność ...ZA
GoHokies
2
Spojrzałem na Trefethena i Baua (ćwiczenie 21.4) i opisują to wyłącznie jako koszty obliczeń, flopów vs. 22)n3)klapy. Nawet jeśli uważasz, że reszty są podobne (czy próbowałeś sprawdzać bardziej źle uwarunkowane macierze, jak w komentarzu GoHokies?), Sam niepotrzebny koszt obliczeń jest prawdopodobnie wart porady. 2)3)n3)
Kirill,
3
Rozmiar macierzy jest o wiele za mały i dobrze uwarunkowany do tego porównania. Nie chodzi o to, że nie ma istotnych problemów w przypadku takich macierzy, ale otrzymana opinia, że ​​nie należy odwracać, jest przeznaczona dla innego ustawienia (np. Tego, o którym wspomniał Chris Rackauckas w swojej odpowiedzi). W rzeczywistości w przypadku małych i - z całą pewnością - dobrze uwarunkowanych matryc, obliczenie odwrotności może być rzeczywiście lepszym rozwiązaniem. Skrajnym przypadkiem byłby macierz obrotu 3x3 (lub, bardziej realistycznie, transformacja afiniczna).
Christian Clason,
1
Jeśli musisz wielokrotnie rozwiązywać Ax=bz tym samym Ai jest wystarczająco mały, aby wziąć odwrotność, możesz zamiast tego zapisać faktoryzację LU i użyć tego ponownie.
Chris Rackauckas

Odpowiedzi:

11

Zwykle istnieje kilka głównych powodów, aby preferować rozwiązanie układu liniowego względem odwrotnego. Krótko:

  • problem z numerem warunkowym (komentarz @GoHokies)
  • problem w rzadkiej sprawie (odpowiedź @ChrisRackauckas)
  • wydajność (komentarz @Kirill)

W każdym razie, jak zauważył @ChristianClason w komentarzach, mogą być przypadki, w których użycie odwrotności jest dobrą opcją.

W notatce / artykule Alexa Druinsky'ego, Sivana Toledo, How Accurate is inv (A) * b? istnieją pewne rozważania na temat tego problemu.

x

odwrotność||xV.-x||O(κ2)(ZA)ϵmzadohjanmi) stabilny do tyłu (LU, QR, ...)||xbzadokwzarre-stzablmi-x||O(κ(ZA)ϵmzadohjanmi)

xV.

V.

V.

V.||xV.||||x||

bZA

Tak więc możliwość użycia lub odwrotności zależy od aplikacji, możesz sprawdzić artykuł i sprawdzić, czy dana sprawa spełnia warunek uzyskania stabilności wstecznej lub jeśli jej nie potrzebujesz.

Ogólnie moim zdaniem bezpieczniejsze jest rozwiązanie układu liniowego.

Mauro Vanzetto
źródło
12

Δu

ut=Δu+fa(t,u).

ZA

ut=ZAu+fa(t,u)

ZAja-γZASpecialMatrices.jl

julia> using SpecialMatrices
julia> Strang(5)
5×5 SpecialMatrices.Strang{Float64}:
 2.0  -1.0   0.0   0.0   0.0
-1.0   2.0  -1.0   0.0   0.0
 0.0  -1.0   2.0  -1.0   0.0
 0.0   0.0  -1.0   2.0  -1.0
 0.0   0.0   0.0  -1.0   2.0

nO(3)n)O(1)

Powiedzmy jednak, że chcemy odwrócić macierz.

julia> inv(collect(Strang(5)))
5×5 Array{Float64,2}:
 0.833333  0.666667  0.5  0.333333  0.166667
 0.666667  1.33333   1.0  0.666667  0.333333
 0.5       1.0       1.5  1.0       0.5
 0.333333  0.666667  1.0  1.33333   0.666667
 0.166667  0.333333  0.5  0.666667  0.833333

O(n2))

\IterativeSolvers.jlZAx=bZA-1ZA

Jak inni wspominali, numer warunku i błąd numeryczny to kolejny powód, ale fakt, że odwrotność rzadkiej macierzy jest gęsta, daje bardzo jasne „to zły pomysł”.

Chris Rackauckas
źródło