Solver linear iteratif mana yang konvergen untuk matriks semidefinit positif?

Saya ingin tahu yang mana dari pemecah linear klasik (mis. Gauss-Seidel, Jacobi, SOR) dijamin akan menyatu untuk masalah mana adalah positif setengah pasti dan tentu saja $Ax=b$ $A$ $b \in im(A)$

(Pemberitahuan adalah semi pasti dan tidak pasti) $A$

linear-algebra iterative-method convergence linear-solver olamundo
sumber

Apakah maksud Anda matriks semi-pasti positif?

meawoppl

Apa gunanya menyelesaikan sistem linear dengan matriks seperti itu? Jika saya tidak salah, jika matriks semidefinite positif Anda non-singular maka itu pasti positif.

faleichik

Ya saya yakin. Saya harus menyegarkan ingatan saya sebagai bukti aktual, tetapi sesuai dengan apa yang Anda katakan - jika penyebut dalam perhitungan

adalah nol, itu berarti

adalah nol, yang berarti bahwa semua "arah pencarian" di mana A bukan singular telah habis, dan residu yang tersisa tidak dalam rentang A (dan dengan demikian ini adalah solusi "optimal"). Dalam kasus yang sebenarnya

, ini tidak akan terjadi sebagai sisa akan mencapai nol sebelum pertama kalinya

α

$\alpha$

A P_{k}

$A P_k$

b \in s p a n (A)

$b \in span(A)$

A P_{k} = 0

$AP_k=0$

olamundo

Set

. Kemudian

. CG akan konvergen karena

x_{0} = b

$x_0=b$

A^{n} b \in I m (A)

$A^nb\in Im(A)$

x_{n}^{*} A x_{n} > 0

$x_n^\ast Ax_n> 0$ untuk semua

. Dengan kata lain, Anda tidak pernah meninggalkan

yang

pasti-positif.

0 \neq x_{n} \in I m (A)

$0\ne x_n\in Im(A)$

I m (A)

$Im(A)$

A

$A$

Deathbreath

@faleichik: matriks kerapatan tereduksi dalam mekanika kuantum adalah semi-pasti positif dalam banyak kasus.

Deathbreath

Jawaban:

Algoritma gradien konjugasi bekerja untuk masalah semidefinite dan menghasilkan solusi norma minimal.

Arnold Neumaier
sumber

Terima kasih. Setiap ide tentang pemecah "kuno", misalnya SOR Gauss-Seidel dll.

olamundo

Mereka hampir tidak pernah digunakan lagi, dan saya tidak tahu bagaimana ini berperilaku.

Arnold Neumaier

Untuk mengklarifikasi: CG pasti tidak bekerja dalam bentuk vanilla untuk matriks semi-pasti; ini dapat bekerja secara teori jika B berada dalam citra A; tetapi ini tidak mungkin berakhir dengan baik dalam praktik numerik. MINRES berbasis krylov yang sangat mirip adalah pilihan yang jauh lebih baik di sini. Juga, ini "kuno" pemecah banyak digunakan dalam pemecah tipe multigrid, untuk menyebutkan satu contoh.

Eelco Hoogendoorn

Berikut ini adalah bukti bahwa Gauss-Seidel cocok dengan kebutuhan Anda, mengingat bahwa ada dalam citra $b$ $A$ .

Hal yang sama sangat tidak benar pada Jacobi; yang memalukan karena siapa yang mau repot dengan Gauss-Seidel pada perangkat keras komputer modern? Jika masalah Anda dapat dipecah menjadi blok-blok yang dominan diagonal, Anda beruntung; Anda dapat menerapkan pembaruan Jacobi ke blok-blok tersebut dengan cara Gauss-Seidel tambahan, dan dapatkan yang terbaik dari keduanya untuk jenis masalah semi-pasti ini.

Eelco Hoogendoorn
sumber