7
$\begingroup$

Let $U \in \mathbb{R}^{N\times N}$ be upper triangular. $U$ is well conditioned if the magnitude of the diagonal elements is sufficiently large compared to that of the corresponding off-diagonal elements.

I'm trying to show that if $|u_{ii}| -2\,\displaystyle\sum_{j\neq i}{|u_{ij}|}>0$, for all $1\leq i\leq N,$ then $\kappa_{\infty}(U)\leq 2\>\dfrac{\|U\|_{\infty}}{\min_{1\leq j\leq N}{|u_{jj}|}}.$

I am struggling to show $\|U^{-1}\|_{\infty} \le \dfrac{2}{\min_{1\leq j\leq N}{|u_{jj}|}}$.

Does anyone have any ideas?

$\endgroup$
2
  • $\begingroup$ Can you remind us, what is this $\kappa_{\infty}$? $\endgroup$
    – Mankind
    Commented Mar 15, 2015 at 22:11
  • $\begingroup$ $\kappa_{\infty}(U)$ is the condition number of $U$ with respect to inversion. So $\kappa_{\infty}(U) = \|U^{-1}\|_{\infty}\|U\|_{\infty}$ $\endgroup$
    – Drew
    Commented Mar 15, 2015 at 22:13

1 Answer 1

4
$\begingroup$

The proof is essentially same as here. The matrix does not need to be triangular; only a row-wise diagonal dominance is needed.

Assume $U$ is a square invertible matrix such that $$\tag{1} |u_{ii}|-\alpha\sum_{j\neq i}|u_{ij}|\geq 0, \quad i=1,\ldots,N, $$ for some $\alpha>1$. Let $x$ be an $N$-vector and $i$ be the index such that $\|x\|_\infty=|x_i|$. Then $$ \begin{align} \|Ux\|_\infty\geq|(Ux)_i|&\geq|u_{ii}||x_i|-\sum_{j\neq i}|u_{ij}||x_j| &&\text{(triangle inequality)} \\ &\geq|u_{ii}||x_i|-\sum_{j\neq i}|u_{ij}||x_i| && \text{(since $|x_j|\leq|x_i|=\|x\|_\infty$)}\\ &\geq\left(1-\frac{1}{\alpha}\right)|u_{ii}||x_i|&&\text{(using (1))} \\&\geq\left(1-\frac{1}{\alpha}\right)\min_i|u_{ii}|\|x\|_\infty&&\text{(making bound independent of $i$).} \end{align} $$ Hence $$ \frac{\|Ux\|_\infty}{\|x\|_\infty}\geq \frac{\alpha-1}{\alpha}\min_i|u_{ii}|. $$ We have then $$\tag{2} \|U^{-1}\|_\infty=\max_{x\neq 0}\frac{\|U^{-1}x\|_\infty}{\|x\|_\infty}=\max_{x\neq 0}\frac{\|x\|_\infty}{\|Ux\|_\infty}\leq\frac{\alpha}{\alpha-1}\frac{1}{\min\limits_i|u_{ii}|}. $$ This already gives the bound you seek with $\alpha=2$.


Note that (1) also implies a bound on $\|U\|_\infty$ in terms of the diagonal entries $u_{ii}$ and hence a more neat bound on $\kappa_{\infty}$ :-). We have $$ |u_{ii}|+\sum_{j\neq i}|u_{ij}|\leq\left(1+\frac{1}{\alpha}\right)|u_{ii}|, \quad i=1,\ldots,N \quad\Rightarrow\quad \|U\|_{\infty}\leq\frac{\alpha+1}{\alpha}\max_i|u_{ii}|, $$ so with (2), we get $$ \kappa_\infty(U)\leq\frac{\alpha+1}{\alpha-1}\frac{\max\limits_i|u_{ii}|}{\min\limits_i|u_{ii}|}. $$

$\endgroup$

You must log in to answer this question.

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