1
$\begingroup$

If we have the tridiagonal matrix

$$A = \begin{bmatrix} 4 & 1 & & & \\ 1 & 4 & 1 & & \\ & \ddots & \ddots & \ddots & \\ & & 1 & 4 & 1\end{bmatrix}$$

then no matter the size of $A$, its condition number, using the infinity norm, is $\kappa (A) = 3$. Is this correct? If so, why does this happen? Why doesn't the condition number change?

$\endgroup$
3
  • $\begingroup$ By "infinity norm", do you mean $\max\{|A_{kj}|:\ k,j\}$? The condition number is usually calculated for an operator norm, as far as I can tell. $\endgroup$ Nov 24, 2013 at 16:57
  • $\begingroup$ I mean this: $ \left \| A \right \|_{oo}=max_{1\leq i\leq n }\sum_{j=1}^{n} \left | a_{ij} \right |$ $\endgroup$
    – evinda
    Nov 24, 2013 at 17:12
  • $\begingroup$ @evinda: I see you haven't accepted any answers to any of the questions you've asked. It might encourage people to help you if you do so. Take a look here. $\endgroup$
    – JohnD
    Nov 28, 2013 at 18:12

1 Answer 1

3
$\begingroup$

As Evinda stated, $$ \|A\|_\infty := \sup\{\|Ax\|_\infty : \|x\|_\infty \le 1 \} = \max_{1\le i\le n} \sum_{j=1}^n |A_{ij}| .$$

I think I can show that $K_\infty(A) \le 3$. Clearly $\|A\|_\infty = 6$. Now write $A = 4 (I + B)$, where $B$ has diagonal entries equal to $0$ and the upper and lower diagonal entries equal to $\frac14$. So $\|B\|_\infty = \frac12 < 1$. Hence we can compute $A^{-1}$ using the geometric series $$ A^{-1} = \frac14 \sum_{k=0}^\infty (-1)^k B^k $$ and hence $$ \|A^{-1}\|_\infty \le \frac14 \sum_{k=0}^\infty \|B\|_\infty^k = \frac14 \cdot \frac1{1-\frac12} = \frac12 .$$ Therefore the condition number of $A$ is less than or equal to $6 \times \frac12 = 3$.

Next, I did some numerical experiments using Mathematica and 50 digit arithmetic. The condition number at $n=100$ is not exactly $3$, rather it is roughly $2.9999999999999999999999999999038729245836257932320$. My guess is that as a function of $n$ it converges monotonically to $3$. Matlab would get $3$ as its answer because it uses IEEE double precision which is only about 17 digits of accuracy.

$\endgroup$
5
  • $\begingroup$ I think it is rather amazing that the geometric series upper bound gives such a sharp answer. Either I made a mistake (but I think the proof will still show $K_\infty(A)$ is uniformly bounded), or some amazing coincidences are going on. $\endgroup$ Nov 24, 2013 at 19:49
  • $\begingroup$ How could I explain it that the upper limit of the condition number is 3? $\endgroup$
    – evinda
    Dec 9, 2013 at 20:36
  • $\begingroup$ I thought I explained this in my answer. $\endgroup$ Dec 9, 2013 at 23:03
  • $\begingroup$ I meant how could I explain it without giving a proof,or do I have to give the proof to explain it? $\endgroup$
    – evinda
    Dec 9, 2013 at 23:05
  • $\begingroup$ I don't know another way to explain it. $\endgroup$ Dec 9, 2013 at 23:07

You must log in to answer this question.

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