CHAPTER 09.08: ADEQUACY OF SOLUTIONS: Relating changes in coefficient matrix to changes in solution vector Proof

 

 

In this segment we will prove this particular theorem which relates the relative change in the solution vector to the relative change we are making in the coefficient matrix as far as the norms are concerned. If we are given this set of equation AX=C. What we want to see is that, hey, if we make a small change in our coefficient matrix shown by delta A. Then it is going to result in a change in the solution vector, which have given as delta X and we want to show that the relative change in the solution vector is related to the relative change in the coefficient matrix based on the norms by on this quantity right here. Which is the norm of A times the norm of A inverse. It can amplify as much as this number which is the norm of A times the norm of A inverse, which is also called the conditioned number of the matrix.

 

So let’s go ahead and see how we can prove this. So let A times X be equal to C. So this is a given set of equations which we have. Now what we are doing is we are making a change to the coefficient matrix. We are making A to be A prime. Then we know  if hey if we keep the right side to be the same, then it is going to result in a change in the solution vector and it’s called X prime. Now if that’s the case, then let’s go and define two different matrixes. One matrix we will define as what is delta A. Delta A is defined as A prime minus A. So it is the coefficient matrix which/what we changed it to minus the original A matrix. And delta X will be called to be X prime minus X. It is the difference between what this X got changed to minus the original solution vector. So based on this, let’s go and see and figure out what is the relationship between the relative change in X to the relative change in the A matrix right here. So we know that A times X is equal to C and so is A prime time’s X prime equal to C.

 

So that means that this quantity is the same as this quantity right here. So I can write that A times X is equal to A prime and X prime. They are the same. But we know that A prime is nothing but A plus delta A. What the original matrix was and what it changed to it is. And we know that X prime is nothing but X plus delta X. So based on this we can use our rules of binary operations here. So we can say hey, this is A times X plus delta A times X plus A times delta X plus delta A times delta X. So we are basically expanding this multiplication of two matrixes to be that. That’s A times X. Now what we are going to do is, since this is the same as this that cancels out. And what we are going to do is bring this spot here to the left hand side. That becomes minus A times delta X and that will be equal to delta A times X plus delta A times delta X. Which is the same as saying, hey let’s put this as delta A times X plus delta X. So we can take a common delta A out of these two additions and we get that. Now since we have this, what we can also do is, we can multiply both sides by A inverse. So I can say A inverse A times delta X. So we are assuming that inverse does exist. Only then will we have a unique solution. So assuming that A inverse does exist for this set of equations, we are going to multiply by A inverse on both sides. So I get A inverse times delta A times X plus delta X right here.

 

So the reason why we are doing that is because we are trying to get what delta X is and then we are going to apply some theorems about norms or the properties of norms to be able to come up with the proof of our theorem. So this and this does not cancel but I shouldn’t have it. It gives us the identity matrix So I times delta X. So this A times A will give you the identity matrix. If you are assuming that inverse exist.so A inverse times delta A times X plus delta X and since I times anything or any other matrixes like delta X equals itself.(5:47)It is defined in this case. So we get minus delta X equal’s inverse A times delta A times X plus delta X. Now we already know if we find the norm of this matrix right here that has to be less than the product of these three norms. What I mean by saying is that the norm of this matrix here will be less than or equal to the product of this norm, of norm of this and norm of this. So what we get is a norm of delta X will be less than or equal to A inverse times delta A times norm of X plus delta X.

 

So we are shedding these brackets here just for simplicity reasons. They are still there. It’s just so it doesn't look bad so that’s why we are shedding these brackets there but they are still matrixes but the norm of these matrixes are simply single scalar, positive scaler. Now what we are going to do is, we are going to multiply by A, norm of A. Again, norm of A is not going to be zero. Because if it is zero, then you will not have the inverse of the matrix. Less than or equal than the norm of A times norm of A inverse times norm of delta A times norm of X plus delta X. Keep in mind what we are doing here is that we are multiplying by a scalar here, which is norm of A and I said that norm of A is even for zero, it will still hold the inequality. But we know that norm of A is not zero because if it were then A inverse would not exist. So now we do is, we do a little bit of manipulation here. We did norm of delta X, we take this X plus delta X norm to the left hand side. Keep in mind that these inequalities will not change because all we are doing is that we are using positive numbers throughout the inequality. So that doesn’t change the inequality from less than equal to greater than equal to.

 

 From here I will get norm of A times norm of A inverse times norm of delta A divided by norm of A. The reason why we multiplied both sides by A so we get the conditioned number right here. That was the reason why we did that. And so now we have the relative change in the solution vector. Which can be amplified as much as the conditioned number of the coefficient matrix if you are making a change in the coefficient matrix. And that’s the proof of this theorem. And that of course is the end of this segment.