Inverse Matrix Condition Number

Inverse Matrix Condition Number Inverse Matrix and Condition No. Saswati Rakshit Contents (Jump to) Aim Scope/Applications Introduction/Basics Objective System Flow Mathematics Figure/Descriptions Future Works References Aim: Consider 2 random matrices B and C of size 8Ãâ€"8 and write a cpgm / matlab to find A to satisfy the bellow condition: If AÃâ€"B = C Prove A = CÃâ€"B-1 And repeat the pgm for matrix of size 32Ãâ€"32 and 128Ãâ€"128. Scope/Application: In many applications we require inversion of matrix. In Linear Algebra, if AÃâ€"B=C, and from B and C we can compute A where A=CÃâ€"B-1. Stimulus-Response Computations In this framework, a system is provided with an input, called a  stimulus, and the resulting response of the system is measured. Some typical examples of stimuli are visual scenes i.e. if we increase incident light’s intensity then scene’s brightness will increase. The general goal is to find a  function  that accurately describes the relation between stimulus and response. Many systems can be modeled as a linear combination of equations, and thus written as a matrix equation: [Interactions]{response}= {stimuli} The system response can thus be found using the matrix inverse. Sometimes in image processing application if we have noisy image matrix and if we know what the noise matrix was added we can find the clear image by multiplying noisy image matrix with inverted noise matrix. Intro/Basics: We have considered two 8Ãâ€"8 matrices B and C. We suppose AÃâ€"B = C. Now by performing matrix multiplication on A and B we get C. Now we have to compute A from B and C. So AÃâ€"B = C and we have to proof A = CÃâ€"B-1. It is conceptually easy to compute AÃâ€"B = C and to find A = CB-1 for 2 dimensional matrices. But for large dimensional matrices it is not possible to easily compute because there is some round off errors in A which is the result of B-1 related to B’s condition number. Thecondition numberof a function with respect to an argument measures how much the output value of the function can change for a small change in the input argument. The condition number of a regular (square) matrix is the product of the norm of the matrix and the norm of its inverse and hence depends on the kind of matrix-norm. Condition number of a square nonsingular (invertible) matrix A is defined by: cond () = |||| ·|||| where the || ·|| above could be any of the norms defined for matrices. The numerical value of the condition number of an nÃâ€"n matrix depends on the particular norm used .The norm of a square matrix A is a non-negative real number denoted by ||A||. These matrix norms have the following properties: 1. ||A|| à ¯Ã¢â€š ¬Ã‚ ¾Ãƒ ¯Ã¢â€š ¬Ã‚  Ãƒ ¯Ã¢â€š ¬Ã‚ ° if A ≠  0 2. ||à ¯Ã‚ Ã‚ §A|| à ¯Ã¢â€š ¬Ã‚ ½Ãƒ ¯Ã‚ Ã‚ ¼Ãƒ ¯Ã‚ Ã‚ §Ãƒ ¯Ã‚ Ã‚ ¼Ã‚ ·Ãƒ ¯Ã‚ Ã‚ ¼Ãƒ ¯Ã‚ Ã‚ ¼A|| for any scalar value à ¯Ã‚ Ã‚ §Ãƒ ¯Ã¢â€š ¬Ã‚  Ãƒ ¯Ã¢â€š ¬Ã‚   à ¯Ã¢â€š ¬Ã‚ ³Ãƒ ¯Ã¢â€š ¬Ã‚ ®Ãƒ ¯Ã¢â€š ¬Ã‚  Ãƒ ¯Ã‚ Ã‚ ¼Ãƒ ¯Ã‚ Ã‚ ¼A|| à ¯Ã¢â€š ¬Ã‚ «Ãƒ ¯Ã¢â€š ¬Ã‚  Ãƒ ¯Ã‚ Ã‚ ¼Ãƒ ¯Ã‚ Ã‚ ¼B|| ≠¤ à ¯Ã¢â€š ¬Ã‚  Ãƒ ¯Ã‚ Ã‚ ¼Ãƒ ¯Ã‚ Ã‚ ¼A|| à ¯Ã¢â€š ¬Ã‚ «Ãƒ ¯Ã¢â€š ¬Ã‚  Ãƒ ¯Ã‚ Ã‚ ¼Ãƒ ¯Ã‚ Ã‚ ¼B||à ¯Ã¢â€š ¬Ã‚  Ãƒ ¯Ã¢â€š ¬Ã‚   à ¯Ã¢â€š ¬Ã‚ ´Ãƒ ¯Ã¢â€š ¬Ã‚ ®Ãƒ ¯Ã¢â€š ¬Ã‚  Ãƒ ¯Ã‚ Ã‚ ¼Ãƒ ¯Ã‚ Ã‚ ¼AB|| ≠¤ à ¯Ã¢â€š ¬Ã‚  Ãƒ ¯Ã‚ Ã‚ ¼Ãƒ ¯Ã‚ Ã‚ ¼A|| ·Ãƒ ¯Ã‚ Ã‚ ¼Ãƒ ¯Ã‚ Ã‚ ¼B||à ¯Ã¢â€š ¬Ã‚  Ãƒ ¯Ã¢â€š ¬Ã‚   à ¯Ã¢â€š ¬Ã‚ µÃƒ ¯Ã¢â€š ¬Ã‚ ®Ãƒ ¯Ã¢â€š ¬Ã‚  Ãƒ ¯Ã‚ Ã‚ ¼Ãƒ ¯Ã‚ Ã‚ ¼Ax|| ≠¤ à ¯Ã¢â€š ¬Ã‚  Ãƒ ¯Ã‚ Ã‚ ¼Ãƒ ¯Ã‚ Ã‚ ¼A|| ·Ãƒ ¯Ã‚ Ã‚ ¼Ãƒ ¯Ã‚ Ã‚ ¼||à ¯Ã¢â€š ¬Ã‚  Ãƒ ¯Ã¢â€š ¬Ã‚  for any vector The norm of a matrix is a measure of how large its elements are. It is a way of determining the â€Å"size† of a matrix that is not necessarily related to how many rows or columns the matrix has. Three commonly used norms are: 1. The 1-norm: = This is the maximum absolute column sum where simply we sum the absolute values down each column and then take the biggest answer. 2. The inifinity-norm: = This is the maximum absolute row sum where simply we sum the absolute values along each row and then take the biggest answer. 3. The Euclidean norm: = This is the square root of the sum of all the squares. However, regardless of the norm, this condition number is always greater or equal to 1. If it is close to one, the matrix is well conditioned which means its inverse can be computed with good accuracy. If the condition number is large, then the matrix is said to be ill-conditioned. Practically, such a matrix is almost singular (not invertible), and the computation of its inverse or solution of a linear system of equations is prone to large numerical errors. A matrix that is not invertible has the condition number equal to infinity. Mathematically, if the condition number is less than ∞, the matrix is invertible. Numerically, there are roundoff errors which occur. A high condition number means that the matrix is almost non-invertible. The higher the condition number, the greater is the error in the calculation. This condition number helps to estimate how difficult a matrix will be to numerically invert. This condition number has certain properties: 1. For any matrix A, cond (A) ≠¥Ãƒ ¯Ã¢â€š ¬Ã‚  1 2. For identity matrix, cond (I) = 1 3. For any matrix A and scalar à ¯Ã‚ Ã‚ §, cond à ¯Ã¢â€š ¬Ã‚ ¨Ãƒ ¯Ã‚ Ã‚ §Ãƒ ¯Ã¢â€š ¬Ã‚  A) = cond (A) 4. For any diagonal matrix D = Diag(di), cond (D) = (max |di|)/(min|di|) A matrix A is ill-conditioned if relatively small changes in the input (in the matrix A) can cause large change in the output (the solution of Ax = b), i.e. the solution is not very accurate if input is rounded. Otherwise it is well-conditioned. If a matrix is ill-conditioned, then a small roundoff error can have a drastic effect on the output. However, if the matrix is well-conditioned, then the computerized solution is quite accurate. Thus the accuracy of the solution depends on the conditioning number of the matrix. Objective: To know how to determine the matrix inverse in an efficient manner. If AÃâ€"B=C and we have to prove A=CÃâ€"B-1 where A, B and C are nÃâ€"n matrices (n = 8, 32, 128) and find out the condition number of matrix using norms and finding accuracy. System flow: Steps performed: 1. Taking two matrices B and C of order 8Ãâ€"8. 2. Performing Matrix multiplication and result is stored in matrix A (performed using C Code) 3. Now calculate B-1 (performed using C Code) 4. Now again multiplying C and B-1. We get result matrix which is not accurate. 5. We need to calculate norms and condition number of a matrix (B) so we need to find norms of B and B-1. We can calculate norms in different way. Here we have used most popularly used 3 types of norms to calculate condition number of that matrix (B) which we need to get in inverse form. The norms are: 1-norm = Infinity-norm = iii) Euclidean norm = 6. Now we use norms to find condition number of matrix B by using formula cond (B) = |||| ·|||| Flow Diagram yes no Math For 22 Matrix First we consider a 22 matrix such that A= B= So by multiplying A and B we ge a 22 matrix C = Now We need to prove A=CB-1 So we need to find B-1 B-1 = 0.800 -0.200 -0.600 0.400 So now by doing CxB-1 = =A (proved) Before finding B-1 we can calculate condition number of B for the correctness of above proof, As we know cond (B) = |||| ·|||| Condition number using the 1-norm and inifinity-norm: Formula used Row Sum taking absolute values B = 2 13 3 47 Column sum 5 5 (taking absolute values) (max) Row sum B-1 = 0.800 -0.200 1.000 -0.600 0.400 1.000 Col Sum 1.4 .6 Applying 1-Norm = = maximum absolute column sum = 5, 1 = 1.4, So, cond1 (B) =  ·1 = 5Ãâ€"1.4= 7 Applying infinity-norm = = max absolute row sum = 7, ∞ = 1 So, cond∞ (B) =  ·Ã¢Ë†Å¾ = 7 Like this way we have also found condition number using the Euclidean norm which is = =5.47 = 1.095 CondE (B) =  ·E = 5.82 Here cond(B) is low in all cases.so we successfully get A =C. Because of low condition number of B,the inverse of B is acceptable. For 88 Matrix A = 1 2 3 4 1 2 2 1 2 3 1 4 3 4 2 1 4 1 3 2 3 3 1 2 2 2 1 4 2 2 2 1 3 2 1 4 3 1 2 1 1 1 2 3 1 2 2 1 1 2 1 2 1 2 1 2 2 2 3 3 2 1 2 2 B= 4 1 3 2 3 3 1 2 2 3 1 4 3 4 2 1 2 2 1 4 2 2 2 1 1 1 2 3 1 2 2 1 2 2 3 3 2 1 2 2 1 2 3 4 1 2 2 1 1 2 1 2 1 2 1 2 3 3 1 3 2 3 1 1 C=AÃâ€"B=27 30 28 52 27 37 28 20 35 38 42 64 35 46 35 27 42 35 41 59 37 43 31 27 29 29 32 49 28 37 27 22 34 30 35 50 32 39 28 25 22 24 24 41 21 29 22 17 23 25 22 39 22 30 20 15 34 33 30 53 32 40 28 23 B-1= -0.016 -0.429 0.063 0.524 0.063 -0.397 -0.222 0.587 -0.365 0.143 -0.540 0.048 0.460 -0.127 -0.111 0.508 0.095 0.071 -0.381 -0.143 0.119 0.381 -0.167 -0.024 0.270 -0.214 0.921 -0.905 -0.579 0.746 0.278 -0.484 0.206 0.571 0.175 -0.810 0.175 0.159 -0.111 -0.635 0.079 0.143 -0.317 0.381 -0.317 -0.016 0.111 0.063 -0.571 0.071 -0.714 1.857 0.786 -1.286 -0.500 0.643 0.159 -0.214 0.365 -0.238 -0.135 -0.032 0.722 -0.373 A=CÃâ€"B-1 =0.995 1.983 3.029 3.987 1.029 1.984 2.006 0.979 1.992 2.975 1.035 3.983 3.035 3.980 2.005 0.972 3.989 0.971 3.029 1.984 3.029 2.981 1.006 1.970 1.993 1.980 1.027 3.987 2.027 1.984 2.004 0.977 2.991 1.976 1.027 3.986 3.027 0.983 2.004 0.974 0.996 0.986 2.022 2.990 1.022 1.987 2.004 0.983 0.994 1.986 1.021 1.991 1.021 1.988 1.005 1.982 1.992 1.979 3.028 2.987 2.028 0.983 2.007 1.975 Relative Error for A11=(1-.995)=.005,A12= 0.017 and so on When we perform CÃâ€" B-1, we do not get original value of A because of B-1. If B-1 is not accurate we will not get accurate A. To get accuracy of A-1 we need to find condition number of B. As we know cond (B) = |||| ·|||| Condition number using the 1-norm and inifinity-norm: Formula used Row Sum taking absolute values B = 4 1 3 2 3 3 1 2 19 2 3 1 4 3 4 2 1 20 (max) 2 2 1 4 2 2 2 1 16 1 1 2 3 1 2 2 1 13 2 2 3 3 2 1 2 2 18 1 2 3 4 1 2 2 1 16 1 2 1 2 1 2 1 2 12 3 3 1 3 2 3 1 1 17 Column sum 16 16 15 25 16 19 13 11 (taking absolute values) (max) B-1 = For B-1, Row sum (max) taking absolute values = 6.428 (7th row) and column sum(max) taking absolute values = 4.906 (4th column) Applying 1-Norm = = maximum absolute column sum = 25, 1 = 4.906, So, cond1 (B) =  ·1 = 25Ãâ€"4.906 = 122.65 Applying infinity-norm = = max absolute row sum = 20, ∞ = 6.428 So, cond∞ (B) =  ·Ã¢Ë†Å¾ = 20Ãâ€"6.428 = 128.56. Like this way we have also found condition number using the Euclidean norm which is = 17.83. So here we can say that as the condition number of matrix B is high for all three cases, therefore the inverse of this matrix is showing numerical roundoff errors. Concept of Relative Error and Condition Number assume A is nonsingular and Ax = b if we change b to b + à ¢Ã‹â€ Ã¢â‚¬  b, the new solution is x + à ¢Ã‹â€ Ã¢â‚¬  x with A(x + à ¢Ã‹â€ Ã¢â‚¬  x) = b + à ¢Ã‹â€ Ã¢â‚¬  b the change in x is à ¢Ã‹â€ Ã¢â‚¬  x = A-1à ¢Ã‹â€ Ã¢â‚¬  b ‘condition’ of the solution †¢ the equations are well-conditioned if small à ¢Ã‹â€ Ã¢â‚¬  b results in small à ¢Ã‹â€ Ã¢â‚¬  x †¢ the equations are ill-conditioned if small à ¢Ã‹â€ Ã¢â‚¬  b can result in large à ¢Ã‹â€ Ã¢â‚¬  x [Singular matrix:A square matrix is called singular matrix if it’s determinant is zero.i.e. a singular matrix is not invertible] Example: Consider the linear system Ax = b with So = So here we easily find x= Now ,we change a small in b.let change in b is à ¢Ã‹â€ Ã¢â‚¬  b= So changed value= and solving the system A = we get =A= where x= changed to = due to small change in b. Now to calculate least condition number of the system we need to find Relative Error in the output and relative error in the input. Here we have relative error in the input/relative residual. = 0.01 Relative Error in the output =1 As we know, If condition number is closed to 1 then relative error and relative residual will be close. The condition number is defined by: Relative error in the output =Condition number Ãâ€" Relative error in the input. So,condition number= 1/.01=100 A matrix has high condition number is related to the fact that A is close to the singular matrix B= The following result shows that 1/cond(A) indicates how close A is to a singular matrix.Here cond(A) is 100 so, 1/cond(A)=.01 which is close enough. Description: The condition number associated with the  linear equation  Ax=bgives a bound on how inaccurate the solutionxwill be after approximation. This is before the effects of  round-off error  are taken into account; conditioning is a property of the matrix. Weshould think of the condition number as being the rate at which the solution,x, will change with respect to a change inb. Thus, if the condition number is large, even a small error inbmay cause a large error inx. On the other hand, if the condition number is small then the error inxwill not be much bigger than the error inb. The condition number may also be infinite, but this implies that the problem does not possess a unique, well-defined solution for each choice of data that is, the matrix is not invertible, and no algorithm can be expected to reliably find a solution. For large dimensional matrix such as for 3232 and 128128, the condition number is high and so inverse of that large dimensional matrix will give much error in output. Codes and Output Matrix multiplication int main() { int m, n, p, q, c, d, k, sum = 0; int A[10][10], B[10][10], C[10][10]; printf(Enter rows and columns of An); scanf(%d%d, m, n); printf(Enter the elements of An); for (c = 0; c for (d = 0; d scanf(%d, A[c][d]); printf(Enter rows and columns of Bn); scanf(%d%d, p, q); printf(Enter the elements of Bn); for (c = 0; c for (d = 0; d scanf(%d, B[c][d]); for (c = 0; c for (d = 0; d for (k = 0; k sum = sum + A[c][k]*B[k][d]; } C[c][d] = sum; sum = 0; } } for (c = 0; c for (d = 0; d printf(%dt, C[c][d]); printf(n); } getch(); } Matrix inverse #include #include int main() { float a[10][10],b[10][10],tem=0,temp=0,temp1=0,temp2=0,temp4=0,temp5=0; int n=0,m=0,i=0,j=0,p=0,q=0; printf(Enter size of 2d array(Square matrix) : ); scanf(%d,n); for(i=0;i { for(j=0;j { printf(Enter element no. %d %d :,i,j); scanf(%f,a[i][j]); if(i==j) b[i][j]=1; else b[i][j]=0; } } for(i=0;i { temp=a[i][i]; if(temp temp=temp*(-1); p=i; for(j=i+1;j { if(a[j][i] tem=a[j][i]*(-1); else tem=a[j][i]; if(temp temp=temp*(-1); if(tem>temp) { p=j; temp=a[j][i]; } } //row exchange in both the matrix for(j=0;j { temp1=a[i][j]; a[i][j]=a[p][j]; a[p][j]=temp1; temp2=b[i][j]; b[i][j]=b[p][j]; b[p][j]=temp2; } //dividing the row by a[i][i] temp4=a[i][i]; for(j=0;j { a[i][j]=(float)a[i][j]/temp4; b[i][j]=(float)b[i][j]/temp4; } //making other elements 0 in order to make the matrix a[][] an indentity matrix and obtaining a inverse b[][] matrix for(q=0;q { if(q==i) continue; temp5=a[q][i]; for(j=0;j { a[q][j]=a[q][j]-(temp5*a[i][j]); b[q][j]=b[q][j]-(temp5*b[i][j]); } } } printf(nnn); printf(Inverse of the matrix using Guass jordan elimination method:nn); for(i=0;i { for(j=0;j { printf(%.3f,b[i][j]); } printf(n); } getch(); } Matrix Condition Number #include #include int main() { int i,j,n,p,x=0,m=0,q,z=0,i1,j1; float Cond_A,poo,a[5][5],b[5],c[5],A[50][50],B[50][50],k[50],l[50]; printf(n n); printf(Program to find condition number of a matrix using infinity-norm); printf(n nn); printf(Enter rows and columns of An); scanf(%d%d, m, n); printf(Enter the elements of An); for (i = 0; i for (j = 0; j scanf(%f, A[i][j]); for(i=0;i { b[x]=0;c[x]=0; for(j=0;j { b[x]=b[x]+A[i][j]; } ++x; } for(i=0;i //FINDING LARGEST { if(b[i]>m) m=b[i]; } printf(largest row sum is %d,m); printf(nnEnter rows and columns of inv[A]n); scanf(%d%d, p, q); printf(Enter the elements of [A]n); for (i1 = 0; i1 for (j1 = 0; j1 scanf(%f, B[i1][j1]); for(i1=0;i1 { k[z]=0;l[z]=0; for(j1=0;j1 { k[z]=k[z]+B[i1][j1]; } ++z; } poo = k[0]; for(i1=1;i1 //FINDING LARGEST { if(k[i1]>poo) poo=k[i1]; } printf(largest row sum is %f,poo); Cond_A=m*poo; printf(nnCondition number of A is %f,Cond_A); //return 0; getch(); } Future works: If we work with a foggy image matrix(C) and we know the fog matrix(B) added to that image and the relation AÃâ€"B = C exist we will know whether it is possible to get the clear image matrix(A) by doing CÃâ€"B-1 calculating condition number of matrix B. If the condition number of matrix B is high then it is not possible to get accurate A from CÃâ€"B-1 as roundoff errors will increase. References: Matrix Inverse and Condition, Berlin Chen, Department of Computer Science Information Engineering, National Taiwan Normal University. Inversion error, condition number, and approximate inverses of uncertain matrices,  Laurent El Ghaoui, Department of Electrical Engineering and Computer Science,  University of California at Berkeley, Berkeley, CA 94720, USA. faculty.nps.edu/rgera/MA3042/2009/ch7.4.pdf www.rejonesconsulting.com/CS210_lect07.pdf http://teal.gmu.edu/ececourses/ece699/notes/note4.html Weisstein, Eric W. Matrix Norm. From MathWorldA Wolfram Web Resource. http://mathworld.wolfram.com/MatrixNorm.html