0
$\begingroup$

For a tridiagonal matrix of the from

\begin{bmatrix} a & -b & \newline -b & a & -b \newline & \ddots & \ddots & \ddots \newline & & & & -b \newline & & &-b & a \end{bmatrix}

with $a \geq 2b > 0$ I would like to compare, in funtion of $a$ and $b$, the convergence of the Gauss-Seidel method and the Steepest Descent method. But how to do such a comparison if the information about Gauss-Seidel convergence is given by is spectral radius and the information about the Steepest Descent convergence is given by the ratio between the largest and the smallest eigenvalues?

$\endgroup$
4
  • 2
    $\begingroup$ You'll want to see www2.cs.cas.cz/semincm/lectures/2007-05-04-ng.pdf for instance. $\endgroup$ Nov 26, 2011 at 18:51
  • $\begingroup$ Seems a little bit strange to use Gauß-Seidel or steepest descent, if there is en.wikipedia.org/wiki/Tridiagonal_matrix_algorithm... $\endgroup$
    – Dirk
    Nov 26, 2011 at 20:26
  • 5
    $\begingroup$ This is a tridiagonal symmetric Toeplitz matrix. There are explicit expressions for its eigenvectors and eigenvalues. For example, they are in Iserles' A First Course in the Numerical Analysis of Differential Equations. Is this for a course you are taking? $\endgroup$ Nov 26, 2011 at 21:35
  • $\begingroup$ Paul is correct, one can relate the characteristic polynomial of a tridiagonal Toeplitz matrix with the Chebyshev polynomials. $\endgroup$ Nov 27, 2011 at 1:54

1 Answer 1

1
$\begingroup$

This is a good question, and I happen to have thought about it. Several comments pointed out that for tridiagonal Toeplitz matrix there are other better algorithms; that's true, but it does not answer the question.

I think the confusion comes from the statement "Gauss-Seidel convergence is given by its spectral radius", which is incorrect. Gauss-Seidel convergence depends on the spectral radius of a new matrix $L^{-1}R$ where $L-R = A$, for solving $Ax=b$. It is hard to estimate the spectral radius of $L^{-1}R$, but I am pretty sure that it is related to the condition number of $A$ (the ratio between the largest and the smallest eigenvalues).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.