Iterative methods for linear system with non-diagonally dominant matrix 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$.
 A: 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.
A: 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.
