Finding the condition number of a matrix $A$, and the values of b such that $A$ is ill-conditioned

condition numbernormed-spacesnumerical methods

Let $A=\begin{pmatrix} 1 & b \\ 0 & 1\\\end{pmatrix}$, what is the condition number of A, for which values of b the matrix A is ill-conditioned.

My trial:
Since it does not specify in which norm to calculate the cond number, therefore I computed it for the $l^1, l^{\infty}, l^2$ norms, using the formula :
$cond(A)= ||A|| ||A^{-1}||$.

I got

For $l^1$ $cond_1(A)= (1+|a|)^2$

For $l^{\infty}$ $cond_{\infty}(A)= (1+|a|)^2$

For $l^2$ $cond_2(A)\leq (2+a^2)$

And the

I don't know if this is what I shoud compute, or there are more options that I shoud consider.

For the second part, i am not sure about it but I think that the matrix would be ill-conditioned when it has a big or large condition number so it happens for big values of b.

Can you correct me, or give any tips.

Best Answer

You computed correctly $K_1(A)$ and $K_{\infty}(A)$.

Try to solve $A x=c$ when $c=[1,1]$ and then compute it for a perturbed r.h.s. $\tilde{c} = c + \delta c$. The key thing point in this case is that $$\frac{||\delta x||}{||x||} \leq K(A) \frac{||\delta c||}{||c||}$$ i.e. the condition number is a magnification factor for the relative error. Note also that it's not so important in this case which norm you use to compute $K(A)$.

For $b=2 \cdot 10^{6}$ you obtain $x=[-1999999,1]$ to be the exact solution.
Let's perturb of the r.h.s. $c$ with a $\delta c$ s.t. $||\delta c||=10^{-3}$: the solution is

$$\tilde{x} =x + \delta x=[-2.001998999000000\cdot 10^{6},1+10^{-3}]$$ where the first component is dramatically different from the first one of $x$. Thus your linear system has an high sensitivity to a small variation of the data, and this behaviour is justified by the large condition number you got in this case: $K_\infty(A)=(1+2 \cdot 10^{6})^2$.

You can try by yourself playing with the following Python snippet

    import numpy as np
    
    b = 1e6;
    A = np.array([[1,b],[0,1]])
    print("Condition number compute with linalg",np.linalg.cond(A))
    c = np.array([1,1])
    
    deltac = np.array([1e-3,1e-3]) #perturbation
    cc = c + deltac #perturbed r.h.s.
    
    x = np.linalg.solve(A,c)
    xx = np.linalg.solve(A,cc)
    
    print("Solution of original system is",x)
    print("Solution with perturbed r.h.s.",xx)

Related Solutions

[Math] Use SVD to reduce condition number of matrix

What you're doing is equivalent to setting all but the top 70 singular values equal to $0$, as the code below illustrates. The resulting matrix is singular.

import numpy as np
import scipy as sp

numRows = 100
numCols = 150
numKeep = 70
A = np.random.randn(numRows,numCols)

U,S,VT = sp.linalg.svd(A)  

# This is how we recover A from U, S, and VT
Sigma = np.zeros((numRows,numCols))
for i in range(numRows):
    Sigma[i,i] = S[i]

A_check = U @ Sigma @ VT
print("Is A equal to A_check?")
print(np.allclose(A,A_check))

#Now compute B using method 1, "removing smaller singular values"
Sigma = np.zeros((numKeep, numCols))
for i in range(numKeep):
    Sigma[i,i] = S[i]

B = U[:,0:numKeep] @ Sigma @ VT

# Now compute B using method 2, 
# by setting all but top 70 singular values set equal to 0.
Sigma = np.zeros((numRows,numCols))
for i in range(numKeep):
    Sigma[i,i] = S[i]

B_check = U @ Sigma @ VT
print("Is B equal to B_check?")
print(numpy.allclose(B,B_check))

Structure of an ill-conditioned matrix

Define a vector $v \in \mathbb{R}^{100}$ by $v_1= 1$, and $v_{n+1} = -\dfrac{500+n}{1000}v_n$ for $n = 1,\ldots,99$.

We can compute the entries of $Av$ as follows:

For $m = 1,\ldots,99$, $(Av)_m = \displaystyle\sum_{n = 1}^{100}A_{m,n}v_n = A_{n,n}v_n+A_{n,n+1}v_{n+1} = \dfrac{500+n}{1000}\cdot v_n+1\cdot-\dfrac{500+n}{1000}v_n = 0$

$(Av)_{100} = \displaystyle\sum_{n = 1}^{100}A_{100,n}v_n = A_{100,100}v_{100} = 0.6 \cdot \displaystyle\prod_{n = 1}^{99}\left(-\dfrac{500+n}{1000}\right) \approx -1.03\times 10^{-26}$

So $Av$ is a vector whose first $99$ entries are $0$ and last entry is $\approx -1.03\times 10^{-26}$. So $\|Av\|_2 \approx 1.03 \times 10^{-26}$. You can check that $\|v\|_2 \approx 1.1557$. Hence $v$ is a non-zero vector that is "almost" in the nullspace of $A$, which is why $A$ has a very small singular value.

In particular, we can bound the smallest singular value as follows:

$$\sigma_{100} = \displaystyle\min_{\substack{x \in \mathbb{R}^{100} \\ x \neq 0}}\dfrac{\|Ax\|_2}{\|x\|_2} \le \dfrac{\|Av\|_2}{\|v\|_2} \approx 8.97 \times 10^{-27}.$$

Best Answer

Related Solutions

[Math] Use SVD to reduce condition number of matrix

Structure of an ill-conditioned matrix

Related Question