11

Given the system $$Ax=b,$$ where $A\in\mathbb{R}^{n\times n}$, I read that, in case Jacobi iteration is used as a solver, the method will not converge if $b$ has a non-zero component in the null-space of $A$. So, how could one formally state that, provided that $b$ has a non-zero component spanning the null-space of $A$, Jacobi method is non-convergent? I wonder how could that be mathematically formalized, since part of the solution orthogonal to the null-space does converge.

Therefore, by projecting the null-space of $A$ out of each iterate, it converges (or?).

.........

I'm particularly interested in the case of $$Lx=b,$$ where $L$ is a symmetric Laplacian matrix with the null-space spanned by a vector $1_n=[1\dots 1]^T\in\mathbb{R}^n$, and $b$ has a zero component in the null-space of $L$, $$Jb=b,$$ where $J=I-\frac{1}{n}1_n1_n^T$ is the centering matrix. Does that imply that each Jacobi iterate will have the null-space of $L$ projected out, ie., each iterate will be centered? I'm asking this since then there would be no need to project out the null-space of $L$ from Jacobi iterates (or, in other words, to center the iterates).

usero
  • 1,663
  • 2
  • 14
  • 27
  • This question may be relevant for you, too: http://scicomp.stackexchange.com/questions/1505/safe-application-of-iterative-methods-on-diagonally-dominant-matrices – shuhalo Apr 27 '12 at 12:18
  • Thanks. I've actually made an extract from my comments there, since the question deserves attention by itself. However, the above was not addressed (not formalized, at least). – usero Apr 27 '12 at 12:35
  • Oh, shame on me, I didn't check it was your own question. – shuhalo Apr 27 '12 at 13:10
  • @JedBrown Your answer on http://scicomp.stackexchange.com/questions/1505/safe-application-of-iterative-methods-on-diagonally-dominant-matrices inspired this question. I think it deserves an independent consideration. I guess you'll be able to consider the above questions. – usero Apr 28 '12 at 19:53

1 Answers1

7

The correct condition for solvability has nothing to do with the null space of $A$ (unless $A$ is symmetric) but with the null space of $A^T$. If $A^Tu=0$ then $Ax=b$ implies that $u^Tb=u^TAx=0$, hence $b$ must be orthogonal to any null vector of $A^T$ (otherwise there is no solution, and the Jacobi iteration has no reason to converge).

But if this is the case, a solution exists, and in the square case there are infinitely many.

In the singular case, as one never knows whether this condition is satisfied (and it would be spoiled by roundoff anyway), one would typically solve the problem as a least squares problem. To find the minimum norm solution, use conjugate gradients on the normal equations; this requires that you code multiplication by $A$ and by $A^T$. (Given only a routine for multiplying with $A$, one could use GMRES instead, with less predictable convergence properties.)

Arnold Neumaier
  • 11,318
  • 20
  • 47
  • Many thanks. Note that I'm specifically interested in Jacobi method (theoretical reasons; otherwise, I accept your suggestion on alternatives.) So: "I'm particularly interested in the case where $b$ has a zero component in the null-space of $A$. Does that imply that each Jacobi iterate will have the null-space of $A$ projected out? I'm asking this since then there would be no need to project out the null-space of $A$ from Jacobi iterates(so, when b has the null-space of $A$ projected out)." – usero Apr 30 '12 at 08:12
  • @usero: As I said, the null space of $A$ has no bearing on the problem. Or is your matrix symmetric? Moreover, the Jacobi method doesn't preserve orthogonality to the null space of $A^T$ unless $A$ has constant diagonal. – Arnold Neumaier Apr 30 '12 at 11:17
  • I've edited the question. Matrix $A$ is a symmetric (Laplacian) with the null space spanned by a vector of all ones. So, will each Jacobi iterate be centered in case $b$ is centered (as defined above)? I apologize for possible confusion I've made. – usero Apr 30 '12 at 12:05
  • 1
    @usero: If the diagonal of $A$ is constant, yes. Wlog the diagonal entries are 1. Then $A=I-B$ and the Jacobi iteration is $x_0=b$, $x_{n+1}=b+Bx_n$ If $Au=0$ and $u^Tb=0$ then by symmetry, $u^TB=u^T$, hence $u^Tx_n$ is constant by induction, hence zero. -- But why do you care about the Jacobi method? It is very slow! – Arnold Neumaier Apr 30 '12 at 12:40
  • Ok, so it the Jacobi iterates are not centered with centered $B$ and $A$ having a positive non-constant diagonal, i.e $diag(A)\neq c\cdot I$, for some $c\in \mathbb{R}$. Note that my interests in Jacobi are purely theoretical. As for the practice, I'd definitely adopt your suggestions. Thank you. – usero Apr 30 '12 at 13:24
  • If $A$ has not a constant diagonal, orthogonality is spoilt after the first Jacobi iteration. – Arnold Neumaier Apr 30 '12 at 16:41