Jacobi method for any b

Question

Determine if Jacobi method converges for any b for, $$\begin{bmatrix} 2 & 2\\ 3 & 4 \end{bmatrix}$$

The solution goes on like this...

D-(L+U) = $$\begin{bmatrix} 2 & 0\\ 0 & 4 \end{bmatrix} - \begin{bmatrix} 0 & -2\\ -3 & 0 \end{bmatrix}$$

D^{-1}(L+U) =$$\begin{bmatrix} 1/2 & 0\\ 0 & 1/4 \end{bmatrix}\begin{bmatrix} 0 & -2\\ -3 & 0 \end{bmatrix}= \begin{bmatrix} 0 & -1\\ -\frac{3}{4} & 0 \end{bmatrix}$$ After that we have, $$\begin{bmatrix} \lambda & 1\\ \frac{3}{4} & \lambda \end{bmatrix}$$

And, since $\lambda_{1} = -\sqrt\frac{3}{4}$ and $\lambda_{2} = \sqrt\frac{3}{4}$, $\rho(A)< 1$. This method converges.

Now I have a couple of questions on this...

1. Why do we have to take inverse when inverse is strictly prohibited in Numerical analysis? Can we use forward substitution instead?

2. How do you come up with$$\begin{bmatrix} \lambda & 1\\ \frac{3}{4} & \lambda \end{bmatrix}$$ from $$\begin{bmatrix} 0 & -1\\ -\frac{3}{4} & 0 \end{bmatrix}$$ and changed the sign? Can someone please explain me these? Thanks.

Answer 1

Question 1:

We would use a stable method to find the inverse of the matrix, like Gaussian Elimination, where we write:

$$[M ~|~ I]$$

Performing Gaussian elimination, we end up with:

$$[I~ | ~ M^{-1}]$$

Question 2:

When we are finding the eigenvalues, we have the choice of writing:

$$|A - \lambda I| = 0~ \mbox{or} ~ |\lambda I - A| = 0$$

Both approaches yield the exact same result and some people prefer one or the other for various reasons. In your example, they used the latter.

Use both methods for the matrix you have and prove to yourself that they give identical eigenvalues.

Answer 2

In numerical work, inverting matrices is frowned upon, as there usually are more efficient methods available. Newbies just think that a nice, simple formula just like the solution of your vanilla equation is the way to go.

To reason about numerical methods, you want clean results, using nice, simple, clear formulas. Even if much of the data to be used is hard or impossible to come by in practice. Just look at the discussion of convergence of iterations, where you start up knowing the fixed point, and all sorts of sordid private details like the derivatives of the functions there and nearby.