În algebră un sistem de ecuații polinomialeLiviu Nicolaescu, O introducere în teoria mecanismelor, Gazeta Matematică: Seria A, anul XXVII (CVI), nr. 1/2009, p. 5 este o mulțimeî de ecuații simultane unde sunt polinoame de mai multe variabile, de exemplu , peste un anumit corp .
O soluție a unui sistem de ecuații polinomiale este o mulțime de valori pentru care aparțin unei extinderi de corp algebric închisă a numerelor complexe și care satisfac toate ecuațiile. Când este corpul numerelor raționale, se presupune în general că este corpul numerelor complexe, deoarece fiecare soluție aparține unei extinderi de corp a lui , care este izomorfă cu un subcorp al numerelor complexe.
Acest articol se referă la metodele de rezolvare, adică la obținerea tuturor soluțiilor sau la descrierea lor. Deoarece aceste metode sunt concepute pentru a fi implementate într-un computer, accentul este pus pe corpurile în care calculul (inclusiv testarea egalității) este ușor și eficient, adică corpul numerelor raționale și al corpurilor finite.
Căutarea soluțiilor care aparțin unei mulțimi specifice este o problemă în general mult mai dificilă și este în afara domeniului acestui articol, cu excepția cazului soluțiilor dintr-un anumit corp finit. Pentru cazul soluțiilor ale căror componente sunt numere întregi sau raționale, a se vedea .
Definiție thumb|Numeroasele puncte singulare ale sexticei lui Barth sunt soluții ale unui sistem de ecuații polinomiale Un exemplu simplu de sistem de ecuații polinomiale este:
Soluțiile sale sunt cele patru perechi . Aceste soluții pot fi ușor verificate prin substituție, dar este mai dificil de demonstrat că nu există și alte soluții.
Subiectul acestui articol este studiul generalizărilor unor astfel de exemple și descrierea metodelor utilizate pentru calcularea soluțiilor.
Un sistem de ecuații polinomiale este o colecție de ecuații:
unde fiecare este un polinom cu variabilele nedeterminate , cu coeficienți întregi sau coeficienți într-un corp fix, adesea corpul numerelor raționale sau un corp finit. Alte corpuri de coeficienți, cum ar fi cel al numerelor reale, sunt mai rar utilizate, deoarece elementele lor nu pot fi reprezentate într-un calculator (în calcule pot fi utilizate doar aproximări ale numerelor reale, iar aceste aproximări sunt întotdeauna numere raționale).
O „soluție” a unui sistem de ecuații polinomiale este un tuplu de valori ale lui care satisface toate ecuațiile sistemului. Soluțiile sunt căutate în numerele complexe sau, mai general, într-un corp algebric închis care conține coeficienții. În special, în caracteristica zero sunt căutate toate soluțiile complexe. Căutarea soluțiilor reale sau raționale sunt probleme mult mai dificile, care nu sunt tratate în acest articol.
Mulțimea soluțiilor nu este întotdeauna finită; de exemplu, soluțiile sistemului
sunt un punctul și dreapta . Chiar și atunci când mulțimea soluțiilor este finită, în general, nu există o a soluțiilor (în cazul unei singure ecuații, aceasta este teorema Abel-Ruffini).
, prezentată în figură, este reprezentarea geometrică a soluțiilor unui sistem de ecuații polinomiale redus la o singură ecuație de gradul 6 în 3 variabile. Unele dintre numeroasele sale puncte singulare sunt vizibile în imagine. Acestea sunt soluțiile unui sistem de 4 ecuații de gradul 5 în 3 variabile. Un astfel de sistem nu are o soluție în general (adică dacă coeficienții nu sunt anume). Dacă are un număr finit de soluții, atunci, conform teoremei lui Bézout, acest număr este cel mult . Totuși, s-a demonstrat că pentru cazul punctelor singulare ale unei suprafețe de gradul 6 numărul maxim de soluții este 65 și este atins de suprafața Barth.
Proprietăți fundamentale și definiții Un sistem este supradeterminat dacă numărul de ecuații este mai mare decât numărul de variabile. Un sistem este inconsistent dacă nu are o soluție în corpul numerelor complexe (sau, dacă coeficienții nu sunt numere complexe, nicio soluție într-un corp algebric închis care conține coeficienții). Prin aceasta înseamnă că 1 este o combinație liniară (cu polinoame drept coeficienți) a primilor membri ai ecuațiilor. Majoritatea, dar nu toate sistemele supradeterminate, atunci când sunt construite cu coeficienți oarecare, sunt inconsistente. De exemplu, sistemul este supradeterminat (având două ecuații, dar doar o necunoscută), dar nu este inconsistent deoarece are soluția .
Un sistem este dacă numărul de ecuații este mai mic decât numărul de variabile. Un sistem nedeterminat este fie inconsistent, fie are un număr infinit de soluții complexe (sau soluții într-un corp algebric închis care conține coeficienții ecuațiilor). Acesta este un rezultat netrivial al algebrei comutative care implică, în special, teorema zerourilor a lui Hilbert și .
Un sistem este zerodimensional dacă are un număr finit de soluții complexe (sau soluții într-un câmp algebric închis). Această terminologie provine din faptul că a soluțiilor are zero. Un sistem cu un număr infinit de soluții este pozitiv dimensional.
Un sistem zero dimensional cu tot atâtea ecuații câte variabile este uneori considerat a avea o comportare bună. Songxin Liang, J. Gerhard, D.J. Jeffrey, G. Moroz, A Package for Solving Parametric Polynomial Systems. Communications in Computer Algebra (2009) Teorema lui Bézout afirmă că un sistem cu comportare bună ale cărui ecuații au gradele are cel mult soluții. Această limită este precisă. Dacă toate gradele sunt egale cu , această limită devine și este exponențială în numărul de variabile. (Teorema fundamentală a algebrei este cazul particular .)
Acest comportament exponențial face dificilă rezolvarea sistemelor polinomiale și explică de ce există puține programe de rezolvare care sunt capabile să rezolve automat sisteme cu limita lui Bézout mai mare decât, să zicem, 25 (trei ecuații de gradul 3 sau cinci ecuații de gradul 2 depășesc această limită).
Cum se rezolvă? Primul lucru de făcut pentru rezolvarea unui sistem de ecuații polinomiale este stabilirea dacă este inconsistent, zerodimensional sau pozitiv dimensional. Acest lucru se poate face prin calcularea unei a membrilor stângi ai ecuațiilor. Sistemul este inconsistent dacă această bază Gröbner este redusă la 1. Sistemul este zerodimensional dacă pentru fiecare variabilă există un monom principal al unui element al bazei Gröbner care este o putere pură a acestei variabile. Pentru acest test, cea mai bună (adică cea care duce, în general, la cel mai rapid calcul) este de obicei ordinea lexicografică inversă gradată (grevlex).
Dacă sistemul este pozitiv dimensional, are o infinitate de soluții. Prin urmare nu este posibil fie enumerate. Rezultă că în acest caz rezolvarea poate însemna doar „găsirea unei descrieri a soluțiilor din care proprietățile relevante ale soluțiilor sunt ușor de extras”. Nu există o astfel de descriere acceptată în general. De fapt, există multe „proprietăți relevante” diferite, din aproape fiecare subdomeniu al geometriei algebrice.
Un exemplu natural al unei astfel de întrebări privind sistemele pozitiv dimensionale este următorul: stabilirea dacă un sistem de ecuații polinomiale peste numerele raționale are un număr finit de soluții reale și calculul lor. O generalizare a acestei întrebări este obținerea a cel puțin a unei soluții în fiecare componentă conexă a mulțimii de soluții reale ale unui sistem de ecuații polinomiale. Algoritmul clasic pentru rezolvarea acestor întrebări este , care are o , prin urmare, cu excepția unor exemple foarte mici, nu poate fi utilizată în practică.
Pentru sistemele zerodimensionale, rezolvarea constă în calcularea tuturor soluțiilor. Există două moduri diferite de obținere a soluțiilor. Metoda obișnuită este posibilă doar pentru soluții reale sau complexe și constă în obținerea aproximărilor numerice ale soluțiilor. O astfel de soluție se spune că este numerică. O soluție este certificată dacă are o limită pentru eroarea aproximărilor și dacă această limită separă diferitele soluții.
Cealaltă posibilitate de reprezentare a soluțiilor este cea algebrică. Aceasta folosește faptul că pentru un sistem zero-dimensional soluțiile aparțin închiderii algebrice a corpului k al coeficienților sistemului. Există mai multe modalități de a reprezenta soluția într-o închidere algebrică, care sunt discutate mai jos. Toate permit calcularea unei aproximări numerice a soluțiilor prin rezolvarea uneia sau mai multor ecuații pentru o singură variabilă. Pentru acest calcul, este de preferat să se utilizeze o reprezentare care implică rezolvarea unui singur polinom cu o variabilă per soluție, deoarece calcularea rădăcinilor unui polinom care are coeficienții aproximați este o problemă extrem de instabilă.
Dezvoltări particulare Ecuații trigonometrice O ecuație trigonometrică este o ecuație unde este un . O astfel de ecuație poate fi transformată într-un sistem de ecuații polinomiale prin dezvoltarea sinusurilor și cosinusurilor din ea (folosind formule de sumă și diferență a unghiurilor), înlocuind și cu două variabile noi și și adăugând noua ecuație
De exemplu, deoarece există identitatea
rezolvarea ecuației
este echivalentă cu rezolvarea sistemului de ecuații polinomiale:
Pentru fiecare soluție a sistemului există o soluție unică a ecuației astfel încât
În cazul acestui exemplu simplu poate fi neclar dacă sistemul este sau nu mai ușor de rezolvat decât ecuația. În exemplele mai complicate lipsesc metode sistematice pentru rezolvarea directă a ecuației, însă există software disponibil pentru rezolvarea automată a sistemului corespunzător.
Soluții într-un corp finit Când se rezolvă un sistem peste un corp finit cu elemente , interesul principal este reprezentat de soluțiile din . Deoarece elementele lui sunt chiar soluțiile ecuației , pentru a restricționa soluțiile la este suficient să se adauge ecuația pentru fiecare variabilă
Coeficienți într-un corp de numere sau într-un corp finit de ordin care nu este prim Elementele unui sunt de obicei reprezentate ca polinoame într-un generator al corpului care satisface o anumită ecuație polinomială de o singură variabilă. Pentru a lucra cu un sistem de ecuații polinomiale ai cărui coeficienți aparțin unui corp de numere, este suficient să se considere acest generator ca o variabilă nouă și să se adauge ecuația generatorului la ecuațiile sistemului. Astfel, rezolvarea unui sistem de ecuații polinomiale peste un corp de numere se reduce la rezolvarea unui alt sistem peste numere raționale.
De exemplu, dacă un sistem conține un sistem peste numerele raționale se obține prin adăugarea ecuației și înlocuirea cu în celelalte ecuații.
În cazul unui corp finit, aceeași transformare permite întotdeauna presupunerea că corpul este de ordin prim.
Reprezentarea algebrică a soluțiilor Lanțuri canonice Modul obișnuit de reprezentare a soluțiilor este prin zerodimensionale. Un astfel de lanț constă dintr-un șir de polinoame , , ... , astfel încât pentru fiecare astfel încât : este un polinom doar în , de gradul în ; coeficientul lui din este un polinom în care nu are niciun zero comun cu , ... ,
Unui astfel de lanț canonic îi este asociat un sistem triunghiular de ecuații:
Soluțiile acestui sistem se obțin prin rezolvarea primei ecuații de o singură variabilă, substituirea soluțiilor în celelalte ecuații, apoi rezolvarea celei de-a doua ecuații, care este acum de o singură variabilă ș.a.m.d. Definiția lanțurilor canonice implică faptul că ecuația de o singură variabilă obținută din are gradul , prin urmare sistemul are soluții, cu condiția să nu existe o rădăcină multiplă în acest proces de rezolvare (teorema fundamentală a algebrei).
Fiecare sistem zerodimensional de ecuații polinomiale este echivalent (adică are aceleași soluții) cu un număr finit de lanțuri canonice. Pot fi necesare mai multe lanțuri canonice, așa cum este cazul următorului sistem, care are trei soluții.