Univerzitet u Beogradu
Elektrotehnički fakultet
Master rad
JAVA APLETI ZA VIZUELIZACIJE U TEORIJI
GREBNER-OVIH BAZA
Mentor:
Dr. Branko Malešević, doc.
Beograd, septembar 2011
Student:
Bojan Banjac
Br. indeksa: 2010/3153
Sadržaj
Uvod ……………………………………………………………………….......................2
Glava I :Grebnerove baze i Buchbergerov algoritam………………………………....3
1. Ideali prstena…………………………………………………………………..3
2. Prsten polinoma…..…………………………………………………………...5
3. Monomijalni ideali…………………………………………………………….7
4. Monomijalni poretci…………………………………………………………..8
5. Deljenje u prstenu više promenljivih i redukcija polinoma………………….11
6. Hilbertova teorema o bazi……………………………………………………14
7. Grebnerova baza …………………………………………………………….14
8. Sizidži niza polinoma i S-polinomi…………………………………………..16
9. Buchbergerov algoritam……………………………………………………...17
10. Algoritam redukcije baze…………………………………………………….20
11. Algoritam za pronalaženje planarnih preseka polinoma……………………..22
Literatura………………………………………………………………………………..24
1
Uvod
Inženjerska struka je od samog početka bila vezana za matematiku. Već u srednjem veku
je bilo jasno da bez temeljnog poznavanja matematike nije moguće precizno izvesti
zaključke iz usvojenih saznanja. Sa daljim razvojem prirodnih nauka ovo je bilo sve
vidljivije. Nijedan zakon fizike nije mogao proći kao definicija ako nije bio jasno
definisan kao matematička formula. Hemijski ogledi su konstantno koristili procentni
račun. Arhitekte su se oslanjale na formule koje su im prikazivale parametre objekta koji
grade. U današnje vreme, kada se primena ovih nauka ogleda u inženjerskim
disciplinama, nemoguće je zamisliti obrazovanog stručnjaka koji nema makar dobre
osnove u matematici.
Ovo je dovelo do toga da svaki fakultet u svetu svoje inženjerske kurseve započinje na
matematici. Ipak, od samih početaka pa do danas je došlo do velikog pomaka u
metodama. Dok je pre sto godina matematika bilo objašnjavana putem primera,
auditivnih predavanja, i vežbanja algoritama za rešavanje zadataka unutar stručne
literature, danas je dostupan daleko širi asortiman pomagala. Studentima je dostupan širi
izbor literature putem interneta. Komunikacija sa nastavnicima se odvija daleko
efikasnije zbog pojave emaila. Predavanja se više ne vrše samo kredom i tablom, već
postoji veliki broj pomagala koja korišćenjem mogućnosti kompjutera vizuelno
predstavljaju pojmove. Mnogi kompjuterski sistemi studentima omogućavaju proveru
rezultata proračuna.
Aplikacije koje su razvijene u okviru ovog master rada su kreirane kao pomoćno
nastavno sredstvo. Buchbegerov algoritam, koji je korišćen u nekoliko njih, danas je
jedan od standardnih načina rešavanja sistema jednačina, i koristi se u većini sistema
kompjuterske algebre. Zbog svoje važnosti ovaj algoritam se predaje na većini fakulteta
sa višim kursevima matematike. Ipak, postoji veoma mali broj aplikacija koje prikazuju
način funkcionisanja ovog algoritma, i načine njegove primene. Namera autora je bila da
se kreira aplikacija koja će moći da prikaže način funkcionisanja ovog algoritma i
grafički prikaže odreñene elemete ove oblasti matematike, kako bi studentima približio
ovu oblast.
U okviru prve glave ovog rada je dat prikaz teorije na osnovu koje su bazirane aplikacije.
Buchbergerov algoritam pripada oblasti simboličke algebre, te su date osnove teoreme i
definicije koje spadaju u ovu oblast. Takoñe je prikazana jedna od primena
Buchbergerovog algoritma, odnosno teorija na kojoj se ona zasniva, kako bi u okviru
prikaza aplikacija bilo definisano na čemu se bazira.
2
Glava I : Grebnerove baze i
Buchbergerov algoritam
U današnjim matematičkim kompjuterskim sistemima možemo sresti rešenja za mnoge
složene proračune. Kao jedna od najpraktičnijih metoda za nalaženje rešenja sistema
polinomijalnih jednačina u većini sistem možemo sresti Grebnerove baze. Teoriju
Grebnerovih baza je još 1932. predstavio Wolfgang Gröbner u okviru svoje doktorske
disertacije Ein Beitrag zum Problem der Minimalbasen. U toku svog daljeg rada on se
bavio računskom algebrom, ali je teorija koju je predstavio dobila ime Grebnerove baze
tek 1965. godine kada je student Wolfganga Gröbnera Bruno Buchberger u svojoj
doktorskoj disertaciji Ein Algorithmus zum Auffinden der Basiselemente des
Restklassenrings nach einem nulldimensionalen Polynomideal po svom mentoru
imenovao pojam Grebnerovih baza. Buchberger je u tom radu takoñe definisao algoritam
dalje poznat kao Buchbergerov algoritam, kojim se može doći do Grebnerove baze. Ovaj
algoritam se u modifikovanoj varijanti javlja i danas u većini sistema kompjuterske
algebre, i predstavlja veoma efikasno rešenje za veliki broj problema sa kojim se
programeri pri kreiranju takvih sistema mogu sresti.
1. Ideali prstena
Definicija 1.1 Neka je R= ( R,+,⋅) prsten, tada podskup I ⊆ R odreñuje ideal prstena
ukoliko je ispunjeno:
a) (∀x ∈ I )(∀y ∈ I ) x − y ∈ I
b) (∀x ∈ I )(∀r ∈ R )r ⋅ x, x ⋅ r ∈ I
Teorema 1.2 Neka je R= ( R,+,⋅) prsten i neka su I , J ⊆ R ideali prstena R. Tada sledeći
skupovi predstavljaju ideale u prstenu R:
a) I + J = {r | r = x + y ∧ x ∈ I ∧ y ∈ J }
n
b) I ⋅ J = {r | (∃n ∈ N )r = ∑ xi yi ∧ ( xi ) in=1 ⊆ I , ( yi ) in=1 ⊆ J }
i =1
c) I ∩ J = {r | r ∈ I ∧ r ∈ J }
d) I : J = {r | r (∀y ∈ J )r ⋅ y, y ⋅ r ∈ I }
Teorema 1.3 Neka je R= ( R,+,⋅) prsten i neka su I , J , M ⊆ R u idelu prstena. Tada važi:
a) I ⋅ J ⊆ I I J
b) ( I ∩ M ) + ( J ∩ M ) ⊆ ( I + J ) ∩ M
c) ( I : M ) + ( J : M ) ⊆ ( I + J ) : M
d) I : ( J + M ) = ( I : J ) ∩ ( I : M )
3
Teorema 1.4 Neka je R= ( R,+,⋅) prsten i neka je A ⊆ R podskup. Tada skup konačnih
suma:
n
m
i =1
j =1
1. I = {r | r = ∑ xi ai yi + ∑ k j b j ∧ ( xi ) in=1 , ( yi )in=1 ⊆ R ∧ (ai ) in=1 , (b j ) mj=1 ⊆ A ∧ (k j ) mj=1 ⊆ Z }
Odreñuje jedan ideal prstena R. Posebno ako je R komutativni prsten sa jedinicom, tada
ideal I se može predstaviti sledećim skupom:
n
2. I = {r | r = ∑ xi ai ∧ ( xi )in=1 ⊆ R ∧ (ai ) in=1 ⊆ A}
i =1
Definicija 1.5 U prethodnoj teoremi ideal I nazivamo ideal generisan skupom A, što
zapisujemo I = A .Pri tom ideal I odreñen sa (1) nazivamo dvostranim idealom, a ideal
I odreñen sa (2) nazivamo dvostranim idealom.
Teorema 1.6 Neka su u prstenu R= ( R,+,⋅) dati ideali I i J generisani skupovima A ⊆ R i
B ⊆ R respektivno. Tada važi:
a) I + J = A ∪ B
b) I ⋅ J = {a ⋅ b | a ∈ A ∧ b ∈ B}
Napomena 1.7 Ideal I ∩ J je najveći ideal sadržan u idealima I i J. Unija dva ideala
I ∪ J ne mora biti ideal, meñutim ideal I + J je najmanji ideal koji sadrži ideale I i J.
Odatle skup ideala nekog prstena u odnosu na presek i sumu ideala predstavlja mrežu.
∞
Napomena 1.8 Za ma koji rastući lanac ideala I1 ⊆ I 2 ⊆ ... unija J ′ = U J k odreñuje
k =0
jedan ideal.
Teorema 1.9 Neka je R= ( R,+,⋅) prsten. Tada su sledeći iskazi meñusobno ekvivalentni.
a) Svaki ideal I prstena R je generisan konačnim skupom.
b) Svaki rastući lanac ideala I1 ⊆ I 2 ⊆ ... prstena R postaje stacionaran, tj. Važi
I m = I m +1 = ... počev od nekog m.
Definicija 1.10 Prsten R= ( R,+,⋅) koji ispunjava bilo koji uslov prethodne teoreme naziva
se Noetherin prsten.
4
2. Prsten polinoma
Neka je K= ( K ,+,⋅) polje. Ako je x promenjiva nad K i ako su a0 , a1...a n ∈ K elementi
polja takvi da a n ≠ 0 uobičajeno je da se izraz a n x n + ... + a1 x + a0 naziva polinomom
stepena n po promenjivoj x. Drugi način definisanja polinoma je definisanje nizom
koeficijenata (a0 , a1 ,..., a n ,...) gde su ai ∈ K (i = 0,1,....) elementi polja takvi da vaši
postoji n takvo da ai = 0 za i > n .
Neka je dat polinom P nizom koeficienata, tada stepen polinoma dg(P) je najveći broj n
takav da a n ≠ 0 . Tada elemente a0 , a1...a n ∈ K nazivamo koeficientima polinoma, a
koeficijent a n nazivamo vodeći koeficijent polinoma. Dalje, za polinom P dat se
beskonačnim nizom koeficijenata koristimo zapis konačnim nizom (a0 , a1 ,..., a n )
podrazumevajući da ai = 0 za i > n . Jedinica polja 1 ∈ K može se poistovetiti sa
polinomom (1) nultog stepena i uopšte svaki element polja c ∈ K može se poistovetiti sa
polinomom (c) nultog stepena. Polinom x = (0,1) nazivamo promenljivom. Uvedimo
skup polinoma jedne promenljive:
K [ x] = {P = P ( x) | p − polinom nad K }
U skupu K [x] uvedimo binarne operacije:
a) ( a0 , a1 ,..., ai ,...) + (b0 , b1 ,..., bi ,...) = ( a0 + b0 , a1 + b1 ,..., ai + bi ,...)
b) (a0 , a1 ,..., ai ,...) ⋅ (b0 , b1 ,..., bi ,...) = (c0 , c1 ,..., ci ,...)
i
gde je ci = ∑ j = 0 a j ab − j (i = 0,1,2,...)
Dva polinoma su jednaka ako imaju jednake koeficijente. Prethodna definicija jednakosti
polinoma se podudara sa jednakošću dve ureñene n-torke.
Teorema 2.1 Neka je K= ( K ,+,⋅) polje, tada je K[x]= ( K [ x],+,⋅) komutativan prsten sa
jedinicom bez delitelja nule.
Napomena 2.2 Prethodna teorema važi ukoliko je K komutativan prsten sa jedinicom
bez delitelja nule, tada je je K[x]= ( K [ x],+,⋅) takoñe komutativan prsten sa jedinicom
bez delitelja nule.
Teoreme 2.3 Ako su dva polinoma nad poljem K jednaka tada su jednake i odgovarajuće
polinomske funkcije. Obratno tvrñenje važi za beskonačno polje K.
Teorema 2.4 Ako je dato konačno polje Galoisa K=GF(m) sa m = p n elemenata (za pprost broj i n ∈ N ). Ako su data dva polinoma Pr i Qs stepena r i s respektivno, pri
5
čemu je ispunjeno: m > max{r , s} , tada su polinomi Pr i Qs sa jednakim koeficijentima
ako i samo ako su im jednake odgovarajuće polinomske funkcije.
Teorema 2.5 Neka su dati polinomi P, Q,∈ K [ x] gde Q nije nula polinom, nad prstenom
K [x] . Tada postoje jedinstveno odreñei polinomi G , R ∈ K [ x ] takvi da važi
P = G ⋅ Q + R , takvi da dg ( R ) < dg (Q ) ili R=0.
Teorema 2.6 Neka je I ideal u prstenu polinoma K [x ] , tada je ideal I generisan jednim
elementom, tj. postoji polinom g ∈ K [x ] takav da važi I = {g} . Na osnovu ovoga
zaključujemo da je algebarska struktura K[x]= ( K [ x],+,⋅) Noetherin prsten.
Neka je K= ( K ,+,⋅) polje. Polazeći od prstena polinoma jedne pomenljive K [x] , saglasno
sa napomenom 2.2, prsten polinoma više promenljivih definišemo induktivno:
K[ x1 ,..., xn ]= ( K [ x 1 ,..., x n − 1 ])[ x n ]
Teorema 2.7 Neka je K= ( K ,+,⋅) polje, tada za svako n ∈ N algebarska struktura
K[ x1 ,..., xn ]= ( K [ x1 ,..., xn ],+,⋅) je komutativan prsten sa jedinicom bez delitelja nule.
Teorema 2.8 U prstenu polinoma jedne i više promenljivih, usled komutativnosti i
postojanja jedinice, svi ideali su jednostrani
Neka je dat polinom P = P ( x1 ,..., xn ) ∈ K [ x1 ,..., xn ] , tada važi jednakost:
P( x1 ,..., xn ) =
cα xα ...xα
∑
α
1
1
n
n
∈A0
gde je A0 ⊂ N
n
0
konačan skup n-torki α = (α1 ,..., α n ) prirodnih brojeva i gde je
cα ∈ K \ {0} . Izrazi M α = x1α1 ...xnα n u prethodnoj sumi nazivaju se monomima. Samim
tim, polinom P predstavlja linearnu kombinaciju monoma nad poljem K. Pojedinačne
sabirke cα x1α1 ...xnα n za α ∈ A0 , koji učestvuju u polinomu P nazivamo još i termima
polinoma. Dalje, n-torku α = (α1 ,..., α n ) nazivamo multistepen monoma, a sumu
n
eksponenata ∑k =1α k odreñuje stepen monoma, koji označavamo dg (M ) . Primetimo da
se jedinica polja 1 ∈ K može predstaviti na jedinstven način kao monom 1 = x10 ...xn0 , dakle
kao monom nultog multistepena 0= (0,......,0)
6
3. Monomijalni ideali
Neka je M α = x1α 1 ...xnα n monom u prstenu polinoma više promenljivih K[ x1 ,..., xn ] gde je
α = (α 1 ,..., α n ) ∈ N 0n multistepen. Tada koristimo kraći zapis xα = x1α ...xnα .
1
n
Za skup multistepenova A ⊆ N 0n skup monoma {xα : α ∈ A} odreñuje ideal generisan tim
skupom monoma I = xα : α ∈ A . Takav ideal se naziva monomijani ideal i on se može
odrediti kao skup konačnih suma :
I = { ∑ qα xα : qα ∈ K [ x1 ,..., xn ] ∧ α ∈ A0 ∧ A0 ∈ A}
α ∈ A0
Teorema 3.1 Neka su x1α1 ...xnα n
monomi u prstenu polinoma više promenljivih
K[ x1 ,..., xn ] sa meñusobno različitim stepenima. Tada je skup monoma {x1α1 ...xnα n }
linearno nezavistan skup.
Teorema 3.2 Neka je za skup multistepenova A ⊆ N 0n u prstenu polinoma više
I = xα : α ∈ A . Tada za
promenljivih K[ x1 ,..., xn ] odreñen monomijalni ideal
multistepen β = ( β1 ,..., β n ) ∈ N 0n važi x β ∈ I ako i samo ako (∃α ∈ A) xα | x β .
Teorema 3.3 Neka je skup multistepenova
A ⊆ N 0n u prstenu polinoma više
promenljivih K[ x1 ,..., xn ] odreñen monomijalni ideal I = xα : α ∈ A . Tada za polinom
m
P = ∑ bk x βk ∈ K [ x1,..., xn ](bk ∈ K \ {0} ∧ bk ∈ N 0n ) važi
k =1
m
∑ b xβ
k
k
∈ I ⇒ (∀k ) x βk ∈ I
k =1
Teorema 3.4 U prstenu polinoma više promenljivih K[ x1 ,..., xn ] dva monomijalna ideala
su jednaka ako i samo ako se sastoje od jednakih skupova monoma.
Definicija 3.5 Neka su data dva monoma xα i x β iz prstena polinoma više promenljivih
K[ x1 ,..., xn ]. Najveći zajednički delilac (GCD) prethodnih monoma je sledeći monom
xγ = GCD ( xα , x β ) , takav da je (∀k ∈{1,....n})γ k = min{α k , β k }
Definicija 3.6 Najmanji zajednički sadržalac prethodno posmatranih monoma je sledeći
monom xδ = LCM ( xα , x β ) , takav da je (∀k ∈ {1,....n})δ k = max{α k , β k }
7
Teorema 3.7 Neka su I = m1 ,..., mr i J = n1 ,..., ns dva monomijalna ideala u prstenu
polinoma više promenljivih K[ x1 ,..., xn ]. Tada važi:
a) I + J = m1 ,..., mr , n1 ,..., ns
r
s
b) I ∩ J = ∑∑ GCD (mi , n j )
i =1 j =1
c) I ⋅ J = m1n1 ,..., m1ns , m2n1 ,..., mr ns
s
d) I : J = I
j =1
m1
mr
,...,
LCM (m1 , n j )
LCM (mr , n j )
Teorema 3.8 Diksonova lema[1](Malešević,2000) Svaki monomijalni ideal I = xα : α ∈ A gde
je A ⊆ N 0n u prstenu polinoma više promenljivih K[ x1 ,..., xn ] je konačno generisan ideal.
4. Monomijalni poretci
Za neprazan skup S ≠ 0 relacija dužine n je neprazan podskup ρ ⊆ S n . Ukoliko je
relacija dužine n = 2 , tu relaciju nazivamo binarna relacija. Osobine relacija mogu biti:
a)
b)
c)
d)
Refleksivnost: (∀x ∈ S ) x ρ x
Simetričnost: (∀x, y ∈ S ) x ρ y ⇒ y ρ x
Antisimetričnost: (∀x, y ∈ S ) x ρ y ∧ y ρ x ⇒ x = y
Tranzitivnost: (∀x, y, z ∈ S ) x ρ y ∧ y ρ z ⇒ x ρ z
Definicija 4.1 Binarna relacija koja refleksivna, simetrična i tranzitivna se naziva relacija
ekvivalencije.
Definicija 4.2 Binarna relacija koja je refleksivna, antisimetrična i tranzitivna naziva se
relacija poretka.
Definicija 4.3 Binarna relacija je totalna ili linearna ako važi (∀x, y ∈ S ) x ρ y ∨ y ρ x
Definicija 4.4 Binarna relacija koja je totalna, antisimetrična i tranzitivna naziva se
relacijom totalnog poretka. Za relaciju totalnog poretka ρ nad skupom S uobičajeno je
da koristimo oznaku f , i tada je za svaka dva elementa x, y ∈ S moguće izvršiti
poreñenje elemenata xf y ili yfx
Defininicija 4.5 Element a ∈ A ⊆ S
(∀α ∈ A)(a f α ⇒ α = a)
je minimalni element skupa A ⊆ S ako važi
8
Definicija 4.6 Binarna relacija totalnog poretka nad skupom S je relacija dobrog ureñenja
ukoliko svaki neprazan podskup A ⊆ S ima minimalni element a = min( A) .
Definicija 4.7 Na skupu N 0n relacija f naziva se relacijom monomijalnog poretka ako
ispunjava sledeće uslova:
a) f je relacija totalnog poretka na N 0n
b) (∀α , β , γ ∈ N 0n )α fβ ⇒ α + γ fβ + γ
c) f je relacija dobrog ureñenja na N 0n
Lema 4.8 Dicksonova lema je ekvivalentna tvrñenju da u skupu monoma ne postoji
beskonačan opadajući niz monoma u odnosu na fiksirani monomijalni poredak f
Definicija 4.8 [1](Malešević,2000) Relacija leksikografskog poretka f lex na skupu N 0n uvodimo
na način koji sleduje. Za α , β ∈ N 0n smatramo da je α f lex β ako je u vektoru razlike
γ = α − β ∈ Z n prva nenulta pozicija sa leve strane pozitivna . Tada takoñe pišemo i
xα f lex x β , čime prenosimo relaciju f lex na skup monoma više promenljivih.
Teorema 4.9 Relacija leksikografskog poretka f lex je relacija monomijalnog poretka
Primer 4.10 U leksikografskom poretku važi:
a) x f lex y f lex z jer je (1,0,0) f lex (0,1,0) f lex (0,0,1)
b) xy 2 f lex y 3 z 4 jer je α = (1,2,0) f lex β = (0,3,4)(α − β = ( 1 ,−1,−4))
( >0 )
3
2
4
3
2
c) x y z f lex x y z jer je α = (3,2,4) f lex β = (3,2,1)(α − β = (0,0, 3 ))
(>0 )
Definicija 4.11 Relaciju obrnutog leksikografskog poretka f invlex na skupu N 0n uvodimo
na način koji sleduje. Za α , β ∈ N 0n smatramo da je α f invlex β ako je u vektoru razlike
γ = α − β ∈ Z n poslednja nenulta pozicija sa desne strane pozitivna. Tada takoñe pišemo
i xα f invlex x β , čime prenosimo relaciju f invlex na skup monoma više promenljivih.
Teorema 4.12 Relacija
monomijalnog poretka.
obrnutog
leksikografskog
poretka
f invlex
je
relacija
Primer 4.13 U obrnutom leksikografskom poretku važi:
a) z f invlex y f invlex x jer je (0,0,1) f invlex (0,1,0) f invlex (1,0,0)
b) y 3 z 4 f invlex xy 2 jer je α = (0,3,4) f invlex β = (1,2,0)(α − β = (−1,1, 4 ))
(> 0 )
5
3
3
2 1
c) x y z f invlex x y z jer je α = (5,3,1) f invlex β = (3,2,1)(α − β = (2, 1 ,0))
>0
9
Definicija 4.14 Relaciju gradiranog leksikografskog poretka f grlex na skupu N 0n
uvodimona način koji sledjuje. Za α , β ∈ N 0n smatramo da je α f grlex β ako je tačno
n
n
i =1
i =1
(| α |= ∑ α i >| β |= ∑ β i ) ∨ (| α |=| β | ∧α f lex β ) . Tada takoñe pišemo i xα f grlex x β ,
čime prenosimo relaciju f grlex na skup monoma više promenljivih.
Teorema 4.15 Relacija gradiranog leksikografskog poretka
monomijalnog poretka.
f grlex
je relacija
Primer 4.16 U gradiranom leksikografskom poretku važi:
a) x f grlex y f grlex z jer je (1,0,0) f grlex (0,1,0) f grlex (0,0,1)
b) y 3 z 4 f grlex xy 2 jer je α = (0,3,4) f grlex β = (1,2,0)(| α |= 7 > 3 =| β |)
c) x 3 y 4 z 2 f grlex x 3 y 2 z 4 jer je
α = (3,4,2) f grlex β = (3,2,4)(| α |= 9 =| β | ∧α − β = (0, 2 ,−2))
( >0 )
Definicija 4.17 Definišimo relaciju α f rinvlex β ako i samo ako β f invlexα ( sa uslovom da
je u vektoru razlike: γ = α − β ∈ Z n poslednja nenulta koordinata negativna). Relacija
f rinvlex nije relacija monomijalnog poretka i služi za definisanje gradiranog obrnutog
leksikografskog poretka. Za α , β ∈ N 0n smatramo da važi α f grevlex β ukoliko je tačna
n
n
disjunkcija (| α |= ∑ α i >| β |= ∑ β i ) ∨ (| α |=| β | ∧α f rinvlex β ) . Tada takoñe u skupu
i =1
i =1
monoma važi xα f grevlex x β
Teorema 4.18 Relacija obrnutog gradiranog leksikografskog poretka f grevlex je relacija
monomijalnog poretka.
Primer 4.19 U obrnuto gradiranom leksikografskom poretku važi:
a) z f grevlex y f grevlex x jer je (0,0,1) f grevlex (0,1,0) f grevlex (1,0,0)
b) y 3 z 4 f grevlex xy 2 jer je α = (0,3,4) f grlex β = (1,2,0)(| α |= 7 > 3 =| β |)
c) x 3 y 4 z 2 f grevlex x 3 y 2 z 4 jer je
α = (3,4,2) f grevlex β = (3,2,4)(| α |= 9 =| β | ∧α − β = (0,2, − 2))
(<0 )
Neka je fiksiran jedan monomijalni poredak f i neka je u prstenu polinoma više
m
pormenljivih K[ x1 ,..., xn ] dat polinom P = ∑ ck xα k
za neke monome xα k i neke
k =0
koeficijente ck ∈ K (k = 0,1,..., m) . Smatramo da je polinom P sreñen u datom
monomijalnom poretku P = cπ 0 xα π 0 + ... + cπ m x
απ m
ako za neku permutaciju π skupa
10
indeksa I m = {0,1,..., m} ispunjeno α π 0 f α π 1 f ... f α π m tj. ako su termovi polinoma P
zapisani u opadajućem poretku multistepena. Svaki polinom se može srediti u datom
poretku. Tada definišemo polinom P pojmove koji su vezani za sreñivanje polinoma u
datom monomijalnom poretki:
a) multistepen: MD( P ) = α π 0
b) vodeći koeficijent: LC ( P ) = cπ 0
c) vodeći monom: LM ( P ) = x
d) vodeći term: LT ( P ) = cπ 0 x
απ 0
απ 0
5. Deljenje u prstenu više promenljivih i redukcija polinoma
Teorema 5.1 Ideali u prstenu polinoma više promenljivih K[ x1 ,..., xn ] za n ≥ 2 u opštem
slučaju nisu generisani jednim elementom.
Algoritam deljenja
Input: f 1, . . . , f k, f
Output: a1, . . . , a k, r
a1 := 0, . . . , a k := 0, r := 0
p := f
WHILE p ≠ 0 DO
i := 1
divisionoccured := false
WHILE i ≤ k and divisionoccured = false DO
IF LT(f i) divides LT(p) THEN
a i:= a i + LT(p)/LT(f i)
p := p − LT(p)/LT(f i) · f i
divisionoccured := true
ELSE
i := i + 1
IF divisionoccured = false THEN
r := r + LT(p)
p := p − LT(p)
(STOP)
Teorema 5.2 Neka je data k-torka polinoma F = ( f1 ... f k ) gde su polinomi
f i ∈ K [ x1 ,..., xn ] svaki za sebe sreñeni u istom monomijalnom poretku f (i = 1,.., k ) . Tada
primenom gore navedenog algoritma deljenja svaki polinom f ∈ K [ x1 ,..., xn ] se može
zapisati na sledeći način f = a1 ⋅ f1 + ... + ak ⋅ f k + r za a i , r ∈ K [ x1 ,..., xn ](i = 1,.., k ) pri
čemu ili je r = 0 ili je r neka K- linearna kombinacija monoma od kojih ni jedan nije
deljiv sa ma kojim od vodećih monoma LT ( f1 ),..., LT ( f k ) pri datom monomijalnom
poretku f . Pri navedenim pretpostavkama važi (∀i ∈ {1,..., s}) LT ( f ) ≥ LT (ai f i )
11
Primer rada algoritma (leksikografski poredak)
Početne pripreme:
Ulaz: f=-x3z +xz + y2z –yz2
f1=x2z
f2=x -z2,
f3=y –z
a1=0
a2=0
a3=0
r= 0
p=f= -x3y +xz –yz
Korak 1:
lt(p)| lt(f1)
p=p-(-x3z)=xz –yz2
a1= a1+(-x)=-x
r=0
Korak 2:
lt(p)| lt(f2)
p=p-(-xz –z3)=y2z -yz2 +z3
a2= a2+(z)=z
r=0
Korak 3:
lt(p)| lt(f3)
p=p-(y2z –yz2)=z3
a3= a3+(yz)=yz
r=0
Korak 4:
lt(p)|{}
r=r +lt(p)=z3
p=p -lt(p)=0
Korak 5:
p=0
Algoritam završava sa izvršavanjem
a1=-x
a2=z
a3=yz
r= z3
Definicija 5.3 Polinom r=Rem(f,F) nazivamo ostatkom pri deljenju polinoma f sa ktorkom sreñenih polinoma F.
Napomena 5.4 Ostatak pri deljenju polinoma f sa k-torkom sreñenih polinoma F zavisi
od redosleda polinoma unutar F, i nije jedinstven.
12
Lema 5.5 Za polinom f i k-torku F = ( f1 ... f k ) sreñenih u istom monomijalnom poretku
f važi r=Rem(f,F)=0 ⇒ f ∈ { f1 ,..., f k }
Definicija 5.6 Za nenula polinome f, g i polinom fˆ iz K[ x1 ,..., xn ], sreñene u istom
monomijalnom poretku f , smatramo da se polinom f redukuje na polinom fˆ po modulu
polinoma g, u oznaci f → g fˆ ili f ≡ fˆ mod g ako postoji term h polinoma f takav da
h
važi: lt ( g ) | h ∧ fˆ = f −
⋅g
lt ( g )
Definicija 5.7 Neka je f polinom i neka je G = {g1 ,..., g k } skup polinoma u K[ x1 ,..., xn ]
sreñenih u istom monomijalnom poretku f . Polinom f se redukuje na polinom fˆ po
modulu skupa polinoma G, u oznaci f → G fˆ , ako postoji polinom g i ∈ G takav da
f → gi fˆ (pri tom je fˆ je sreñen u istom monomijalnom poretku f ). Smatramo da se
polinom f u potpunosti redukovao na polinom fˆ po modulu skupa polinoma G ako je
f → G fˆ → G fˆ . Navedeno označavamo f →*G fˆ .
Definicija 5.8 Polinom fˆ je normalna forma polinoma f po modulu skupa polinoma G
takav da f → fˆ . Normalnu formu polinoma označavamo fˆ = normalf ( f , G ) .
*G
Teorema 5.9 Neka je dat skup polinoma G = {g1 ,..., g k } u prstenu polinoma više
promenljivih K[ x1 ,..., xn ]. Tada za svaki polinom f ∈ K [ x1 ,..., xn ] normalna forma
h = normalf ( f , G ) odreñuje se u konačnom broju koraka. Pri tom se polazni polinom f
može zapisati na sledeći način f = a1 ⋅ g1 + ... + ak ⋅ g k + h za neke polinome
ai ∈ K [ x1 ,..., xn ](i = 1,..., k ) , pri čemu ili je h=0 ili je h neka K-linearna kombinacija
monoma od kojih ni jedan nije deljiv sa ma kojim od vodećih monoma lt ( g1 ),..., lt ( g k ) .
Pri tome važi (∀i ∈ {1,..., s})lf ( f )flt (ai f i ) .
Teorema 5.10 Neka je dat skup polinoma G = {g1 ,..., g k } u prstenu polinoma više
promenljivih K[ x1 ,..., xn ]. Polinom f ∈ K [ x1 ,..., xn ] se u potpunosti redukuje na nulu po
modulu skupa polinoma G ako i samo ako se polinom f može zapisati na sledeći način:
f = a1 ⋅ g1 + ... + ak ⋅ g k za neke polinome ai ∈ K [ x1 ,..., xn ](i = 1,..., k ) . Pri navedenim
pretpostavkama važi (∀i ∈ {1,..., s})lf ( f )flt (ai f i )
13
6. Hilbertova teorema o bazi
Definicija 6.1 Neka je I nenula ideal u prstenu polinoma više promenljivih K[ x1 ,..., xn ].
Tada skupom vodećih termova ideala lt ( I ) = {lt ( f ) | f ∈ I } generišemo ideal vodećih
termova lt ( I ) = {lt ( f ) | f ∈ I }
Teorema 6.2 Neka je I nenula ideal u K[ x1 ,..., xn ], tada važi:
a)
lt ( I ) jeste monomijalni ideal u K[ x1 ,..., xn ]
b) (∃g1 ,..., g s ∈ I ) lt ( I ) = {lt ( g1 ),..., lt ( g s )}
Teorema 6.3 Hilbertova teorema o bazi Svaki ideal I u prstenu polinoma više
promenljivih K[ x1 ,..., xn ] jeste konačno generisan ideal
Napomena 6.4 Na osnovu Hilbertove teoreme o bazi zaključujemo da je algebarska
struktura K[ x1 ,..., xn ] = ( K [ x1 ,..., xn ],+,⋅) Noetherin prsten.
7. Grebnerova baza
U razmatranju u ovom delu i narednim delovima koji se odnose na Grebnerove baze
smatraćemo da je dat fiksiran monomijalni poredak f .
Teorema 7.1 Neka je I = f1 ,..., f s
ideal u prstenu polinoma više promenljivih
K[ x1 ,..., xn ] tada važi {lt ( f1 ),..., lt ( f s )} ⊆ lt ( I )
Definicija 7.2 Konačan skup G = {g1 ,..., g k } u idealu I prstena polinoma više
promenljivih K[ x1 ,..., xn ] naziva se standardna Grebnerova baza ideala I ako važi
lt ( I ) = {lt ( g1 ),..., lt ( g s )}
Primer 7.3 Za polinome f 1 = xy + 1 i
f 2 = y 2 + 1 postoje polinomi g1 = f 2 = y 2 + 1 i
g 2 = x ⋅ f 2 − y ⋅ f 1 = xy 2 + x − xy 2 − y = x − y ,
takvi
da
I = {g 1 , g 2 }
i
da
{lt ( f 1 ), lt ( f 2 ) ⊆ {lt ( g 1 ), lt ( g 2 )
Napomena 7.4 Neka je G = {g1 ,..., g k } baza ideala I prstena više promenljivih
K[ x1 ,..., xn ] . Uslov da je normalna forma po modulu skupa G jedinstveno odreñena je
ekvivalentan sa uslovom da je G Grebnerova baza ideala I. Navedeni uslov je koristio B.
Buchberger pri definiciji standardne Grebnerove baze.
14
Teorema 7.5 Svaki ideal I u prstenu polinoma više promenljivih K[ x1 ,..., xn ] ima bar
jednu standardnu Grebnerovu bazu G koja jeste jedna baza za ideal I.
Teorema 7.6 Konačan skup G = {g1 ,..., g k } u idealu I prstena više promenljivih
K[ x1 ,..., xn ] jeste standardna Grebnerova baza ideala ako i samo ako za svako f ∈ I važi
(∃g i ∈ G )lt ( g i ) | lt ( f )
Teorema 7.7 Neka je G = {g1 ,..., g k } Grebnerova baza ideala I ⊆ K [ x1 ,..., xn ] . Tada za
svako f ∈ K [ x1 ,..., xn ] postoji jedinstveno odreñen r ∈ K [ x1 ,..., xn ] sa sledećim
pretpostavkama:
a) Ako je r ≠ 0 , tada nijedan monom koji se javlja u r kao sabirak nije deljiva sa
nekim od monoma lt ( g1 ),..., lt ( g s )
b) Postoji g ∈ I tako da f = g + r
Definicija 7.8 Neka je G = {g1 ,..., g s } Grebnerova baza ideala I ⊆ K [ x1 ,..., xn ] . Tada za
svako f ∈ K [ x1 ,..., xn ] jedinstveno odreñen polinom r iz prethodne teoreme nazivamo
ostatakom polinoma f u odnosu na Grebnereovu bazu G .
Teorema 7.9 Neka je G = { g 1 ,..., g s } baza ideala I prstena više promenljivih
K[ x1 ,..., xn ].
Uslov
da
za
svako
f ∈ K [ x1 ,..., xn ]
važi
ekvivalencija
f ∈ I ⇔ rem( f , ( g1 ,..., g s )) = 0
ideala I.
je ekvivalentan sa uslovom da je G Grebnerova baza
Teoreme 7.10 Svaka Grebnerova baza G = { g 1 ,..., g s } , u prstenu više
promenljivih K[ x1 ,..., xn ] jeste jedna baza za ideal I.
Teorema 7.11 Neka su G = {g1 ,..., g s } i G ′ = {g1′ ,..., g ′k } dve Grebnerove baze ideala
I ⊆ K [ x1 ,..., xn ]
u odnosu na isti monomijalni poredak
f ∈ K [ x1 ,..., xn ] važi rem( f , ( g1 ,..., g s )) = rem( f , ( g1′ ,..., g ′k ))
f . Tada za svako
Teorema 7.12 Sledeći uslovi su meñusobno ekvivalentni:
a) Skup G je grebnerova baza za ideal I ⊆ K [ x1 ,..., xn ]
f = a1 ⋅ g1 + ... + a s ⋅ g s za neke
b) Svako f ∈ I možemo zapisati u obliku
a1 ,..., as ∈ K [ x1 ,..., xn ] pri čemu (∀i ∈{1,..., s})lt ( f )flt (ai g i )
c) Svako f ∈ I se u potpunosti redukuje na 0 po modulu skupa G
Teorema 7.13 Neka je G = {g1 ,..., g s } Grebnerova baza ideala I prstena više
promenljivih K[ x1 ,..., xn ]. Smatramo da je G redukovana Grebnerova baza ako su
ispunjeni sledeći uslovi:
15
a) Skup {lt ( g1 ),..., lt ( g s )} odreñuje minimalni generatorski skup za lt ( I )
b) Vodeći termovi lt ( g i ) su monomični monomi, tj. lc ( g i ) = 1 , za svako
i ∈ {1,..., s}
c) Nijedan monom lm( g i ) nije deljiv ma kojim monomom koji se javlja kao sabirak
u generatoru g j = lm( g j ) + c j1 m j1 + ... + + c jk m jk ∈ G za i ≠ j (i, j ∈{1,..., s})
Teorema 7.14 Svaki nenula ideal I prstena više promenljivih K[ x1 ,..., xn ] ima
jedinstveno odreñenu redukovanu Grebnerovu bazu.
8. Sizidži niza polinoma i S-polinomi
Definicija 8.1 Neka je data k-torka polinoma F = ( f1 ,..., f k ) nad prstenom polinoma više
promenljivih K[ x1 ,..., xn ], tada k-torka polinoma S = (a1 ,..., ak ) polinoma nad prstenom
polinoma više promenljivih K[ x1 ,..., xn ] naziva se Sizidži k-torke polinoma F ako važi
a1 ⋅ f1 + ... + ak ⋅ f k = 0
Teorema 8.2 Neka je m1 ,..., mk niz monoma u prstenu polinoma više promenljivih
K[ x1 ,..., xn ]. Ako je S = syz (m1 ,..., mk ) , tada je S linearna kombinacija sizudžia oblika
nzs (mi , m j ) r nzs (m j , mi ) r
sij =
ei −
e j za 1 ≤ i < j ≤ k
mi
mj
Neka su f , g ∈ K [ x1 ,..., xn ] dva polinoma, S-polinom
nzs (lm( f ), lm( g ))
nzs (lm( f ), lm( g ))
za polinome f i g odreñen je sa S ( f , g ) =
⋅f −
⋅g
lt ( f )
lt ( g )
Primer računanja S-polinoma
2
2
f = ( x + yz − 2 z )
Definicija 8.3
[11.]
(Cox,Little,O’Shea,1997)
g = 3 xz 2 + y 3 − yz
nzs(f, g) = nzs(lm(f), lm(g)) = nzs ( x 2 , xz 2 ) = x 2 z 2
nzs (lm( f ), lm( g ))
nzs (lm( f ), lm( g ))
S( f , g) =
⋅f −
⋅g
lt ( f )
lt ( g )
x2 z2
x2 z 2
2
2
x
yz
z
⋅
(
+
−
2
)
−
⋅ (3 xz 2 + y 3 − yz )
2
2
x
3 xz
x
S ( f , g ) = z 2 ⋅ ( x 2 + yz 2 − 2 z ) − ⋅ (3 xz 2 + y 3 − yz )
3
xy 3 xyz
S ( f , g ) = x 2 z 2 + yz 4 − 2 z 3 − x 2 z 2 −
+
3
3
3
xy
xyz
S( f , g) = −
+
+ yz 4 − 2 z 3
3
3
S( f , g) =
16
Lema 8.4 Za polinome f , g ∈ K [ x1 ,..., xn ] važi lt ( f ⋅ g ) = lt ( f ) ⋅ lt ( g )
Lema
8.5
Za
polinome
f1 , f 2 , g1 , g 2 ∈ K [ x1 ,..., xn ]
neka
važe
uslovi
lt ( f1 g1 ) + lt ( f 21 g 2 ) = 0
i
nzs (lm( g1 ), lm( g 2 )) | nzs (lm( f1 ), lm( f 2 )) .
Neka
je
γ = md (lt ( f1 g1 )) = md (lt ( f 2 g 2 ))
i
δ = md (nzs (lm( g1 ), lm( g 2 ))) .
Tada
važo
lt ( f1 ) g1 + lt ( f 2 ) g 2 = c1 x γ 1 ⋅ S ( g1 , g 2 ) za neki koeficijent c1 ∈ K \ {0} i multistepen
γ 1 = γ − δ ∈ N 0n .
Lema
8.6
Za
svaka
nzs (lm( f ), lm( g )) f lt ( S ( f , g ))
dva
polinoma
f , g ∈ K [ x1 ,..., xn ]
važi
Teorema 8.7 Neka je da skup G = {g1 ,..., g s } koji generiše ideal I ⊆ K [ x1 ,..., xn ] . Ako
za svako g i , g j ∈ G S-polinomi S ( g i , g j ) ispunjavaju uslove S ( g i , g j ) = a1 g1 + ... + a s g s
i (∀k ∈ {1,..., s})lt ( S ( g i g j ))flt ( ak g k ) za neke polinome a1 ,..., as ∈ K [ x1 ,..., xn ] tada skup
G odreñuje Grebnerovu bazu.
Teorema
8.8
Skup
G = {g1 ,..., g s }
odreñuje
jednu
Grebnerovu
bazu
ideala
I = {g1 ,..., g s } u prstenu polinoma više promenljivih K[ x1 ,..., xn ] ako i samo ako važi
(∀g i , g j ∈ G ) S ( g i , g j ) ∈ I
9. Buchbergerov algoritam
Input:
Output:
Buchbergerov algoritam
Skup polinom F = ( f1 ,..., f k ) koji generiše ideal I
Skup G = ( g1 ,..., g s ) Grebnerova baza ideala I
G := F
M := {( f i , f j ) | f i , f j ∈ G ∧ f i = f j }
while ( M ≠ 0)do
(p,q):=a neki ureñeni par iz M
M := M \ {( p.q )}
S := S ( p, q )
h := normalf ( S , G )
if ( h ≠ 0)then
M := M ∪ {( g , h) | g ∈ G}
G := G ∪ {h}
endWhile
17
Teorema 9.1
[11.]
(Cox,Little,O’Shea,1997)
Neka je dat skup polinoma F = ( f1 ,..., f k ) gde su
polinomi f i ∈ K [ x1 ,..., xn ] svaki za sebe sreñeni u istom monomijalnom poretku
f (i = 1,..., k ) . Tada primenom Buchbergerovog algoritma od svako skupa polinoma
F = ( f1 ,..., f k ) dobijamo G = ( g1 ,..., g s ) koji odreñuje jednu Grebnerovu bazu ideala I.
Primer funkcionisanja Buchbergerovog algoritma
Ulazni polinomi: f1=-4x2 -9y2 +z
f2=4x2 -2x +9y2 -3y
M:={( f1, f2 )}
Korak 1:
p= f1
q= f2
M=M/{( f1, f2 )}
s=S(f1, f2)
x2
x2
2
2
⋅ −4 x − 9 y + z − 2 ⋅ 4 x 2 − 2 x + 9 y 2 − 3 y
s=
2
− 4x
4x
s= x /2 +3y/4 -z /4
h=normalf(s,G)
x/2 +3y/4 -z/4:( -4x2 -9y2 +z, 4x2 -2x +9y2 -3y)=(0,0)
rem = x /2 +3y/4 -z /4
h=x/2 +3y/4 -z/4
h≠0
f3=h
G = G ∪ { f 3}
M = M ∪ {( f1, f3 ), ( f2, f3 )}
Korak 2:
p= f1
q= f3
M=M/{( f1, f3 )}
s=S(f1, f3)
s= 3xy/2 - xz/2 -9y2/4 +z/4
h=normalf(s,G)
h= -9y2/2 +3yz/2 –z2/4 +z/4
h≠0
f4=h
G = G ∪ { f 4}
M = M ∪ {( f1, f4 ), ( f2, f4 ) , ( f3, f4 )}
18
Korak 3:
p= f2
q= f3
M=M/{( f2, f3 )}
s=S(f2, f3)
s= 3xy/2 -xz/2 +x/2 -9y2/4 +3y/4
h=normalf(s,G)
h= 0
Korak 4:
p= f1
q= f4
M=M/{( f1, f4 )}
s=S(f1, f4)
s= -x2yz/3 + x2z2/18 - x2z/18 -9y4/4 + y2z/4
h=normalf(s,G)
h= 0
Korak 5:
p= f2
q= f4
M=M/{( f2, f4 )}
s=S(f2, f4)
s= - x^2yz/3 +x2z2/18 - x2z/18 + xy2/2 -9 y4/4 +3 y3/4
h=normalf(s,G)
h= 0
Korak 6:
p= f3
q= f4
M=M/{( f3, f4 )}
s=S(f3, f4)
s= -xyz/3 + xz2/18 -xz/18 -3y3/2 + y2z/2
h=normalf(s,G)
h= 0
Grebnerova baza: f1=-4x2 -9y2 +z
f2=4x2 -2x +9y2 -3y
f3=x/2 +3y/4 -z/4
f4=-9y2/2 +3yz/2 –z2/4 +z/4
19
10. Algoritam redukcije baze
Teorema 10.1 Neka je G jedna Grebnerova baza ideala I ⊆ K [ x1 ,..., xn ] . Ako postoji
element p ∈ G takav da lt ( p ) ∈ lt (G \ { p})
Grebnerova baza.
tada je
G \ { p} generatorski skup i
Definicija 10.2 Grebnerova baza ideala I ⊆ K [ x1 ,..., xn ] jeste minimalna Grebnerova
baza ideala I ako važi:
a) (∀p ∈ G )lc ( p ) = 1
b) (∀p ∈ G )lt ( p ) ∉ lt (G \ { p})
Teorema 10.3 Grebnerova baza G ideala I ⊆ K [ x1 ,..., xn ] jeste minimalna Grebnerova
baza ako i samo ako važi:
a) (∀p ∈ G )lc ( p ) = 1
b) lt (G ) jeste minimalna baza monomijalnog ideala lt ( I )
Definicija 10.4 [11.](Cox,Little,O’Shea,1997) Grebnerova baza G ideala I ⊆ K [ x1 ,..., xn ] jeste
redukovana Grebnerova baza ako važi:
a) (∀p ∈ G )lc ( p ) = 1
b) Za svako p ∈ G ne postoji monom xα polinoma p tako da xα ∈ lt (G \ { p})
Algoritam redukcije Grebnerove baze
Input:
G = {g1 ,..., g s } - Grebnerova baza
Output: Gˆ = {gˆ1 ,..., gˆ k } - Redukovana Grebnerova baza
Gˆ := G
for all g ∈ Gˆ do
if (∃µ ∈ Gˆ | µ ≠ g )lt ( µ ) | lt ( g ) then
Gˆ := Gˆ \ {g}
else
g := rem( g , Gˆ \ {g})
for all g ∈ Gˆ do
g
g :=
lc( g )
Teorema 10.5 Neka je data Grebnerova baza ideala I ⊆ K [ x1 ,..., xn ] u odnosu na
fiksirani monomijalni poredak f . Primenom algoritma redukcije baze od svake
Grebnerove baze dobijamo redukovanu Grebnerovu bazu.
20
Teorema 10.6 Redukovana Grebnerova baza je jedinstvena i predstavlja specijalan slučaj
minimalne Grebnerove baze nenula ideala I.
Primer funkcionisanja algoritma redukcije Grebnerove baze
Grebnerova baza: f1=-4x2 -9y2 +z
f2=4x2 -2x +9y2 -3y
f3=x/2 +3y/4 -z/4
f4=-9y2/2 +3yz/2 –z2/4 +z/4
Korak 1:
p= f1=-4x2 -9y2 +z
lt(p)= -4x2
{ 4x2, x/2 }|lt(p)
Gˆ := G \ { f1}
Korak 2:
p= f2=4x2 -2x +9y2 -3y
lt(p)= 4x2
{ x/2 }|lt(p)
Gˆ := G \ { f 2 }
Korak 3:
p= f3= x/2 +3y/4 -z/4
lt(p)= x/2
{ }|lt(p)
p=rem(p,G)
p=x/2 +3y/4 -z/4
Korak 4:
p= f4= -9y2/2 +3yz/2 –z2/4 +z/4
lt(p)= x/2
{ }|lt(p)
p=rem(p,G)
p=-9 y2/2 +3yz/2 –z2/4 +z/4
Redukovana Grebnerova baza:
f1= x/2 +3y/4 -z/4
f2= -9 y2/2 +3yz/2 –z2/4 +z/4
21
11. Algoritam za pronalaženje planarnih preseka polinoma
Definicija 11.1 [5.](Malešević,Obradović ,2009) Ukoliko je dat sistem dve nelinearne polinomijalne
jednačine f1 ( x, y, z ) = 0 ∧ f 2 ( x, y, z ) = 0 , sistem ima planarno rešenje ako postoji linearan
polinom g = g ( x, y , z ) = Ax + By + Cz + D takvo da svako rešenje sistema je takoñe
rešenje linearne jednačine g ( x, y , z ) = 0 za neke realne promenljive A,B,C i D.
Teorema 11.2 Ukoliko Grebnerova baza sadrži linearan polinom, onda je rešenje sistema
planarno.
Teorema 11.3 Sistem ima planarni presek Ax + By + Cz + D = 0 za neke A, B, C , D ∈ R i
A ≠ 0 . Ukoliko za ideal I = f1 , f 2 je istinito y ∉ lt ( I ) ∧ z ∉ lt ( I ) onda linearni
gˆ = gˆ ( x, y , z ) = x + ( B / A) y + (C / A) z + ( D / A) je element redukovane
polinom
Grebnerove Baze
Teorema 11.4 [5.](Malešević,Jovovoić,Čampara,2010) Ako za ideal I = f1 , f 2 postoji generator h u
Buchbergerovom algoritmu koji je linearan, ili primenom algoritma redukcije pronañemo
redukovani algoritam hp koji je linearan, onda sistem ima planaran presek
Napomenat 11.5 Pomenuta tvrñenja su dokazana samo na leksikografskom
monomijalnom poretku, a nisu još dokazana na sistemima sa više od tri promenljive i u
drugim monomijalnim poretcima
Ulazni polinomi :
Primer utvrñivanja planarnog preseka
f1 = x + yz + y − z 4 − 4
f2 = y − z3 − 1
Korak 1:
GB = buchberger ( f1 , f 2 )
GB = {x + yz + y − z 4 − 4, y − z 3 − 1}
Nijedan polinom u GB nije linearan.
Vrši se redukcija GB
Korak 2:
Vrši se redukcija nad polinomom p = x + yz + y − z 4 − 4
Parcijalna redukcija
p = x + yz + y − z 4 − 4
f2 = y − z3 − 1
lt2=y
Korak 1:
t=x
lt1 ne deli t
22
Korak 2:
t=yz
lt1 | t
t / lt1 = z
p=p - z*f2
p=(x + yz + y –z4 -4) – (yz – z4 - z) =x + y + z – 4
p je planaran polinom
p′ = x + y + z – 4
Otkriven planarni presek p′ .
Izvršavanje algoritma se zaustavlja
23
Literatura
[1.] Profesor Branko Malešević , Materijali za nastavu iz predmeta Simbolička
aglebra, Elektrotehnički fakultet u Beogradu
[2.] A. Heck: Bird's-eye view of Gröbner Bases, Nuclear Inst. and Methods in Physics
Research A 389 (1997), 16-21
[3.] K. Forsman: Hitchhiker guide to Gröbner bases, Research Institute for Symbolic
Computation, Linz, Technical Report 0374(1992).
[4.] B. Malešević, M. Obradović: An Application of Groebner Basest to Planarity of
Intersection of Surfaces, Filomat 23:2 (2009), pp. 43-55. (Thompson SCIE list
2009.)
[5.] B. Malešević, I. Jovović, M. Čampara: Groebner bases in JAVA with applications
in computer graphics, Proceedings of 2-nd International Conference for Geometry
and Engineering Graphics “moNGeometrija 2010”, Paper No. 29, pp. 1-10, June
2010, Belgade.
[6.] B. Malešević, I. Jovović, M. Makragić, B. Banjac, V. Katić, A. Jovanović, A.
Pejović:
Buchberger-ov algoritam i vizuelizacija monomijalnih ideala,
konferencija „Matematika i promene”, Prirodno matematički fakultet, maj 2011,
Beograd
[7.] D. Cox, J. Little, D. O’Shea : Ideals,Varieties and Algorithms, Springer, New
York, 1997
[8.] Ralf Frooberg: An Introduction to Groobner bases, John Wiley & Sons Ltd., 1997
24
Download

Teorija Grebner