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?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ You'll want to see www2.cs.cas.cz/semincm/lectures/2007-05-04-ng.pdf for instance. $\endgroup$
    – J. M. isn't a mathematician
    Commented 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
    Commented 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$
    – Paul Tupper
    Commented 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$
    – J. M. isn't a mathematician
    Commented Nov 27, 2011 at 1:54

1 Answer 1

Reset to default
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).

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .