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

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

0
138
lượt xem
15
download

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

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

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

Chủ đề:
Lưu

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

  1. 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. 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
  3. 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. 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.

CÓ THỂ BẠN MUỐN DOWNLOAD

Đồng bộ tài khoản