Wystawianie zerowej przestrzeni

Biorąc pod uwagę system gdzie , przeczytałem, że w przypadku gdy iteracja Jacobiego jest używana jako solver, metoda nie zbiegnie się, jeśli ma wartość niezerową składnik zerowa przestrzeni . Jak zatem można formalnie stwierdzić, że pod warunkiem, że ma niezerowy składnik obejmujący zerową przestrzeń , metoda Jacobiego jest niespójna? Zastanawiam się, jak można to sformalizować matematycznie, ponieważ część rozwiązania prostopadłego do przestrzeni zerowej jest zbieżna.

A x = b,

$Ax=b,$

A \in R^{n \times n}

$A\in\mathbb{R}^{n\times n}$

b

$b$

A

$A$

b

$b$

A

$A$

Dlatego przez rzutowanie pustej przestrzeni z każdej iteracji zbiega się (lub?). $A$

.........

Szczególnie interesuje mnie przypadek gdzie jest symetryczną macierzą Laplaciana z zerową przestrzenią rozpiętą przez wektor , i ma składową zerową w zerowej przestrzeni , gdzie jest macierzą centrującą. Czy to oznacza, że każda iteracja Jacobiego będzie miała wyrzuconą zerową przestrzeń , tj. Każda iteracja będzie wyśrodkowana ? Pytam o to, ponieważ odtąd nie byłoby potrzeby rzutowania pustej przestrzeni z iteracji Jacobiego (lub innymi słowy, do wyśrodkowania

L x = b,

$Lx=b,$

L

$L$

1_{n} = [1 \dots 1]^{T} \in R^{n}

$1_n=[1\dots 1]^T\in\mathbb{R}^n$

b

$b$

L

$L$

J b = b,

$Jb=b,$

J = I - \frac{1}{n} 1_{n} 1_{n}^{T}

$J=I-\frac{1}{n}1_n1_n^T$

L

$L$

L

$L$ iteracje).

linear-algebra optimization matrix iterative-method linear-solver usero
źródło

To pytanie może być również dla Ciebie istotne: scicomp.stackexchange.com/questions/1505/…

shuhalo

Dzięki. Właściwie zrobiłem tam fragment z moich komentarzy, ponieważ samo pytanie zasługuje na uwagę. Powyższe nie zostało jednak rozwiązane (przynajmniej nie sformalizowane).

usero

Och, szkoda, nie sprawdziłem, że to twoje pytanie.

shuhalo

@JedBrown Twoja odpowiedź na scicomp.stackexchange.com/questions/1505/... zainspirowała to pytanie. Myślę, że zasługuje na niezależne rozważenie. Myślę, że będziesz w stanie rozważyć powyższe pytania.

usero

Odpowiedzi:

Prawidłowe warunkiem rozwiązywalności nie ma nic wspólnego z przestrzenią NULL (chyba jest symetryczna), ale z przestrzenią NULL . Jeśli to oznacza, że , stąd musi być ortogonalne do dowolnego wektora zerowego (w przeciwnym razie nie ma rozwiązania, a iteracja Jacobiego nie ma powodu Zbiegać się). $A$ $A$ $A^T$ $A^Tu=0$ $Ax=b$ $u^Tb=u^TAx=0$ $b$ $A^T$

Ale jeśli tak jest, istnieje rozwiązanie, aw przypadku kwadratu jest nieskończenie wiele.

W pojedynczym przypadku, ponieważ nigdy nie wiadomo, czy warunek ten jest spełniony (a i tak zostałby zepsuty przez zaokrąglenie), zwykle rozwiązuje się problem jako problem najmniejszych kwadratów. Aby znaleźć rozwiązanie normy minimalnej, użyj gradientów sprzężonych na równaniach normalnych; Wymaga to kod mnożenie przez i . (Biorąc pod uwagę tylko procedurę mnożenia przez , można zamiast tego użyć GMRES, z mniej przewidywalnymi właściwościami konwergencji). $A$ $A^T$ $A$

Arnold Neumaier
źródło

b

$b$

A

$A$

A

$A$

A

$A$

A

$A$

A

$A$

A^{T}

$A^T$

A

$A$

A

$A$

b

$b$

A

$A$

A = I - B

$A=I-B$

x_{0} = b

$x_0=b$

x_{n + 1} = b + B x_{n}

$x_{n+1}=b+Bx_n$

A u = 0

$Au=0$

u^{T} b = 0

$u^Tb=0$

u^{T} B = u^{T}

$u^TB=u^T$

u^{T} x_{n}

$u^Tx_n$ jest stały przez indukcję, stąd zero. - Ale dlaczego obchodzi Cię metoda Jacobiego? To jest bardzo wolne!

Arnold Neumaier

B

$B$

A

$A$

d i a g (A) \neq c \cdot I

$diag(A)\neq c\cdot I$

c \in R

$c\in \mathbb{R}$