Projetando o espaço nulo de

11

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 R n × n b A b A

Ax=b,
ARn×nbAbA

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, centralizarL 1 n = [ 1 1 ] TR n b L J b = b , J = I - 1

Lx=b,
L1n=[11]TRnbL
Jb=b,
LLJ=I1n1n1nTLL itera).
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:

7

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

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 um T . (Dada apenas uma rotina para multiplicar com A , pode-se usar o GMRES, com propriedades de convergência menos previsíveis.)AATA

Arnold Neumaier
fonte
bAAAA
AATA
Ab
1
@usero: Se a diagonal de for constante, sim. Wlog as entradas diagonais são 1. Então A = I - BAA=IBx0=bxn+1=b+BxnAu=0uTb=0uTB=uTuTxné constante por indução, portanto zero. - Mas por que você se importa com o método Jacobi? Está muito lento!
Arnold Neumaier
BAdiag(A)cIcR