Bagaimana NumPy memecahkan kuadrat terkecil untuk sistem yang tidak ditentukan?

14

Katakanlah kita memiliki X bentuk (2, 5)
dan y bentuk (2,)

Ini bekerja: np.linalg.lstsq(X, y)

Kami berharap ini berfungsi hanya jika X adalah bentuk (N, 5) di mana N> = 5 Tapi mengapa dan bagaimana?

Kami mendapatkan kembali 5 bobot seperti yang diharapkan, tetapi bagaimana masalah ini diselesaikan?

Bukankah kita memiliki 2 persamaan dan 5 yang tidak diketahui?
Bagaimana numpy bisa menyelesaikan ini?
Itu harus melakukan sesuatu seperti interpolasi untuk membuat lebih banyak persamaan buatan? ..

George Pligoropoulos
sumber
3
Mengapa itu tidak berhasil? Sistem yang tidak ditentukan memiliki banyak solusi.
Matthew Gunn
Apakah Anda mungkin memiliki tautan ke teori yang relevan? ..
George Pligoropoulos

Jawaban:

19

Pemahaman saya adalah bahwa numpy.linalg.lstsq bergantung pada dgelsd rutin LAPACK .

Masalahnya adalah untuk menyelesaikan:

minimize(overx)Axb2

Tentu saja, ini tidak memiliki solusi unik untuk matriks A yang peringkatnya kurang dari panjang vektor . Dalam kasus sistem yang tidak ditentukan, solusi sedemikian rupa sehingga:bdgelsdz

  • Az=b
  • z2x2 untuk semua yang memenuhi . (yaitu adalah solusi norma minimum untuk sistem yang tidak ditentukan.xAx=bz

Contoh, jika sistem , numpy.linalg.lstsq akan mengembalikan .x+y=1x=.5,y=.5

Bagaimana cara kerja dgelsd?

Rutin dgelsdmenghitung dekomposisi nilai singular (SVD) dari A.

Saya hanya akan membuat sketsa ide di balik menggunakan SVD untuk menyelesaikan sistem linear. Dekomposisi nilai singular adalah faktorisasi mana dan adalah matriks ortogonal dan adalah matriks diagonal di mana entri diagonal dikenal sebagai nilai singular.UΣV=AUVΣ

Peringkat efektif matriks adalah jumlah nilai singular yang secara efektif bukan nol (yaitu cukup berbeda dari nol relatif terhadap presisi mesin dll ...). Biarkan menjadi matriks diagonal dari nilai singular non-nol. SVD demikian:AS

A=U[S000]V

The pseudo-inverse dari diberikan oleh:A

A=V[S1000]U

Pertimbangkan solusinya . Kemudian:x=Ab

Axb=U[S000]VV[S1000]Ubb=U[I000]Ubb

Pada dasarnya ada dua kasus di sini:

  1. Jumlah nilai singular non-nol (yaitu ukuran matriks ) kurang dari panjang . Solusi di sini tidak akan tepat; kami akan memecahkan sistem linear dalam arti kuadrat terkecil.Ib
  2. Axb=0

Bagian terakhir ini agak sulit ... perlu melacak dimensi matriks dan menggunakan bahwa adalah matriks ortogonal.U

Kesetaraan dari invers semu

Ketika memiliki baris bebas linear, (mis. Kami memiliki matriks gemuk), maka: A

A=A(AA)1

Untuk sistem yang tidak ditentukan, Anda dapat menunjukkan bahwa invers semu memberi Anda solusi norma minimum.

Ketika memiliki kolom yang bebas linear, (mis. Kami memiliki matriks kurus), maka: A

A=(AA)1A

Matthew Gunn
sumber
dgelsd menggunakan SVD tetapi Rm menggunakan QR?
Haitao Du
@ hxd1011R lmmenggunakan faktorisasi QR secara default tetapi Anda dapat menentukan alternatif.
Sycorax berkata Reinstate Monica