3
$\begingroup$

Suppose a linear system is given $$AX=B,$$ where $A\in\mathbb{R}^{n\times n}$ is a symmetric strictly diagonal matrix, and $X, B\in\mathbb{R}^{n\times 2}$. Therefore, the 2D Jacobi iterative solver is applicable here, $$X_{k+1}=D^{-1}(B-RX_k),$$ where the splitting corresponds to $A=D+R$, with $D$ containing only the diagonal entries of $A$. Could it be proven that the iterands $X_0, X_1, X_2, \dots$ are maintaining the line per each row of $X$, meaning that, for $x^i\in\mathbb{R}^2$ being the $i-$th row of $X$, the rows in sequence $x^i_0, x^i_1, x^i_2, \dots$, are colinear (on one line)?

$\endgroup$
  • $\begingroup$ My first instinct is no, but I don't have any sources to back it up. $\endgroup$ – Paul Mar 7 '12 at 19:25
3
$\begingroup$

Let's take the difference between two successive iterations, and define $P$ and $Q$ this way: $$ \Delta_k = X_{k+1} - X_{k} = D^{-1}B - (D^{-1}R + I)X_{k} = P-QX_{k} $$ Then $$ \Delta_{k+1} = X_{k+2} - X_{k+1} = P-QX_{k+1} $$ To be row-wise collinear, we need $\Delta_{k+1} - \Delta_{k} = S \Delta_{k}$ for some diagonal matrix $S$. Doing this, we get $$ \Delta_{k+1} - \Delta_{k} = Q(X_{k+1}-X_k) = Q\Delta_k $$ Since $Q = D^{-1}R + I$ is not diagonal unless $R$ is diagonal, then in general these iterates will not be collinear.

$\endgroup$
  • $\begingroup$ Good argument. If you are aware of some other iterative solver that has a property of "line maintenance" in case of 2D, please let me know. $\endgroup$ – usero Mar 8 '12 at 8:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.