Phương pháp biểu diễn SOS

Chia sẻ: Sang Sang | Ngày: | Loại File: PDF | Số trang:4

Thêm vào BST

Báo xấu

194
lượt xem 16
download

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

Phương pháp biểu diễn SOS

Chủ đề:

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

Lưu

Nội dung Text: Phương pháp biểu diễn SOS

0.1. BI U DI N CƠ S PHƯƠNG PHÁP SOS 1 0.1 Bi u di n cơ s phương pháp SOS M đ u Trong các bài toán đư c d n ra các m c trư c h n các b n đã nh n th y s l p đi l p l i c a bi u di n d ng F (a, b, c) = Sa (b − c)2 + Sb (c − a)2 + Sc (a − b)2 . Các đ nh lý sau đây s cho th y s t n t i c a bi u di n đó. Chúng tôi t gi i h n mình trong l p các b t đ ng th c 3 bi n đ i x ng, tuy nhiên đi u đó s không làm h n ch t m ng d ng c a phương pháp này. Các b n có th s d ng các ví d đ ki m ch ng r ng v i cùng tư tư ng dư i đây, h u h t các b t đ ng th c hoán v 3 cũng có nh ng bi u di n tương t . Chúc các b n may m n ! 0.1.1 Các khái ni m cơ b n i) T p xác đ nh (TXĐ) T đây tr đi n u không có gì thay đ i, đ cho bài toán rõ ràng và tránh nh ng phi n ph c không đáng có, TXĐ c a t t c các hàm s và b t đ ng th uc s gi i h n trong t p các s th c không âm R3 hơn n a đôi khi đ h p lý chúng + ta s b đi đi m (0, 0, 0). ii) Đ nh nghĩa 1: v hàm đ i x ng ba bi n M t hàm phân th c ba bi n F (a, b, c) đư c g i là đ i x ng n u và ch n u đ ng nh t th c sau F (a, b, c) = F (x, y, z) đúng v i m i hoán v (x, y, z) c a (a, b, c). Hơn n a n u v i m i s th c dương x mà F (x, x, x) = 0 thì F (a, b, c) đư c g i là hàm đ i x ng ba bi n chu n. iii) Đ nh nghĩa 2: v hàm n a đ i x ng ba bi n M t hàm phân th c ba bi n G(a, b, c) đư c g i là n a đ i x ng n u và ch n u đ ng nh t th c sau G(a, b, c) = G(a, c, b) đúng v i m i b ba s th c dương (a, b, c). Hơn n a n u v i m i c p hai s th c dương x, y mà G(x, y, y) = 0 thì G(a, b, c) đư c g i là hàm n a đ i x ng ba bi n chu n. 0.1.2 Các đ nh lý cơ s i) Đ nh lý 1: v cơ s c a phương pháp SOS Gi s F (a, b, c) là m t đa th c đ i x ng ba bi n chu n thì t n t i m t đa th c n a đ i x ng ba bi n G(a, b, c) sao cho đ ng nh t th c sau là đúng F (a, b, c) = G(a, b, c)(b − c)2 + G(b, c, a)(c − a)2 + G(c, a, b)(a − b)2 Trư c khi đưa ra m t ch ng minh c a đ nh lý này d a trên m t s hi u bi t đơn gi n v không gian vecto chúng tôi mu n nh n m nh v i các b n r ng đ nh lý trên là đ đ áp d ng đ i v i t t c các hàm phân th c đ i x ng ba bi n.
2 B i vì đ nh lý 1 h n ch trong l p các đa th c ba bi n nên có có th nói t i b c c a đa th c. Trong đa th c ba bi n a, b, c s ch a (và ch ch a !) các h ng t d ng tm,n,p am bn cp trong đó m, n, p là các s nguyên không âm. N u tm,n,p = 0 thì m + n + p đư c g i là b c c a h ng t này. Trong trư ng h p ngư c l i ta quy ư c b c c a h ng t này b ng 0. S m + n + p l n nh t đư c g i là b c c a đa th c đó. Ch ng minh đ nh lý 1 Ta ch ng minh đ nh lý 1 cho l p các đa th c b c n. Ký hi u S(F ) là t p h p t t c các đa th c ba bi n F (a, b, c) đ i x ng chu n b c n, S(Q) là t p h p t t c các đa th c Q(a, b, c) đ i x ng ba bi n chu n b c n có d ng Q(a, b, c) = G(a, b, c)(b − c)2 + G(b, c, a)(c − a)2 + G(c, a, b)(a − b)2, đây G(a, b, c) là đa th c n a đ i x ng ba bi n b c n − 2 (ta xét n ≥ 2 vì v i n=1 thì đ nh lý hi n nhiên đúng). Rõ ràng S(Q) là không gian vecto con c a không gian vecto F (a, b, c). Và do đó s chi u c a S(Q) không vư t quá s chi u c a S(F ). (∗) V i các s nguyên không âm α, β, γ xét các đa th c đ c bi t sau đây i) Fα,β,γ (a, b, c) = aα bβ cγ (t ng đư c l y trên t t c các hoán v (α , β , γ ) c a (α, β, γ)) ii) Gα,β,γ (a, b, c) = aα bβ cγ + aα bγ cβ iii) Qα,β,γ (a, b, c) = Gα,β,γ (a, b, c)(b−c)2+Gα,β,γ (b, c, a)(c−a)2+Gα,β,γ (c, a, b)(a− b)2 Ký hi u fn là t p h p t t c các b s (α, β, γ) tho mãn các đi u ki n α + β + γ = n, α ≥ β ≥ γ. Rõ ràng t p h p t t c các đa th c Fα,β,γ (a, b, c) v i (α, β, γ) ∈ fn là h sinh đ c l p tuy n tính c a S(F ) do đó s chi u c a S(F ) b ng s ph n t c a fn (1) Ký hi u qn là t p h p t t c các b s (α, β, γ) tho mãn các đi u ki n α + β + γ = n − 2, α + 2 ≥ β ≥ γ. Rõ ràng t p h p t t c các đa th c Qα,β,γ (a, b, c) v i (α, β, γ) ∈ qn là h vecto đ c l p tuy n tính c a S(Q) do đó s chi u c a S(Q) không nh hơn s ph n t c a qn (2) T các k t qu (1), (2) v i chú ý là fn và qn có cùng s ph n t ta suy ra s chi u c a S(Q) không nh hơn s chi u c a S(F ) (∗∗) V y t các k t qu (∗), (∗∗) suy ra s chi u c a hai không gian S(Q), S(F ) là b ng nhau, t đó suy ra m i ph n t c a không gian S(F ) đ u có th bi u di n qua các ph n t c a không gian S(Q). Đây là k t qu c n ph i ch ng minh. T đ nh lý này có th nh n th y m t thu t toán tìm bi u di n cơ s , đó là tìm ma tr n chuy n gi a hai không gian vecto S(Q) và S(F ). Dư i đây là m t thu t toán sơ c p hơn
0.1. BI U DI N CƠ S PHƯƠNG PHÁP SOS 3 ii) Đ nh lý 2: v thu t toán tìm bi u di n cơ s Gi s M (a, b, c), N (a, b, c) là hai đa thưc n a đ i x ng ba bi n, hơn n a v i m i s th c dương x thì phân s M (x, x, x)/N (x, x, x) là m t h ng s t. Khi đó t n t i hàm s n a đ i x ng ba bi n G(a, b, c) sao cho đ ng nh t th c sau là đúng M (a, b, c) M (b, c, a) M (c, a, b) F (a, b, c) = + + − 3t N (a, b, c) N (b, c, a) N (c, a, b) = G(a, b, c)(b − c)2 + G(b, c, a)(c − a)2 + G(c, a, b)(a − b)2 Ch ng minh đ nh lý 2 Đ i v i hàm n a đ i x ng G(a, b, c) chúng ta ti n hành ghép c p các h ng t n a đ i x ng am bncp + am bp cn. Sau đó nhóm t t c các h ng t có cùng b c vào m t nhóm. B s (n1 , n2, ..., nk) v i n1 > n2 > ... > nk g m t t c các giá tr b c c a đa th c đó s p theo th t gi m d n g i là b ch th cho đa th c đó. Lúc này ta có th vi t k G(a, b, c) = gm,n,p .am (bncp + bp cn ) i=1 m+n+p=ni ,n≥p Rõ ràng đi u ki n M (x, x, x)/N (x, x, x) là h ng s v i m i s th c dương x tương đương v i s ki n b ch th c a các đa th c M (a, b, c), N (a, b, c) là gi ng h t nhau. Và do đó ta xét hi u k M (a, b, c)/n(a, b, c) − t = [ αm,n,p .am (bncp + bp cn )]/N (a, b, c) i=1 m+n+p=ni ,n≥p trong đó αm,n,p = mm,n,p − tnm,n,p và do đó αm,n,p = 0, ∀i = 1, n m+n+p=ni ,n≥p Bây gi đ i v i m i t ng bên trong ng v i m i giá tr ni c a t s chúng ta ti n hành s p x p l i th t các h ng t trong t s c a phân s trên sau đó s dùng m t bi n đ i nh đ làm xu t hi n các nhân t a − b, b − c, c − a. Trư c h t ta chia các nghi m nguyên không âm (m, n, p) tho mãn n gep c a phương trình m + n + p = ni thành ni nhóm theo các giá tr c a m. S p x p l i th t các nhóm đó theo đ gi m d n c a m. Trong m i nhóm thì giá tr c a m là c đ nh, ta s p x p l i các nghi m nguyên không âm c a phương trình n + p = ni − m theo đ gi m d n c a n n u ni − m l và theo đ tăng d n c a n n u ni − m ch n. Sau khi đã s p th t xong, chúng ta có m t th t m i c a t p các nghi m ban đ u, mà ta s ký hi u là {(mj , nj , pj )|j = 1, l}, đây l là m t hàm s ph thu c ni . Đ đơn gi n ta ký hi u aj = amj (bnj cpj + bpj cnj ), bj = αmj ,nj ,pj
4 Khi đó m u s có th vi t l i m t các đơn gi n là a1b1 + a2b2 + ... + al bl = (a1 − a2)b1 + (a2 − a3 )(b1 + b2) + ... + (al−1 − al )(b1 + b2 + ... + bl). S d ng đi u ki n b1 + b2 + ...bl = 0 và chia các hi u a1 − a2 , a2 − a3, ..., al−1 − al vào ba lo i sau bn−p − cn−p i)am (bn+1cp + bn cp+1 ) − am (bn cp+1 + bn+1cp ) = am bn cp . .(b − c)2 b−c ii)am+1 (bncn + bncn ) − am (bn+1cn + bncn+1 ) = am bncn [(a − b) − (c − a)] Xét bi u th c am bncn [(a − b) − (c − a)] bm cn an[(b − c) − (a − b)] cm an bn[(c − a) − (b − c)] + + N (a, b, c) N (b, c, a) N (c, a, b) Ti n hành ghép t ng ph n trong ba h ng t trong bi u th c này thành ba c p theo các nhân t a − b, b − c, c − a. M t trong ba h ng t m i s là am−n bm−n (a − b)anbn cn[ − ] = (a − b)2.G(c, a, b) N (a, b, c) N (b, c, a) Trong đó cn an bn am−nN (a, b, c) − bm−nN (b, c, a) G(c, a, b) = . N (a, b, c).N (b, c, a) a−b đây ta đã s d ng N (b, c, a) = N (b, a, c). Do c t s và m u s c a phân s trên đ u là nh ng đã th c n a đ i x ng ba bi n a, b, c và d i x ng hai bi n a, b nên G(c, a, b) là hàm n a đ i x ng ba bi n. iii)am+1 (bn+1 cn + bncn+1 ) − am (bn+1cn+1 + bn+1cn+1 ) = am bncn [c(a − b) − b(c − a)] Xét bi u th c am bn cn[c(a − b) − b(c − a)]/N (a, b, c) + bm cn an[a(b − c) − c(a − b)]/N (b, c, a) + cm anbn [b(c − a) − a(b − c)]/N (c, a, b). Ti n hành ghép t ng ph n trong ba h ng t trong bi u th c này thành ba c p theo các nhân t a − b, b − c, c − a. M t trong ba h ng t m i s là am−n bm−n (a − b)anbn cn+1[ − ] = (a − b)2.G(c, a, b) N (a, b, c) N (b, c, a) Trong đó cn+1 an bn am−nN (a, b, c) − bm−nN (b, c, a) G(c, a, b) = . N (a, b, c).N (b, c, a) a−b đây ta đã s d ng N (b, c, a) = N (b, a, c). Do c t s và m u s c a phân s trên đ u là nh ng đã th c n a đ i x ng ba bi n a, b, c và d i x ng hai bi n a, b nên G(c, a, b) là hàm n a đ i x ng ba bi n. V y trong c ba trư ng h p ta đ u đã ch ra cách bi n đ i thích h p đ đưa bi u th c v d ng bi u di n c n thi t. Đi u này hoàn thành vi c ch ng minh đ nh lý 2. Ni m tin v s t n t i bi u di n cơ s đã đư c kh ng đ nh.