Principles of Mathematics in Operations Research

46 3 Orthogonality

w

Fig. 3.8. Least norm squared solution: (ATA) is not invertible and A^ = QiE'Qj

Table 3.1. How to solve Ax = b, where A G Rmx"

Case

b e -£(4)

b e M(AT)

b <jL 11(A)

bgAf(A)

Subcase

r=n=m

r=m < n

A=[B\N]

r=m

[A\\b

B\N

o

r <

A^ -

< n

6'

0

m

I\N~\

O \

(ATA):

invertible

(ATA):

not

invertible

Solution

x=A~^1 b

XB =

B_16-

B~^1 Nxn

XB =

B-'b-

B^NXn

many

x=A*b

many

x=A*b

min.norm

Type

Exact

unique

Exact

many

Exact

many

Trivial

Least

Squares

Unique

Least

Squares

Least

Norm

Squares

Special Forms

A=LU => Lc=b,Ux=c

A=QR => Rx=QTb

A = QtEQl =»

x=Q 2 Z-xQlb

B=LU => Lc=b,UxB=c

B=QR => RxB=QTb

B=Q-,EQl =>

xB=Q2S-^1 Qjb

B=LU =• Lc=b,UxB-c

B=QR => RxB=QTb

B=Q 1 EQ 2 r =>

xB=Q2Z~^1 QTb

T

x=a

VaG

' -N'

I

M.n~r

)

A=QR => Rx=QTb

A = QxEQl =>

x=Q 2 E-lQjb

A^QiEQZ =*

x=Q 2 E1iQjb

Inverse

A^A-^1

A^B-^1

A* « B-^1

none

A*=

(ATA)~^1 AT

A*=

Q 2 E^Ql