Apa kompleksitas kasus terburuk dari Conjugate Gradient?

9

Biarkan ARn×n , simetris dan pasti positif. Misalkan dibutuhkan m unit kerja untuk memperbanyak vektor oleh A . Diketahui bahwa melakukan algoritma CG pada A dengan kondisi nomor κ membutuhkan O(mκ), unit kerja.

Sekarang, tentu saja, sebagai pernyataan O ini adalah batas atas. Dan algoritma CG selalu dapat berakhir dalam nol langkah dengan tebakan awal yang beruntung.

Apakah kita tahu jika ada RHS dan tebakan awal (sial) yang membutuhkan Θ(κ)langkah? Dengan kata lain, apakah kompleksitas kerja kasus terburuk dari CG benar-benarΘ(mκ)?

Pertanyaan ini muncul ketika saya mencoba menentukan apakah manfaat dari prekondisi ( lebih rendah κ) melebihi biayanya (lebih tinggi m ). Saat ini, saya bekerja dengan masalah mainan dan ingin memiliki ide yang lebih baik sebelum saya menerapkan apa pun dalam bahasa yang dikompilasi.

fred
sumber
5
Anda mungkin dapat membuat dugaan awal pesimis dengan menjalankan algoritme CG "mundur" dan memasukkan energi yang sesuai ke masing-masing arahan pencarian A ortogonal yang dibutuhkan semua langkah.
origimbo

Jawaban:

9

Jawabannya adalah ya. Batas laju konvergensi tajam pada himpunan matriks pasti positif simetris dengan nomor kondisiκ. Dengan kata lain, mengetahui apa-apa tentangAdaripada jumlah kondisinya, CG benar-benar dapat mengambil(κ1)/(κ+1)κA iterasi untuk konvergen. Secara longgar, batas atas diperoleh jika nilai eigen dariAterdistribusi secara seragam (yaitu "dibumbui") dalam interval angka kondisiκ.κAκ

Ini pernyataan yang lebih keras. Versi deterministik lebih banyak terlibat tetapi bekerja menggunakan prinsip yang sama.

Teorema (Pilihan kasus terburuk dari ). Pilih salah satu matriks ortogonal acak U , misalkan λ 1 , , λ n menjadi bilangan real yang diambil secara sampel dari interval nyata [ 1 , κ ] , dan misalkan b = [ b 1 ; ... ; b n ] menjadi n bilangan real yang diambil sampel dari Gaussian standar. Tentukan A = U d i a g ( λ 1 ,AUλ1,,λnn[1,κ]b=[b1;;bn]nKemudian pada batas n , gradien konjugat akan bertemu dengan probabilitas satu ke ϵ solusi akurat A x = b dalam tidak kurang dari Ω (

A=Udiag(λ1,,λn)UT.
nϵAx=biterasi.Ω(κlogϵ1)

Bukti. Bukti standar didasarkan pada perkiraan polinomial Chebyshev yang optimal, menggunakan teknik yang ditemukan di sejumlah tempat, seperti buku Greenbaum atau buku Saad .

Richard Zhang
sumber
1
Batasnya tidak tajam, seperti jawaban yang dijelaskan kemudian, Jika nilai eigen tidak terdistribusi secara merata, cg konvergen lebih cepat, karena itu bukan iterasi stasional. Jadi, kita perlu tahu lebih banyak tentang matriks.
Guido Kanschat
Aκ
p(A)kp(0)=1minpmaxλΛ(A)|p(λ)|Λ(A)[1,κ]κ
0

Mengambil ini sebagai pertanyaan awal saya: Apakah kita tahu jika ada RHS dan tebakan awal (tidak beruntung) yang memerlukan langkah-langkah ?Θ(κ)

Jawaban atas pertanyaannya adalah "tidak". Ide jawaban ini berasal dari komentar dari Guido Kanschat.

Klaim: Untuk setiap nomor kondisi diberikan , terdapat matriks , dengan nomor kondisi yang akan diakhiri algoritma CG paling banyak dalam dua langkah (untuk RHS dan tebakan awal yang diberikan).kA

Pertimbangkan mana . Maka nomor kondisi adalah . Biarkan menjadi RHS, dan tunjukkan nilai eigen dari sebagai mana ARn×nA=diag(1,κ,κ,,κ)AκbRnAλi

λi={1i=1κi1.

Kami pertama-tama mempertimbangkan kasus di mana , tebakan awal, adalah nol. Nyatakan sebagai estimasi kedua dari algoritma CG. Kami menunjukkan bahwa dengan menunjukkan . Memang sudahx(0)Rnx(2)RnA1bx(2)=A1bx(2)A1b,A(x(2)A1b)=0

x(2)A1b,A(x(2)A1b)=x(2)A1bA2=minppoly1(p(A)A1)bA2=minppoly1i=1n(p(λi)λi1)2λibi2i=1n(p^(λi)λi1)2λibi2=0

Di mana kami menggunakan polinomial orde pertama didefinisikan sebagai . Jadi kami membuktikan kasus untuk .p^p^(x)=(1+κx)/κx(0)=0

Jika , maka mana adalah estimasi kedua dari algoritma CG dengan diganti dengan . Jadi kami telah mengurangi kasus ini ke yang sebelumnya. x(0)0x(2)=x(2)¯+x(0)x(2)¯bb¯=bAx(0)

fred
sumber
Berapa banyak dari ini yang kuat untuk aritmatika presisi terbatas?
origimbo
@origimbo Jika pertanyaan Anda ditujukan kepada saya, jawabannya adalah, "Saya tidak tahu."
fred