Principles of Mathematics in Operations Research

6

Computational Aspects

For square matrices, we can measure the sensitivity of the solution of the linear

algebraic system Ax = b with respect to changes in vector 6 and in matrix

A by using the notion of the condition number of matrix A. If the condition

number is large, then the matrix is said to be ill-conditioned. Practically, such

a matrix is almost singular, and the computation of its inverse or solution of a

linear system of equations is prone to large numerical errors. In this chapter,

we will investigate computational methods for solving Ax = b, and obtaining

eigen values/vectors of A.

6.1 Solution of Ax = b

Let us investigate small changes in the right hand side of Ax = b as if we are

making a sensitivity analysis:

6 n> b + Ab => x i-»- x + Ax

A(x + Ax) = b + Ab& A(AX) = Ab.

Similarly, one can investigate the effect of perturbing the coefficient matrix

A:

A\-^A + AA^-x^x + Ax

We will consider these cases with respect to the form of the coefficient matrix

A in the following subsections.

6.1.1 Symmetric and positive definite

Let A be symmetric. Without loss of generality, we may assume that we or-
dered the nonnegative eigen values: 0 < Ai < A2 < • • • < An. Since Ab is a
vector itself, it could be represented in terms of the basis formed by the asso-
ciated eigen vectors v\,V2,...,vn. Moreover, we can express Ab as a convex
combination because its norm is sufficiently small.