ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC LÊ HOÀNG TÙNG SỬ DỤNG CƠ SỞ GROEBNER GIẢI HỆ PHƯƠNG TRÌNH ĐA THỨC BẰNG PHƯƠNG PHÁP KHỬ BIẾN LUẬN VĂN THẠC SỸ TOÁN HỌC THÁI NGUYÊN - NĂM 2015 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC LÊ HOÀNG TÙNG SỬ DỤNG CƠ SỞ GROEBNER GIẢI HỆ PHƯƠNG TRÌNH ĐA THỨC BẰNG PHƯƠNG PHÁP KHỬ BIẾN LUẬN VĂN THẠC SỸ TOÁN HỌC Chuyên ngành: PHƯƠNG PHÁP TOÁN SƠ CẤP Mã số 60.46.01.13 Người hướng dẫn khoa học GS.TS LÊ THỊ THANH NHÀN THÁI NGUYÊN - NĂM 2015 Mục lục Mở đầu Vành đa thức, iđêan tập đại số 1.1 Vành đa thức, iđêan vành đa 1.2 Định lý sở Hilbert 1.3 Tập đại số 1.4 Iđêan đơn thức thức 4 11 Ứng dụng sở Groebner để giải hệ phương trình đa thức phương pháp khử biến 2.1 Thứ tự đơn thức thuật toán chia với dư 2.2 Cơ sở Groebner 2.3 Thuật toán Buchberger 2.4 Định lý khử biến ứng dụng giải hệ phương trình đa thức 2.5 Các ví dụ 17 17 23 27 32 34 Kết luận 40 Tài liệu tham khảo 41 Mở đầu Trong luận văn thường giả thiết K trường, R trường số thực C trường số phức Thuật toán chia với dư kết quan trọng vành đa thức biến K[x], giúp giải toán quan trọng toán thành viên, toán tìm ước chung lớn hai đa thức, toán tìm tổng, thương, giao iđêan Mặc dù thuật toán chia với dư đa thức biến biết từ xa xưa, thuật toán chia với dư hữu hiệu cho đa thức nhiều biến phát triển vào năm 60 kỉ trước B Buchberger giới thiệu lí thuyết sở Groebner luận án tiến sĩ vào năm 1965 hướng dẫn giáo sư W Groebner Điểm mấu chốt khởi đầu cho hình thành lí thuyết sở Groebner việc mở rộng thuật toán chia với dư thuật toán Euclid tìm ước chung lớn cho đa thức biến sang thuật toán chia với dư thuật toán Buchberger tìm sở Groebner cho đa thức nhiều biến Mục đích luận văn "Sử dụng sở Groebner để giải hệ phương trình đa thức phương pháp khử biến" trình bày lại số kết báo [5] Mencinger năm 2013, giảng [4] Lall năm 2004 báo [7] Sturmfels năm 2005 sở Groebner, tập trung chủ yếu vào ứng dụng sở Groebner để giải hệ phương trình đa thức nhiều ẩn phương pháp khử biến Luận văn gồm hai chương, có phần kết luận danh mục tài liệu tham khảo Chương trình bày vành đa thức nhiều biến, iđêan vành đa thức nhiều biến tập đại số (đó tập nghiệm họ đa thức vành đa thức K[x1 , , xn ]) Chương trình bày Định lý sở Hilbert nhằm quy tập đại số tập nghiệm họ hữu hạn đa thức Chương giới thiệu sở Groebner tập trung trình bày việc giải hệ phương trình đa thức nhiều biến phương pháp khử biến Trong suốt luận văn làm việc với đa thức có hệ số trường K Riêng phần Định lí sở Hilbert Chương 1, phải làm việc với đa thức có hệ số vành K[x1 , , xn−1 ], từ dùng quy nạp để chứng minh iđêan K[x1 , , xn ] hữu hạn sinh Trong thời gian thực luận văn này, nhận dẫn tận tình, chu đáo Giáo sư - Tiến sĩ Lê Thị Thanh Nhàn Tôi xin bày tỏ lòng biết ơn sâu sắc tới cô giúp hoàn thành luận văn Tác giả Chương Vành đa thức, iđêan tập đại số Trong suôt chương này, giả thiết K trường Kí hiệu N tập số nguyên dương N0 tập số nguyên không âm Trong chương tập trung trình bày vành đa thức, iđêan vành đa thức nhiều biến tập đại số, đồng thời trình bày Định lý sở Hilbert nhằm quy tập đại số tập nghiệm họ hữu hạn đa thức Ngoài trình bày iđêan đơn thức, nghiên cứu đến toán thành viên, toán tìm giao toán tìm iđêan thương hai iđêan đơn thức 1.1 Vành đa thức, iđêan vành đa thức Định nghĩa 1.1.1 Kí hiệu K[x1 , , xn ] tập đa thức n biến với hệ số K Với i, j ∈ Nn0 , i = (i1 , , in ) j = (j1 , , jn ), ta định nghĩa i + j = (i1 + j1 , , in + jn ).Kí hiệu xi đơn thức xi11 xinn ta gọi i1 + + in bậc xi Khi K[x1 , , xn ] vành với phép cộng phép nhân xi + bi xi = (ai + bi )xi ; i∈Nn0 i∈Nn0 x i i∈Nn0 bi xi = i∈Nn0 x i , với đa thức i∈Nn0 i∈Nn0 ck xk , ck = k∈Nn0 bj i+j=k bi xi ∈ K[x1 , , xn ] Vành K[x1 , , xn ] i∈Nn0 gọi vành đa thức n biến x1 , , xn với hệ số K Chú ý 1.1.2 Vành đa thức n biến x1 , , xn với hệ số K xây dựng quy nạp theo n sau Khi n = 1, vành đa thức trở thành vành đa thức biến K[x1 ] Với n = 2, vành đa thức hai biến K[x1 , x2 ] với hệ số K vành đa thức biến x2 với hệ số K[x1 ] Bằng quy nạp, vành đa thức n biến K[x1 , , xn ] với hệ số K vành đa thức biến xn với hệ số vành K[x1 , , xn−1 ] Với a phần tử khác K , ta gọi bậc từ axi bậc đơn thức xi Chú ý đa thức biểu diễn cách thành tổng từ không đồng dạng (nếu không kể đến thứ tự hạng tử) Ta gọi bậc (hay bậc tổng thể) đa thức khác bậc cao từ đa thức Từ định nghĩa, ta có tính chất sau bậc đa thức Bổ đề 1.1.3 Cho f1 (x1 , , xn ), f2 (x1 , , xn ) ∈ K[x1 , , xn ] đa thức khác cho tổng chúng khác Khi (i) deg(f1 (x1 , , xn ) + f2 (x1 , , xn )) ≤ max deg fi (x1 , , xn ), i=1,2 (ii) deg f1 (x1 , , xn )f2 (x1 , , xn ) = deg f1 + deg f2 Tiếp theo, trình bày tính chất phổ dụng vành đa thức nhiều biến Mệnh đề 1.1.4 Gọi j : K → K[x1 , , xn ] cho j(a) = a với a ∈ K phép nhúng tự nhiên Với vành giao hoán S , hệ gồm n phần tử s1 , , sn S đồng cấu ϕ : K → S , tồn đồng cấu ϕ∗ : K[x1 , , xn ] → S cho ϕ∗ (xi ) = si với i ∈ {1, , n} ϕ∗ j = ϕ Chứng minh Xét ánh xạ ϕ∗ : K[x1 , , xn ] → S xác định ϕ∗ (f (x1 , , xn )) = ϕ(ai )si11 sinn i=(i1 , ,in )∈Nn0 với xi11 xinn ∈ K[x1 , , xn ] f (x1 , , xn ) = i=(i1 , ,in )∈Nn0 Khi ϕ∗ đồng cấu vành, ϕ∗ (xi ) = si với i ∈ {1, , n} ϕ∗ j = ϕ Do ϕ∗ đồng cấu thỏa mãn yêu cầu Bây ta chứng minh tính Giả sử ϕ∗1 đồng cấu từ K[x1 , , xn ] đến S thỏa mãn ϕ∗1 (xi ) = si với i ∈ {1, , n} ϕ∗1 j = ϕ Khi ϕ∗1 (a) = ϕ∗1 j(a) = ϕ(a) với a ∈ K Lại ϕ∗1 đồng cấu vành nên với đa thức f (x1 , , xn ) = xi11 xinn i=(i1 , ,in )∈Nn0 vành K[x1 , , xn ] ta có ϕ∗1 (f (x1 , , xn )) = ϕ(ai )si11 sinn i=(i1 , ,in )∈Nn0 Do ϕ∗ = ϕ∗1 Cho A vành K Khi áp dụng Mệnh đề 1.1.4 đồng cấu nhúng ϕ : A → K ta có kết sau Hệ 1.1.5 Cho A vành K Với k1 , , kn ∈ K cho trước, tồn đồng cấu vành ϕ∗ : A[x1 , , xn ] → K cho ϕ∗ (xi ) = ki với i = 1, , n ϕ∗ (a) = a với a ∈ A Hệ 1.1.6 Giả sử B vành giao hoán, b1 , , bn ∈ B j : K → B đồng cấu vành cho với vành giao hoán S , đồng cấu ϕ : K → S hệ gồm n phần tử s1 , , sn ∈ S , tồn đồng cấu ϕ∗ : B → S cho ϕ(bi ) = si với i ∈ {1, , n} ϕ∗ j = ϕ Khi j đơn cấu B ∼ = K[x1 , , xn ] Hệ 1.1.6 cho ta cách xác định khác vành đa thức sau: Vành đa thức n biến với hệ số K (B, j, b1 , , bn ), B vành giao hoán, b1 , , bn ∈ B j : K → B đồng cấu vành thỏa mãn điều kiện: với vành giao hoán S , với gồm n phần tử s1 , , sn ∈ S với đồng cấu ϕ : K → S , tồn đồng cấu ϕ∗ : B → S cho ϕ∗ (bi ) = si với i ∈ {1, , n} ϕ∗ j = ϕ Định nghĩa 1.1.7 Một tập I ⊆ K[x1 , , xn ] gọi iđêan K[x1 , , xn ] ∈ I, f − g ∈ I, hf ∈ I với f, g ∈ I h ∈ K[x1 , , xn ] Định nghĩa 1.1.8 Iđêan I gọi iđêan hữu hạn sinh K[x1 , , xn ] tồn hữu hạn đa thức f1 , , ft ∈ I cho I = {h1 f1 + + ht ft | h1 , , ht ∈ K[x1 , , xn ]} Trong trường hợp ta viết I = (f1 , , ft ) ta nói {f1 , , ft } hệ sinh I Nếu I = (f ) ta nói I iđêan sinh f 1.2 Định lý sở Hilbert Trong suốt tiết này, giả thiết V vành giao hoán khác K trường Ta nói vành V vành Noether dãy tăng iđêan V dừng, tức I1 ⊆ I2 ⊆ ⊆ In ⊆ dãy tăng iđêan V tồn n0 ∈ N cho In = In0 với n ≥ n0 Mục tiêu tiết chứng minh Định lí sở Hilbert, phát biểu V vành Noether vành đa thức V [x] vành Noether Để chứng minh Định lí sở Hilbert, cần số đặc trưng sau vành Noether Mệnh đề 1.2.1 Các phát biểu sau tương đương (i) V vành Noether (ii) Mỗi iđêan V hữu hạn sinh (iii) Mỗi họ khác rỗng iđêan V có phần tử cực đại (theo quan hệ bao hàm) Chứng minh (i)⇒(ii) Cho I iđêan V Giả sử I không hữu hạn sinh Lấy a1 ∈ I Do I không hữu hạn sinh nên (a1 ) = I , tồn a2 ∈ I\(a1 ) Do I không hữu hạn sinh nên (a1 , a2 ) = I , tồn a3 ∈ I\(a1 , a2 ) Cứ tiếp tục trình ta thu dãy tăng không dừng (a1 ) ⊂ (a1 , a2 ) ⊂ ⊂ (a1 , , an ) ⊂ iđêan V , điều mâu thuẫn với giả thiết (i) (ii)⇒(iii) Cho Γ = ∅ họ iđêan V Giả sử Γ phần tử cực đại Lấy I1 ∈ Γ Do I1 không cực đại nên tồn I2 ∈ Γ cho I1 ⊂ I2 I1 = I2 Do I2 không cực đại nên tồn I3 ∈ Γ cho I2 ⊂ I3 I2 = I3 Cứ tiếp tục trình ta dãy tăng không dừng I1 ⊂ I2 ⊂ ⊂ In ⊂ phần tử Γ Đặt I = In Khi I iđêan n≥1 V Theo giả thiết (ii), I hữu hạn sinh Giả sử I = (a1 , , ak ) Với i = 1, , k , ∈ I nên tồn ni cho ∈ Ini Chọn n0 = max ni i=1, ,k Khi ∈ In0 với i = 1, , k Suy I ⊆ In0 Do In = In0 với n ≥ n0 Điều vô lí (iii)⇒(i) Cho I1 ⊆ I2 ⊆ ⊆ In ⊆ dãy tăng iđêan V Đặt Γ = {In }n≥1 Theo giả thiết (iii), Γ có phần tử cực đại In0 Suy In = In0 với n ≥ n0 Định lý 1.2.2 (Định lý sở Hilbert) Cho V vành Noether Khi V [x] vành Noether Chứng minh Theo Mệnh đề 1.2.1, ta cần chứng minh iđêan V [x] hữu hạn sinh Cho J iđêan V [x] Nếu J = {0} rõ ràng J hữu hạn sinh Cho J = {0} Gọi m số bé bậc đa thức khác thuộc J Với n ≥ m ta định nghĩa n xi ∈ J, deg f (x) = n, an = a} ∪ {0} In = {a ∈ V | ∃f (x) = i=0 Khi In iđêan V In ⊆ In+1 Vì V vành Noether nên In hữu hạn sinh theo Mệnh đề 1.2.1, ta viết In = (an,1 , , an,in ) với n ≥ m Hơn nữa, V Noether nên tồn số tự nhiên k ≥ m cho In = Ik với n ≥ k Với n = m, , k j = 1, , in , gọi fn , j(x) ∈ J đa thức có bậc n hệ số cao an j Đặt An = {fnj (x)|j = 1, , in } k A = An Khi A tập hữu hạn Ta chứng minh J = (A) n=m Rõ ràng (A) ⊆ J Cho = p(x) ∈ J với a hệ số cao p(x) Khi deg p(x) ≥ m Ta chứng minh p(x) ∈ (A) quy nạp theo deg p(x) Cho deg p(x) = m Khi a ∈ Im Do tồn c1 , , cim ∈ K cho im a = cj am,j Đặt q(x) = p(x) − j=1 im cj fm,j (x) Khi q(x) j=1 có bậc nhỏ m Chú ý q(x) ∈ J Do q(x) = theo cách chọn m Suy p(x) ∈ (A) Cho deg p(x) = n > m giả thiết đa thức J với bậc nhỏ n thuộc (A) Khi a ∈ In Đặt t = min{n, k} Suy In = It a ∈ It Do tồn c1 , , cit ∈ K it cho a = it cj at,j Đặt q(x) = p(x)− j=1 cj xn−t ft,j (x) Khi q(x) ∈ J j=1 q(x) hoặc có bậc nhỏ n Theo giả thiết quy nạp, q(x) ∈ (A) Suy p(x) ∈ (A) Do J = (A) Chú ý 1.2.3 Có chứng minh khác ngắn gọn cho Định lý sở Hilbert Cho V vành Noether Giả sử V [x] không Noether Khi V [x] có iđêan J không hữu hạn sinh Rõ ràng J = Chọn f1 đa thức khác i = 1, , s Suy r2 − r1 = 0f1 + + 0fs + (r2 − r1 ) thỏa mãn điều kiện Định lý 2.1.9 Do r2 − r1 dư phép chia r2 − r1 cho f1 , , fs Do r2 − r1 ∈ I f1 , , fs sở Groebner I nên theo Định lý 2.2.7, dư phép chia r2 − r1 cho f1 , , fs Vì r1 = r2 2.3 Thuật toán Buchberger Trong suốt tiết này, giả thiết U = K[x1 , , xn ] vành đa thức n biến trường K ≤ thứ tự đơn thức Mon(U ) Buchberger dùng Định lí chia với dư để đưa tiêu chuẩn cho hệ sinh iđêan sở Groebner Từ ông xây dựng thuật toán, gọi thuật toán Buchberger, để tìm sở Groebner iđêan cho trước hệ sinh hữu hạn Thuật toán Buchberger xem tổng quát thuật toán Euclid tìm ước chung lớn Cho f, g ∈ K[x1 , , xn ] với in(f ) = axi11 xinn in(g) = bxj11 xjnn Ta kí hiệu lcm(in(f ), in(g)) = xt11 xtnn bội chung nhỏ in(f ) in(g), tk = max{ik , jk } với k = 1, , n Định nghĩa 2.3.1 Với f, g ∈ K[x1 , , xn ], đặt S(f, g) = lcm(in(f ), in(g)) lcm(in(f ), in(g) f− g in(f ) in(g) S(f, g) gọi S -đa thức f g Trước đưa tiêu chuẩn Buchberger cho hệ đa thức sở Groebner, cần bổ đề sau Bổ đề 2.3.2 Cho u đơn thức, f1 , , fs đa thức c1 , , cs s phần tử K thỏa mãn lm(f1 ) = = lm(fs ) = u lm( ci fi ) < u i=1 s ci fi tổ hợp tuyến tính với hệ số K S -đa thức Khi i=1 S(fj , fk ) Hơn nữa, lm(S(fj , fk )) < u với j, k = 1, , s Chứng minh Không tính tổng quát giả thiết ci = với i Đặt s in(fi ) = di lm(fi ), in(fi ) = di u với i = 1, , s Vì lm( i=1 27 ci fi ) < u nên s ci di = Đặt pi = i=1 s fi di Khi pi có hệ số cao ta có s ci di pi = c1 d1 (p1 − p2 ) + (c1 d1 + c2 d2 )(p2 − p3 ) ci fi = i=1 i=1 s−1 s ci di )(ps−1 − ps ) + ( + + ( i=1 ci di )ps i=1 Do lcm(in(fj ), in(fk )) = u nên ta có S(fj , fk ) = u u u u fj − fk = fj − f k = pj − pk in(fj ) in(fk ) dj u dk u s Thay biểu diễn pj − pk S(fj , fk ) vào công thức s s ci di = 0, ta suy với ý i=1 ci fi phía i=1 ci fi tổ hợp tuyến tính với hệ số i=1 K S(fj , fk ) Vì pj pk có hệ số cao nên từ cao hai đa thức u Do pj − pk có từ cao nhỏ u, tức S(fj , fk ) có từ cao nhỏ u Định lý 2.3.3 (Tiêu chuẩn Buchberger) Cho I iđêan K[x1 , , xn ] f1 , , ft hệ sinh I Khi f1 , , ft sở Groebner I với i = j , phần dư phép chia S -đa thức S(fi , fj ) cho f1 , , ft Chứng minh Giả sử f1 , , fs sở Groebner I Vì S(fi , fj ) ∈ I nên theo Định lí 2.3.7, dư phép chia S(fi , fj ) cho f1 , , fs đa thức Ngược lại, giả sử dư phép chia S(fi , fj ) cho f1 , , fs đa thức với i = j Ta chứng minh f1 , , fs sở Groebner I Cho = f ∈ I Ta cần in(f ) ∈ (in(f1 ), , in(fs )) Vì f ∈ I nên tồn đa thức hi cho f = h1 f1 + + hs fs Đặt mi = lm(hi fi ) với i Gọi u đơn thức cao đơn thức m(1), , m(s) Khi rõ ràng lm(f ) ≤ u Xét tất biễu diễn f thành tổ hợp f1 , , fs Với biểu diễn ta nhận đơn thức u Theo định nghĩa thứ tự đơn thức, tập đơn thức u thu từ biểu diễn f qua f1 , , fs ta chọn đơn thức bé nhất, kí hiệu u0 Với u0 vừa chọn, ta khẳng định lm(f ) = u0 Chú ý khẳng định 28 chứng minh in(f ) ∈ (in(f1 ), , in(fs )), định lí chứng minh Giả sử trái lại, lm(f ) < u0 Từ biểu diễn f ứng với u0 ta viết f= hi fi + hi f i m(i)=u0 = m(i) z > x hệ y − x2 , z − x3 sở Groebner iđêan I = (y − x2 , z − x3 ) Tuy nhiên, chọn thứ tự đơn thức thứ tự từ điển x > y > z hệ y − x2 , z − x3 không sở Groebner iđêan I = (y−x2 , z −x3 ) Thật vậy, ta có in(y−x2 ) = −x2 , in(z −x3 ) = −x3 Do S(y −x2 , z −x3 ) = x3 −xy −x3 +z = −xy +z Vì dư phép chia S(y − x2 , z − x3 ) cho y − x2 , z − x3 −xy + z Theo tiêu chuẩn Buchberger, y − x2 , z − x3 không sở Groebner I Từ tiêu chuẩn Buchberger, có thuật toán, gọi thuật toán Buchberger, để thu sở Groebner I xuất phát từ hệ sinh I Sau mô tả bước thuật toán 30 Thuật toán 2.3.7 (Thuật toán Buchberger) Cho I = (f1 , , fs ) iđêan khác vành đa thức K[x1 , , xn ] Để tìm sở Groebner I ta tiến hành bước: Bước Đặt G0 = {f1 , , fs } Với i, j ∈ {1, , s}, chia S(fi , fj ) cho f1 , , fs Nếu đa thức dư G0 sở Groebner I , trình kết thúc Nếu ngược lại, gọi fs+1 đa thức dư khác xuất phép chia S(fi , fj ) cho f1 , , fs Đặt G1 = {f1 , , fs , fs+1 } Rõ ràng G1 = {f1 , , fs , fs+1 } hệ sinh I Bước k+1 Giả sử thực xong bước k ,ta tiến hành Bước k + Khi ta có hệ sinh Gk = {f1 , , fs+k } I , fs+t dư khác chia S(fi , fj ) cho hệ f1 , , fs+t−1 với t ≤ k Với i, j ∈ {1, , s+k}, chia S(fi , fj ) cho f1 , , fs+k Nếu đa thức dư Gk sở Groebner I , trình kết thúc Nếu ngược lại, gọi fs+k+1 đa thức dư khác xuất phép chia S(fi , fj ) cho f1 , , fs+k Đặt Gk+1 = {f1 , , fs+k+1 } Cứ tiếp tục trình Quá trình phải kết thúc sau số hữu hạn bước hệ sinh cuối thu sở Groebner I Thật vậy, giả sử trình không kết thúc Khi với số tự nhiên k , đa thức dư fs+k+1 phép chia S(fi , fj ) cho hệ f1 , , fk có tính chất: fs+k+1 = từ fs+k+1 bội in(ft ) với t ≤ k Suy in(fs+k+1 ) ∈ / Ik , Ik = (in(f1 , , in(fs+k )) Do ta có dãy tăng không dừng iđêan đơn thức I1 ⊂ I2 ⊂ Theo Định lí sở Hilbert, điều xảy Ví dụ 2.3.8 (Xem [3, Trang 90]) Trên vành đa thức R[x, y], cho I = (f1 , f2 ), f1 = x3 − 2xy f2 = x2 y − 2y + x Xét thứ tự từ điển phân bậc x > y Ta có S(f1 , f2 ) = −x2 Do dư phép chia S(f1 , f2 ) cho f1 , f2 f3 = −x2 = Xét hệ sinh f1 , f2 , f3 I Ta có S(f1 , f2 ) = f3 Do dư phép chia S(f1 , f2 ) cho f1 , f2 , f3 Ta có S(f1 , f3 ) = f1 − (−x)f3 −2xy Do dư tương ứng f4 = −2xy = Xét hệ sinh f1 , f2 , f3 , f4 Ta có S(f1 , f2 ) = f3 , S(f1 , f3 ) = f4 Vì dư chia S(f1 , f2 ) S(f1 , f3 ) cho f1 , f2 , f3 , f4 Ta có S(f1 , f4 ) = yf1 − (− 21 )x2 f4 Do dư phép chia S(f1 , f4 ) cho f1 , f2 , f3 , f4 Ta có S(f2 , f3 ) = f2 − (−y)f3 Do dư tương ứng với S(f2 , f3 ) Chia S(f2 , f4 ) cho hệ f1 , f2 , f3 , f4 ta 31 dư f5 = −2y +x Xét hệ sinh f1 , f2 , f3 , f4 , f5 Ta dễ kiểm tra dư phép chia S(fi , fj ) cho f1 , f2 , f3 , f4 , f5 với i, j = 1, 2, 3, 4, Vậy f1 , f2 , f3 , f4 , f5 sở Groebner I Như nêu Tiết 2.2, thuật toán Buchberger tìm sở Groebner cho ta lời giải toán thành viên Cụ thể, với đa thức f iđêan I , xác định xem f có phần tử I hay không cách tìm sở Groebner I chia f cho sở Khi f ∈ I dư phép chia đa thức Ví dụ 2.3.9 Trong vành đa thức Q[x, y, z], cho I = (xz − y , x3 − z ) f = xy −5z +x Chọn thứ tự từ điển phân bậc với x > y > z Sử dụng thuật toán Buchberger ta thu sở Groebner I f1 , f2 , f3 , f4 , f1 = xz − y , f2 = x3 − z , f3 = x2 y − z , f4 = xy − z , f5 = y − z Ta chia f cho f1 , f2 , f3 , f4 , f5 Ta có lm(f1 ) = xz, lm(f2 ) = x3 , lm(f3 ) = x2 y , lm(f4 ) = xy , lm(f5 ) = y Rõ ràng từ f bội lm(fi ) với i = 1, 2, 3, 4, Do dư phép chia f cho f1 , f2 , f3 , f4 , f5 f Vì f = 0, tức dư phép chia khác 0, nên f ∈ / I 2.4 Định lý khử biến ứng dụng giải hệ phương trình đa thức Bây trình bày nội dung luận văn Cơ sở Groebner sử dụng để giải hệ phương trình đa thức cách khử số biến số phương trình, sau quay trở lại giải hệ phương trình ban đầu Trước hết ta cần khái niệm sau Định nghĩa 2.4.1 Cho I = (f1 , , fs ) iđêan K[x1 , , xn ] Với số tự nhiên k = 1, , n − ta đặt Ik = I ∩ K[xk+1 , , xn ] Khi Ik iđêan K[xk+1 , , xn ] Ta gọi Ik iđêan khử thứ k I Định lý 2.4.2 (Định lý khử biến) Cho I iđêan K[x1 , , xn ] Giả sử G = {f1 , , fs } sở Groebner I ứng với thứ tự từ điển x1 > > xn Khi Gk = G ∩ K[xk+1 , , xn ] sở Groebner Ik với k = 1, , n − Chứng minh Cho k ∈ {1, , n − 1} Rõ ràng Gk ⊆ Ik Cho f ∈ Ik Khi f ∈ I Do G sở Groebner I nên lm(f ) ∈ (lm(f1 ), , lm(fs )) Theo Hệ 1.4.3, tồn fi cho lm(f ) bội lm(fi ) Vì f ∈ Ik nên 32 lm(fi ) ∈ K[xk+1 , , xn ] Do x1 > > xn nên từ khác fi thuộc K[xk+1 , , xn ] Vì fi ∈ K[xk+1 , , xn ] Suy fi ∈ Gk Giả sử Gk = {g1 , , gt } Khi lm(f ) ∈ (lm(g1 ), , lm(gt )) Do (lm(g1 ), , lm(gt )) = in(Ik ) Vì g1 , , gt sở Groebner Ik Chú ý 2.4.3 Chúng ta tóm tắt phương pháp dùng sở Groebner Định lí khử biến để giải hệ phương trình đa thức sau: Với tập S K[x1 , , xn ], Chương ta kí hiệu Z(S) ⊆ n K tập không điểm chung S Xét hệ phương trình f1 = 0, , fs = với f1 , , fs ∈ K[x1 , , xn ] Đặt I = (f1 , , fs ) Sử dụng thuật toán Buchberger, ta tìm sở Groebner G = {g1 , , gt } I Khi đó, theo Bổ đề 2.2.6 (iii), hệ G hệ sinh I Vì Z(f1 , , fs ) = Z(I) = Z(G), tức tập nghiệm hệ f1 = 0, , fs = Z(G) Với số tự nhiên k = 1, , n − 1, nhờ Định lí khử biến, hệ Gk = G ∩ K[xk+1 , , xn ] sở Groebner iđêan Ik Chú ý Gn−1 ⊆ K[xn ] hệ đa thức biến xn Do đó, giải hệ phương trình biến xn ta tính Z(Gn−1 ) Với k ≤ n − 1, giả sử tìm Z(Gk ), ta cần tìm Z(Gk−1 ) Nếu Gk−1 = {h1 , , hr } (ak+1 , , an ) ∈ Z(Gk ), (ak , , an ) ∈ Z(Gk−1 ) ak nghiệm hệ r phương trình biến hi (xk , ak+1 , , an ) = với i = 1, , r Từ ta tìm Z(Gk−1 ) Cứ tiếp tục vậy, ta tìm Z(G1 ) Thay phần tử (a2 , , an ) ∈ Z(G1 ) vào đa thức G ta hệ phương trình đa thức biến x1 Từ ta tìm Z(G) Chúng ta minh họa điều ví dụ sau Ví dụ 2.4.4 Cho hệ phương trình 2x2 − 4x + y − 4y + = x2 − 2x + 3y − 12y + = Để tìm nghiệm C2 hệ này, ta xét iđêan I = (f1 , f2 ) vành đa thức C[x, y], f1 = 2x2 − 4x + y − 4y + f2 = x2 − 2x + 3y − 12y + Chọn thứ tự từ điển với x > y Khi S -đa thức ứng với f1 , f2 −5y 15 S(f1 , f2 ) = + 10y − 2 33 Ta có lm(f1 ) = x2 = lm(f2 ) Rõ ràng từ S(f1 , f2 ) bội x2 Do S(f1 , f2 ) dư phép chia S(f1 , f2 ) cho f1 , f2 Vì −5y 15 ta có hệ sinh f1 , f2 , f3 I với f3 = S(f1 , f2 ) = + 10y − 2 Ta thấy đa thức dư phép chia S -đa thức S(fi , fj ) cho f1 , f2 , f3 với i, j = 1, 2, Do G = {f1 , f2 , f3 } sở Groebner I Đặt G1 = G ∩ C[y] Theo Định lí khử biến, G1 = {f3 } sở Groebner iđêan I ∩ C[y] Suy Z(G1 ) = Z(f3 ) = {1, 3} ⊆ C Thay y = vào đa thức G ta x = x = Thay y = vào đa thức G ta x = x = Do Z(G) = {(0, 1), (2, 1), (0, 3), (2, 3)} Đây tập nghiệm phức hệ cho 2.5 Các ví dụ x+y+z =1 x2 + y + z = x3 + y + z = Ví dụ 2.5.1 Giải hệ phương trình Lời giải Xét iđêan I = (x + y + z − 1, x2 + y + z − 1, x3 + y + z − 1) Chọn thứ tự từ điển với x > y > z Thuật toán Buchberger cho ta sở Groebner I G = {g1 , g2 , g3 }, g1 = x + y + z − 1, g2 = y + yz − y + z − z, g3 = z − z Xét phương trình g3 = ta suy z ∈ {0; 1} Với z = 0, thay vào đa thức G ta y = {0; 1} x = {1; 0} Với z = 1, thay vào đa thức G ta y = x = Vậy tập nghiệm hệ Z(G) = {(1; 0; 0), (0; 1; 0), (0; 0; 1)} x2 + y + z − = x2 − 2x + y + z = 2x − 3y − z = Ví dụ 2.5.2 Giải hệ phương trình 34 Lời giải Xét iđêan I = (x2 + y + z − 1, x2 − 2x + y + z , 2x − 3y − z) Chọn thứ tự từ điển với x > y > z Thuật toán Buchberger cho ta sở Groebner I G = {g1 , g2 , g3 }, g1 = 2x − 1, g2 = 3y + z − 1, g3 = 40z − 8z − 23 √ √ − 26 + 26 ; Xét phương trình g3 = ta suy z ∈ 20 20 √ √ − 26 + 26 Với z = , thay vào đa thức G ta y = 20 20 x= √ √ + 26 − 26 Với z = , thay vào đa thức G ta y = 20 20 x= Vậy tập nghiệm hệ √ √ √ √ + 26 − 26 − 26 + 26 Z(G) = ; ; , ; ; 20 20 20 20   x2 + y + z − = Ví dụ 2.5.3 Giải hệ phương trình x + y2 + z − =  x + y + z − = Lời giải Xét iđêan I = (x2 + y + z − 1, x + y + z − 1, x + y + z − 1) Chọn thứ tự từ điển với x > y > z Thuật toán Buchberger cho ta sở Groebner I G = {g1 , g2 , g3 , g4 }, g1 g2 g3 g4 = x + y + z − 1, = y − y − z + z, = 2yz + z − z , = z − 4z + 4z − z = z (z − 1)2 (z + 2z − 1) 35 √ √ Xét phương trình g4 = ta suy z ∈ {0; 1; −1 + 2; −1 − 2} Với z = thay vào đa thức G ta y = {0; 1} x = {1; 0} Với z = thay vào đa thức G ta y = x = √ √ Với z = −1 + thay vào đa thức G ta y = −1 + √ x = −1 + √ √ Với z = −1 − thay vào đa thức G ta y = −1 − √ x = −1 − Vậy tập nghiệm hệ Z(G) = {(1; 0; 0); (0; 1; 0); (0; 0; 1); √ √ √ √ √ √ (−1 + 2; −1 + 2; −1 + 2); (−1 − 2; −1 − 2; −1 − 2)}   x2 + yz + x = Ví dụ 2.5.4 Giải hệ phương trình xy + z + z =  xz + y + y = Lời giải Xét iđêan I = (x2 + yz + x, xy + z + z, xz + y + y) Chọn thứ tự từ điển với x > y > z Thuật toán Buchberger cho ta sở Groebner I G = {g1 , g2 , g3 , g4 , g5 , g6 }, g1 g2 g3 g4 g5 g6 = x2 + x + yz, = xy + z + z, = xz + 2yz + yz + z + z, = y − 2yz − yz − y − z − z, = 2yz + 2yz + z + z , = 2z + 3z + z = z (2z + 3z + 1) Với z = 0, thay vào đa thức G ta y = x = y = x = −1 y = −1 x = Với z = −1, thay vào đa thức G ta y = x = 1 Với z = − , thay vào đa thức G ta y = − x = − 2 Vậy tập nghiệm hệ Xét phương trình g6 = ta suy z ∈ Z(G) = 0; −1; − 1 (0; 0; 0); (−1; 0; 0); (0; −1; 0); (− ; − ; − ) 2 36 2x + xy − x − y = x2 + x2 y + yz − z = x − x2 + y = Ví dụ 2.5.5 Giải hệ phương trình Lời giải Xét iđêan I = (2x + xy − x − y, x2 + x2 y + yz − z, x − x2 + y) Chọn thứ tự từ điển với x > y > z Thuật toán Buchberger cho ta sở Groebner I G = {g1 , g2 , g3 , g4 }, g1 g2 g3 g4 = 3x + 3y − z − 2z, = 3y − z + z, = 2yz + z − z, = z + 2z − 3z = z(z + 2z − 3) Xét phương trình g4 = ta suy z ∈ {0; 1; −3} Với z = 0, thay vào đa thức G ta y = x = Với z = 1, thay vào đa thức G ta y = x = Với z = −3, thay vào đa thức G ta y = x = −1 Vậy tập nghiệm hệ Z(G) = {(0; 0; 0); (1; 0; 1); (−1; 2; −3)}    x y−z =0 2xy − 4z = Ví dụ 2.5.6 Giải hệ phương trình   z 3− y = x − 4zy = Lời giải Xét iđêan I = (x2 y − z , 2xy − 4z, z − y , x3 − 4zy) Chọn thứ tự từ điển với x > y > z Thuật toán Buchberger cho ta sở Groebner I G = {1} Ta thấy sở Groebner G I chứa đa thức Vì hệ phương trình cho vô nghiệm Nhận xét 2.5.7 Các hệ phương trình Ví dụ 2.5.1 - 2.5.6 giải sử dụng phương pháp tìm sở Groebner dùng Định lí khử biến Tuy nhiên, hệ giải cách Dưới đây, trình bày hai ví dụ để minh họa 37   t2 + x2 + y + z = Ví dụ 2.5.8 Xét hệ phương trình sau t2 + 2x2 − xy − z =  t + y − z = Xét iđêan I = (t2 + x2 + y + z , t2 + 2x2 − xy − z , t + y − z ) Chọn thứ tự từ điển với t > x > y > z , ta có sở Groebner I G = {g1 , g2 , g3 , g4 , g5 }, g1 = x2 + y + z + y − 2y z + z , g2 = 2y + 3z + y − 2y z + z + xy, g3 = −5y − 7yz − 5y + 10y z − 3yz + 6z y + 4y z − 5y z + 2z y − 3y z − y 1 + 3xz + xz , g4 = t + y − z , g5 = 13y z + 9z + 6y z − 12z y + 6z + 5z y + 6z y − 4z y + z 12 + 5y − 10y z − 4y z + y 12 Ta thấy dù tìm sở Groebner I giải hệ phương trình đa thức g1 , g2 , g3 , g4 , g5 chứa nhiều biến    −2wx + 3x + 2yz = −2wy + 2xz = Ví dụ 2.5.9 Xét hệ phương trình sau −2wz + 2xy − 2z =   x + y + z − = Xét iđêan I = (−2wx + 3x2 + 2yz, −2wy + 2xz, −2wz + 2xy − 2z, x2 + y + z − 1) Chọn thứ tự từ điển với w > x > y > z , ta có sở Groebner I G = {g1 , g2 , g3 , g4 , g5 , g6 , g7 , g8 }, g1 g2 g3 g4 g5 g6 g7 g8 = 7670w − 11505x − 11505yz − 335232z + 477321z − 134419z , = x2 + y + z − 1, = 3835xy − 19584z + 25987z − 6043z, = −3835xz − 3835yz + 1152z + 1404z − 2556z, = −3835y − 3835yz + 3835y + 9216z − 11778z + 2562z, = 3835y z − 6912z + 10751z − 3839z, = 118yz − 118yz − 1152z + 1605z − 453z , = −1152z + 1763z − 655z + 44z 38 Ta thấy dù tìm sở Groebner I phương trình g8 = có biến z , bậc g8 lại lớn tìm nghiệm z = g8 (6 nghiệm lại không tìm được) Do giải hệ 39 Kết luận Luận văn trình bày tổng quan kiến thức lí thuyết sở Groebner ứng dụng giải hệ phương trình đa thức phương pháp khử biến Các kiến thức viết luận văn tham khảo chủ yếu từ báo [5, 7], sách [1, 3] giảng gần lí thuyết khử biến S Lall [4] Các nội dung luận văn là: Nhắc lại số kiến thức vành đa thức iđêan vành đa thức (nhiều biến); Chứng minh Định lí sở Hilbert, từ quy tập nghiệm họ đa thức (tập đại số) thành tập nghiệm họ hữu hạn đa thức; Trình bày tổng quan lí thuyết sở Groebner, nhấn mạnh thuật toán chia với dư, khái niệm sở Groebner thuật toán Buchberger để tìm sở Groebner; Chứng minh Định lí khử biến phương pháp giải hệ phương trình đa thức lí thuyết sở Groebner Định lí khử biến; Trình bày ví dụ minh họa việc giải hệ phương trình đa thức; Đưa ví dụ để thấy phương pháp dùng lí thuyết sở Groebner Định lí khử biến để giải hệ phương trình đa thức có hạn chế 40 Tài liệu tham khảo Tài liệu Tiếng Việt [1] Lê Thị Thanh Nhàn, Lý thuyết đa thức, NXB Đại học Quốc gia Hà Nội, 2015 Tài liệu Tiếng Anh [2] B Buchberger and F Winkler, (editors), Gr¨ obner Bases and Applications, London Mathematical Society Lectures Notes Series 251, Cambridge University Press, 1998 [3] D Cox, J Little and D O’Shea, Ideals, Varieties, and Algorithms, Springer-Verlag, New York, 1992 [4] S Lall, Elimination, http://lall.stanford.edu/data/engr210b_0405/ elimination_2004_11_07_01.pdf, 2004 [5] M Mencinger, On Groebner bases and their use in solving some practical problems, Universal Journal of Computational Mathematics, (2013), 514 [6] Victor V Prasolov, Polynomials, Springer, 2004 (second edition) [7] B Sturmfels, What is a Groebner basis?, Notices of the AMS, 52 (2005), 1-3 41 [...]... là f Vì f = 0, tức là dư của phép chia khác 0, nên f ∈ / I 2.4 Định lý khử biến và ứng dụng giải hệ phương trình đa thức Bây giờ chúng ta trình bày nội dung chính nhất của luận văn Cơ sở Groebner có thể sử dụng để giải hệ phương trình đa thức bằng cách khử một số biến ở một số phương trình, rồi sau đó quay trở lại giải hệ phương trình ban đầu Trước hết ta cần khái niệm sau Định nghĩa 2.4.1 Cho I = (f1... theo tiêu chuẩn Buchberger, hệ f1 , , fs là một cơ sở Groebner nếu và chỉ nếu phần dư của phép chia S(fi , fj ) cho f1 , , fs là đa thức 0 với mọi i < j Chú ý rằng cơ sở Groebner phụ thuộc vào thứ tự đơn thức Một hệ đa thức là cơ sở Groebner của một iđêan I đối với thứ tự đơn thức này, nhưng có thể không là cơ sở Groebner của I đối với thứ tự đơn thức khác Ta minh họa điều này bằng ví dụ sau Ví dụ 2.3.6... Theo hệ quả 2.1.11 ta có (I : u1 ) = (v1 , v2 , v3 ) = (y, xy, yz) Tương tự (I : u2 ) = (x, yz, z 2 ) Theo Hệ quả 2.1.6, (I : J) = (I : u1 )∩(I : u2 ) = (x, xy, yz)∩(x, yz, z 2 ) = (xy, yz, yz 2 , xyz, xyz 2 ) = (xy, yz) 16 Chương 2 Ứng dụng cơ sở Groebner để giải hệ phương trình đa thức bằng phương pháp khử biến 2.1 Thứ tự đơn thức và thuật toán chia với dư Ta kí hiệu U = K[x1 , , xn ] là vành đa thức. .. Vì thế f1 , , fs là một cơ sở Groebner của I Từ Định lý 2.2.7 ta có thể giải quyết bài toán thành viên cho một iđêan trong vành đa thức nhiều biến khi biết một cơ sở Groebner của iđêan đó Hệ quả 2.2.8 Cho f1 , , fs là một cơ sở Groebner của iđêan I Khi đó một đa thức f là phần tử của I nếu và chỉ nếu dư của phép chia f cho f1 , , fs là 0 Hệ quả 2.2.9 Nếu f1 , , fs là một cơ sở Groebner của iđêan I thì... sở Groebner và Định lí khử biến để giải hệ phương trình đa thức như sau: Với mỗi tập con S của K[x1 , , xn ], như trong Chương 1 ta kí hiệu Z(S) ⊆ n K là tập các không điểm chung của S Xét hệ phương trình f1 = 0, , fs = 0 với f1 , , fs ∈ K[x1 , , xn ] Đặt I = (f1 , , fs ) Sử dụng thuật toán Buchberger, ta tìm một cơ sở Groebner G = {g1 , , gt } của I Khi đó, theo Bổ đề 2.2.6 (iii), hệ G cũng là hệ. .. , f4 , f5 là cơ sở Groebner của I Như đã nêu trong Tiết 2.2, thuật toán Buchberger tìm cơ sở Groebner cho ta lời giải bài toán thành viên Cụ thể, với một đa thức f và một iđêan I , chúng ta có thể xác định xem f có là phần tử của I hay không bằng cách tìm một cơ sở Groebner của I rồi chia f cho cơ sở đó Khi đó f ∈ I nếu và chỉ nếu dư của phép chia là đa thức 0 Ví dụ 2.3.9 Trong vành đa thức Q[x, y,... 2.2 Cơ sở Groebner Trong phần cuối Tiết 2.1, chúng ta đã trình bày ví dụ chỉ ra "hạn chế" liên quan đến phép chia với dư các đa thức nhiều biến (thương và dư không duy nhất, chúng phụ thuộc vào việc chọn thứ tự các đa thức chia) Điều này dẫn đến những khó khăn trong việc sử dụng thuật toán chia với dư để giải quyết một số bài toán về đa thức nhiều biến Mục tiêu của tiết này là nghiên cứu những hệ đa thức, ... Z(f1 , , fs ) = Z(I) = Z(G), tức là tập nghiệm của hệ f1 = 0, , fs = 0 chính là Z(G) Với mỗi số tự nhiên k = 1, , n − 1, nhờ Định lí khử biến, hệ Gk = G ∩ K[xk+1 , , xn ] là một cơ sở Groebner của iđêan Ik Chú ý rằng Gn−1 ⊆ K[xn ] là hệ đa thức một biến xn Do đó, giải hệ phương trình một biến xn ta tính được Z(Gn−1 ) Với k ≤ n − 1, giả sử đã tìm được Z(Gk ), ta cần tìm Z(Gk−1 ) Nếu Gk−1 = {h1... và chỉ nếu ak là nghiệm của hệ r phương trình một biến hi (xk , ak+1 , , an ) = 0 với mọi i = 1, , r Từ đây ta tìm được Z(Gk−1 ) Cứ tiếp tục như vậy, ta tìm được Z(G1 ) Thay mỗi phần tử (a2 , , an ) ∈ Z(G1 ) vào các đa thức trong G ta được hệ phương trình đa thức một biến x1 Từ đó ta tìm được Z(G) Chúng ta minh họa điều này bằng ví dụ sau đây Ví dụ 2.4.4 Cho hệ phương trình 2x2 − 4x + y 2 − 4y + 3... vậy ta có hệ sinh mới f1 , f2 , f3 của I với f3 = S(f1 , f2 ) = + 10y − 2 2 Ta thấy rằng các đa thức dư trong phép chia S -đa thức S(fi , fj ) cho f1 , f2 , f3 là 0 với mọi i, j = 1, 2, 3 Do đó G = {f1 , f2 , f3 } là một cơ sở Groebner của I Đặt G1 = G ∩ C[y] Theo Định lí khử biến, G1 = {f3 } là một cơ sở Groebner của iđêan I ∩ C[y] Suy ra Z(G1 ) = Z(f3 ) = {1, 3} ⊆ C Thay y = 3 vào các đa thức của ... TRƯỜNG ĐẠI HỌC KHOA HỌC LÊ HOÀNG TÙNG SỬ DỤNG CƠ SỞ GROEBNER GIẢI HỆ PHƯƠNG TRÌNH ĐA THỨC BẰNG PHƯƠNG PHÁP KHỬ BIẾN LUẬN VĂN THẠC SỸ TOÁN HỌC Chuyên ngành: PHƯƠNG PHÁP TOÁN SƠ CẤP Mã số 60.46.01.13... Ứng dụng sở Groebner để giải hệ phương trình đa thức phương pháp khử biến 2.1 Thứ tự đơn thức thuật toán chia với dư Ta kí hiệu U = K[x1 , , xn ] vành đa thức n biến trường K Mon(U ) tập đơn thức. .. luận văn "Sử dụng sở Groebner để giải hệ phương trình đa thức phương pháp khử biến" trình bày lại số kết báo [5] Mencinger năm 2013, giảng [4] Lall năm 2004 báo [7] Sturmfels năm 2005 sở Groebner,