So, armed with the notion of vector and matrix norms, we're finally ready to discus sensitivity of a linear system. So, suppose you're solving linear system, and suppose for simplicity, that your left-hand side matrix A is known exactly, but the right-hand side is on the non approximately. In real life, of course, both are known only approximately, but let's simplify matters a little bit. Let's assume that the matrix is known for somehow. When known approximation for the right-hand side, we can only compute an approximation for the solution. So we have essentially two systems. One, exists but we don't have any way of actually dealing with this. That's a true system. We have an approximate solution to an approximate system. Now, we want the solutions of these two systems to be close. Then what we have is, we have an absolute error of input and want to quantify the errors of the results. Now, it's usually more useful to deal with relative errors, not absolute errors because that just scale-invariant. So what we actually are interested in is, the so-called condition number, and the condition number relates the relative error in the inputs to the relative error of the results. Essentially, what we want to know is how much the jitter in the inputs influences what we get. That's the proportionality known as a condition number, and that's what I'm going to discuss for the next few minutes. Let's do some preparatory steps. First of all, let's define a residual, which is the difference between the true right-hand side and at approximate right-hand side. Or alternatively, that's the difference between the true right-hand side and the result of the application of our matrix to the approximate solution. This is related to the difference between the true solution and approximate one. So we can discuss one or the other. Typically, it's easier more conveniently to deal with the residual. Second bit is again, some relation, which we will use in a few minutes. I just want to estimate the ratio of norms of the right-hand side to the norm of the solution to the norm of the true solution. Since the right-hand side is related to the matrix A times unknown vector x, I have this ratio of b to x is the ratio of the left-hand side of the system to x. By definition of a norm, I'll use p-norms for now. I'm not specifying the specific norm yet. But let's keep in mind that we will use p-norms. This is less than or equal to the norm of the matrix A. The last bit is, let's define this relative errors. Let's call it Delta x, the relative error in the solution, and Delta b is the relative error in our input. We see that the absolute error in the input is the norm of the residual, so this Delta b is the norm of the residual divided by the norm of b. So we want to relate again, this Delta X to Delta b. The calculation is actually fairly simple. First and foremost, we use the fact that this difference between the true solution, approximate solution is given by the inverse matrix acting on the residual. That's an identity. Here in the numerator, we have the norm of the product which is bounded by the product of norms, so that we have the norm of the inverse times the norm of r divided by the norm of x that bounds the relative error in the solution. Then, I will divide and multiply by b, by the norm of b. They are just multiplying by one that's an identical operation. Now, let's stare in to this line for a little bit. First of all, the norm of r divided by the norm of b is the relative error in the right-hand side, that's Delta b. Then, let's see. The norm of b divided by the norm of x is bounded by the norm of A as we have seen on the previous slide. So, overall, what I get is the last line, which says that the relative error in x is bounded by the relative error of b multiplied by this product. That's the product of the norm of the matrix times norm of its inverse. This combination, this product is known as the condition number of the matrix. We'll have this condition number. Now, it has several nice properties. First of all, it's scaling way around. If I multiply the matrix by a scalar, the condition number doesn't change. Notice that this is different from say, determinant. If a have a well-behaved matrix, I can multiply the matrix by a small number. This will multiply each element by the small number, and this will multiply the determinant by a small number to a large power. So the determinant being close to zero being small doesn't tell me much about the matrix. On the other hand, the condition number being large or small tells me something. Of course, condition number is norm-dependent. However, whether it's large or small, it's pretty much invariant to the norm because all the norms are are consistent. So if one norm of a matrix is large in some sense, then all other norms are large in again, in some sense. They're all related or they're all equivalent. So what's most important is, we need to define some notion of what's large. Once we have this, we say that if the condition number of a matrix is large, we call the matrix ill-conditioned. What it means is, if a matrix's ill-conditioned, then a small jitter in the right-hand side produces large errors, large differences in the solution. So basically, when the condition number is very large, you simply cannot solve a linear system. That's not pathological rare actually, it happens more often that we would want it to. You can write down the matrix. You can write down a linear system, which you actually cannot solve numerically. Again, this happens for ill-conditioned matrixes and they're not.