Principles of Mathematics in Operations Research

42 3 Orthogonality

Definition 3.2.14 A = QR is known as Q~R decomposition.

Remark 3.2.15 If A = QR, then it is easy to solve Ax — b:

x = (ATA)-^1 ATb = (RTQTQR)-^1 RTQTb = {RTR)-lRTQTb = R~^1 QTb.

Rx = QTb.

3.2.3 Pseudo (Moore-Penrose) Inverse

Ax = b<->Ax=p = Pb<&x = (ATA)~lATb.

Ax = p have only one solution o- The columns of A are linearly inde-

pendent <$• N{A) contains only 6 <& rank(A) = n •& ATA is invertible.

Let A^ be pseudo inverse of A. If A is invertible, then A^ = A"^1. Oth-

erwise, A^ — (ATA)~*AT', if the above conditions hold. Then, x = A%.

Otherwise, the optimal solution is the solution of Ax — p which is the one

that has the minimum length.

Let x~o 9 j4afo = P> x"o = xr + w where xr G TZ(AT) and w £ N{A). We

have the following properties:

i. Axr = A{xr + w) = Ax~o = p.

ii. VS 9 Ax — p, x = xr + w with a variation in w part only, where xr is

fixed.

iii. \\xr +w\\ — \\xr\\^2

w

where a > 0, /3 > 0.

Proposition 3.2.16 The optimal least squares solution to Ax = b is xr (or

simply x), which is determined by two conditions

1. Ax — p, where p is the projection ofb onto the column space of A.


2. x lies in the row space of A.
   Then, x = A^b.

"00 0 0
Example 3.2.17 A = 0/300

[o 0 a0

Then, K(A) = R^2 and p = Pb = (0, b 2 , b 3 )T

Ax =p •&

x 2 — -r, X3 — —, £i=a;4 = 0, with the minimum length!

a a

"0 0 0 0'

0/3 0 0

0 0 a0

Xi

X2

X~4

=

"0"

&2

b 3