6
$\begingroup$

I know that the Gauss-Seidel method converges given that the matrix you want to solve is symmetric positive definite. However, I'm wondering if the "converse" of the statement is true. Namely, if $A$ is a symmetric matrix with positive diagonals and the Gauss-Seidel method converges for all initial guess $x_0$, is $A$ guaranteed to be positive definite?

$\endgroup$
5
$\begingroup$

There is an interesting though partial answer to your question:

Under your assumptions, it is not possible that the signature of $A$ be $(n-1,1)$ (exactly one negative eigenvalue).

Proof: With standard notations, $A=D-E-E^T$ where $E$ is strictly triangular and $D$ diagonal. By assumption, $D>0_n$. Notice that the assumption of convergence implies that $A$ is invertible.

The iteration matrix is $G=(D-E)^{-1}E^T$. The quadratic form $q(x):=x^TAx$ satisfies the identity $$q(Gx)+y^TDy=q(x),\qquad y:=x-Gx=(D-E)^{-1}Ax.$$ This implies that $G$ preserves the set $q<0$. If the signature of $A$ is $(n-1,1)$, this set is the union of two opposite convex cones $\pm K$. Thus $\pm G$ preserves $K$. One deduces from Brouwer fixed point theorem that $G$ admits an eigenvector $x\in K$, $Gx=\mu x$. Then $\mu^2q(x)<q(x)<0$ gives $|\mu|>1$, which contradicts the convergence of the Gauss-Seidel method.

Nota. The identity about $q$ is the one used to prove the convergence of the method when $A$ is positive definite. More generally, it is used to prove that any method with iteration matrix $L:=M^{-1}N$ where $A=M-N$, such that both $A$ and $M^T+N$ are positive definite, is convergent

$\endgroup$
2
  • $\begingroup$ Thank you for your answer. But I'm wondering what is $q$ in your proof? $\endgroup$ – bernard May 14 '20 at 11:39
  • $\begingroup$ @bernard. Oups, $q$ is the quadratic form associated with $A*. I edit the post. $\endgroup$ – Denis Serre May 14 '20 at 12:18
0
$\begingroup$

Note that, as Prof. Serre's answer, $q(x)=x^TAx$ decreases as the iterations go on. In particular, consider $Ax=b$ with $b=0$, we have $x_0^TAx>x_1^TAx_1>\cdots>x^T_nAx_n>\cdots$ and $\lim\limits_{n\to \infty} x_n=0$. If $A$ is not positive definite, there exists $x_*$ such that ${x_*}^{T}Ax_*<0$. Take $x_0=x_*$ then we have $0>x_0^TAx_0>\cdots$, thus $\lim\limits_{n\to \infty} x_n^TAx_n<0$, which contradicts to $\lim\limits_{n\to \infty} x_n=0$.

$\endgroup$

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.