Iterative methods for linear system with non-diagonally dominant matrix

Question

I have a linear system \begin{align*} \left[\begin{array}{cccc} 1 & 2 & 1 & -1 \\ 3 & 2 & 4 & 4 \\ 4 & 4 & 3 & 4 \\ 2 & 0 & 1 & 5 \\ \end{array}\right] \left[\begin{array}{c} w \\ x \\ y \\z \end{array}\right] = \left[\begin{array}{c} 5 \\ 16 \\ 22 \\ 15 \end{array}\right], \end{align*} whose matrix $\bf{A}$ is not diagonally dominant. What are the iterative methods that can be used to find the solution? I have tried Jacobi method, Gauss-Seidel method and SOR method but nothing works (the output diverges). The answer is ${\bf x}=[16,-6,-2,-3]^T$.

Answer 1

You can see your equation as $f(u)=Au-b$, with $f(u)=0$. You can use some numerical method to solve it. One way is to use the minimization problem $$\min_u g(u),\qquad g(u)=\frac{1}{2}\|f(u)\|^2.$$ This gives you the equation $$0=\nabla g(u)=A^T(Au-b)\quad \text{ or } \quad A^TAu=A^Tb$$ which gives you the possible minimizers.

To your matrix $A$ and vector $b$, you can use the conjugate gradient method to solve $$A^TAu=A^Tb,$$ and it gives you the answer in four steps.

If you prefer to play with more steps, you can try gradient descent method.

You can find more searching for "\(Au=b\) gradient " on SearchOnMath.

Note: If you use the gradient descent method to minimize $h(u)=u^TAu-2u^Tb$ directly, you are going in the direction $$\frac{du}{dt}=- \nabla h(u)=-2(Au-b),$$ which is unstable, since $A$ has one negative eigenvalue and three positive ones.

Answer 2

I suggest not to use CG on the normal equations as suggested in the other answer, as it converts your system into one with squared condition number $\kappa(A)^2$, which will negatively affect your accuracy.

There is a different Krylov-space-based method that works for nonsymmetric systems, GMRES.

Remarks on convergence:

• Today Krylov-based methods are typically preferred to classical iterative methods such as Jacobi and Gauss-Seidel, unless one is severely constrained by the hardware architecture.

• On a $4\times 4$ system GMRES will converge in 4 iterations, and overall it will be slower than any reasonable direct method.

• Unfortunately there is little you can infer about the convergence for larger matrices from this $4\times 4$ experiment, since the first three iterations are too few to get a glimpse of the convergence curve.

• As with CG, the real trick of the trade for a large system is preconditioning it, i.e., turning it into a modified system $PAx=Pb$ with better convergence properties. This is a huge research topic, and the best preconditioners are often problem-based.