Sensitivity Analysis in Linear Systems

This chapter will discuss the behaviour of the system of linear simultaneous equations when the matrix A and the vector b are subjected to small order perturbations ∆A and ∆b respectively. The problem then becomes and we are mainly concerned with studying the deviation ∆x of the solution with the perturbation. Such an exercise is called sensitivity analysis, for the extent of the deviation ∆x relative to ∆A and ∆b defines the sensitivity of the system. A highly sensitive system is roughly one where a relatively large deviation ∆x is incurred by small perturbations ∆A and ∆b. As we shall see, highly sensitive systems are generally to be avoided in practice. They are referred to as ill-conditioned, for a highly sensitive system would yield large variations in the results for only small uncertainties in the data. To clarify this fact, let us study the behaviour of the system of equations — representing a pair of straight lines intersecting at x = 1, y = 1 — when a small term ε is added to the equations. Surprisingly enough, the set of equations obtained, namely represents a pair of straight lines meeting at a point (x, y) given by x = 1 + 25.5ε; y = 1 − 24.5ε, and rather distant from x = 1, y = 1. Here, a small change of order ε in the equations has produced a change of 25ε in the solution. This system has definitely a high sensitivity to perturbations in its matrix A and vector b.

Three types of errors are encountered in numerical analysis, namely:

Whereas direct methods for solving linear equations yield results after a specified amount of computation, iterative methods, in contrast, ameliorate on an approximate solution until it meets a prescribed level of accuracy. In theory, direct methods should give exact solutions in the absence of round-off errors. Yet in practice, due to conditioning problems, this is never the case. For small matrices, direct methods are recommended. For the large ones, direct methods involve very large operations without real need, since the matrices are usually sparse.

The set of linear simultaneous equations Ax = b, A ∈ ℝ^m×n, has either a unique solution for x, more than one solution for x or no solution at all. For x to be unique, A is necessarily nonsingular and x is expressed as x = A⁻¹ b (m = n). The situation in which there is more than one solution occurs when b can be expressed linearly in some few column vectors of A having rank equal to r(A) < n. The equations are said to be consistent yet indeterminate. The solution comes as x = A ⁱ b, where A ⁱ is some generalized inverse of A satisfying AA ⁱ A = A. A generalized inverse A ⁱ satisfying the latter condition can be easily suggested (Bellman 1970, p. 105) as where R and P are respectively elementary row and column operations which bring A to the canonical form, namely while X,Y and Z are arbitrary. x is therefore given by where A ^t is the determinate part of A ⁱ and c is an arbitrary vector accounting for X, Y and Z. To see how this equivalence follows we note that A(I − A ^t A)= A(I − A ⁱ A)= 0 and that AA ^t b = b, so that premultiplying x by A yields b on the right hand side as our starting assumption. But the vectors of (I − A ^t A) lie in the null space of A, and a linear combination of them would represent the homogeneous solution.

Whilst the theory of linear equations is concerned with solving the equations Ax = b and the methods involved therein, linear programming is used to study the set of linear inequalities Ax≦ b. These latter inequalities define the set X = {x: Ax ≦ b, x ≧ 0} in ℝ ⁿ ; n = dim x; X being a convex set with a polyhedral shape. Linear programming’s major concern becomes then the selection among the vertices of X of the one that would either maximize or minimize the linear function Mathematically, the problem of linear programming is formulated as follows subject to the restrictions With The coefficients c₁, ... , c _n are called the cost coefficients. The elements a _ij are sometimes called the input-output coefficients; they form the so-called technological matrix. The different values of b define a bound on the available resources that set a limit on production. This nomenclature originated from the practical applications of linear programming The reader is referred to Gass (1969) for an account on these applications.