Aplikasi aman dari metode berulang pada matriks dominan diagonal

Misalkan sistem linear berikut ini diberikan mana adalah Laplacian tertimbang yang dikenal sebagai pasti positif dengan ruang nol satu dimensi yang dibentang oleh , dan variasi terjemahan , yaitu, tidak mengubah nilai fungsi (yang turunannya adalah ). Satu-satunya entri positif adalah diagonal, yang merupakan penjumlahan dari nilai absolut entri negatif di-diagonal.

\begin{matrix} (1) & L x = c, \end{matrix}

$Lx=c,\tag1$

L

$L$

s e m i -

$semi-$

1_{n} = (1, \dots, 1) \in R^{n}

$1_n=(1,\dots,1)\in\mathbb{R}^n$

x \in R^{n}

$x\in\mathbb{R}^{n}$

x + a 1_{n}

$x+a1_n$

(1)

$(1)$

L

$L$

Saya menemukan di satu yang sangat dikutip karya akademis di bidangnya bahwa, meskipun $L$ adalah $not~strictly$ diagonal dominan, metode seperti Conjugate Gradient, Gauss-Seidl, Jacobi, masih bisa aman digunakan untuk memecahkan $(1)$ . Alasannya adalah bahwa, karena invarian terjemahan, seseorang aman untuk memperbaiki satu titik (misalnya, menghapus baris pertama dan kolom $L$ dan entri pertama dari $c$ ), sehingga mengubah $L$ ke matriks dominan diagonal $strictly$ . Bagaimanapun, sistem asli diselesaikan dalam bentuk penuh $(1)$ , dengan $L\in\mathbb{R}^{n\times n}$ .

Apakah asumsi ini benar, dan, jika demikian, apa alasan alternatifnya? Saya mencoba memahami bagaimana konvergensi metode masih berlaku.

Jika metode Jacobi konvergen dengan $(1)$ , apa yang bisa salah satu negara tentang spektral radius $\rho$ dari iterasi matriks $D^{-1}(D-L)$ , di mana $D$ adalah matriks diagonal dengan entri dari $L$ pada diagonal? Apakah $\rho(D^{-1}(D-L)\leq1$ , sehingga berbeda dengan jaminan konvergensi umum untuk $\rho(D^{-1}(D-L))<1$ ? Aku bertanya ini karena nilai eigen dari Matriks Laplacian $D^{-1}L$ dengan yang ada di diagonal harus dalam kisaran $[0, 2]$ .

Dari karya aslinya:

..........................................

Pada setiap iterasi, kami menghitung tata letak baru (x (t +1), y (t + 1)) dengan menyelesaikan sistem linear berikut: Tanpa kehilangan generalitas kita dapat memperbaiki lokasi salah satu sensor-sensor (memanfaatkan tingkat kebebasan penerjemahan dari tekanan yang terlokalisasi) dan memperoleh matriks dominan diagonal yang ketat. Oleh karena itu, kita dapat dengan aman menggunakan iterasi Jacobi untuk menyelesaikan (8)

\begin{matrix} (8) & L \cdot x (t + 1) = L (x (t), y (t)) \cdot x (t) L \cdot y (t + 1) = L (x (t), y (t)) \cdot y (t) \end{matrix}

$L · x(t + 1) = L(x(t),y(t)) · x(t) \\ L · y(t + 1) = L(x(t),y(t)) · y(t) \tag 8$

.......................................

Dalam hal di atas, gagasan "iterasi" terkait dengan prosedur minimisasi yang mendasarinya, dan tidak harus dikacaukan dengan iterasi Jacobi. Jadi, sistem diselesaikan oleh Jacobi (iteratif), dan kemudian solusi dibeli ke sisi kanan (8), tetapi sekarang untuk iterasi lain dari minimisasi yang mendasarinya. Saya harap ini menjelaskan masalah ini.

Perhatikan bahwa saya menemukan Solver linier iteratif yang menyatu untuk matriks semidefinit positif? , tetapi saya mencari jawaban yang lebih rumit.

linear-algebra optimization iterative-method matrix linear-solver usero
sumber

Bisakah Anda memposting tautan atau kutipan ke karya yang sangat dikutip?

Geoff Oxberry

Itu bisa diambil dari: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.164.1421 Karena Anda tidak diharapkan untuk membaca seluruh pekerjaan, lihat halaman 7 (bawah). Saya kira pilihan pemecah iteratif dibenarkan, tetapi saya merasa alasan yang lebih baik (atau, setidaknya, berbeda) diperlukan.

usero

Saya bertanya-tanya apakah orang-orang ini berasal dari komunitas yang sama dengan prasyarat kombinasi.

shuhalo

Jawaban:

Iterasi Jacobi dapat dibuktikan konvergen.

Hal pertama yang harus Anda pastikan adalah , yang merupakan kondisi untuk adanya solusi (saya berasumsi , jika tidak, Anda perlu ) karena Anda mengatakan . Kami akan menggunakan konvensi bahwa $c^T \mathbf{1}_n = 0$ $L=L^T$ $c\in (\mathrm{Ker} L^T)^\perp$ $V_0:=\mathrm{Ker} L = \mathrm{span}\{\mathbf{1}_n\}$ $V_0$ juga merupakan matriks dengan kolom yang menjadi dasar ortonormal. Dalam kasus Anda, . $V_0:=\mathbf{1}_n/\sqrt{n}$

Kemudian, untuk kesalahan iterasi Jacobi pada sistem asli, Anda memiliki mana

e_{1} = (I - D^{- 1} L) e_{0} = (I - D^{- 1} L) (P e_{0} + V_{0} a) = (I - D^{- 1} L) P e_{0} + V_{0} a,

$e_1 = (I-D^{-1}L)e_0 = (I-D^{-1}L) (P e_0 + V_0a)=(I-D^{-1}L) P e_0 + V_0a,$

adalah proyeksi orthogonal ke

. Dari iterasi di atas, kita tahu bahwa

dari mana kita memiliki matriks iterasi

dalam

Tidak

P := I - V_{0} V_{0}^{'}

$P:=I-V_0V_0'$

V_{1} := V_{0}^{⊥}

$V_1:=V_0^\perp$

P e_{1} = P (I - D^{- 1} L) P e_{0},

$P e_1 = P (I-D^{-1}L) P e_0,$

S

$S$

V_{1}

$V_1$

S := P (I - D^{- 1} L) P .

$S: = P (I-D^{-1}L) P.$

memiliki spektrum yang sama (kecuali nol) dengan matriks berikut

S

$S$

Kami ingin jari-jari spektral

kurang dari satu untuk membuktikan konvergensi.

\tilde{S} := (I - D^{- 1} L) P P = (I - D^{- 1} L) P = (I - D^{- 1} L) (I - V_{0} V_{0}^{'}) = I - D^{- 1} L - V_{0} V_{0}^{'} .

$\tilde{S}:= (I-D^{-1}L) P P=(I-D^{-1}L) P=(I-D^{-1}L)(I-V_0V_0')\\ =I-D^{-1}L-V_0V_0'.$

S

$S$

Kutipan berikut sudah tua dan disimpan hanya untuk referensi. Lihat setelah untuk bukti baru.

Dalam kasus Anda, Dan Anda dapat memverifikasi bahwa benar-benar dominan diagonal dengan menggunakan asumsi bahwa entripositif pada diagonal dan negatif sebaliknya. Untuk menunjukkan nilai eigen dari adalah nyata, kami mencatat bahwa matriks adalah self-adjoint di bawah produk dalam $V_0V_0'=\frac{1}{n}\mathbf{1}_{n\times n}.$ $D^{-1}L+V_0V_0'$ $L$ $D^{-1}L+V_0V_0'$ $<x,y>:=y^TDx.$

Jika tidak dalam bentuk spesifik Anda, saya belum menemukan jawaban untuk pertanyaan konvergensi. Bisakah seseorang mengklarifikasi ini? $V_0$

Perhatikan bahwa adalah eigen-vektor yang sesuai dengan nilai eigen dari . Berdasarkan pengamatan, kami menyebut Teorema 2.1 dari nilai Eigen dari matriks pembaruan peringkat-satu dengan beberapa aplikasi oleh Jiu Ding dan Ai-Hui Zhou. $V_0$ $1$ $I-D^{-1}L$

Teorema 2.1 Misalkan dan adalah dua vektor kolom dimensi sedemikian rupa sehingga adalah vektor eigen terkait dengan nilai eigen . Kemudian, nilai eigen dari yang menghitung banyaknya aljabar. $u$ $v$ $n$ $u$ $A$ $\lambda_1$ $A+uv^T$ $\{\lambda_1+u^Tv,\lambda_2,\ldots,\lambda_n\}$

Kemudian, kita tahu bahwa spektrum sama dengan kecuali bahwa nilai eigen pada yang terakhir digeser oleh ke nilai eigen nol di yang sebelumnya. Karena , kita memiliki . $\tilde{S}$ $I-D^{-1}L$ $1$ $-1$ $\rho(I-D^{-1}L)\subset (-1,1]$ $\rho(\tilde{S})\subset (-1,1)$

Hui Zhang
sumber

Terimakasih telah menjawab. Sesuatu yang serupa adalah apa yang saya pertimbangkan: yaitu, dengan Laplacian tertimbang terstruktur sebagai

atas, dapat ditunjukkan bahwa nilai eigennya berada dalam

, maka dengan jari-jari spektral dalam

(satu nilai eigen lebih besar dari

, dan setidaknya satu adalah

). Oleh karena itu, jari-jari spektral dari matriks iterasi

kurang dari

, maka dengan Jacobi konvergen. Mungkin asumsi di atas pada jari - jari spektral

D^{- 1} L

$D^{-1}L$

[0, 2)

$[0, 2)$

(0, 2)

$(0, 2)$

0

$0$

0

$0$

I - D^{- 1} L

$I-D^{-1}L$

1

$1$

(tidak termasuk

) tidak aman?

I - D^{- 1} L

$I-D^{-1}L$

0

$0$

usero

Saya pikir spektrum

harus dalam

, yang ditutup pada

. Saya tidak tahu bagaimana Anda bisa mendapatkan

pengecualian. Dari sudut pandang saya, (teorema lingkaran Gershgorin) [ en.wikipedia.org/wiki/Gershgorin_circle_theorem] hanya dapat memberikan perkiraan termasuk

. Jika demikian halnya, estimasi jari-jari spektral

adalah

dengan kesetaraan yang dapat dicapai dengan vektor-vektor dalam kernel

D^{- 1} L

$D^{-1}L$

[0, 2]

$[0,2]$

2

$2$

2

$2$

2

$2$

I - D^{- 1} L

$I-D^{-1}L$

\leq 1

$\leq 1$

L

$L$ . Saya pikir konvergensi yang Anda inginkan adalah bahwa dalam ruang ortogonal komplemen

seperti yang disebutkan dalam 'jawaban' di atas.

V_{1}

$V_1$

Hui Zhang

Anda dapat melihat Lemma 1.7 (v) dari math.ucsd.edu/~fan/research/cb/ch1.pdf Matriks

dapat dianggap sebagai Laplacian berbobot pada grafik lengkap, karenanya dengan mengecualikan

. Saya kira itu adalah argumen yang cukup untuk bukti konvergensi? ........... Apakah pendekatan Anda memerlukan pra / pasca-pemrosesan iterate di luar centering

. Saya bertanya karena Anda memperkenalkan

Dan mengenai spektrum

: mengingat bahwa jari-jari spektral (

)

D^{- 1} L

$D^{−1}L$

2

$2$

c

$c$

V_{0}

$V_0$

I - D^{- 1} L - V_{0} V_{0}^{'}

$I-D^{-1}L-V_0V_0'$

s r

$sr$

adalah

, penambahan

I - D^{- 1} L

$I-D^{-1}L$

(0, 1]

$(0, 1]$

, akan menghasilkan

. Bukankah ini argumen yang cukup bagus?

- \frac{1}{n}

$-\frac{1}{n}$

s r < 1

$sr<1$

usero

Hai, terima kasih telah menunjukkan buku yang bagus. Tetapi saya menemukan saya tidak dapat melihat dengan cepat. Tentang argumen terakhir Anda, tampaknya hampir sama dengan "jawaban" di atas. Hanya hati-hati, Anda tidak menambahkan

tetapi

\frac{1}{n}

$\frac{1}{n}$

\frac{1}{n} 1_{n \times n}

$\frac{1}{n}\mathbf{1}_{n\times n}$

s r

$sr$

I - D^{- 1} L

$I-D^{-1}L$

s r

$sr$

s r

$sr$

V_{0}

$V_0$

Metode Krylov tidak pernah secara eksplisit menggunakan dimensi ruang yang mereka ulangi, oleh karena itu Anda dapat menjalankannya pada sistem tunggal selama Anda menyimpan iterasi di subruang non-nol. Ini biasanya dilakukan dengan memproyeksikan ruang nol pada setiap iterasi. Ada dua hal yang bisa salah, yang pertama jauh lebih umum daripada yang kedua.

Prekondisi tidak stabil jika diterapkan pada operator tunggal. Pemecah langsung dan faktorisasi yang tidak lengkap mungkin memiliki sifat ini. Secara praktis, kami hanya memilih prekondisi yang berbeda, tetapi ada lebih banyak cara berprinsip untuk merancang prekondisi untuk sistem tunggal, misalnya Zhang (2010) .
$x$ $A x$

Untuk memecahkan sistem tunggal menggunakan PETSc, lihat KSPSetNullSpace(). Sebagian besar metode dan prekondisi dapat memecahkan sistem tunggal. Dalam praktiknya, ruang nol kecil untuk PDE dengan kondisi batas Neumann hampir tidak pernah menjadi masalah selama Anda memberi tahu pemecah ruang nol Krylov dan memilih prasyarat yang masuk akal.

$A x = b$ $b$ $A$ $b$

Jed Brown
sumber

Q

$Q$

A_{1} = Q^{T} A Q

$A_1 = Q^T A Q$

A_{1}

$A_1$

A_{1}

$A_1$

Z

$Z$

(I - Z) P^{- 1} A x = (I - Z) P^{- 1} b

$(I-Z)P^{-1} A x = (I-Z)P^{-1} b$

Hmm, sepertinya saya membalas komentar yang sudah dihapus. Saya akan meninggalkan komentar di sini kalau-kalau itu berguna.

Jed Brown

d i a g (A)

$diag(A)$

X_{k + 1} = D^{- 1} (b - (A - D) X_{k})

$X_{k+1}=D^{-1}(b-(A-D)X_k)$

X_{k + 1}

$X_{k+1}$

X_{k}

$X_{k}$

N = Z Z^{T}

$N=ZZ^T$

Z

$Z$

I - N

$I-N$

Z

$Z$

N = I - Z Z^{T}

$N=I-ZZ^T$ adalah proyektornya.)

Jed Brown