Principles of Mathematics in Operations Research

82 6 Computational Aspects

n

A/, — 2_.aivi where Vi <-> A,, 2_aj ~ ^' a> — 0;Vi.

i=l

If A), is along i>i, i.e. At, — ev\, then Ax = ^- since Zix = A~lAb- That is,

the error of size || A>|| is amplified by the factor j-, which is just the largest

eigen value of A-1. On the other hand, if b — v„, then x = A~xb = •£-, which

makes the relative error

\AX\\

INI

A„ II A,

MIL Xi

An

as much as possible.

Proposition 6.1.1 For a positive definite matrix, the solution x — A lb and

the error Ax — A~xAb always satisfy

||x|| > M and \AX\ < J!M.

Therefore, the relative error is bounded by

\AX

<

A„ \\Ah

Definition 6.1.2 The quantity c 2 a — k°- = v™*"^1 is known as condition number

Ai Amin

of A.

Remark 6.1.3 Notice that c is not affected by the size of a matrix. If A — I

or A' — -k then cA = 1 = cA> = 4™^. However, detA = 1, det A' = 10~".

Thus, determinant is a terrible measure of ill conditioning.

Example 6.1.4

2.00002 2

2 2.00002 => Ai = 2 x 10~°, A^2 = 4.00002 => c « 2 x 10

s.

2.00001

2.00001

0.5

0.5

In particular,

0 = Oi = 2 Qnnm =$• X = X\

Then, we have

\\b\\ = 2.00001 v^, Ab = b 2 -b 1 = 10 _s

and b 2 =

1

-1

2.00002

2 X2

\Ab\\ = \/2x 10-^5 ;