find the (infinity norm) condition number of the following matrix?

Question

How can I find the (infirmity norm) condition number of the following matrix? $$A =\begin{bmatrix}1 & 2 \\2&4.001\end{bmatrix}$$

Looking for some guidance on how to solve this problem, thanks!

Answer 1

I am assuming that means infinity norm

$$ A = \begin{bmatrix} 1 & 2 \\ 2 & 4.001 \end{bmatrix} \tag{1} $$

$$ \| A\|_{\infty} = \max_{1 \leq i \leq m } \| a_{i}^{*} \|_{1} \tag{2} $$

the $\infty $ norm is equal to the max row sum. So $a_{i}^{*}$ denotes the $ith$ row

then we have

$$ \|a_{1}^{*}|| = 3 \\ \| a_{2}^{*}|| = 6.001 $$

$$ \|A\|_{\infty} = 6.001 \tag{3}$$

import numpy as np
import math


A = np.matrix([[1 ,2],[2, 4.001 ]])
Ainf = np.linalg.norm(A,np.inf)

Ainf
Out[5]: 6.001

This is an example matrix of an ill-conditioned matrix apparently

Acond = np.linalg.cond(A)

A1 = np.matrix([[1 ,2],[2, 4.000 ]])
A1cond = np.linalg.cond(A1)

Acond
Out[8]: 250008.00009210614

A1cond
Out[9]: 2.517588727560788e+16

If we create a slight perturbation it is massively ill-conditioned.

Note that

$$ \kappa(A) = \| A \| \| A^{-1}\| \tag{4} $$

using the $\infty $ norm

we take the inverse

$$ A^{-1} = \frac{1}{4.001-4.00}\begin{bmatrix} 4.001 & -2 \\ -2 & 1 \end{bmatrix} \tag{5} $$ $$ A^{-1} = \frac{1}{0.001}\begin{bmatrix} 4.001 & -2 \\ -2 & 1 \end{bmatrix} \tag{6} $$

if you see here where the problem is where you invert the matrix $$ A^{-1} = \begin{bmatrix} 4001.000 & -2000 \\ -2000 & 1000 \end{bmatrix} \tag{7} $$

then we take $\infty$ norm

$$ \kappa(A) = 6.001 \cdot 6001 \approx 36000 \tag{6}$$

Note that

$$\|A^{-1}\|_{\infty} = 6001 \tag{7}$$

because it has max absolute value

See here

np.linalg.cond(A,np.inf)
Out[30]: 36012.00099998798

Eigenvalues

$$ det(A - \lambda I ) = det \bigg( \begin{bmatrix} 1 - \lambda & 2 \\ 2 & 4.00-\lambda+\epsilon \end{bmatrix} \bigg) \tag{8}$$

$$ det(A - \lambda I ) = (1-\lambda)(4.00-\lambda+\epsilon) -4 \tag{9}$$

$$ det(A - \lambda I ) = \lambda^{2} -5\lambda + \epsilon - \epsilon \lambda \tag{10}$$

Can you continue from there? I was on this path because

$$ \kappa(A) = \frac{\lambda_{max}(A)}{\lambda_{min}(A)} \tag{11} $$

there are only two eigenvalues..this isn't exactly for the $\infty$ norm

If $\epsilon =0$

$$ det(A - \lambda I ) = \lambda^{2} -5\lambda \implies \lambda_{1} =5 \lambda_{2} =0 \tag{12}$$

what is that ratio.

On Ill-Conditioning

Ill-Conditioning is most understood perhaps when you have an algorithm that isn't backwards stable like classical gram Schmidt.

function qrcgs(A)
# Classical Gram Schmidt for an m x n matrix 

(m,n) = size(A) 
# Generates the Q, R matrices
Q = zeros(m,n) 
R = zeros(n,n)
    for k = 1:n
        # Assign the vector for normalization
        w = A[:,k]
        for j=1:k-1
            # Gets R entries
            R[j,k] = Q[:,j]'*w
        end

        for j = 1:k-1
           # Subtracts off orthogonal projections 
           w = w-R[j,k]*Q[:,j]
        end
        # Normalize 
        R[k,k] = norm(w)
        Q[:,k] = w./R[k,k]
    end

    return Q,R
end 

function generate_matrix(eps)
# generates matrix

    matrix = [[ 1 2];[2 4+eps] ]

    return matrix

end   

function backsub(R,b)
# Backsub for upper triangular matrix.
(m,n) = size(R)
p = min(m,n)
x  = zeros(n,1)

    for i=p:-1:1
        # Look from bottom, assign to vector
        r = b[i]
        for j=i+1:p
            # Subtract off the difference
            r = r-R[i,j]*x[j]
        end
        x[i] = r/R[i,i]
    end

    return x
end 

mu = 1e-5

my_matrix = generate_matrix(mu)

2×2 Array{Float64,2}:
 1.0  2.0    
 2.0  4.00001

x = ones(2)

b = my_matrix*x

if I take $Ax=b$ and solve $QRx=b$ and find the relative error $\frac{\| \hat{x} -x\|}{\|x\|} $ when you do $Rx = Q^{-1}b $

Q,R = qrcgs(my_matrix)

b1 = Q'*b
x1 = backsub(R,b1)
x2 = norm(x1-x)/norm(x)

0.0003159759388686106

the closer $\epsilon $ is to $0$ the worse this error is because the more ill-conditioned we are. We are losing more precision.

See if I make $\mu = 1e-10$

mu = 1e-10

I get massive error, my $\hat{x}$ comes out like this

2×1 Array{Float64,2}:
  1.33203e10
 -6.66015e9 

it is supposed to be

2-element Array{Float64,1}:
 1.0
 1.0

so my error is

1.0530625888158983e10