Numerical work on a tridiagonal matrix

Question

Consider a tridiagonal matrix with diagonal entries equal to 10 and subdiagonal and superdiagonal entries -3.5. I'm working on an iterative method where I can solve $Ax=b$ using the iteration $x_{i+1} = x_i + \Xi(b-Ax_i),$ where $\Xi \in \mathbb{R}.$

I want to find which values of $\Xi$ there are such that we converge to the solution $\tilde{x}$ such that $A\tilde{x} = b.$ I'm wondering if I might be able to figure out the $\Xi$'s by pulling some of the ideas from the standard Thomas algorithm, but otherwise I am having difficulty figuring out how the properties of a tridiagonal matrix will infer any information about $\Xi$.

I was wondering if I could get some suggestions on this problem.

Answer 1

The iteration can be rewritten as $x_{i+1} = \Xi b + (I-\Xi A)x_i$. This is guaranteed to converge if $\|I-\Xi A\| < 1$. Since $I-\Xi A$ is symmetric this is equivalent to requiring that all the eigenvalues of $I - \Xi A$ have magnitude strictly less than $1$.

The eigenvalues of $I - \Xi A$ are in the form $1-\Xi \lambda$ where $\lambda$ is an eigenvalue of $A$. Since $A$ is symmetric, all the eigenvalues are real. Thus, we need $-1 < 1-\Xi\lambda < 1$, i.e. $0 < \Xi < \dfrac{2}{\lambda}$ for all eigenvalues $\lambda$ of $A$.

By applying the Gershgorin circle theorem to your tridiagonal matrix $A$, we get that all of the eigenvalues will satisfy $|\lambda - 10| \le 2 \cdot 3.5 = 7$, i.e. $3 \le \lambda \le 17$.

Therefore, the iteration is guaranteed to converge if $0 < \Xi < \dfrac{2}{17}$.