Contoh praktis mengapa tidak baik untuk membalikkan matriks

16

Saya sadar bahwa membalikkan matriks untuk menyelesaikan sistem linear bukanlah ide yang baik, karena itu tidak seakurat dan seefisien langsung memecahkan sistem atau menggunakan LU, Cholesky atau penguraian QR.

Namun, saya belum dapat memeriksa ini dengan contoh praktis. Saya telah mencoba kode ini (dalam 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))

dan residu selalu dalam urutan yang sama (10 ^ -13).

Bisakah seseorang memberikan contoh praktis di mana inv (A) * b jauh kurang akurat daripada A \ b?

------ Pembaruan pertanyaan ------

Terima kasih atas jawaban anda Namun, misalkan kita harus menyelesaikan kali suatu sistem , di mana selalu matriks yang sama. Pertimbangkan itunAx=bA

- penuh, dan dengan demikian membutuhkan penyimpanan memori yang sama dari .AA1A

-Jumlah kondisi A kecil, maka A1 dapat dihitung dengan akurasi.

Dalam hal itu, bukankah lebih efisien untuk menghitung daripada menggunakan dekomposisi LU? Misalnya, saya sudah mencoba kode Matlab ini: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))

Untuk matriks dengan angka kondisi sekitar 450, residualnya adalah dalam kedua kasus, tetapi dibutuhkan 19 detik untuk menyelesaikan sistem n kali menggunakan dekomposisi LU, sedangkan menggunakan inversi A hanya dibutuhkan 9 detik.O(1011)

Manu
sumber
8
halaman bantuan MATLAB untuk inv memberikan contoh yang baik. Lihat di bawah bagian berjudul Solve Linear System .
GoHokies
1
btw, berapakah nomor kondisi dari matriks Anda ? Saya tidak punya MATLAB di PC saya di tempat kerja jadi saya tidak bisa memeriksa, tapi saya kira itu cukup kecil bagi Anda untuk mendapatkan invers yang akurat ...A
GoHokies
2
Saya telah melihat Trefethen dan Bau (latihan 21.4), dan mereka menggambarkannya murni dari segi biaya perhitungan, jepit vs 22n3jepit. Jadi, bahkan jika Anda menemukan residu yang serupa (pernahkah Anda mencoba memeriksa matriks yang lebih buruk, seperti dalam komentar GoHokies?), Biaya perhitungan yang tidak perlu saja mungkin bernilai nasihat. 23n3
Kirill
3
Ukuran matriks Anda terlalu kecil dan dikondisikan dengan baik untuk perbandingan ini. Bukan berarti tidak ada masalah yang relevan di mana Anda memiliki matriks seperti itu, tetapi pendapat yang diterima bahwa Anda tidak boleh membalikkan dimaksudkan untuk pengaturan yang berbeda (misalnya, yang disebutkan oleh Chris Rackauckas dalam jawabannya). Bahkan, untuk matriks kecil dan - yang dapat disertifikasi - dikondisikan dengan baik, menghitung invers mungkin menjadi pilihan yang lebih baik. Kasus ekstrem adalah matriks 3x3 rotasi (atau, lebih realistis, transformasi affine).
Christian Clason
1
Jika Anda perlu berulang kali menyelesaikannya Ax=bdengan hal yang sama Adan cukup kecil untuk mengambil kebalikannya, Anda dapat menyimpan faktorisasi LU dan menggunakannya kembali.
Chris Rackauckas

Jawaban:

11

Biasanya ada beberapa alasan utama untuk lebih suka memecahkan sistem linear sehubungan dengan menggunakan invers. Secara singkat:

  • masalah dengan nomor kondisional (komentar @GoHokies)
  • masalah dalam kasus jarang (jawaban @ChrisRackauckas)
  • efisiensi (@Kirill komentar)

Bagaimanapun, seperti yang dikatakan @ChristianClason dalam komentar, bisa jadi ada beberapa kasus di mana penggunaan invers adalah pilihan yang baik.

Dalam catatan / artikel oleh Alex Druinsky, Sivan Toledo, How Accurate is inv (A) * b? ada beberapa pertimbangan tentang masalah ini.

x

inverse||xVx||O(κ2(A)ϵmachine) backward stable (LU, QR,...)||xbackwardstablex||O(κ(A)ϵmachine)

xV

V

V

V||xV||||x||

bA

Jadi, peluang untuk menggunakan atau tidak, kebalikannya bergantung pada aplikasi, semoga Anda dapat memeriksa artikel dan melihat apakah Anda memenuhi syarat untuk mendapatkan stabilitas mundur atau jika Anda tidak membutuhkannya.

Secara umum, menurut saya, lebih aman menyelesaikan sistem linear.

Mauro Vanzetto
sumber
12

Δu

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

A

ut=Au+f(t,u)

AIγASpecialMatrices.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(3n)O(1)

Namun, katakanlah kita ingin membalikkan matriks.

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.jlAx=bA1A

Seperti yang telah disebutkan orang lain, angka kondisi dan kesalahan numerik adalah alasan lain, tetapi fakta bahwa kebalikan dari matriks jarang padat memberikan sangat jelas "ini adalah ide yang buruk".

Chris Rackauckas
sumber