Projetando o espaço nulo de

Dado o sistema onde , li que, caso a iteração Jacobi seja usada como solucionador, o método não convergirá se tiver um valor diferente de zero componente no nulo-espaço de . Então, como alguém poderia formalmente afirmar que, desde que tenha um componente diferente de zero, abrangendo o espaço nulo de , o método Jacobi não é convergente? Pergunto-me como isso poderia ser formalmente matematicamente formalizado, já que parte da solução ortogonal ao espaço nulo converge.

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$

Portanto, ao projetar o espaço nulo de em cada iteração, ele converge (ou?). $A$

.........

Estou particularmente interessado no caso de onde é uma matriz laplaciana simétrica com o espaço nulo estendido por um vetor , e tem um componente zero no espaço nulo de , onde é a matriz centralizadora. Isso implica que cada iteração de Jacobi terá o espaço nulo de projetado para fora, ou seja, cada iteração será centralizada ? Estou perguntando isso desde então, não haveria necessidade de projetar o espaço nulo de de Jacobi itera (ou, em outras palavras, centralizar

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$ itera).

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

Esta questão pode ser relevante para você, também: scicomp.stackexchange.com/questions/1505/...

shuhalo

Obrigado. Na verdade, fiz um extrato dos meus comentários, pois a pergunta merece atenção por si só. No entanto, o acima exposto não foi abordado (pelo menos não formalizado).

usero

Oh, que vergonha, eu não verifiquei se era sua própria pergunta.

precisa saber é o seguinte

@JedBrown Sua resposta em scicomp.stackexchange.com/questions/1505/… inspirou esta pergunta. Eu acho que merece uma consideração independente. Eu acho que você poderá considerar as perguntas acima.

usero

Respostas:

A condição correta para solvabilidade não tem nada a ver com o espaço nulo de (a menos que é simétrica), mas com o espaço nulo de . Se , então implica que , portanto, deve ser ortogonal em relação a qualquer vector nula de (de outra forma não há uma solução, e o Jacobi iteração não tem razão convergir). $A$ $A$ $A^T$ $A^Tu=0$ $Ax=b$ $u^Tb=u^TAx=0$ $b$ $A^T$

Mas, se esse for o caso, existe uma solução e, no caso quadrado, existem infinitas.

No caso singular, como nunca se sabe se essa condição é satisfeita (e seria prejudicada pelo arredondamento de qualquer maneira), normalmente resolveria o problema como um problema dos mínimos quadrados. Para encontrar a solução-padrão mínima, use gradientes conjugados nas equações normais; isso requer que você multiplicação código por e por . (Dada apenas uma rotina para multiplicar com , pode-se usar o GMRES, com propriedades de convergência menos previsíveis.) $A$ $A^T$ $A$

Arnold Neumaier
fonte

b

$b$

A

$A$

A

$A$

A

$A$

A

$A$

A

$A$

A^{T}

$A^T$

A

$A$

A

$A$

b

$b$

@usero: Se a diagonal de

for constante, sim. Wlog as entradas diagonais são 1. Então

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$ é constante por indução, portanto zero. - Mas por que você se importa com o método Jacobi? Está muito lento!

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}$