ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
-------------------------------

TRẦN THỊ THU HƯỜNG

PHƯƠNG PHÁP BÌNH PHƯƠNG
TỐI THIỂU TOÀN PHẦN

LUẬN VĂN THẠC SĨ TOÁN HỌC

THÁI NGUYÊN - 2019


ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
-------------------------------

TRẦN THỊ THU HƯỜNG

PHƯƠNG PHÁP BÌNH PHƯƠNG
TỐI THIỂU TOÀN PHẦN
Chuyên ngành: Toán ứng dụng
Mã số
: 8 46 01 12

LUẬN VĂN THẠC SĨ TOÁN HỌC

NGƯỜI HƯỚNG DẪN KHOA HỌC
TS. Nguyễn Thị Ngọc Oanh

THÁI NGUYÊN - 2019


✶

▼ö❝ ❧ö❝

❚r❛♥❣

▲í✐ ❝↔♠ ì♥

✷

▲í✐ ♥â✐ ✤➛✉

✸

❈❤÷ì♥❣ ✶ ●✐î✐ t❤✐➺✉ ✈➲ ♣❤÷ì♥❣ ♣❤→♣ ❜➻♥❤ ♣❤÷ì♥❣ tè✐
t❤✐➸✉ t♦➔♥ ♣❤➛♥

✻

✶✳✶✳

▼ët sè ❦þ ❤✐➺✉ ✈➔ ❦✐➳♥ t❤ù❝ ❝ì ❜↔♥ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳

✻

✶✳✷✳


P❤÷ì♥❣ ♣❤→♣ ❜➻♥❤ ♣❤÷ì♥❣ tè✐ t❤✐➸✉ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳

✽

✶✳✸✳

✶✳✹✳

✶✳✷✳✶✳

P❤➙♥ t➼❝❤ ❣✐→ trà ❦➻ ❞à

✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✶✶

✶✳✷✳✷✳

◆❣❤✐➺♠ ❜➻♥❤ ♣❤÷ì♥❣ tè✐ t❤✐➸✉ ✈➔ ❙❱❉

✳ ✳ ✳ ✳ ✳ ✳ ✳ ✶✹

P❤÷ì♥❣ ♣❤→♣ ❜➻♥❤ ♣❤÷ì♥❣ tè✐ t❤✐➸✉ t♦➔♥ ♣❤➛♥ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✶✹
✶✳✸✳✶✳

❚❤✐➳t ❧➟♣ ❜➔✐ t♦→♥

✶✳✸✳✷✳

◆❣❤✐➺♠ ❝ì ❜↔♥

✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✶✹


✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✶✻

❚❤✉➟t t♦→♥ ❜➻♥❤ ♣❤÷ì♥❣ tè✐ t❤✐➸✉ t♦➔♥ ♣❤➛♥ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✷✵

❈❤÷ì♥❣ ✷ ▼ët sè ù♥❣ ❞ö♥❣ ❝õ❛ ♣❤÷ì♥❣ ♣❤→♣ ❜➻♥❤ ♣❤÷ì♥❣
tè✐ t❤✐➸✉ t♦➔♥ ♣❤➛♥

✷✷

✷✳✶✳

❍ç✐ q✉② ✤ì♥ t✉②➳♥ t➼♥❤ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✷✷

✷✳✷✳

❍ç✐ q✉② ♣❤✐ t✉②➳♥ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✷✻


✷

▲í✐ ❝↔♠ ì♥
▲✉➟♥ ✈➠♥ ✤÷ñ❝ ❤♦➔♥ t❤➔♥❤ ❞÷î✐ sü ❝❤➾ ❜↔♦ ✈➔ ❤÷î♥❣ ❞➝♥ t➟♥ t➻♥❤ ❝õ❛
❚❙✳ ◆❣✉②➵♥ ❚❤à ◆❣å❝ ❖❛♥❤✳ ❈æ ✤➣ ❞➔♥❤ ♥❤✐➲✉ t❤í✐ ❣✐❛♥ ❤÷î♥❣ ❞➝♥ ✈➔
❣✐↔✐ ✤→♣ t❤➢❝ ♠➢❝ ❝õ❛ tæ✐ tr♦♥❣ s✉èt q✉→ tr➻♥❤ ❧➔♠ ❧✉➟♥ ✈➠♥✳ ❚æ✐ ①✐♥
❜➔② tä ❧á♥❣ ❜✐➳t ì♥ s➙✉ s➢❝ ✤➳♥ ❝æ✳
❚æ✐ ①✐♥ ❣û✐ tî✐ ❝→❝ t❤➛②✱ ❝æ tr♦♥❣ ❦❤♦❛ ❚♦→♥ ✲ ❚✐♥ ❝õ❛ ❚r÷í♥❣ ✣↕✐
❤å❝ ❑❤♦❛ ❤å❝ ✲ ✣↕✐ ❤å❝ ❚❤→✐ ◆❣✉②➯♥ ❧í✐ ❝↔♠ ì♥ s➙✉ s➢❝ ♥❤➜t ✈➲ ❝æ♥❣
❧❛♦ ❞↕② ❞é tr♦♥❣ s✉èt q✉→ tr➻♥❤ ❤å❝ t➟♣ t↕✐ tr÷í♥❣✳
❈✉è✐ ❝ò♥❣ tæ✐ ①✐♥ ❝↔♠ ì♥ ❇❛♥ ❣✐→♠ ❤✐➺✉ tr÷í♥❣ ❚❍P❚ ◗✉➳ ❱ã sè ✶✱

t➟♣ t❤➸ ❝→❝ t❤➛② ❝æ ❣✐→♦ tr♦♥❣ tê ❚♦→♥✲❚✐♥ ❝õ❛ ❚r÷í♥❣✱ ❣✐❛ ✤➻♥❤✱ ❜↕♥
❜➧ ✈➔ ♥❣÷í✐ t❤➙♥ ✤➣ q✉❛♥ t➙♠✱ t↕♦ ✤✐➲✉ ❦✐➺♥✱ ✤ë♥❣ ✈✐➯♥✱ ❝ê ✈ô ✤➸ tæ✐ ❝â
t❤➸ ❤♦➔♥ t❤➔♥❤ ♥❤✐➺♠ ✈ö ❝õ❛ ♠➻♥❤✳

❚❤→✐ ◆❣✉②➯♥✱ ♥❣➔②✳✳✳t❤→♥❣ ✹ ♥➠♠ ✷✵✶✾
❍å❝ ✈✐➯♥

❚r➛♥ ❚❤à ❚❤✉ ❍÷í♥❣




ớ õ
Pữỡ ữỡ tố t t t st sqr
ữủ ợ t ữ ởt tt
q rtr sst tự ỳ õ
số ữỡ tr ỡ số õ

A Rmìn
t ợ

B Rmìd



m > n

trữợ

AX B


X Rnìd

ợ tr

ữ t

õ ổ õ

X



t Pữỡ ữỡ tố t t sỹ tờ qt
q ừ ữỡ ữỡ tố t st sqr
tr

A



B



Pữỡ ữỡ tố t t ởt tt
q ữợ ữủ t số t t t ữợ ữủ t số t
t tợ ởt ợ rở r ỹ ồ ữ ỷ ỵ t
tỹ ở ự ử tr tt tố
t ỵ t s ồ õ ữủ t ởt ữỡ tr

t t s

1 x1 + ã ã ã + n xn =
tr õ

1 , . . . , n







x = [x1 , . . . , xn ]T Rn


tỡ

t số trữ t t r tứ ỳ ữủ
õ ừ t ởt ữợ ữủ ừ t số ữ t
t ởt ú t
ồ

A Rmìn

i , i = 1, . . . , n

tr õ tự

tỡ


b Rm

ự

.

Ax = b

i

tữỡ ự ự ỳ

õ t õ





ỗ

m

ữỡ tr

n



ợ t t ữỡ ữỡ tố t

t tr

A

ừ ỳ

i

tr ừ ữủ sỷ

ổ õ s số õ s số ữủ t r tỡ
q st

b

tự ừ sỷ ổ

t tỹ t tt s số ừ ổ s số ụ
ữủ t r ỳ ừ tr

A

ữỡ tố

t t ỵ tỹ t ỡ t s số ữủ t r
tỡ q st

b

tr ỳ


A.

ồ t ỳ ừ ữỡ ữỡ tố t
t s ợ ữỡ ữỡ tố t t õ t t ởt
ử tr trữớ ủ t õ ởt t số tự ợ

n = 1

Pữỡ

tr tr t

x = .
t t r tứ

x

số



m ừ t ữợ ữủ t

s ợ

A = [a1 , . . . , am ]T




b = [b1 , . . . , bm ]T

tr õ

ợ

ai , bi



ai = a0i + ai ,



bi = b0i + bi , i = 1, . . . , m,



s số ở ỳ

a0i , b0i

ừ

, .






ữủ tự





ự tr

b

ai = 0

õ s số r

r trữớ ủ t õ t sỷ ử

ữỡ ữỡ tố t ữỡ tr tự t
ỹ t õ tờ ữỡ õ

m

(bi ai x)2 .
i=1
r trữớ ủ tr tờ tr t ỹ t




ữợ ữủ


x

ừ

x

ữủ ổ tự

x =




ổ õ s số tự

n
i=1 ai bi
n
2
i=1 ai

bi = 0

t t ữỡ tr

ữợ


= .
x

ỷ ử ữỡ ữỡ tố t ỹ t õ
tờ ữỡ s t t ữủ ữợ ữủ tốt t

x =

x

ữ s

n
2
i=1 bi
.
n
i=1 ai bi

tr tỹ t ữủ ổ õ s số


bi = 0.

ai = 0

r trữớ ủ t sỷ ử ữỡ

ữỡ tố t t ự t t
t ữỡ ỵ tỹ t ỡ
ữủ ữỡ ữỡ ợ t ữỡ
ữỡ tố t t ũ ởt số tự q
ữ P t tr ữỡ tố t

ữỡ tố t õ ọ t ữỡ tố t t
ỵ ữỡ tố t t ữỡ
ừ tr ởt số ự ử ừ ữỡ ữỡ
tố t t tr ự ỗ q ỡ t t ỗ q
t ởt số ử số ữủ tr ồ t
q ừ ữỡ


✻

❈❤÷ì♥❣ ✶

●✐î✐ t❤✐➺✉ ✈➲ ♣❤÷ì♥❣ ♣❤→♣ ❜➻♥❤
♣❤÷ì♥❣ tè✐ t❤✐➸✉ t♦➔♥ ♣❤➛♥
❚r♦♥❣ ❝❤÷ì♥❣ ♥➔②✱ ❝❤ó♥❣ tæ✐ tr➻♥❤ ❜➔② ♠ët sè ❦✐➳♥ t❤ù❝ ❧✐➯♥ q✉❛♥
tî✐ ♣❤÷ì♥❣ ♣❤→♣ ❜➻♥❤ ♣❤÷ì♥❣ tè✐ t❤✐➸✉✱ ♣❤÷ì♥❣ ♣❤→♣ ❜➻♥❤ ♣❤÷ì♥❣ tè✐
t❤✐➸✉ t♦➔♥ ♣❤➛♥ ✈➔ ❝â ♠✐♥❤ ❤å❛ ♠ët ✈➔✐ ✈➼ ❞ö ❦❤✐ sû ❞ö♥❣ ❤❛✐ ♣❤÷ì♥❣
♣❤→♣ ♥â✐ tr➯♥✳

✶✳✶✳ ▼ët sè ❦þ ❤✐➺✉ ✈➔ ❦✐➳♥ t❤ù❝ ❝ì ❜↔♥
•

▼❛ tr➟♥ ❝❤✉②➸♥ ✈à ❝õ❛ ♠❛ tr➟♥

• R(S)

✭t÷ì♥❣ ù♥❣

Rr (S)✮


❝→❝ ❤➔♥❣✮ ❝õ❛ ♠❛ tr➟♥
❧➔ ♥❤➙♥ ❝õ❛

•

A

S ✱ N (S) ❦þ ❤✐➺✉ ❧➔ ❦❤æ♥❣ ❣✐❛♥ ✈➨❝ tì ❦❤æ♥❣ ❤♦➦❝

S✳

▼❛ tr➟♥ ✤÷í♥❣ ❝❤➨♦

aij = 0

AT .

❧➔ ❦❤æ♥❣ ❣✐❛♥ s✐♥❤ ❜ð✐ ❝→❝ ❝ët ✭t÷ì♥❣ ù♥❣

A

❝ï

m×n

A = ❞✐❛❣(α1 , · · · , αp ),
✈î✐

✤÷ì❝ ❦þ ❤✐➺✉ ❧➔


✈î✐

i=j

✈➔

•

▼❛ tr➟♥ ✤ì♥ ✈à ❝ï

•

❈❤♦ ♣❤÷ì♥❣ tr➻♥❤

aii = αi
m×m

✈î✐

❦➼ ❤✐➺✉ ❧➔
✈î✐

p = min {m, n}

i = 1, . . . , p.

✤÷ñ❝ ❦➼ ❤✐➺✉ ❧➔

Im


❤❛② ✤ì♥ ❣✐↔♥ ❧➔

AX = B
tr♦♥❣ ✤â

A

❧➔ ♠❛ tr➟♥ ❝ï

m × n✱ X

❧➔ ♠❛ tr➟♥ ❝ï

I.
✭✶✳✶✮

n × d✱

✈➔

B

❧➔ ♠❛


✼

tr➟♥ ❝ï

m × d✳


◆❣❤✐➺♠ ❜➻♥❤ ♣❤÷ì♥❣ tè✐ t❤✐➸✉ ❝â ❝❤✉➞♥ ♥❤ä ♥❤➜t ❝õ❛ ♣❤÷ì♥❣ tr➻♥❤
✭✶✳✶✮ ✤÷ñ❝ ❦þ ❤✐➺✉ ❧➔

X

✱ ♥❣❤✐➺♠ ❜➻♥❤ ♣❤÷ì♥❣ tè✐ t❤✐➸✉ t♦➔♥ ♣❤➛♥ ❝â

❝❤✉➞♥ ♥❤ä ♥❤➜t ✤÷ñ❝ ❦þ ❤✐➺✉ ❧➔
❚r♦♥❣ tr÷í♥❣ ❤ñ♣
✈➨❝ tì

•

x, b

d = 1✱

ˆ✳
X

t❛ ❝â t❤➸ ❦➼ ❤✐➺✉ ❝→❝ ♠❛ tr➟♥

X, B

❜ð✐ ❝→❝

t÷ì♥❣ ù♥❣✳

❈❤✉➞♥ ❋r♦❜❡♥✐✉s ❝õ❛ ♠❛ tr➟♥


n

M

F

M

❝ï

m×n

✤÷ñ❝ ✤à♥❤ ♥❣❤➽❛ ❜ð✐

m

m2ij =

=

tr(M T M ),

✭✶✳✷✮

i=1 i=1
tr♦♥❣ ✤â tr(M

•


T

M)

❧➔ ✈➳t ❝õ❛ ♠❛ tr➟♥

M T M.

❈❤✉➞♥ ✷ ❤❛② ❝❤✉➞♥ ❊✉❝❧✐❞❡ ❝õ❛ ✈➨❝ tì

y

tr♦♥❣ ❦❤æ♥❣ ❣✐❛♥

n

❝❤✐➲✉

✤÷ñ❝ ✤à♥❤ ♥❣❤➽❛ ❜ð✐

n

y

2

yi2 .

=


✭✶✳✸✮

i=1

•

P❤➙♥ t➼❝❤ ❣✐→ trà ❦➻ ❞à ✲ ❙❱❉✳

❑þ ❤✐➺✉ ❙❱❉ ❝õ❛ ♠❛ tr➟♥

A

❝ï

m × n, m > n

❝â ❞↕♥❣

A = U Σ V T,

✭✶✳✹✮

tr♦♥❣ ✤â

U = [U1 ; U2 ], U1 = [u1 , · · · , un ], U2 = [un+1 , · · · , um ], ui ∈ Rm , U T U = Im ,
V = [v1 , · · · , vn ], vi ∈ Rn , V T V = In ,
Σ = ❞✐❛❣(σ1 , · · · , σn ) ∈ Rm×n , σ1 ≥ · · · ≥ σn ≥ 0.
❚❛ ❝ô♥❣ ❦➼ ❤✐➺✉ ❙❱❉ ❝õ❛ ♠❛ tr➟♥

[A; B] ❝ï m × (n + d), m > n ❝â ❞↕♥❣


[A; B] = U ΣV T ,

✭✶✳✺✮


✽

tr♦♥❣ ✤â

U = [U1 ; U2 ], U1 = [u1 , · · · , un ], U2 = [un+1 , · · · , um ], ui ∈ Rm , U T U = Im ,
V =

Σ=

V11 V12

= [v1 , · · · , vn+d ], vi ∈ Rn+d , V T V = In+d ,

V21 V22
Σ1

0

0

Σ2

= ❞✐❛❣(σ1 , · · · , σn+t ) ∈ Rm×(n+d) , t = min{m − n, d},


Σ1 = ❞✐❛❣(σ1 , · · · , σn ) ∈ Rn×n ,
Σ1 = ❞✐❛❣(σn+1 , · · · , σn+t ) ∈ R(m−n)×d ,
✈➔

σ1 ≥ · · · ≥ σn+t ≥ 0.

✶✳✷✳ P❤÷ì♥❣ ♣❤→♣ ❜➻♥❤ ♣❤÷ì♥❣ tè✐ t❤✐➸✉
P❤÷ì♥❣ ♣❤→♣ ❜➻♥❤ ♣❤÷ì♥❣ tè✐ t❤✐➸✉ ✭▲❙✮ ❧➔ ♠ët ❝→❝❤ t✐➳♣ ❝➟♥ ♣❤ê
❜✐➳♥ ❦❤✐ ❣✐↔✐ ❤➺ t✉②➳♥ t➼♥❤ q✉→ ①→❝ ✤à♥❤✱ tù❝ ❧➔ sè ♣❤÷ì♥❣ tr➻♥❤ ♥❤✐➲✉
❤ì♥ sè ➞♥✳ ◆â✐ ❝❤✉♥❣ ❝→❝ ❤➺ ♥❤÷ ✈➟② ❦❤æ♥❣ ❝â ♥❣❤✐➺♠ ♥❤÷♥❣ t❛ t➻♠
♥❣❤✐➺♠ ①➜♣ ①➾ ❝õ❛ ❤➺ ❜➡♥❣ ❝→❝❤ ❝ü❝ t✐➸✉ ❤â❛ tê♥❣ ❜➻♥❤ ♣❤÷ì♥❣ ❝õ❛ s❛✐
sè ✤÷ñ❝ t↕♦ t❤➔♥❤ ❦❤✐ ❣✐↔✐ ♠é✐ ♣❤÷ì♥❣ tr➻♥❤ ✤ì♥ ❧➫✳
❳➨t ❜➔✐ t♦→♥ t➻♠

x ∈ Rn

t❤ä❛ ♠➣♥ ♣❤÷ì♥❣ tr➻♥❤

Ax = b,
tr♦♥❣ ✤â

b ∈ Rm

✤➣ ❜✐➳t ✈➔ ❞ú ❧✐➺✉

♥❤✐➲✉ ❤ì♥ sè ➞♥✱ tù❝ ❧➔
tr÷í♥❣ ❤ñ♣

b∈
/ R(A)


A ∈ Rm×n ✳

❑❤✐ sè ♣❤÷ì♥❣ tr➻♥❤

m > n t❤➻ ❤➺ ✤÷ñ❝ ❣å✐ ❧➔ ❤➺

q✉→ ①→❝ ✤à♥❤✳ ❚r♦♥❣

t❤➻ ❤➺ q✉→ ①→❝ ✤à♥❤ ❦❤æ♥❣ ❝â ♥❣❤✐➺♠ ❝❤➼♥❤ ①→❝✱

❞♦ ✈➟② t❛ sû ❞ö♥❣ ❦➼ ❤✐➺✉

Ax ≈ b.

◆❣❤✐➺♠ ❜➻♥❤ ♣❤÷ì♥❣ tè✐ t❤✐➸✉ ✤÷ñ❝ tr➻♥❤ ❜➔② tr♦♥❣ ✤à♥❤ ♥❣❤➽❛ ❞÷î✐
✤➙②✳

✣à♥❤ ♥❣❤➽❛ ✶✳✶

❳➨t ❜➔✐ t♦→♥ t➻♠ ❝ü❝ t✐➸✉

min Ax − b 2 ,

x∈Rn
❈ü❝ t✐➸✉

Ax ≈ b.

x


A ∈ Rm×n , b ∈ Rm .

✭✶✳✻✮

❜➜t ❦ý ✤÷ñ❝ ❣å✐ ❧➔ ♥❣❤✐➺♠ ❜➻♥❤ ♣❤÷ì♥❣ tè✐ t❤✐➸✉ ❝õ❛ ❤➺


✾

▼ët tr♦♥❣ ♥❤ú♥❣ ù♥❣ ❞ö♥❣ q✉❛♥ trå♥❣ ❝õ❛ ❜➔✐ t♦→♥ ▲❙ ❧➔ ÷î❝ ❧÷ñ♥❣
t❤❛♠ sè tr♦♥❣ ♠æ ❤➻♥❤ t❤è♥❣ ❦➯ t✉②➳♥ t➼♥❤✳ ●✐↔ sû r➡♥❣ t❛ ❝â
s→t

b = [b1 , . . . , bm ]T

n

❧✐➯♥ ❤➺ ✈î✐

t❤❛♠ sè ❝❤÷❛ ❜✐➳t

m

q✉❛♥

x = [x1 , . . . , xn ]T

❜ð✐ ♣❤÷ì♥❣ tr➻♥❤


Ax = b0 ,
✈î✐

∆b [∆b1 , . . . , ∆bm ]T

❚❛ s➩ ❣✐↔ sû r➡♥❣

A

∆bi , i = 1, 2, . . . , m

✈➔

n

❝â ❤↕♥❣ ❧➔

❑❤✐ ✤â ÷î❝ ❧÷ñ♥❣ ▲❙

x

b = b0 + ∆b,

✈➔

∆b

❧➔ ❝→❝ s❛✐ sè ♥❣➝✉ ♥❤✐➯♥✳

❝â ❣✐→ trà tr✉♥❣ ❜➻♥❤ ❜➡♥❣


0✳

t❤ä❛ ♠➣♥ ❤❛✐ ✤✐➲✉ ❦✐➺♥ ❞÷î✐ ✤➙②

✐✮ ❑❤æ♥❣ ❝â s❛✐ sè ❤➺ t❤è♥❣ tr♦♥❣ ÷î❝ ❧÷ñ♥❣✳
✐✐✮ ❈→❝ ÷î❝ ❧÷ñ♥❣ ❧➔ ❤➔♠ t✉②➳♥ t➼♥❤ ❝õ❛

b.

❚➼♥❤ ❝❤➜t ♥❣❤✐➺♠ ❝õ❛ ♣❤÷ì♥❣ ♣❤→♣ ❜➻♥❤ ♣❤÷ì♥❣ tè✐ t❤✐➸✉ ✤÷ñ❝ tr➻♥❤
❜➔② tr♦♥❣ ✤à♥❤ ❧þ s❛✉ ✤➙②✳

✣à♥❤ ❧þ ✶✳✶ ✭❚➼♥❤ ❝❤➜t ♥❣❤✐➺♠ ❜➻♥❤ ♣❤÷ì♥❣ tè✐ t❤✐➸✉✮ ✣➦t
S = {x ∈ Rn

✈î✐

Ax − b

2

−→ min}

❧➔ t➟♣ ❝→❝ ♥❣❤✐➺♠ ❝õ❛ ❜➔✐ t♦→♥ ✭✶✳✻✮✳ ❑❤✐ ✤â t❛ ❝â
x ∈ S ⇐⇒ AT (b − Ax ) = 0.

✭✶✳✼✮

❈❤ù♥❣ ♠✐♥❤✳

✧⇐✧✿ ❈❤♦

AT (b − Ax ) = 0

✈➔

z ∈ Rn

❧➔ ♠ët ✈➨❝ tì ❜➜t ❦➻✳ ❑❤✐ ✤â t❛

❝â

b − Az = b − Ax + A(x − z),
❞♦ ✤â

b − Az

❱➻

2
2

= b − Ax

2
2

+ 2 b − Ax , A(x − z) + A(x − z)

= b − Ax


2
2

+ 2 AT (b − Ax ), x − z + A(x − z) 22 .

AT (b − Ax ) = 0

♥➯♥

b − Az
❉♦ ✤â

b − Az

2
2

2
2

= b − Ax

≥ b − Ax

2
2,

2
2


+ A(x − z) 22 .

∀z ∈ Rn ,

tù❝ ❧➔

x ∈ S✳

2
2




ự ự
sỷ

x S



AT (b Ax ) = z = 0,

t

u = x + z,

> 0


t õ

b Au = b Ax Az.
õ

b Au

ữ

2
2

= b Ax

2
2

2 b Ax , Az +

= b Ax

2
2

2

= b Ax

2
2


2 z

AT (b Ax ), z +
2
2

2

+

x S.

2

2
2

Az

Az 22 .

ừ ọ t õ t t ữủ

t ợ tt

2

bAx


2
2

bAu

2
2

ữủ ự


ỵ r r ữ
ữỡ tố t


b

x

r = b Ax

trỹ ợ tr

ừ

R(A)

ừ

A


õ

ữủ t t trỹ

r Ax = b ,

b = Ax + r = b + r ,
tr õ

b

trỹ ừ

b



R(A).

ụ tứ ỵ t s r r ữỡ tố t s
tọ ữỡ tr

AT Ax = AT b.



õ q s

q ữỡ tố t ữ


r(A) = n t t õ t ởt ữỡ tố
t x ữủ ổ tự
x = (AT A)1 AT b.



ữ tữỡ ự
r = b Ax = b b ,

b = PA b,

tr õ PA = A(AT A)1AT trỹ R(A).






r(A)


x

= r < n

t t õ ổ số

ởt ỹ t


z N (A)

t

x+z

ụ ỹ t

t õ ọ t ồ r tứ t tt ỹ
t

X = {x Rn : Ax b


x

2 min}.

ú ỵ r tr trữớ ủ ừ

t õ t ởt õ õ õ ọ
t
r t t t s tr ữỡ
tố t

x

ữ

r = b Ax


tổ q

P t tr

r st

P t tr
ỵ P t tr

tỗ t tr trỹ U = [u1, . . . , cm] Rmìm V
Rnìn s
U T CV = = (1 , . . . , p ),

C Rmìn ,

t

= [u1 , . . . , cn ]

1 ã ã ã p , p = min{m, n}.


r t t õ ự tt ỵ
tr

i

ữủ ồ


tr ý ừ C t tr

ờ ý tỡ ui vi tữỡ ự tỡ
tr tự i tỡ tự i ở (ui , i , vi ) ữủ ồ ý

ữủ ồ

ứ õ t õ

Cvi = i ui



C T ui = i vi ,

i = 1, . . . , p.



P t tr õ q ợ tợ trú ừ tr
t tr ừ

C

ữủ ỵ

ữ s

1 ã ã ã r > r+1 = ã ã ã = p = 0,


r

ữủ


✶✷

t❤➻
r❛♥❦(C)

= r,

R(C) = R([u1 , . . . , ur ]),
N (C) = R([vr+1 , . . . , vn ]),
R(C T ) = R([v1 , . . . , vr ]),
N (C T ) = R([ur+1 , . . . , um ]).
❍ì♥ ♥ú❛✱ ♥➳✉ ✤➦t

Ur = [u1 , . . . , ur ]✱

❞✐❛❣(σ1 , . . . , σr ) ✈➔

Vr = [v1 , . . . , vr ]

t❛ ❝â ❦❤❛✐ tr✐➸♥ ❙❱❉

r

Ur Σr VrT


C=

σi ui viT .

=

✭✶✳✶✸✮

i=1
P❤÷ì♥❣ tr➻♥❤ ✭✶✳✶✸✮ ✤÷ñ❝ ❣å✐ ❧➔
tr➟♥

C

❤↕♥❣

r

t❤➔♥❤ tê♥❣ ❝õ❛

♣❤➙♥ t➼❝❤ ❤❛✐ ♥❣æ✐✱ tù❝ ❧➔ ♣❤➙♥ t➼❝❤ ♠❛
r

♠❛ tr➟♥ ❤↕♥❣

1✳

❈❤✉➞♥ ✷ ✈➔ ❝❤✉➞♥

❋r♦❜❡♥✐✉s ✤÷ñ❝ t➼♥❤ t❤æ♥❣ q✉❛ ❝→❝ ♣❤➛♥ tû ❝õ❛ ❙❱❉ ♥❤÷ s❛✉


m

C

F

n

c2ij = σ12 + · · · + σp2 ,

=

p = min{m, n},

i=1 j=1

C

F

= sup
y=1

Cy 2
= σ1 .
y 2

❚ø ♣❤÷ì♥❣ tr➻♥❤ ✭✶✳✶✶✮ t❛ s✉② r❛ r➡♥❣


C T C = V ΣT ΣV T
❉♦ ✤â

σi2 , i = 1, . . . , p
CT C

❦❤æ♥❣ ➙♠

❱➼ ❞ö ✶✳✶

✈➔

tr♦♥❣ ✤â

γ

CC T = U ΣΣT U T .

❧➔ ❣✐→ trà r✐➯♥❣ ❝õ❛ ♠❛ tr➟♥ ✤è✐ ①ù♥❣✱ ①→❝ ✤à♥❤

CC T

✈î✐ ❝→❝ ✈➨❝ tì r✐➯♥❣ t÷ì♥❣ ù♥❣ ❧➔

❳➨t tr÷í♥❣ ❤ñ♣

C = [c1 , c2 ],

✈➔


✈î✐

n = 2✱

❝❤♦

cT1 c2 = cos γ

❧➔ ❣â❝ ❣✐ú❛ ❤❛✐ ✈➨❝ tì

CT C =

vi

c1

✈➔

c1

✈➔

c2 ✳

2

= c2

▼❛ tr➟♥


1

cos γ

cos γ

1

2

= 1,

✈➔

ui ✳


✶✸

❝â ❝→❝ ❣✐→ trà r✐➯♥❣

γ
γ
λ1 = 2 cos2 , λ2 = 2 sin2
2
2
❞♦ ✤â

σ1 =
❈→❝ ✈➨❝ tì ❦➻ ❞à ♣❤↔✐ ❝õ❛


√
C

√
γ
γ
2 cos , σ2 = 2 sin .
2
2
❧➔

1
1 1
1
v1 = √
; v2 = √
.
2 1
2 −1
❈→❝ ✈➨❝ tì ❦➻ ❞à tr→✐ ❝õ❛

u1 =

C

❧➔

1
1

(c
+
c
);
u
=
(c1 − c2 ).
1
2
2
2 cos γ2
2 sin γ2

✣à♥❤ ❧þ ✶✳✸ ✭✣à♥❤ ❧þ ①➜♣ ①➾ ♠❛ tr➟♥ ❊❝❦❛rt✲❨♦✉♥❣✲▼✐rs❦②✮ ❈❤♦

♣❤➙♥ t➼❝❤ ❙❱❉ ❝õ❛ C ∈ Rm×n ❝â ❞↕♥❣ C =
◆➳✉ k < r ✈➔ Ck = ki=1 σiuiviT t❤➻
min

C −D

rank(D)=k

2

= C − Ck

r
T
i=1 σi ui vi


✈î✐ r = rankC✳

= σk+1

✭✶✳✶✹✮

2

✈➔
p

min

C −D

rank(D)=k

F

= C − Ck

F

σi2 , p = min{m, n}.

=

✭✶✳✶✺✮


i=k+1

✣à♥❤ ❧þ ✶✳✸ ❜❛♥ ✤➛✉ ✤÷ñ❝ ❝❤ù♥❣ ♠✐♥❤ ❝❤♦ ❝❤✉➞♥ ❋r♦❜❡♥✐✉s ✈➔♦ ♥➠♠ ✶✾✸✻
❜ð✐ ❊❝❦❛rt ✈➔ ❨♦✉♥❣ ❬✸❪✳ ❱➔♦ ♥➠♠ ✶✾✻✵ ▼✐♥s❦② ✤➣ ❝❤ù♥❣ ♠✐♥❤ ✤à♥❤ ❧þ
❝❤♦ ❝❤✉➞♥ ✷✱ tø ✤â ✣à♥❤ ❧þ ✶✳✸ ✤÷ñ❝ ❣å✐ ❧➔ ✣à♥❤ ❧þ ❊❝❦❛rt✲❨♦✉♥❣✲▼✐rs❦②✳

✣à♥❤ ❧þ ✶✳✹ ✭✣à♥❤ ❧þ ①❡♥ ❦➩ ❝→❝ ❣✐→ trà ❦➻ ❞à✮ ❈❤♦ C ❧➔ ♠❛ tr➟♥

❝ï m × n ✈î✐ ❣✐→ trà ❦➻ ❞à γ1 ≥ · · · ≥ γmin
✳ ❈❤♦ D ❧➔ ♠❛ tr➟♥
❝♦♥ ❝ï p × q ❝õ❛ C ✈î✐ ❣✐→ trà ❦➻ ❞à δ1 ≥ · · · ≥ δmin{p,q}✳ ✣➸ t❤✉➟♥ t✐➺♥✱
t❛ ✤à♥❤ ♥❣❤➽❛ γt = 0 ✈î✐ min{m, n} < t ≤ max{m, n} ✈➔ δt = 0 ✈î✐
min{p, q} < t ≤ max{p, q}✳ ❑❤✐ ✤â
min{m,n}

γi ≥ δi ,

i = 1, . . . , min{p, q},

δi ≥ γi+(m−p)+(n−q) ,

i ≤ min{p + q − m, p + q − n}.

✭✶✳✶✻✮
✭✶✳✶✼✮




ú ỵ


tr

D

õ ữủ õ ởt ởt ừ

C

t

t õ


m n : 1 1 2 2 ã ã ã n1 n 0;





m < n : 1 1 2 2 ã ã ã m m 0.



ữỡ tố t
ởt ổ ử t ữỡ tố t
t ữ tr trỹ

C


tr ữớ t ổ tự

õ t q ỡ s

ỵ ữỡ tố t õ ọ t

sỷ ừ tr A Rmìn ữủ ổ tự
A = ni=1 i ui v Ti sỷ r(A) = r b Rm t



tự

r
1

x =

T

i vi u i b



i=1

ỹ t õ
ỡ ỳ

Ax b


2

õ ọ t tr tt ỹ t
m

2

r = Ax b

2
2

T

(u i b)2 .

=



i=r+1
õ t t ữợ s

x = A b
tr õ



r 2 = (I AA )b 22 ,


A = V U T , =

ữủ ồ

ừ A.

1

( 1

nìm
, ã ã ã , 1
r , 0, ã ã ã , 0) R

Pữỡ ữỡ tố t t
t t
tt ữỡ ữỡ tố t t
trữợ t t t ữỡ ữỡ tố t t ởt



✶✺

✣à♥❤ ♥❣❤➽❛ ✶✳✷
✈î✐

n

❈❤♦ ♠ët ❤➺ q✉→ ①→❝ ✤à♥❤ ❣ç♠


m ♣❤÷ì♥❣ tr➻♥❤ Ax ≈ b

➞♥✱ ♣❤÷ì♥❣ ♣❤→♣ ❜➻♥❤ ♣❤÷ì♥❣ tè✐ t❤✐➸✉ ❧➔ ✤✐ t➻♠ ❝ü❝ t✐➸✉

b−b

♠✐♥

b ∈Rm

2,

✭✶✳✷✷✮

✈î✐

b ∈ R(A).
❑❤✐ t➻♠ ✤÷ñ❝ ❝ü❝ t✐➸✉

b

t❤➻ ♥➳✉

x

✭✶✳✷✸✮

t❤ä❛ ♠➣♥


Ax = b
t❤➻

x

✤÷ñ❝ ❣å✐ ❧➔ ♥❣❤✐➺♠ ❜➻♥❤ ♣❤÷ì♥❣ tè✐ t❤✐➸✉ ✈➔

∆b = b − b

❧➔ ❤✐➺✉

❝❤➾♥❤ ❜➻♥❤ ♣❤÷ì♥❣ tè✐ t❤✐➸✉ ✭▲❡❛st sq✉❛r❡ ❝♦rr❡❝t✐♦♥✮✳
P❤÷ì♥❣ tr➻♥❤ ✭✶✳✷✹✮ ✈➔ ✭✶✳✷✺✮ t❤ä❛ ♠➣♥ ♥➳✉
❝õ❛

b

❧➔ ♣❤➨♣ ❝❤✐➳✉ trü❝ ❣✐❛♦

b ❧➯♥ R(A)✳ ◆❤÷ ✈➟②✱ t❛ t❤➜② r➡♥❣ ✤è✐ ✈î✐ ♣❤÷ì♥❣ ♣❤→♣ ❜➻♥❤ ♣❤÷ì♥❣

tè✐ t❤✐➸✉ t❤➻ ❝❤➾ ❝â ✈➳ ♣❤↔✐

b ❝â s❛✐ sè ✭❝â ♥❤✐➵✉✮ ❝á♥ ♠❛ tr➟♥ A ✤÷ñ❝ ❝❤♦

❝❤➼♥❤ ①→❝✳ ❚✉② ♥❤✐➯♥ ✤✐➲✉ ❦✐➺♥ ♥➔② ❦❤æ♥❣ t❤ü❝ t➳ ✈➻ ❝→❝ ♠æ ❤➻♥❤ ❤♦➦❝
❝→❝ s❛✐ sè ✤♦ ✤↕❝ ❧✉æ♥ ↔♥❤ ❤÷ð♥❣ tî✐ ♠❛ tr➟♥
❤ñ♣ ♠❛ tr➟♥

A✳


❇➡♥❣ ❝→❝❤ ①➨t tr÷í♥❣

A ❝â ♥❤✐➵✉✱ t❛ ❞➝♥ tî✐ ❜➔✐ t♦→♥ ❜➻♥❤ ♣❤÷ì♥❣ tè✐ t❤✐➸✉ t♦➔♥

♣❤➛♥ ♥❤÷ s❛✉

✣à♥❤ ♥❣❤➽❛ ✶✳✸
t➼♥❤

Ax ≈ b

✈î✐

n

❈❤♦ ♠ët ❤➺ q✉→ ①→❝ ✤à♥❤ ❝â

m

♣❤÷ì♥❣ tr➻♥❤ t✉②➳♥

➞♥✱ ♣❤÷ì♥❣ ♣❤→♣ ❜➻♥❤ ♣❤÷ì♥❣ tè✐ t❤✐➸✉ t♦➔♥ ♣❤➛♥ ❧➔

✤✐ t➻♠
♠✐♥✐♠✐③❡

ˆ ˆb]∈Rm×(n+1)
[A;


ˆ ˆb]
[A; b] − [A;

F,

✭✶✳✷✹✮

✈î✐

ˆb ∈ R(A).
ˆ
❑❤✐ t➻♠ ✤÷ñ❝ ❝ü❝ t✐➸✉

ˆ ˆb]
[A,

t❤➻ ♥➳✉

x

✭✶✳✷✺✮

t❤ä❛ ♠➣♥

ˆ = ˆb
Ax
ˆ ∆ˆb] =
x ✤÷ñ❝ ❣å✐ ❧➔ ♥❣❤✐➺♠ ❜➻♥❤ ♣❤÷ì♥❣ tè✐ t❤✐➸✉ t♦➔♥ ♣❤➛♥ ✈➔ [∆A;
ˆ ˆb] ❧➔ ❤✐➺✉ ❝❤➾♥❤ ❜➻♥❤ ♣❤÷ì♥❣ tè✐ t❤✐➸✉ t♦➔♥ ♣❤➛♥ ✭❚♦t❛❧ ❧❡❛st
[A; b] − [A;


t❤➻


✶✻

sq✉❛r❡ ❝♦rr❡❝t✐♦♥✮✳ ❚❛ ❦➼ ❤✐➺✉ ♥❣❤✐➺♠ ❜➻♥❤ ♣❤÷ì♥❣ tè✐ t❤✐➸✉ t♦➔♥ ♣❤➛♥
❧➔

xˆ.
▼ët tr♦♥❣ ♥❤ú♥❣ ù♥❣ ❞ö♥❣ q✉❛♥ trå♥❣ ❝õ❛ ❜➔✐ t♦→♥ ❚▲❙ ❧➔ ÷î❝ ❧÷ñ♥❣

t❤❛♠ sè tr♦♥❣ ♠æ ❤➻♥❤ ❜✐➳♥ ❝â s❛✐ sè✳ ●✐↔ sû r➡♥❣ t❛ ❝â
❝õ❛

A, b

❧✐➯♥ ❤➺ ✈î✐

n

t❤❛♠ sè ❝❤÷❛ ❜✐➳t

A0 x = b0 ,
✈î✐

∆A, ∆b

❤➔♥❣ ❝õ❛


m

A0

❝â ❤↕♥❣ ✤➛② ✤õ ✈➔ ❝→❝

❧➔ ✤ë❝ ❧➟♣ t✉②➳♥ t➼♥❤ ✈➔ ❝â ❝ò♥❣ ♣❤➙♥ ❜è ✈î✐ ❣✐→ trà

❧÷ñ♥❣ ❣✐→ trà t❤❛♠ sè ❝❤➼♥❤ ①→❝
❦❤✐

❜ð✐ ♣❤÷ì♥❣ tr➻♥❤

❧➔ ❝→❝ s❛✐ sè ✤♦ ✤↕❝✳ ●✐↔ sû r➡♥❣

[∆A; ∆b]

❣✐→ trà ✤♦

A = A0 + ∆A, b = b0 + ∆b,

tr✉♥❣ ❜➻♥❤ ❜➡♥❣ ✵✳ ❑❤✐ ✤â ♥❣❤✐➺♠ ❚▲❙

x0

x

m

x0


xˆ

❝õ❛ ♣❤÷ì♥❣ tr➻♥❤

✤÷ñ❝ ❝❤♦ ❜ð✐

Ax = b

÷î❝

A†b0 , tù❝ ❧➔ xˆ ❤ë✐ tö tî✐

t✐➳♥ r❛ ✈æ ❝ò♥❣✳

✶✳✸✳✷✳ ◆❣❤✐➺♠ ❝ì ❜↔♥
❙❛✉ ✤➙② t❛ s➩ sû ❞ö♥❣ ❦ÿ t❤✉➙t ♣❤➙♥ t➼❝❤ ❣✐→ trà ❦➻ ❞à ✭❙❱❉✮ ✤➸ ❣✐↔✐
❜➔✐ t♦→♥ ❜➻♥❤ ♣❤÷ì♥❣ tè✐ t❤✐➸✉ t♦➔♥ ♣❤➛♥✳ ❚❛ ❝❤✉②➸♥ ❤➺

Ax = b ✈➲ ❞↕♥❣

[A; b][x; −1]T = 0
●✐↔ sû ✭✶✳✺✮ ❧➔ ♣❤➙♥ t➼❝❤ ❣✐→ trà ❦➻ ❞à ❝õ❛
tr➙♥

[A; b]

❤↕♥❣

n+1


✈➔

S

[A; b]✳

✭✶✳✷✻✮
◆➳✉

σn+1 = 0

❧➔ ❦❤æ♥❣ ❣✐❛♥ s✐♥❤ ❜ð✐ ❝→❝ ❞á♥❣ ❝õ❛

Rn+1 ✳ ❙û ❞ö♥❣ ✣à♥❤ ❧þ ✶✳✸✱ ①➜♣ ①➾ ❜➻♥❤ ♣❤÷ì♥❣
ˆ ˆb] tèt ♥❤➜t ❤↕♥❣ n ❝õ❛ [A; b] ✤÷ñ❝ ❝❤♦ ❜ð✐
[A;

trò♥❣ ✈î✐
♣❤➛♥

t❤➻ ♠❛

ˆ ˆb] = U ΣV
ˆ T,
[A;

✈î✐

ˆ = ❞✐❛❣(σ1 , · · · , σn , 0).

Σ

[A; b]

tè✐ t❤✐➸✉ t♦➔♥

✭✶✳✷✼✮

❍✐➺✉ ❝❤➾♥❤ ❜➻♥❤ ♣❤÷ì♥❣ tè✐ t❤✐➸✉ t♦➔♥ ♣❤➛♥ ♥❤ä ♥❤➜t ✤÷ñ❝ ❝❤♦ ❜ð✐

σn+1 =

min

ˆ ˆb])=n
r❛♥❦([A;

ˆ ˆb]
[A; b] − [A;

F

✈➔

ˆ ˆb] = [∆A;
ˆ ∆ˆb] = σn+1 un+1 v T .
[A; b] − [A;
n+1

✭✶✳✷✽✮


❈❤ó þ r➡♥❣ ♠❛ tr➟♥ ❤✐➺✉ ❝❤➾♥❤ ❚▲❙ ❝â ❤↕♥❣ ❜➡♥❣ ✶ ✈➔ t➟♣ ❝→❝ ❣✐→ trà
①➜♣ ①➾

ˆ ˆb][xT ; −1]T = 0
[A;

✭✶✳✷✾✮




tữỡ t ừ ú ữủ t tỡ
tự ởt ố ũ ừ
tỡ

vn+1

V

ữủ

s t õ t ố ũ

[xT ; 1]T =


b]
N [A;


tở

vn+1,n+1 = 0

1
vn+1,n+1

1

vn+1 .




t

b = A
x =

1
vn+1,n+1

1,n+1 , . . . , vn,n+1 ]T R(A)

A[v

ữ ữủ tọ õ

x




ỵ ừ t Ax b sỷ


vn+1



tữỡ ự ừ tr A [A; b] n > n+1 t
b] = U V
T
[A;

= (1, . . . , n, 0),





ợ tr tữỡ ự
b] = [A; b] [A;
b] = n+1 un+1 v T ,
[A;
n+1

t




x =



tỗ t t

1
vn+1,n+1

[v1,n+1 , ã ã ã , vn,n+1 ]T



= b.
ừ t Ax

ự

ỵ tr t õ

1 1 ã ã ã n n n+1 .


n > n+1 n+1 ổ trũ ợ t tr ừ [A; b]



[A; b]T [A; b]

y

0

2
= n+1

õ t ợ
ữ

y
0
2n



2
y = 0 AT Ay = n+1
y.

tr r ọ t ừ

AT A

b]) ự tỡ õ t tự n + 1 0.
N ([A;


✶✽

✈➟②✱ ❜➔✐ t♦→♥ ❚▲❙ ❝â ♥❣❤✐➺♠✳ ❱➻


ˆ ˆb]) = 1
dim N ([A;

♥➯♥ ♥❣❤✐➺♠ ♥➔② ❧➔

❞✉② ♥❤➜t✳
❍ì♥ ♥ú❛✱ sû ❞ö♥❣ ✣à♥❤ ❧þ ✶✳✸✱ ①➜♣ ①➾ ❚▲❙

ˆ ˆb]
[A;

❤↕♥❣

n

❝õ❛

[A; b]

σn+1

✤÷ñ❝

✤÷ñ❝ ❝❤♦ ❜ð✐

ˆ ˆb] = U ΣV
ˆ T
[A;

✈➔


ˆ = ❞✐❛❣(σ1 , . . . , σn , 0).
Σ

❍✐➺✉ ❝❤➾♥❤ ❚▲❙ ♥❤ä ♥❤➜t ❧➔

σn+1 =

min

ˆ ˆb])=n
r❛♥❦([A;

ˆ ˆb]
[A; b] − [A;

✈➔

ˆ ˆb] = [∆A;
ˆ ∆ˆb] = σn+1 un+1 v T .
[A; b] − [A;
n+1
❑➳t ❤ñ♣ ✈î✐

ˆ ˆb]) = 1✱
dim N ([A;

t❛ ❝â

ˆ ˆb][x T ; −1]T = 0.

[A;
❚ø ✤â t❛ ❝â t❤➸ ❦➳t ❧✉➟♥

ˆb = Aˆ
ˆx =

−1
vn+1,n+1

◆❤÷ ✈➟②

xˆ =

ˆ 1,n+1 , · · · , vn,n+1 ]T ∈ R(A).
ˆ
A[v

−1
vn+1,n+1

[v1,n+1 , · · · , vn,n+1 ]T .

❚❛ ❝â ✤✐➲✉ ♣❤↔✐ ❝❤ù♥❣ ♠✐♥❤✳
❚➼♥❤ ❝❤➜t ❝õ❛ ♥❣❤✐➺♠ ❚▲❙

xˆ

✈➔ ❤✐➺✉ ❝❤➾♥❤ ❚▲❙ ♥❤ä ♥❤➜t

tr➻♥❤ ❜➔② tr♦♥❣ ✤à♥❤ ❧þ s❛✉ ✤➙②


✣à♥❤ ❧þ ✶✳✼ ✭❇✐➸✉ ❞✐➵♥ ❞↕♥❣ ✤â♥❣ ❝õ❛ ♥❣❤✐➺♠ ❚▲❙✮ ●✐↔ sû
✈➔

✭✶✳✺✮

✭✶✳✹✮

t÷ì♥❣ ù♥❣ ❧➔ ❙❱❉ ❝õ❛ ♠❛ tr➟♥ A ✈➔ [A; b]✳ ◆➳✉ σn > σn+1 t❤➻
2
xˆ = (AT A − σn+1
I)−1 AT b

✈➔

n
2
σn+1

1+
i=1

(u Ti b)2
= minn Ax − b 22 .
2
2
x∈R
σ i − σn+1

✭✶✳✸✹✮


✭✶✳✸✺✮


✶✾

❈❤ù♥❣ ♠✐♥❤✳
σn > σn+1

❉♦

✈➨❝ tì r✐➯♥❣ ❝õ❛

♥➯♥

xˆ

❧➔ tç♥ t↕✐ ✈➔ ❞✉② ♥❤➜t✳ ❱➻ ❝→❝ ✈➨❝ tì ❦➻ ❞à ❧➔ ❝→❝

[A; b]T [A; b] ♥➯♥ xˆ t❤ä❛ ♠➣♥ ♣❤÷ì♥❣ tr➻♥❤ ❞➔♥❤ ❝❤♦ ✈➨❝

tì r✐➯♥❣ s❛✉

xˆ

T

[A; b] [A; b]

AT A A T b


=

−1

bT A

xˆ

bT b

xˆ

2
= σn+1

−1

−1

.

✭✶✳✸✻✮

❉♦ ✤â t❛ ❝â

2
AT Aˆ
x − AT b = σn+1
xˆ

❤❛②

2
xˆ = (AT A − σn+1
I)−1 AT b.
▼➦t ❦❤→❝✱ tø ❝æ♥❣ t❤ù❝ ✭✶✳✸✼✮ t❛ ♥❤➟♥ ✤÷ñ❝

Σ TΣ

g

gT

b

z
2
2

2
= σn+1

−1

z
−1

,

✈î✐


T

T

T

g = Σ U b, z = V xˆ.

✭✶✳✸✼✮

❚ø ♣❤÷ì♥❣ tr➻♥❤ ♥➔②✱ t❛ ❝â

T

2
(Σ Σ − σn+1
I)z = g
❚❤➳

z

✈➔

2
σn+1
+ g T z = b 22 .

✭✶✳✸✽✮


tø ♣❤÷ì♥❣ tr➻♥❤ tr÷î❝ tr♦♥❣ ✭✶✳✸✽✮ ✈➔♦ ♣❤÷ì♥❣ tr➻♥❤ s❛✉ tr♦♥❣

✭✶✳✸✽✮ t❛ ❝â

T

2
2
σn+1
+ g T (Σ Σ − σn+1
I)−1 g = b 22 .

✭✶✳✸✾✮

❉♦ ✤â t❛ ❝â t❤➸ ✈✐➳t ❧↕✐ ♣❤÷ì♥❣ tr➻♥❤ ✭✶✳✸✾✮ ❞÷î✐ ❞↕♥❣

n
2
σn+1

+
i=1

❤❛②

n
2
σn+1

1+

i=1

m

(u Ti b)2
=
2
σ 2i − σn+1

T

(u i b)2

✭✶✳✹✵✮

i=1
m

(u Ti b)2
T 2
=
(u
i b) .
2
2
σ i − σn+1
i=n+1

✭✶✳✹✶✮


▼➦t ❦❤→❝✱ ✈➻

m

min b − Ax
x

2
2

T

= min u b − Σω
ω

2
2

=

T

(u i b)2
i=n+1

✭✶✳✹✷✮







n
2
n+1

1+
i=1

(u Ti b)2
= minn Ax b 22 .
2
2
xR
i n+1



t t ữỡ tố t t
t t t ữỡ tố t t ữủ ổ t
ữ s



tr

A Rmìn




B Rmìd



[A; B] = U V T
tr õ

V :=


V11 V12

.

V21 V22

V22 ổ t ữỡ tố t x = V12 V221

ữủ t ổ õ ữỡ tố t t
ứ tt t

r

ữỡ tố t t

x ừ ữỡ tr

Ax = b.

ử


ợ

n=1



[A; b] =

1 0
0 2

.

A; b] õ t ởt tr
b]
2 = 1 v2 = [10]T v2,2 = 0 ỹ t t [A;

r trữớ ủ
ọ t
ữ tợ

b] = [A A;
b b] =
[A;
õ t

0 0
0 2


.

Ax b ổ tữỡ t ổ tỗ t

ừ


✷✶

✣à♥❤ ❧þ ❞÷î✐ ✤➙② s➩ ❝❤➾ r❛ r➡♥❣ ❤✐➺✉ ❝❤➾♥❤ ❚▲❙ ✭✶✳✷✹✮ ❧✉æ♥ ♥❤ä ❤ì♥ ❤✐➺✉
❝❤➾♥❤ ▲❙ ✭✶✳✷✷✮✳

ˆ = ˆb t÷ì♥❣ ù♥❣ ❧➔ ①➜♣ ①➾ ▲❙ ✈➔ ❚▲❙
✣à♥❤ ❧þ ✶✳✽ ❈❤♦ Ax = b ✈➔ Ax

❝õ❛ t➟♣ Ax ≈ b t❤➻ ❦❤✐ ✤â

b−b

❱➼ ❞ö ✶✳✸

❳➨t ♣❤÷ì♥❣ tr➻♥❤


N − 1 −1

 −1 N − 1


 ...



−1
 −1

 −1
−1

−1
−1
♥❣❤✐➺♠ ▲❙

2

x

···
···
···
···
···

−1

ˆ ˆb]
≥ [A; b] − [A;
Ax = b


✈➔ ♥❣❤✐➺♠ ❚▲❙


❝â ❞↕♥❣



xˆ

N,N −2



1




 
−1

 x2  


 

.
.
.

 
,

=  ...  ≈ 


 
−1 
x
 

 N −3  
N − 1


xN −2
−1



−1 





N − 1

−1 

−1

F.


x1



✭✶✳✹✹✮

✤÷ñ❝ t➼♥❤ ♠ët ❝→❝❤ ❣✐↔✐ t➼❝❤ ✈➔ ❝❤♦ ❜ð✐

x = −0.5[1, 1, . . . , 1]T ,

xˆ = −[1, 1, . . . , 1]T .

❈→❝ ❤✐➺✉ ❝❤➾♥❤ t÷ì♥❣ ù♥❣

∆b = b − b = 0.5[0, 0, . . . , 0, N, −N ]T
ˆ ∆ˆb] = [A; b] − [A;
ˆ ˆb] = 1 [−1, . . . , −1, N − 1]T [1, . . . , 1].
[∆A;
N −1
❚ø ✤â t❛ ❝â

s➩ ❧î♥ ❦❤✐

N

∆b 22
ˆ ∆ˆb]
[∆A;
❧î♥✳


2
F

=

N
2




ữỡ

ởt số ự ử ừ ữỡ
ữỡ tố t t
ỗ q ỡ t t
r ổ

R2



m

số

{(xi , yi ) R2 | i = 1, ã ã ã , m}
tọ ố q t t


y(x) = a + bx


t số

a, b



t ỹ t tốt t ừ tờ ữỡ ữ

m

(yi a bxi )2 .

f (a, b) :=



i=1
õ t t t ữớ t

R2 |y = a + bx}

l := {(x, y)

ỳ t õ t ồ

ỳ ỳ ữớ t


l

ữ tr

ữợ
ỷ ử trồ t

f (a, b)

z = (
x, y)T = ( m1

1
i=1 mxi , m

T
i=1 myi ) , t t

ữợ

m

m
2

(yi y + b(xi x))2 + m(
y a b
x)2

(yi a bxi ) =


f (a, b) :=
i=1

i=1
m

(yi y + b(xi x))2 , a, b.


i=1


✷✸

❍➻♥❤ ✷✳✶✿

✣➥♥❣ t❤ù❝ ①↔② r❛ ❦❤✐
t❤➥♥❣✱ tù❝ ❧➔

z¯ ∈ l.
b=

✣÷í♥❣ ▲❙✿ ❑❤♦↔♥❣ ❝→❝❤ t❤❡♦ trö❝ y✳

y¯ = a + b¯
x✱

❦❤✐ ✤â trå♥❣ t➙♠ ♥➡♠ tr➯♥ ✤÷í♥❣


❑❤✐ ✤â ❝ü❝ t✐➸✉ ❝õ❛ ✭✷✳✷✮ ❧➔

m
x − xi )(¯
y − yi )
i=1 (¯
✈➔
m
2
(¯
x
−
x
)
i
i=1

a = y¯ − b¯
x.

◆❤÷ tr♦♥❣ ❝æ♥❣ t❤ù❝ ✭✷✳✷✮ ✈➔ ❍➻♥❤ ✷✳✶✱ t❛ ①➨t ❜➔✐ t♦→♥ t➻♠ ✈à tr➼ ❝õ❛
✤÷í♥❣ t❤➥♥❣ ❣➛♥ ♥❤➜t ❝❤♦ t➟♣ ❝→❝ ✤✐➸♠✳ ❚❛ s➩ sû ❞ö♥❣ ❦❤♦↔♥❣ ❝→❝❤
❊✉❝❧✐❞❡✱ ✤÷í♥❣ t❤➥♥❣ sû ❞ö♥❣ ♣❤÷ì♥❣ ♣❤→♣ ❜➻♥❤ ♣❤÷ì♥❣ tè✐ t❤✐➸✉ ❝â
t❤➸ ✤÷ñ❝ ♠✐♥❤ ❤å❛ ♥❤÷ ❍➻♥❤ ✷✳✷

❚❛ ①➨t ❜➔✐ t♦→♥ ❜➻♥❤ ♣❤÷ì♥❣ tè✐ t❤✐➸✉ t♦➔♥ ♣❤➛♥ t➻♠ ✤÷í♥❣ t❤➥♥❣
❝ü❝ t✐➸✉ ❤â❛ tê♥❣ ❜➻♥❤ ♣❤÷ì♥❣ ❝õ❛ ❦❤♦↔♥❣ ❝→❝❤ t❤➟t

m


dist((xi , yi ), l)2 .

f (l) =
i=1
❚❤❛② ✈➻ t➻♠ ✤÷í♥❣ t❤➥♥❣

y = ax + b✱

t❛ sû ❞ö♥❣ ❞↕♥❣ ✤è✐ ①ù♥❣ s❛✉

l = {(x, y) ∈ R2 |a + r1 x + r2 y = 0} = w + r⊥

✈î✐

r

2

= r12 + r22 = 1,

l