MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
You'll want to see for instance. – J. M. Nov 26 '11 at 18:51
Seems a little bit strange to use Gauß-Seidel or steepest descent, if there is – Dirk Nov 26 '11 at 20:26
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? – Paul Tupper Nov 26 '11 at 21:35
Paul is correct, one can relate the characteristic polynomial of a tridiagonal Toeplitz matrix with the Chebyshev polynomials. – J. M. Nov 27 '11 at 1:54

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).

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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