[Math] Jacobi Method and Gauss-Seidel Multiple Choice Convergence Answer Verification

linear algebraMATLABmatricesnumerical linear algebranumerical methods

The book gives the following problems.

  1. A sufficient condition for the Jacobi method to converge for the linear system $Ax=b$ is …
    $a. \quad A-I$ is diagonally dominant
    $b. \quad A$ is diagonally dominant
    $c. \quad G$ is nonsingular where $G$ is the iteration matrix: $G=I-Q^{-1}A$.
    $d.\quad $ The spectral radius of $G$ is less than $1$.
    $e.\quad $ none of these.

My answer: $b.$ i.e. the condition that $A$ is diagonally dominant.

Reasoning: The book gives the Jacobi and Gauss-Seidel Convergence Theorem:

If $A$ is diagonally dominant, then the Jacobi and Gauss-Seidel methods converge for any starting vector $x^{(0)}$. (Notice that this is a sufficient, but not a necessary condition.)

The next problem:

  1. A sufficient condition for the Gauss-Seidel Method to work on the linear system $Ax=b$ is …
    $a. \quad A$ is diagonally dominant
    $b. \quad A-I$ is diagonally dominant
    $c.\quad $ The spectral radius of $A$ is less than $1$.
    $d. \quad G$ is nonsingular.
    $e.\quad $ none of these.

My answer: $a.$ that $A$ is diagonally dominant.

Reasoning: The book gives the Jacobi and Gauss-Seidel Convergence Theorem, see above.

Concerns: I'm not sure if my answers are correct. It seems a bit too simple/straightforward. I'm not sure if these are trick questions and I'm missing a key fact or idea. Also the first question asks for a sufficient condition for Jacobi Method to converge, and the second question asks for a sufficient condition for Gauss-Seidel to work.

I'm not sure if there is a difference between converge and work. Any help would be much appreciated. Thank you.

Best Answer

For these methods convergence occurs if and only if the spectral radius of the iteration/error propagation matrix $G$ is strictly less then one: $$\rho(G) \overset{!}<1.$$ Now, for a general matrix-splitting based method like Jacobi or Gauss-Seidel, you do the splitting $$A = Q - N$$ resulting in the iteration matrix $$G = I - Q^{-1} A = Q^{-1}N.$$ For the Jacobi method $Q_J = D, N_J = L+U$. So for question one, a certainly correct answer is d. Concerning diagonal-dominance, it is usually a matter of definition. Jacobi converges guaranteed for strict or irreducible diag. dom. matrices $A$. Question is now, what your definition of diagonal-dominance is, i.e., whether b. is also correct or not.

This matter of definition determines actually also the outcome of the second question - it is either b. or e..

Related Question