[Math] Determine the condition of matrix $A$

combinatoricslinear algebramatricesnumerical methods

Given is a system of equation $Ax=y$, where $A= \begin{pmatrix} 1 &
2\\ 1 & 2.01 \end{pmatrix}$ and $y=(1,1)'$

Determine the condition of the matrix $A$.

I'm not sure if I'm supposed to calculate the condition number or rather say what kind of condition this matrix is. But I think both are related to each other?

So I started by calculating the inverse of $A$ (I skip the calculation steps to keep it short):

$A^{-1}= \begin{pmatrix}
201 & -200\\
-100 & 100
\end{pmatrix}$

$\left \| A \right \|_1=\text{max}(1+1, 2+2.01)=4.01$

$det(A)= 1 \cdot 2.01 -2 \cdot 1 = 0.01$

$\left \| A^{-1} \right \|_1= \text{max}(201+100, 200+100)=301$

$det(A^{-1})=\frac{1}{det(A)}=100$

$cond(A)=\left \| A \right \|_1 \cdot \left \| A^{-1} \right \|_1=4.01 \cdot 301 = 1207.01$

And thus we can say that the matrix is badly conditioned (because the result is a high value)?


I hope it's fine like that?

Best Answer

I dont know if you have to compute the conditioning $\kappa$ as the ratio of the eigenvalues $\max(\sigma)/\min(\sigma)$ under norm 2, which would not require to compute the actual inverse.

From the R manual: "The condition number takes on values between 1 and infinity, inclusive, and can be viewed as a factor by which errors in solving linear systems with this matrix as coefficient matrix could be magnified."

The condition number must be specified by the required resolution of your algorithm.

Double Precision Representation

If you are having computations under IEEE 754 64-bit double precision representation, i.e. 64 bits per value, such as MATLAB, you will have:

  • 64 bits for the representation,
  • For the fraction: 1 bit for the sign, 52 bits for the value,
  • For the exponent: 11 bits for the exponent, biased by 1023,
  • Hence, $v=(-1)^{b_{63}} \left(1+\sum_{i=0}^{51} b_i 2^{i-52} \right) 2^\left(\sum_{i=52}^{62} b_i 2^{i-52}-2^{10}+1\right)$
  • The minimum real value is $\pm 2.2251\cdot 10^{-308}$,
  • The maximum real value is $\pm 1.7977\cdot 10^{308}$,
  • The minimum/maximum integer is: $\mp 9223372036854775808$.

From here you can build some VERY rough estimates, which are only referencial about how deep the figures can go.

Significative Order

The smallest order is $10^{-308}$. If your condition number / eigenvalue ratio $\kappa$ is $10^{-6}$, you could only make 308/6=51 products of the power of A approx., before the smallest or the biggest eigenvalue got truncated.

For example, if $v=10^{6}$, $v^{51}=10^{306}$, and $v^{52}=$Inf.

From here, the allowable conditioning would be given as, with $n$ the number of expected iterations using the compromised values: $$\kappa=10^{-308/n}$$

Significative Digits

By other side, the representation allows 52 bits i.e. $10^{-15}$ significative digits on the fractions. Hence if you want to keep a resolution in significative digits of $10^{-6}$, you could only make 15-6=9 products approximatedly of the power of A before the smallest or the biggest eigenvalue got truncated.

For example:

  • $v=123456$ (6 digits),
  • $v^2=15241383936$ (11 digits),
  • $v^3=1881640295202816$ (16 digits),
  • $v^4=232299784284558852096$ (21 digits) truncated to $\sim 232299784284558847360$, with a error ratio of $10^{-17}$.
  • $v^5=28678802168634497644363776$ (26 digits) truncated to $\sim 28678802168634496830758912$, with a error ratio of $10^{-17}$.
  • $v^6=3540570200530940541182574329856$ (31 digits) truncated to $\sim 3540570200530 940126422213591000$, with a error ratio of $10^{-16}$.

From here, the allowable conditioning would be given as, with $n$ the number of expected iterations using the compromised values: $$\kappa=10^{15-n}$$

Hence, it must be observed from the problem factors which is the proper conditioning figure your calculation should retain, based on the usage of the data and the purpose of the algorithms.

https://stat.ethz.ch/R-manual/R-devel/library/Matrix/html/rcond.html https://www.mathworks.com/help/matlab/ref/cond.html https://en.wikipedia.org/wiki/Condition_number https://en.wikipedia.org/wiki/Double-precision_floating-point_format

Related Question