Memecahkan sistem dengan pembaruan diagonal peringkat kecil

Misalkan saya memiliki sistem linier besar, jarang: . Sekarang, saya tidak memiliki A - 1 karena A terlalu besar untuk faktor atau segala bentuk penguraian A , tetapi berasumsi bahwa saya memiliki solusi x 0 yang ditemukan dengan penyelesaian berulang.$A\textbf{x}_0=\textbf{b}_0$$A^{-1}$$A$$\textbf{x}_0$

Sekarang, saya ingin menerapkan pembaruan peringkat kecil ke diagonal A (mengubah beberapa entri diagonal): mana D adalah matriks diagonal dengan sebagian besar 0 pada diagonal dan beberapa nilai bukan nol. Jika saya memiliki A - 1 saya akan dapat mengambil keuntungan dari rumus Woodbury untuk menerapkan pembaruan ke kebalikannya. Namun, saya tidak memiliki ini tersedia. Adakah yang bisa saya lakukan selain menyelesaikan seluruh sistem lagi? Apakah ada beberapa cara yang mungkin saya dapat membuat prekondisi M yang mudah \ lebih mudah untuk dibalik, sehingga M A 1$(A+D)\textbf{x}_1=\textbf{b}_0$$D$$A^{-1}$$M$ , sehingga yang harus saya lakukan jika saya memiliki x 0 adalah menerapkan M - 1 dan metode berulang akan menyatu dalam beberapa / beberapa iterasi?$MA_1 \approx A_0$$\textbf{x}_0$$M^{-1}$

1. Simpan di kolom dua matriks dan C semua vektor b j yang Anda terapkan matriks dalam iterasi sebelumnya dan hasilnya c j = A b j .$B$$C$$b_j$$c_j=Ab_j$

2. Untuk setiap sistem baru (atau A x = b ′ , yang merupakan kasus khusus D = 0 ), kira-kira selesaikan sistem linear yang terlalu ditentukan ( C + D B ) y ≈ b ′ , misalnya , dengan memilih subset dari baris (mungkin semua) dan menggunakan metode kuadrat terkecil padat. Perhatikan bahwa hanya bagian C + D B yang dipilih yang perlu dirakit; jadi ini adalah operasi yang cepat!$(A+D)x'=b'$$Ax=b'$$D=0$$(C+DB)y\approx b'$$C+DB$

3. Masukkan . Ini adalah perkiraan awal yang baik untuk memulai iterasi untuk menyelesaikan ( A + D ) x ′ = b ′ . Jika sistem lebih lanjut harus diproses, gunakan produk vektor matriks dalam iterasi baru ini untuk memperluas matriks B dan C pada subsistem yang dihasilkan.$x_0=By$$(A+D)x'=b'$$B$$C$

Jika matriks dan C tidak sesuai dengan memori utama, simpan B pada disk, dan pilih subset baris terlebih dahulu. Ini memungkinkan Anda untuk tetap inti bagian yang relevan dari B dan C yang diperlukan untuk membentuk sistem kuadrat terkecil, dan x 0 berikutnya dapat dihitung dengan satu melewati B dengan sedikit penggunaan memori inti.$B$$C$$B$$B$$C$$x_0$$B$

Baris harus dipilih sedemikian rupa sehingga kira-kira sesuai dengan diskritisasi kasar dari masalah penuh. Mengambil baris lima kali lebih banyak dari jumlah total perkalian vektor matriks yang diharapkan sudah cukup.

Sunting: Mengapa ini berfungsi? Dengan konstruksi, matriks dan C terkait dengan C = A B . Jika subruang yang direntang oleh kolom B berisi vektor solusi yang tepat x ′ (situasi yang jarang tetapi sederhana) maka x ′ memiliki bentuk x ′ = B y untuk beberapa y . Mengganti ini menjadi persamaan yang mendefinisikan x ′ memberikan persamaan ( C + D B ) y = b $B$$C$$C=AB$$B$$x'$$x'$$x'=By$$y$$x'$$(C+DB)y= b'$. Jadi dalam hal ini, proses di atas memberikan titik awal , yang merupakan solusi tepat.$x_0=By=x'$

Pada umumnya, satu tidak bisa mengharapkan untuk berbaring di ruang kolom dari B , tapi titik awal yang dihasilkan akan menjadi titik dalam ruang cloumn ini paling dekat dengan x ' , di metrik ditentukan oleh baris yang dipilih. Dengan demikian itu kemungkinan merupakan pendekatan yang masuk akal. Ketika lebih banyak sistem diproses, ruang kolom tumbuh dan perkiraan akan cenderung meningkat banyak, sehingga orang dapat berharap untuk bertemu dalam iterasi yang lebih sedikit dan lebih sedikit.$x'$$B$$x'$

Sunting2: Tentang subruang yang dihasilkan: Jika seseorang memecahkan setiap sistem dengan metode Krylov, vektor yang digunakan untuk mendapatkan titik awal untuk sistem kedua span subruang Krylov dari sisi kanan pertama. Dengan demikian orang mendapatkan perkiraan yang baik setiap kali ruang bagian Krylov ini mengandung vektor dekat dengan solusi sistem kedua Anda. Secara umum, vektor digunakan untuk mendapatkan titik awal untuk rentang sistem st ruang yang berisi Krylov ruang bagian pertama k sisi kanan.$(k+1)$$k$