2
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ Perhaps you mean the infinity norm? If not, we need a definition of the infirmity norm. $\endgroup$ – GEdgar Oct 1 '18 at 20:49
  • $\begingroup$ What do you know about condition numbers and the infinity norm? Have you tried working with the definitions? $\endgroup$ – Ethan Bolker Oct 1 '18 at 20:50
  • $\begingroup$ yes infinity norm $\endgroup$ – fr14 Oct 1 '18 at 20:51
  • 3
    $\begingroup$ @GEdgar well of course if a matrix is ill-conditioned, we say it's infirm $\endgroup$ – Ben Grossmann Oct 1 '18 at 23:01
4
$\begingroup$

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
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ why is $a_1=3$ but $a_2$ is only $4.001$? $\endgroup$ – fr14 Oct 1 '18 at 20:54
  • $\begingroup$ i screwed up one moment $\endgroup$ – user3417 Oct 1 '18 at 20:56
  • $\begingroup$ would this be well-conditioned or ill-conditioned then? $\endgroup$ – fr14 Oct 1 '18 at 20:58
  • $\begingroup$ visually looking at, sometimes I remember example matrices like this where you add .00001 and it becomes ill-conditioned $\endgroup$ – user3417 Oct 1 '18 at 20:59
  • 1
    $\begingroup$ okay well thanks for everything! $\endgroup$ – fr14 Oct 1 '18 at 22:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.