Polinom liber de pătrate
În matematică un polinom liber de pătrate este un polinom definit peste un corp (sau, mai general, un domeniu de integritate) care nu are ca divizor vreun pătrat al unui polinom neconstant.[1] Un polinom de o singură variabilă este liber de pătrate dacă și numai dacă nu are vreo rădăcină multiplă într-un corp algebric închis care conține coeficienții săi.
În cazul polinoamelor de o singură variabilă regula produsului(d) implică că, dacă p2 divide f, atunci p divide derivata f ' a lui f. Inversa este și ea valabilă în caracteristica zero și pentru polinoame peste un corp finit (sau, mai general, peste un corp perfect). Adică, în aceste cazuri, un polinom este liber de pătrate dacă și numai dacă 1 este cel mai mare divizor comun (cmmdc) al polinomului și al derivatei sale.
Descriere
modificareO descompunere liberă de pătrate sau factorizare liberă de pătrate a unui polinom este o factorizare după puteri prin polinoame libere de pătrate
unde cele ak care sunt neconstante sunt polinoame coprime în perechi.[1] Fiecare polinom nenul admite o factorizare liberă de pătrate, care este unică până la înmulțirea și împărțirea factorilor cu constante nenule. Factorizarea liberă de pătrate este mult mai ușor de calculat decât factorizarea completă în factori ireductibili(d), prin urmare este adesea preferată atunci când factorizarea completă nu este cu adevărat necesară, ca și pentru descompunerea în fracții simple și obținerea integralelor nedefinite ale fracțiilor raționale. Factorizarea liberă de pătrate este primul pas al algoritmilor de factorizare ai polinoamelor care sunt implementați în programele de calcul simbolic. Prin urmare, algoritmul de factorizare liberă de pătrate este unul de bază în calculul formal(d).
Peste un corp cu caracteristica 0, câtul lui f prin cmmdc al său cu derivata sa este produsul ai din descompunerea liberă de pătrate de mai sus. Peste un corp perfect cu caracteristică diferită de zero p, acest cât este produsul ai astfel încât i nu este un multiplu al lui p. Alte calcule despre cmmdc și divizările exacte permit calcularea factorizării libere de pătrată. Pentru caracteristica zero, este cunoscut un algoritm mai bun, algoritmul lui Yun, care este descris mai jos.[1] Complexitatea sa de calcul(d) este cel mult de două ori mai mare decât calculul cmmdc al polinomului de intrare și al derivatei sale. Mai precis, dacă Tn este timpul necesar pentru a calcula cmmdc al două polinoame de gradul n și câtul acestor polinoame prin cmmdc, atunci 2Tn este o limită superioară pentru timpul necesar pentru a calcula descompunerea liberă de pătrate.
De asemenea, există algoritmi cunoscuți pentru calcularea descompunerii liberă de pătrate a polinoamelor de mai multe variabile, care lucrează în general prin considerarea unui polinom de mai multe variabile ca fiind un polinom de o singură variabilă cu coeficienți polinomiali și aplicând recursiv un algoritm pentru o singură variabilă.[2]
Algoritmul lui Yun
modificareAceastă secțiune descrie algoritmul lui Yun pentru descompunerea liberă de pătrate a polinoamelor de o singură variabilă peste un corp cu caracteristica 0.[1] Se procedează printr-o succesiune de calcule ale cmmdc și împărțiri exacte.
Intrarea este un polinom diferit de zero, f, iar primul pas al algoritmului constă în calcularea cmmdc a0 al lui f și al derivatei sale f '.
Dacă
este factorizarea dorită, atunci
și
Dacă se pune , și , se obține
și
Iterând până la se obțin toți
Acest lucru este formalizat într-un algoritm după cum urmează:
- repetă
- până când
- Rezultatul
Gradul lui ci și di este cu unu mai mic decât gradul lui bi. Deoarece f este produsul bi, suma gradelor bi este gradul lui f. Pe măsură ce complexitatea calculelor și împărțirilor cu cmmdc crește mai mult decât liniar cu gradul, rezultă că timpul total de rulare al buclei de „repetare” este mai mic decât timpul de rulare al primei linii a algoritmului și că timpul total de rulare al algoritmului lui Yun este limitat superior de dublul timpului necesar pentru a calcula cmmdc al f și f ' și câtul lui f și f ' prin cmmdc al lor.
Rădăcina pătrată
modificareÎn general, un polinom nu are rădăcină pătrată. Mai precis, majoritatea polinoamelor nu pot fi scrise ca pătratul altui polinom.
Un polinom are rădăcină pătrată dacă și numai dacă toți exponenții descompunerii libere de pătrate sunt pari. În acest caz, rădăcina pătrată se obține împărțind la 2 acești exponenți.
Astfel, problema de a decide dacă un polinom are rădăcină pătrată și de a calcula dacă aceasta există, este un caz particular de factorizare liberă de pătrate.
Note
modificare- ^ a b c d en Yun, David Y.Y. (). „On square-free decomposition algorithms”. SYMSAC '76 Proceedings of the third ACM symposium on Symbolic and algebraic computation. Association for Computing Machinery. pp. 26–35. doi:10.1145/800205.806320. ISBN 978-1-4503-7790-4.
- ^ en Gianni, P.; Trager, B. (). „Square-Free Algorithms in Positive Characteristic”. Applicable Algebra in Engineering, Communication and Computing. 7 (1): 1–14. doi:10.1007/BF01613611.