Báo cáo nghiên cứu khoa học: " Hệ phân hoạch hoàn toàn không gian RN"

Chia sẻ: Nguyễn Phương Hà Linh Linh | Ngày: | Loại File: PDF | Số trang:8

Thêm vào BST

Báo xấu

36
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Nh ng h vec-tơ như v y thư ng g p trong bài toán bù tuy n tính và vi c nghiên c u chúng có th mang l i m t công c nghiên c u hi u qu bài toán bù. T

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Báo cáo nghiên cứu khoa học: " Hệ phân hoạch hoàn toàn không gian RN"

T P CHÍ KHOA H C, Đ i h c Hu , S 53, 2009 PHÂN HO CH HOÀN TOÀN KHÔNG GIAN RN H Huỳnh Th Phùng Trư ng Đ i h c Khoa h c, Đ i h c Hu TÓM T T M t phân ho ch hoàn toàn c a Rn là m t h g m 2n vec-tơ U = u1,0 , u1,1 , u2,0 , u2,1 , · · · , un,0 , un,1 ⊆ Rn sao cho, v i m i x ∈ Rn t n t i duy nh t vec-tơ λ tho mãn λ = (λ1,0 , λ1,1 , · · · , λn,0 , λn,1 )T ∈ R2n , λi,s ≥ 0, (i, s) ∈ I × S, λi,0 .λi,1 = 0, i ∈ I, λi,s ui,s x= (i,s)∈I ×S đây I := {1, 2, · · · , n}, và S := {0, 1}. Nh ng h vec-tơ như v y thư ng g p trong bài toán bù tuy n tính và vi c nghiên c u chúng có th mang l i m t công c nghiên c u hi u qu bài toán bù. Trong bài này chúng tôi s thi t l p m t đ c trưng cơ b n c a h phân ho ch không gian Rn và m t vài ng d ng tr c ti p c a nó trong vi c kh o sát s nghi m c a bài toán bù. 1 M đu Cho U là m t h g m 2n vec-tơ trong không gian Rn : U = u1,0 , u1,1 , u2,0 , u2,1 , · · · , un,0 , un,1 . (1.1) Đ thu n ti n ta cũng xem U như m t ma tr n th c c p n × 2n. U đư c g i là m t phân ho ch hoàn toàn cu không gian n u v i m i x ∈ Rn t n t i duy nh t m t vec-tơ λ tho mãn  λ = (λ1,0 , λ1,1 , · · · , λn,0 , λn,1 )T ∈ R2n ,    i,s λ ≥ 0, (i, s) ∈ I × S, (1.2) λi,0 .λi,1 = 0, i ∈ I,   i,s i,s  x = U λ = (i,s)∈I ×S λ u , đây I := {1, 2, · · · , n}, và S := {0, 1}. Lúc đó ta nói x đư c bi u di n dư i d ng m t t h p bù c a U . V y U là m t phân ho ch hoàn toàn c a không gian n u m i vec-tơ x ∈ Rn đ u đư c bi u di n m t cách duy nh t dư i d ng t h p bù c a U . 65
V i m i t p con α c a I ta thi t l p ma tr n U (α) ∈ Rn×n , g i là ma tr n bù c a U tương ng v i α, mà vec-tơ c t th i c a nó đư c xác đ nh b i ui,0 , i ∈ α, U (α)i = (1.3) ui,1 , i ∈ I \ α. Ký hi u M(U ) = {U (α) | α ⊆ I }. Rõ ràng, |M(U )| = 2n . Hai t p con α và β c a I đư c g i là k nhau t i r ∈ I n u (α ∪ β ) \ (α ∩ β ) = {r}. Trong trư ng h p đó ta cũng nói U (α) và U (β ) là k nhau t i c t th r. Hi n nhiên lúc đó, U (α)i = U (β )i , i ∈ I \ {r } , {U (α)r , U (β )r } = ur,0 , ur,1 . K t qu chính c a bài này là đ nh lý sau Đ nh lý 1.1. Ba phát bi u sau là tương đương a. U là m t phân ho ch hoàn toàn c a Rn , b. V i m i c p ma tr n bù U (α), U (β ), ta có det(U (α)). det(U (β )) < 0. (1.4) c. V i m i λ = (λ1,0 , λ1,1 , λ2,0 , λ2,1 , · · · , λn,0 , λn,1 )T ∈ R2n tho mãn λi,0 .λi,1 ≥ 0, λi,0 + λi,1 = 0, i ∈ I, (1.5) h λi,0 .ui,0 − λi,1 .ui,1 | i ∈ I (1.6) đ c l p tuy n tính. Ch ng minh Đ nh lý 1.1 s đư c trình bày trong m c ti p theo còn m c cu i cùng dành cho vi c nghiên c u s nghi m c a bài toán bù tuy n tính b ng cách s d ng đ c trưng c a h phân ho ch. 2 Ch ng minh Đ nh lý 1.1 Nh n xét 2.1. N u m t trong các phát bi u c a Đ nh lý 1.1 tho mãn thì U (α) không suy bi n v i m i α ⊆ I. Ch ng minh Đ nh lý 1.1. (a ⇒ b) Không m t tính t ng quát ta có th gi s r ng α = {1, 2, · · · , r − 1} và β = α ∪ {r}. Như v y U (α) = [u1,0 , u2,0 , · · · , u(r−1),0 , ur,1 , u(r+1),1 · · · , un,1 ]; 66
U (β ) = [u1,0 , u2,0 , · · · , u(r−1),0 , ur,0 , u(r+1),1 , · · · , un,1 ]. Đ t t := U (β )−1 ur,1 ta có r n r,1 i,0 tj uj,1 . u = U (β )t = ti u + i=1 j =r+1 Thay v ph i c a đ ng th c trên vào c t th r c a U (α) và tính đ nh th c c a ma tr n này ta nh n đư c det(U (α)) = tr det(U (β )). Vì U (α) không suy bi n tr = 0 và như v y (1.4) tương đương v i kh ng đ nh tr < 0. Gi s ngư c l i r ng tr > 0. Lúc đó ta đ t r−1 n i,0 r,1 uj,1 x= u + εu + (2.1) i=1 j =r+1 r−1 n i,0 r,0 (1 + εtj )uj,1 . = (1 + εti )u + εtr u + (2.2) i=1 j =r+1 V i ε > 0 đ bé ta có 1 + εti > 0 v i m i i = r. Nhưng lúc đó (2.1) và (2.2) cho ta hai bi u di n khác nhau c a x dư i d ng t h p bù c a U , mâu thu n v i gi thi t r ng U là m t phân ho ch hoàn toàn. (b ⇒ c) B ng quy n p trên |α| ta có th ch ng minh đư c r ng (−1)|α| . det(U (α)). det(U (∅)) > 0, α ⊆ I. Suy ra, (−1)|I \α| . det(U (α)).(−1)|I \β | . det(U (β )) > 0, α, β ⊆ I. (2.3) T nh ng tính ch t đã bi t c a đ nh th c ma tr n ta d dàng ki m ch ng đư c r ng det λ1,0 u1,0 − λ1,1 u1,1 , λ2,0 u2,0 − λ2,1 u2,1 , · · · , λn,0 un,0 − λn,1 un,1 λj,1 (−1)|I \α| det(U (α)). λi,0 = i∈ α α⊆ I j ∈I \α K t h p (1.5) và (2.3) ta có th kh ng đ nh r ng t t c các s h ng c a t ng trên là cùng d u và hơn n a, có ít nh t m t s h ng là khác không. Vì v y đ nh th c c a ma tr n khác không và do đó h (1.6) đ c l p tuy n tính. Trong su t ph n còn l i c a m c này ta gi thi t phát bi u (c) là đúng. Vi c ch ng minh (a) đư c th c hi n b i m t s b đ . B đ 2.1. V i m i λ = (λi,s : (i, s) ∈ I × S ) ∈ R2n , tho mãn n (λi,0 ui,0 − λi,1 ui,1 ) = 0 và λi,0 .λi,1 ≥ 0, i ∈ I, (2.4) i=1 ta có λ = 0. 67
Ch ng minh. Do λi,0 .λi,1 ≥ 0 v i m i i ∈ I , ta ch c n ch ra r ng t p h p γ := {i | λi,0 + λi,1 = 0} là r ng. Th t v y, n u γ = ∅ thì t (2.4) ta có (λi,0 ui,0 − λi,1 ui,1 ) = 0. i∈γ Đi u này là không th vì {λi,0 .ui,0 − λi,1 .ui,1 | i ∈ γ } là m t h con khác r ng c a (1.6). B đ 2.2. V i m i λ = (λi,s : (i, s) ∈ I × S ), µ = (µi,s : (i, s) ∈ I × S ) ∈ R2n tho mãn λi,0 .λi,1 = µi,0 .µi,1 = 0, λi,s ≥ 0, µi,s ≥ 0; i ∈ I, s ∈ S và λi,s ui,s = µi,s ui,s , (i,s)∈I ×S (i,s)∈I ×S ta có λ = µ. Ch ng minh. T đ nh nghĩa ta nh n đư c n [(λi,0 − µi,0 )ui,0 − (µi,1 − λi,1 )ui,1 ] = 0, i=1 và hơn n a, (λi,0 − µi,0 ).(µi,1 − λi,1 ) = λi,0 .µi,1 + λi,1 .µi,0 ≥ 0; i ∈ I. T B đ 2.1 suy ra r ng λi,0 − µi,0 = λi,1 − µi,1 = 0 v i m i i ∈ I , t c là λ = µ. Bây gi l y tuỳ ý x ∈ Rn . Do (c) tho mãn, U (α) không suy bi n v i m i α ⊆ I . Tương ng v i m t t p con như th ta đ t y α := U (α)−1 x, t c là, x = U (α )y α = yi ui,0 + α yi ui,1 . α i∈ α i∈I \α Ta đ nh nghĩa tα = sgn(y α ), vec-tơ d u c a y α , đư c xác đ nh như sau α α n u (yi > 0) ho c (yi = 0 và i ∈ α), 1, tα := i α α −1, n u (yi < 0) ho c (yi = 0 và i ∈ I \ α). B đ 2.3. Φ : P (I ) → {−1, 1}n xác đ nh b i Φ(α) = tα là ánh x song ánh, đây P (I ) ký hi u t p t t c các t p con c a I . Ch ng minh. Vì |P (I )| = | {−1, 1}n | = 2n ta ch c n ch ng minh Φ là đơn ánh. Gi s ngư c l i r ng t n t i các t p con khác nhau α, β ⊆ I sao cho tα = tβ . T đ nh nghĩa c a y α và y β ta có β β yi ui,0 + α yi ui,1 = x = α yi ui,0 + yi ui,1 . i∈ α i∈β i∈I \α i∈I \β 68
T đó suy ra β β β (yi − yi )ui,0 + α (yi ui,0 − yi ui,1 ) + α (−yi ui,0 + yi ui,1 ) α i∈α∩β i∈α\β i∈β \α β (yi − yi )ui,1 = 0. α + i∈I \(α∪β ) αβ β M t khác, t tα = tβ ta có yi yi ≥ 0 v i m i i ∈ I . V y theo B đ 2.1, ta có yi − yi = 0 α β α v i m i i ∈ (α ∩ β ) ∪ (I \ (α ∪ β )) và yi = yi = 0 v i m i i ∈ (α \ β ) ∪ (β \ α). Vì α = β t n t i, ch ng h n, r ∈ α \ β . Theo đ nh nghĩa c a vec-tơ d u ta có tα = 1 và tβ = −1, đi u này là r r mâu thu n. Bây gi ta ch ng minh kh ng đ nh (a). V i m i x ∈ Rn , ta ch ng minh r ng có duy nh t m t vec-tơ λ tho mãn λi,s ui,s v i λi,s ≥ 0, λi,0 .λi,1 = 0, (i, s) ∈ I × S. x= (2.5) (i,s) Th t v y, theo B đ 2.3 t n t i α ⊆ I sao cho tα = sgn(y α ) = (1, 1, · · · , 1). Như v y α yi ≥ 0 v i m i i ∈ I và vec-tơ λ xác đ nh b i α n u i ∈ α, n u i ∈ α, yi , 0, λi,0 = λi,1 = α n u i ∈ I \ α, n u i ∈ I \ α, 0, yi , tho mãn (2.5). Cu i cùng, tính duy nh t c a λ đư c suy ra t B đ 2.2 và đ nh lý đã đư c ch ng minh hoàn toàn. Nh n xét 2.2. Cho α ⊆ I , ta ký hi u U −α là ma tr n nh n đư c t U b ng cách thay các vec-tơ ui,0 , ui,1 l n lư t b i −ui,0 , −ui,1 v i m i i ∈ α. Rõ ràng là n u U tho mãn phát bi u (c) trong Đ nh lý 1.1 thì U −α cũng v y. Do ba phát bi u là tương đương ta suy ra r ng U −α là m t phân ho ch hoàn toàn khi và ch khi U cũng có tính ch t đó. 3 S nghi m bài toán bù tuy n tính Trong m c này b ng cách s d ng đ c trưng c a h phân ho ch không gian đư c thi t l p trong Đ nh lý 1.1 ta s thi t l p m t vài k t qu m i v s nghi m c a bài toán bù tuy n tính. Nh c l i r ng v i ma tr n M ∈ Rn×n và vec-tơ q ∈ Rn Bài toán bù tuy n tính LCP(M, q ) là tìm (x, z ) ∈ Rn × Rn tho mãn  x ≥ 0, z ≥ 0,  xT .z = 0, (3.1)  q = −M x + z.  Tính th i s cũng như vai trò quan tr ng c a bài toán này trong lý thuy t t i ưu đư c ch ng minh thông qua m t kh i lư ng l n các k t qu đư c công b , và đư c k t t p trong 69
các công trình đ s , ch ng h n [4], [1] và [2]. Ký hi u SOL(M, q ) là t p nghi m c a bài toán LCP(M, q ), t c là t p t t c các (x, z ) tho mãn (3.1). C n lưu ý r ng, n u ký hi u U [M ] = {−M 1 , e1 , · · · , −M n , en } v i M i và ei l n lư t là các vec-tơ c t th ith c a M và c a ma tr n đơn v c p n E , thì LCP(M, q ) là bài toán tìm λ = (x1 , z1 , x2 , z2 , · · · , xn , zn )T ≥ 0 sao cho xi zi = 0, i ∈ I = {1, 2, · · · , n} và q = U λ. (3.2) V i m i t p con ∅ = α ⊆ I ta đ t Mα là ma tr n con chính c a M tương ng v i α. M đư c g i là P −ma tr n và ký hi u M ∈ P , n u det(Mα ) > 0 v i m i α = ∅. Như m t m r ng c a khái ni m này ta s g i M là P (k) −ma tr n và vi t M ∈ P (k) , n u t n t i m t t p con γ ⊆ I sao cho |γ | = k và ma tr n M −γ , nh n đư c t M b ng cách thay các c t M i b i −M i v i m i i ∈ γ , là m t P −ma tr n. Ch ng h n, ma tr n sau   21 2 1 −1 0  0 −1 −1 là m t P (2) −ma tr n vì   2 −1 −2 M −{2,3} 0  ∈ P. = 1 1 01 1 Rõ ràng l p các P (0) −ma tr n trùng v i l p các P −ma tr n. Ta đã bi t r ng, n u M ∈ P thì | SOL(M, q )| ≤ 1 v i m i q ∈ Rn . Th t ra, đây là m t đ c trưng c a P −matrices [3]. Bây gi ta s m r ng k t qu này cho các bài toán LCP(M, q ) v i M là P (k) −ma tr n. B đ 3.1. M ∈ P n u và ch n u U [M ] là m t phân ho ch hoàn toàn c a Rn . Ch ng minh. Lưu ý r ng, U [M ](α), ma tr n bù c a U [M ] tương ng v i α ⊆ I , có các c t xác đ nh b i −M i , i ∈ α, U [M ](α)i = ei , i ∈ I \ α. V y d th y det(U [M ](∅)) = det(E ) = 1 và det(U [M ](α)) = (−1)|α| det(Mα ) (3.3) v i m i t p khác r ng α ⊆ I . T Đ nh lý 1.1 ch c n ch ng minh r ng M là P − ma tr n n u và ch n u l p {U [M ](α) | α ⊆ I } tho mãn (1.4). Gi s M là P −ma tr n và α, β ⊆ I là k nhau. T đ nh nghĩa ta có, ch ng h n, |β | = |α| + 1. N u α = ∅ thì |β | = 1 và det(U [M ](β )) det(U [M ](α)) = det(U [M ](β )) = − det(Mβ ) < 0. 70
N u α = ∅ ta có det(U [M ](β )) det(U [M ](α)) = (−1)|α|+|β | det(Mβ ) det(Mα ) < 0. Tóm l i det(U [M ](β )) det(U [M ](α)) < 0 v i m i c p ma tr n bù k nhau. Bây gi gi s {U [M ](α) | α ⊆ I } tho mãn (1.4) ta s ch ng minh det(Mα ) > 0, v i m i ∅ = α ⊆ I , b ng quy n p theo |α|. N u |α| = 1 thì α là k v i ∅, do đó det(Mα ) = − det(U [M ](α)) = − det(U [M ](α)) det(U [M ](∅)) > 0. Gi s det(Mβ ) > 0 v i m i |β | = k ≥ 1 và α ⊆ I sao cho |α| = k + 1. L y tuỳ ý r ∈ α. Hi n nhiên α k v i β = α \ {r}. Ta có det(Mα ) det(Mβ ) = (−1)2k+1 det(U [M ](α)) det(U [M ](β )) > 0. Vì |β | = k nên det(Mβ ) > 0, ta suy ra det(Mα ) > 0. Tóm l i, det(Mα ) > 0 v i m i ∅ = α ⊆ I , t c là M ∈ P . H qu 3.1. M ∈ P n u và ch n u | SOL(M, q )| = 1 v i m i q ∈ Rn . Ch ng minh. Trư c tiên ta c n lưu ý r ng U [M ] là m t phân ho ch hoàn toàn n u và ch n u v i m i q ∈ Rn t n t i duy nh t vec-tơ λ = (x1 , z1 , · · · , xn , zn ) ≥ 0 tho mãn (3.2), t c là LCP(M, q ) có duy nh t nghi m. Như v y h qu có th suy ra tr c ti p t b đ trên. M nh đ 3.1. N u M ∈ P (k) thì | SOL(M, q )| ≤ 2k v i m i q ∈ Rn . Ch ng minh. Gi s ngư c l i r ng | SOL(M, q )| > 2k . Ký hi u γ là t p con c a I sao cho |γ | = k và M −γ ∈ P . V i m i (x, z ) ∈ SOL(M, q ) ta ký hi u α(x, z ) là t p các ch s i ∈ γ sao cho xi > 0 (và lúc đó, zi = 0): α(x, z ) := {i ∈ γ | xi > 0 = zi } ⊆ γ. Vì | SOL(M, q )| > 2k = s các t p con c a γ , t n t i (x, z ), (x , z ) ∈ SOL(M, q ) sao cho (x, z ) = (x , z ) và α(x, z ) = α(x , z ) =: α. Không m t tính t ng quát ta có th gi s α = {1, 2, · · · , l} ⊆ γ = {1, · · · , l, l + 1, · · · , k } . Vì M −γ ∈ P , t B đ 3.1 suy ra r ng U [M −γ ] = M 1 , e1 , · · · , M l , el , M l+1 , el+1 , · · · , M k , ek , −M k+1 , ek+1 , · · · , −M n , en là m t phân ho ch hoàn toàn. Nhưng theo Nh n xét 2.2, h sau đây V = −M 1 , −e1 , · · · , −M l , −el , M l+1 , el+1 , · · · , M k , ek , −M k+1 , ek+1 , · · · , −M n , en cũng là m t h phân ho ch hoàn toàn. M t khác t đ nh nghĩa c a t p α ta có l k n i i (xi (−M i ) + zi ei ), xi (−M ) + q= zi e + (3.4) i=1 i=l+1 i=k+1 l k n i i (xi (−M i ) + zi ei ). xi (−M ) + q= zi e + (3.5) i=1 i=l+1 i=k+1 Nhưng (3.4) và (3.5) l i cho ta hai bi u di n khác nhau c a q dư i d ng t h p bù c a V , mâu thu n vì V là h phân ho ch hoàn toàn c a Rn . 71
TÀI LI U THAM KH O [1] R.C. Cottle, J.S. Pang and R.E. Stone, The Linear Complementarity Problem, Academic Press, New York, 1992. [2] F. Facchinei, J.S. Pang, Finite-Dimentional Variational Inequalities and Complementarity Problems, Springer-Verlag, 2003. [3] K.G. Murty, On the number of solutions to the complementarity problems and spanning properties of complementarity cones, Linear Algebra and Its Applications 5(1972), 65-108. [4] K.G. Murty, Linear complementarity, linear and nonlinear programming, Heldermann- Verlag, Berlin, Germany, 1987. COMPLETE PARTITIONS OF Rn Huynh The Phung College of Sciences, Hue University SUMMARY A complete partition of Rn is, by definition, a system of 2n vectors U = u1,0 , u1,1 , u2,0 , u2,1 , · · · , un,0 , un,1 ⊆ Rn such that, for every x ∈ Rn there exists a unique vector λ sastisfying λ = (λ1,0 , λ1,1 , · · · , λn,0 , λn,1 )T ∈ R2n , λi,s ≥ 0, (i, s) ∈ I × S, λi,0 .λi,1 = 0, i ∈ I, λi,s ui,s , x= (i,s)∈I ×S where I := {1, 2, · · · , n} and S := {0, 1}. Systems of this type are usually encountered in linear complementarity problems. By study- ing them we expect to provide some strong tools for investigating theory of complementarity problems. Specifically, in this paper we shall prove a basic characterization of complete parti- tions in Rn and then derive some direct applications to linear complementarity problems. 72