Let $a,b,c \in \mathbb{R}$ and $A := \begin{pmatrix} a & b \\ b & c \end{pmatrix}$ and $\det(A) \neq 0$.
Find the condition number with respect to the 1-, 2- and $\infty$-norm and discuss for which relationships among $a,b,c$ the corresponding linear systems are well conditioned.
What I've done so far
We have $A^{-1} = \frac{1}{ac – b^2}\begin{pmatrix} c & -b \\ – b & a\end{pmatrix}$ and, therefore,
\begin{align}
\kappa_1(A)
& = \| A \|_1 \| A^{-1} \|_1
= \max\{a + b, b + c\} \cdot\max\left\{\frac{c – b}{ac – b^2}, \frac{a – b}{ac – b^2} \right\} \\
& = \big( b + \max(a, c)\big) \cdot \frac{1}{ac – b^2}\big( \max(a, c) – b\big) \\
& = \frac{b^2 – (\max(a, c))^2}{b^2 – ac}
\end{align}
Note: The above steps only work for $\det(A) > 0$ and $a,c > b$ and are the same for the $\| \cdot \|_1$-norm, since the matrix is symmetric.
Now, I'm not sure to find out for which values of $a,b,c$ this would be small (other than that for $a = c$, it's 1 and for $a = b = c$ and $b = a \ge c$ it's undefined) and especially not how to find this out which out plotting it with a computer.
While plotting I noticed that when |b| gets large, the term is very close to one for a sufficiently large plane around zero (i.e for $|b| = 60$ the term is very similar to 1 for all $(x,y) \in [-25,25]^2$).
For $a = -c$, the term becomes $\frac{b^2 – c^2}{b^2 + c^2} = \frac{2 b^2}{b^2 + c^2} – 1$, because $\max(-c,c) = |c|$.
Also, you can use
\begin{align}\tag{$\star$} \label{eq:star}
\max(x,y) = \frac{x + y + |x – y|}{2}
\end{align} to obtain
$$
\kappa_1(A)
= \frac{1}{2}\big( 2b + a + c + |a – c|\big)
\left( \frac{a – b}{ac – b^2} + \left| \frac{2c – a – b}{ac – b^2} \right| \right)
$$
Similar problems arise for the next norm:
We have $\kappa_2 = \sqrt{\rho(A^T A) \rho((A A^T)^{-1})}$ and $A^T A = A A^T = A^2$.
Now, we have
\begin{gather}
A^2 = \begin{pmatrix} a^2 + b^2 & b(a + c) \\ b(a + c) & b^2 + c^2 \end{pmatrix} \\
(A A^T)^{-1} = (A^{2})^{-1}
= \frac{1}{(b^2 – ac)^2} \begin{pmatrix} b^2 + c^2 & -b(a + c) \\ -b(a + c) & a^2 + b^2 \end{pmatrix},
\end{gather}
where $\rho(B)$ is the largest eigenvalue of $B$.
Now we obtain the eigenvalues by finding roots of the [characteristic polynomial][1]:
\begin{gather*}
\det(A^2 – t \cdot I_2)
= (a^2 + b^2 – t)(b^2 + c^2 – t) – b^2(a + c)
\overset{!}{=} 0 \\
\implies t_{1,2} = \frac{a^2 + 2b^2 + c^2 \pm(a + c) \sqrt{(a – c)^2 + 4b^2}}{2}
\end{gather*}
and, [similarly][2]
$$
\rho(A^{-2})
= \max\left\{ \frac{a^2 + 2b^2 + c^2 + \pm (a + c) \sqrt{(a – c)^2 + 4b^2}}{2(b^2 – ac)^2} \right\}
$$
So,
\begin{align}
\kappa_2(A)
& = \sqrt{\max\left\{\frac{a^2 + 2b^2 + c^2 \pm(a + c) \sqrt{(a – c)^2 + 4b^2}}{2} \right\} \cdot \max\left\{ \frac{a^2 + 2b^2 + c^2 \pm (a + c) \sqrt{(a – c)^2 + 4b^2}}{2(b^2 – ac)^2} \right\} } \\
& = \frac{1}{| b^2 – ac |} \max\left\{ \frac{a^2 + 2b^2 + c^2 \pm (a + c) \sqrt{(a – c)^2 + 4b^2}}{2} \right\} \\
& \overset{\eqref{eq:star}}{=} \frac{a^2 + 2b^2 + c^2 + |a + c|\sqrt{(a – c)^2 + 4b^2}}{2| b^2 – ac |}
\end{align}
How do I simplify this result?
Best Answer
Below follows an alternative analysis which does not rely on Gershgorin's theorem.
We begin the analysis with a sequence of elementary steps designed to reduce the number of variables and simplify the necessary calculations.
In general, we have $$\|A\|_\infty = \|A^T\|_1.$$ If $A$ is symmetric and non-singular, then $A^{-1}$ is also symmetric. It follows that $$ \kappa_\infty(A) = \kappa_1(A).$$ Since our matrix $$A = \begin{bmatrix} a & b \\ b & c \end{bmatrix}$$ is symmetric, we are therefore free to concentrate on, say, the 2-norm and the infinity norm.
We will distinguish between the case of $b=0$ and $b \not = 0$. If $b=0$, then $$ \|A\|_2 = \|A\|_\infty = \max \{|a|,|c|\}, \|A^{-1}\|_2 = \|A^{-1}\|_\infty = \max \{|a|^{-1},|c|^{-1}\}.$$ It follows, that $$ \kappa_2(A) = \kappa_\infty(A) = \max\left\{ \frac{|a|}{|c|}, \frac{|c|}{|a|} \right\}$$ In the case of $b = 0$, it is clear that $A$ is well-conditioned precisely when $|a| \approx |c|$ and ill conditioned when $|a| \ll |c|$ or $|c| \ll |a|$.
In the case of $b \not = 0$ we can without loss of generality assume that $b = 1$. If $b \not = 1$, then we simply scale the matrix with $b^{-1}$. The condition numbers are invariant under this scaling because $(b^{-1}A)^{-1} = b A^{-1}$. We can therefore concentrate on the case of $b=1$ where $$A = \begin{bmatrix} a & 1 \\ 1 & c \end{bmatrix}.$$ This matrix is non-singular if and only if $ac \not =1$. In this case, we have $$A^{-1} = \frac{1}{1 - ac} \begin{bmatrix} c & -1 \\ -1 & a \end{bmatrix}.$$ It follows, that $$ \|A\|_\infty = \max\{1 + |a|,1+|c|\}, \quad \|A^{-1}\|_\infty = \frac{1}{|1 - ac|}\max\{1 + |a|,1+|c|\},$$ which implies $$ \kappa_\infty(A) = \frac{1}{|1 - ac|}\max\{(1 + |a|)^2,(1+|c|)^2\}$$ A contour plot of the right hand side could now be obtained. A detailed understanding can be developed by covering the punctured plane $\mathbb{R}^2 - \{(0,0)\}$ with hyperbolas, i.e., curves of the form $$ac = \gamma$$ where $\gamma \not = 0$. On the curve corresponding to a $\gamma \not = 1$ we have $$ \kappa_\infty(A) \ge \frac{1}{|1 - \gamma|} \left( 1 + \sqrt{|\gamma|}\right)^2$$ with equality achieved when $|a|=|c| = \sqrt{|\gamma|}$. Moreover, $$ \kappa_\infty(A) \rightarrow \infty, $$ as $$\max\{|a|,|c|\} \rightarrow \infty, \quad ac=\gamma.$$ This covers the analysis of the infinity norm.
Explicit calculation of the 2-norm condition number is tedious, but a short-cut is possible because of the equivalence of norms. In general, we have $$ \|x\|_\infty \leq \| x\|_2 \leq \sqrt{n} \|x\|_\infty $$ This implies that $$ \kappa_2(A) \leq n \kappa_\infty(A) \leq n^2 \kappa_2(A)$$ Why? We have $$ \|Ax\|_2 \leq \sqrt{n} \|Ax\|_\infty \leq \sqrt{n} \|A\|_\infty \|x\|_\infty \leq \sqrt{n} \|A\|_\infty \|x\|_2 $$ This implies that $$ \|A\|_2 \leq \sqrt{n} \|A\|_\infty$$ Similarly, we have $$ \|Ax\|_\infty \leq \|Ax\|_2 \leq \|A\|_2 \|x\|_2 \leq \sqrt{n} \|A\|_2 \|x\|_\infty.$$ This implies that $$ \|A\|_\infty \leq \sqrt{n} \|A\|_2.$$ In our case $n=2$, so $$ \kappa_2(A) \leq 2 \kappa_\infty(A) \leq 4 \kappa_2(A)$$ or equivalently $$ \frac{1}{2} \kappa_\infty(A) \leq \kappa_2(A) \leq 2 \kappa_\infty(A). $$ In other words, when it comes to the conditioning of the matrix $A$ there is little to be learned from the 2-norm which cannot be discerned from the infinity norm.