Polynomiální největší společný dělitel - Polynomial greatest common divisor

tento článek potřebuje další citace pro ověření. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: "Polynomiální největší společný dělitel"  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Září 2012) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

V algebře je největší společný dělitel (často zkráceně GCD) dvou polynomy je polynom, nejvyššího možného stupně, tj. a faktor obou původních polynomů. Tento koncept je obdobou největší společný dělitel dvou celých čísel.

V důležitém případě univariate polynomy nad a pole polynomiální GCD může být vypočítán, stejně jako pro celé číslo GCD, pomocí Euklidovský algoritmus použitím dlouhé rozdělení. Polynomiální GCD je definován pouze až do násobení invertibilní konstantou.

Podobnost mezi celočíselným GCD a polynomiálním GCD umožňuje rozšířit k univariaci polynomů všechny vlastnosti, které lze odvodit z euklidovského algoritmu a Euklidovské dělení. Polynomiální GCD má navíc specifické vlastnosti, díky nimž je základním pojmem v různých oblastech algebry. Typicky kořeny GCD dvou polynomů jsou společné kořeny dvou polynomů, a to poskytuje informace o kořenech bez jejich výpočtu. Například více kořenů polynomu jsou kořeny GCD polynomu a jeho derivátu a další výpočty GCD umožňují výpočet faktorizace bez čtverců polynomu, který poskytuje polynomy, jejichž kořeny jsou kořeny daného multiplicita původního polynomu.

Největší společný dělitel může být definován a existuje obecněji pro vícerozměrné polynomy přes pole nebo kruh celých čísel a také přes a jedinečná faktorizační doména. Existují algoritmy pro jejich výpočet, jakmile má jeden algoritmus GCD v kruhu koeficientů. Tyto algoritmy pokračují a rekurze o počtu proměnných ke snížení problému na variantu euklidovského algoritmu. Jsou základním nástrojem v počítačová algebra, protože systémy počítačové algebry systematicky je používejte ke zjednodušení zlomků. Naopak, většina moderní teorie polynomiální GCD byla vyvinuta, aby uspokojila potřebu účinnosti systémů počítačové algebry.

Obecná definice

Nechat p a q být polynomy s koeficienty v integrální doména F, typicky a pole nebo celá čísla. A největší společný dělitel z p a q je polynom d který rozděluje p a q, a takové, že každý společný dělitel p a q také rozděluje d. Každý pár polynomů (ne oba nula) má GCD právě tehdy F je jedinečná faktorizační doména.

Li F je pole a p a q nejsou oba nula, polynom d je největší společný dělitel právě tehdy, když rozděluje oba p a q, a má největší stupeň mezi polynomy, které mají tuto vlastnost. Li p = q = 0, GCD je 0. Někteří autoři se však domnívají, že v tomto případě není definována.

Největší společný dělitel p a q je obvykle označeno "gcd (p, q)".

Největší společný dělitel není jedinečný: pokud d je GCD z p a q, potom polynom F je další GCD právě tehdy, když existuje invertibilní prvek u z F takhle

${displaystyle f = ud}$

a

${displaystyle d = u ^ {- 1} f}$.

Jinými slovy, GCD je jedinečný až do násobení invertibilní konstantou.

V případě celých čísel byla tato neurčitost vyřešena výběrem, jako GCD, jedinečného pozitivního (existuje další, který je jeho opakem). S touto konvencí je GCD dvou celých čísel také největším (pro obvyklé řazení) společným dělitelem. Protože však neexistuje žádný přirozený celková objednávka pro polynomy nad integrální doménou zde nelze postupovat stejným způsobem. Pro univariate polynomy nad polem, lze navíc požadovat, aby byl GCD monic (to znamená mít 1 jako jeho koeficient nejvyššího stupně), ale v obecnějších případech neexistuje žádná obecná konvence. Rovnosti proto mají rádi d = gcd (p, q) nebo gcd (p, q) = gcd (r, s) jsou běžná zneužití notace, která by měla být přečtena "d je GCD z p a q" a "p a q mít stejnou sadu GCD jako r a s". Zejména, gcd (p, q) = 1 znamená, že invertibilní konstanty jsou jedinými společnými děliteli. V tomto případě to analogicky s celočíselným případem říká jeden p a q jsou coprime polynomy.

Vlastnosti

• Jak je uvedeno výše, GCD dvou polynomů existuje, pokud koeficienty patří buď do pole, do kruhu celých čísel, nebo obecněji do jedinečná faktorizační doména.
• Li C je jakýkoli společný dělitel p a q, pak C rozděluje jejich GCD.
• ${displaystyle gcd (p, q) = gcd (q, p).}$
• ${displaystyle gcd (p, q) = gcd (q, p + rq)}$ pro libovolný polynom r. Tato vlastnost je základem důkazu euklidovského algoritmu.
• Pro jakýkoli invertibilní prvek k prstence koeficientů, ${displaystyle gcd (p, q) = gcd (p, kq)}$.
• Proto ${displaystyle gcd (p, q) = gcd (a_ {1} p + b_ {1} q, a_ {2} p + b_ {2} q)}$ pro všechny skaláry ${displaystyle a_ {1}, b_ {1}, a_ {2}, b_ {2}}$ takhle ${displaystyle a_ {1} b_ {2} -a_ {2} b_ {1}}$ je invertibilní.
• Li ${displaystyle gcd (p, r) = 1}$, pak ${displaystyle gcd (p, q) = gcd (p, qr)}$.
• Li ${displaystyle gcd (q, r) = 1}$, pak ${displaystyle gcd (p, qr) = gcd (p, q), gcd (p, r)}$.
• Pro dva univariate polynomy p a q nad polem existují polynomy A a A, takový, že ${displaystyle gcd (p, q) = ap + bq}$ a ${displaystyle gcd (p, q)}$ rozděluje každou takovou lineární kombinaci p a q (Bézoutova identita ).
• Největší společný dělitel tří nebo více polynomů lze definovat podobně jako u dvou polynomů. To může být vypočítáno rekurzivně z GCD dvou polynomů podle identit:

${displaystyle gcd (p, q, r) = gcd (p, gcd (q, r)),}$

a

${displaystyle gcd (p_ {1}, p_ {2}, tečky, p_ {n}) = gcd (p_ {1}, gcd (p_ {2}, tečky, p_ {n})).}$

GCD ručním výpočtem

Existuje několik způsobů, jak najít největšího společného dělitele dvou polynomů. Dva z nich jsou:

1. Faktorizace polynomů, ve kterém jeden najde faktory každého výrazu, pak vybere soubor společných faktorů držených všemi z každé sady faktorů. Tato metoda může být užitečná pouze v jednoduchých případech, protože factoring je obvykle obtížnější než výpočet největšího společného dělitele.
2. The Euklidovský algoritmus, které lze použít k vyhledání GCD dvou polynomů stejným způsobem jako u dvou čísel.

Factoring

Chcete-li najít GCD dvou polynomů pomocí factoringu, jednoduše proveďte faktorizaci dvou polynomů úplně. Poté vezměte součin všech běžných faktorů. V této fázi nemusíme nutně mít monický polynom, takže to nakonec vynásobte konstantou, aby se z něj stal monický polynom. Toto bude GCD dvou polynomů, protože zahrnuje všechny běžné dělitele a je monické.

Příklad jedna: Najděte GCD z X² + 7X + 6 a X² − 5X − 6.

X² + 7X + 6 = (X + 1)(X + 6)

X² − 5X − 6 = (X + 1)(X − 6)

Jejich GCD tedy je X + 1.

Euklidovský algoritmus

Faktorování polynomů může být obtížné, zvláště pokud mají polynomy velkou míru. The Euklidovský algoritmus je metoda, která funguje pro jakoukoli dvojici polynomů. Opakovaně využívá Euklidovské dělení. Při použití tohoto algoritmu na dvou číslech se velikost čísel v každé fázi zmenšuje. U polynomů se stupeň polynomů v každé fázi snižuje. Poslední nenulový zbytek, vyrobený monic je-li to nutné, je GCD dvou polynomů.

Přesněji řečeno, pro nalezení gcd dvou polynomů A(X) a b(X), lze předpokládat b ≠ 0 (jinak je GCD A(X)), a

${displaystyle deg (b (x)) leq deg (a (x)) ,.}$

Euklidovské dělení poskytuje dva polynomy q(X), kvocient a r(X), zbytek takhle

${displaystyle a (x) = q_ {0} (x) b (x) + r_ {0} (x) qquad {ext {a}} qquad deg (r_ {0} (x))$

Polynom G(X) rozděluje obě A(X) a b(X) právě tehdy, když rozděluje obojí b(X) a r₀(X). Tím pádem

${displaystyle gcd (a (x), b (x)) = gcd (b (x), r_ {0} (x)).}$

Nastavení

${displaystyle a_ {1} (x) = b (x), b_ {1} (x) = r_ {0} (x),}$

lze opakovat euklidovské dělení a získat nové polynomy q₁(X), r₁(X), A₂(X), b₂(X) a tak dále. V každé fázi máme

${displaystyle deg (a_ {k + 1}) + deg (b_ {k + 1})$

takže posloupnost nakonec dosáhne bodu, ve kterém

${displaystyle b_ {N} (x) = 0}$

a jeden má GCD:

${displaystyle gcd (a, b) = gcd (a_ {1}, b_ {1}) = cdots = gcd (a_ {N}, 0) = a_ {N}.}$

Příklad: nalezení GCD z X² + 7X + 6 a X² − 5X − 6:

X² + 7X + 6 = 1 ⋅ (X² − 5X − 6) + (12 X + 12)

X² − 5X − 6 = (12 X + 12) (1/12 X − 1/2) + 0

Od té doby 12 X + 12 je poslední nenulový zbytek, je to GCD původních polynomů a monic GCD je X + 1.

V tomto příkladu není obtížné vyhnout se zavedení jmenovatelů vyřazením 12 před druhým krokem. To lze vždy provést pomocí sekvence pseudo-zbytku, ale bez opatrnosti to může během výpočtu zavést velmi velká celá čísla. Proto se pro počítačový výpočet používají jiné algoritmy, které jsou popsány níže.

Tato metoda funguje pouze v případě, že lze otestovat nulovou rovnost koeficientů, které se vyskytnou během výpočtu. V praxi tedy koeficienty musí být celá čísla, racionální čísla, prvky a konečné pole, nebo k někomu musí patřit konečně generované rozšíření pole jednoho z předchozích polí. Pokud jsou koeficienty čísla s plovoucí desetinnou čárkou které představují reálná čísla které jsou známé jen přibližně, pak je třeba znát stupeň GCD pro dobře definovaný výsledek výpočtu (to je numericky stabilní výsledek; v tomto případě mohou být použity jiné techniky, obvykle založené na rozklad singulární hodnoty.

Jednorozměrné polynomy s koeficienty v poli

Případ jednorozměrných polynomů nad polem je obzvláště důležitý z několika důvodů. Zaprvé je to nejzákladnější případ, a proto se objevuje ve většině prvních kurzů algebry. Za druhé, je to velmi podobné případu celých čísel a tato analogie je zdrojem pojmu Euklidovská doména. Třetím důvodem je, že teorie a algoritmy pro vícerozměrný případ a pro koeficienty v a jedinečná faktorizační doména jsou silně založeny na tomto konkrétním případě. V neposlední řadě umožňují polynomiální algoritmy GCD a odvozené algoritmy získat užitečné informace o kořenech polynomu, aniž by je musely počítat.

Euklidovské dělení

Euklidovské dělení polynomů, které se používá v Euklidův algoritmus pro výpočet GCD je velmi podobný Euklidovské dělení celých čísel. Jeho existence je založena na následující větě: Vzhledem k tomu, dva univariate polynomy A a b ≠ 0 definované nad polem, existují dva polynomy q (dále jen kvocient) a r (dále jen zbytek) které uspokojují

${displaystyle a = bq + r}$

a

${displaystyle deg (r)$

kde „deg (...)“ označuje stupeň a stupeň nulového polynomu je definován jako záporný. Navíc, q a r jsou těmito vztahy jednoznačně definovány.

Rozdíl od euklidovského dělení celých čísel spočívá v tom, že u celých čísel je stupeň nahrazen absolutní hodnotou a pro jedinečnost je třeba předpokládat, že r není negativní. Kruhy, pro které taková věta existuje, se nazývají Euklidovské domény.

Stejně jako u celých čísel lze euklidovské rozdělení polynomů vypočítat pomocí dlouhé rozdělení algoritmus. Tento algoritmus je obvykle prezentován pro výpočet papírem a tužkou, ale na počítačích funguje dobře, když je formalizován následujícím způsobem (všimněte si, že názvy proměnných přesně odpovídají oblastem papírového listu ve výpočtu tužkou a papírem dlouhých divize). V následujícím výpočtu „deg“ znamená stupeň jeho argumentace (s konvencí deg (0) <0) a „lc“ znamená přední koeficient, koeficient nejvyššího stupně proměnné.

Euklidovské děleníVstup: A a b ≠ 0 dva polynomy v proměnné X;Výstup: q, kvocient, a r, zbytek;Začít    q := 0    r := A    d : = deg (b)    C : = lc (b)    zatímco deg (r) ≥ d dělat        s := lc (r)/C Xdeg (r)−d        q := q + s        r := r − sb    konec udělej    vrátit se (q, r)konec

Důkaz platnosti tohoto algoritmu závisí na skutečnosti, že během celé smyčky „while“ máme A = bq + r a deg (r) je nezáporné celé číslo, které se snižuje při každé iteraci. Důkaz platnosti tohoto algoritmu tedy také dokazuje platnost euklidovského dělení.

Euklidův algoritmus

Pokud jde o celá čísla, euklidovské dělení nám umožňuje definovat Euklidův algoritmus pro výpočet GCD.

Počínaje dvěma polynomy A a b, Euklidův algoritmus spočívá v rekurzivní výměně páru (A, b) podle (b, rem (A, b)) (kde "rem (A, b)"označuje zbytek euklidovské divize, vypočítaný algoritmem předchozí části), dokud b = 0. GCD je poslední nenulový zbytek.

Euklidův algoritmus může být formován ve stylu rekurzivního programování jako:

${displaystyle gcd (a, b): = {ext {if}} b = 0 {ext {then}} a {ext {else}} gcd (b, operatorname {rem} (a, b)).}$

Ve stylu imperativního programování se stane stejný algoritmus, který pojmenuje každý přechodný zbytek:

${displaystyle {egin {aligned} r_ {0}: = a  r_ {1}: = bend {aligned}}}$pro (${displaystyle i: = 1}$; ${displaystyle r_ {i} eq 0}$; ${displaystyle i: = i + 1}$) dělat    ${displaystyle {egin {aligned} r_ {i + 1} &: = operatorname {rem} (r_ {i-1}, r_ {i}) end {aligned}}}$konec udělejvrátit se ${displaystyle (r_ {i-1}).}$

Posloupnost stupňů r_i přísně klesá. Tedy po nanejvýš deg (b) kroky, jeden dostane nulový zbytek, řekněme r_k. Tak jako (A, b) a (b, rem (A,b)) mají stejné dělitele, sada společných dělitelů se nemění Euklidovým algoritmem a tedy všechny páry (r_i, r_i+1) mít stejnou sadu společných dělitelů. Společní dělitelé A a b jsou tedy společnými děliteli r_k−1 a 0. Tedy r_k−1 je GCD z A a bTo nejen dokazuje, že Euklidův algoritmus počítá GCD, ale také dokazuje, že GCD existují.

Bézoutova identita a rozšířený algoritmus GCD

Bézoutova identita je věta související s GCD, původně prokázaná pro celá čísla, která platí pro všechny hlavní ideální doména. V případě jednorozměrných polynomů nad polem lze uvést následující.

Li G je největší společný dělitel dvou polynomů A a b (ne oba nula), pak existují dva polynomy u a proti takhle

${displaystyle au + bv = gquad}$ (Bézoutova identita)

a buď u = 1, proti = 0nebo u = 0, proti = 1nebo

${displaystyle deg (u)$

Zájem o tento výsledek v případě polynomů spočívá v tom, že existuje účinný algoritmus pro výpočet polynomů u a proti„Tento algoritmus se liší od Euklidova algoritmu několika dalšími výpočty provedenými při každé iteraci smyčky. Proto se tomu říká rozšířený algoritmus GCD. Další rozdíl od Euklidova algoritmu spočívá v tom, že používá pouze kvocient, označený „quo“, euklidovského dělení, nikoli pouze zbytek. Tento algoritmus funguje následovně.

Rozšířená GCD algoritmusVstup: A, b, jednorozměrné polynomyVýstup:    G, GCD z A a b    u, proti, jak je uvedeno výše A1, b1, takový, že ${displaystyle {egin {aligned} a = ga_ {1}  b = gb_ {1} end {aligned}}}$Začít    ${displaystyle {egin {array} {ll} r_ {0} = a & r_ {1} = b  s_ {0} = 1 & s_ {1} = 0  t_ {0} = 0 & t_ {1} = 1end {pole}}}$      pro (i = 1; ri ≠ 0; i = i+1) dělat        ${displaystyle q = operatorname {quo} (r_ {i-1}, r_ {i})}$        ${displaystyle {egin {aligned} r_ {i + 1} & = r_ {i-1} -qr_ {i}  s_ {i + 1} & = s_ {i-1} -qs_ {i}  t_ {i +1} & = t_ {i-1} -qt_ {i} konec {zarovnáno}}}$    konec udělej    ${displaystyle {egin {zarovnáno} g & = r_ {i-1}  u & = s_ {i-1}  v & = t_ {i-1} konec {zarovnáno}}}$    ${displaystyle {egin {aligned} a_ {1} & = (- 1) ^ {i-1} t_ {i}  b_ {1} & = (- 1) ^ {i} s_ {i} end {align} }}$konec

Důkaz, že algoritmus splňuje svoji výstupní specifikaci, závisí na tom, že pro každého i my máme

${displaystyle r_ {i} = as_ {i} + bt_ {i}}$

${displaystyle s_ {i} t_ {i + 1} -t_ {i} s_ {i + 1} = s_ {i} t_ {i-1} -t_ {i} s_ {i-1},}$

z toho vyplývá rovnost

${displaystyle s_ {i} t_ {i + 1} -t_ {i} s_ {i + 1} = (- 1) ^ {i}.}$

Tvrzení o stupních vyplývá ze skutečnosti, že při každé iteraci jsou stupně s_i a t_i zvýší se maximálně o stupeň r_i klesá.

Zajímavou vlastností tohoto algoritmu je, že když jsou potřebné koeficienty Bezoutovy identity, získá se zdarma kvocient vstupních polynomů jejich GCD.

Aritmetika algebraických rozšíření

Důležitou aplikací rozšířeného algoritmu GCD je, že umožňuje vypočítat rozdělení algebraická rozšíření pole.

Nechat L algebraické rozšíření pole K., generovaný prvkem, jehož minimální polynom F má titul n. Prvky L jsou obvykle reprezentovány jednorozměrnými polynomy K. stupně menší než n.

Přidání v L je jednoduše přidání polynomů:

${displaystyle a + _ {L} b = a + _ {K [X]} b.}$

Násobení v L je násobení polynomů následované dělením F:

${displaystyle acdot _ {L} b = operatorname {rem} (a ._ {K [X]} b, f).}$

Inverzní hodnota nenulového prvku A z L je koeficient u v Bézoutově identitě au + F v = 1, které lze vypočítat rozšířeným algoritmem GCD. (GCD je 1, protože minimální polynom F je neredukovatelný). Nerovnost stupňů ve specifikaci rozšířeného algoritmu GCD ukazuje, že další dělení F není nutné získat deg (u) F).

Subresultanti

V případě jednorozměrných polynomů existuje silný vztah mezi největšími společnými děliteli a výslednice. Přesněji řečeno, výslednice dvou polynomů P, Q je polynomiální funkcí koeficientů P a Q který má hodnotu nula právě tehdy, když je GCD P a Q není konstantní.

Teorie subresultantů je zobecněním této vlastnosti, která umožňuje obecně charakterizovat GCD dvou polynomů, a výsledkem je n-tý subresultantní polynom.^[1]

The i-th subresultantní polynom S_i(P ,Q) dvou polynomů P a Q je polynom stupně i jehož koeficienty jsou polynomiálními funkcemi koeficientů P a Qa i-th hlavní subresultantní koeficient s_i(P ,Q) je koeficient stupně i z S_i(P, Q). Mají tu vlastnost, ze které GCD P a Q má titul d kdyby a jen kdyby

${displaystyle s_ {0} (P, Q) = cdots = s_ {d-1} (P, Q) = 0, s_ {d} (P, Q) eq 0}$.

V tomto případě, S_d(P ,Q) je GCD z P a Q a

${displaystyle S_ {0} (P, Q) = cdots = S_ {d-1} (P, Q) = 0.}$

Každý koeficient subresultant polynomials is defined as the determinant of a submatrix of the Sylvesterova matice z P a Q. To znamená, že subresultanti se „specializují“ dobře. Přesněji řečeno, subresultanti jsou definováni pro polynomy přes libovolný komutativní kruh R, a mají následující vlastnost.

Nechat φ být prstencovým homomorfismem R do jiného komutativního kruhu S. Rozšiřuje se na další homomorfismus, označovaný také φ mezi polynomy zazvoní R a S. Pak, pokud P a Q jsou jednorozměrné polynomy s koeficienty v R takhle

${displaystyle deg (P) = deg (varphi (P))}$

a

${displaystyle deg (Q) = deg (varphi (Q)),}$

pak subresultantní polynomy a hlavní subresultantní koeficienty φ(P) a φ(Q) jsou obrázky od φ těch z P a Q.

Subresultanti mají dvě důležité vlastnosti, které je činí základními pro výpočet GCD dvou polynomů s celočíselnými koeficienty na počítačích. Za prvé, jejich definice pomocí determinantů umožňuje ohraničení, prostřednictvím Hadamardova nerovnost, velikost koeficientů GCD. Zadruhé tato vazba a vlastnost dobré specializace umožňují vypočítat GCD dvou polynomů s celočíselnými koeficienty prostřednictvím modulární výpočet a Čínská věta o zbytku (vidět níže ).

Technická definice

Nechat

${displaystyle P = p_ {0} + p_ {1} X + cdots + p_ {m} X ^ {m}, quad Q = q_ {0} + q_ {1} X + cdots + q_ {n} X ^ { n}.}$

být dva jednorozměrné polynomy s koeficienty v poli K.. Označme tím ${displaystyle {mathcal {P}} _ {i}}$ the K. vektorový prostor dimenze i polynomy stupně menší než i. Pro nezáporné celé číslo i takhle i ≤ m a i ≤ n, nechť

${displaystyle varphi _ {i}: {mathcal {P}} _ {n-i} imes {mathcal {P}} _ {m-i} ightarrow {mathcal {P}} _ {m + n-i}}$

být taková lineární mapa

${displaystyle varphi _ {i} (A, B) = AP + BQ.}$

The výsledný z P a Q je určující pro Sylvesterova matice, což je (čtvercová) matice ${displaystyle varphi _ {0}}$ na základě pravomocí X. Podobně i-subresultantní polynom je definován z hlediska determinantů dílčích matic matice ${displaystyle varphi _ {i}.}$

Popíšme tyto matice přesněji;

Nechat p_i = 0 pro i <0 nebo i > m, a q_i = 0 pro i <0 nebo i > n. The Sylvesterova matice je (m + n) × (m + n) -matice taková, že koeficient i-tá řada a j-tý sloupec je p_m+j−i pro j ≤ n a q_j−i pro j > n:^[2]

${displaystyle S = {egin {pmatrix} p_ {m} & 0 & cdots & 0 & q_ {n} & 0 & cdots & 0 p_ {m-1} & p_ {m} & cdots & 0 & q_ {n-1} & q_ {n} & cdots & 0 p_ {m-2 } & p_ {m-1} & ddots & 0 & q_ {n-2} & q_ {n-1} & ddots & 0 vdots & vdots & ddots & p_ {m} & vdots & vdots & ddots & q_ {n} vdots & vdots & cdots & p_ {m-1} & vdots & vdots & cdots & q_ {n-1} p_ {0} & p_ {1} & cdots & vdots & q_ {0} & q_ {1} & cdots & vdots 0 & p_ {0} & ddots & vdots & 0 & q_ {0} & ddots & vdots & vdots & vdots & ddots & p_ {1} & vdots & vdots & ddots & q_ {1} 0 & 0 & cdots & p_ {0} & 0 & 0 & cdots & q_ {0} end {pmatrix}}.}$

Matice T_i z ${displaystyle varphi _ {i}}$ je (m + n − i) × (m + n − 2i) -podmatice z S který se získá odstraněním posledního i řádky nul v submatici sloupců 1 až n − i a n + 1 až m + n − i z S (to je odstranění i sloupce v každém bloku a i poslední řady nul). The hlavní subresultantní koeficient s_i je určující pro m + n − 2i první řady T_i.

Nechat PROTI_i být (m + n − 2i) × (m + n − i) matice definována následovně. Nejprve přidáme (i + 1) sloupce nul napravo od (m + n − 2i − 1) × (m + n − 2i − 1) matice identity. Potom ohraničíme spodní část výsledné matice řádkem skládajícím se z (m + n − i - 1) nuly následované Xⁱ, Xⁱ⁻¹, ..., X, 1:

${displaystyle V_ {i} = {egin {pmatrix} 1 & 0 & cdots & 0 & 0 & 0 & cdots & 0 0 & 1 & cdots & 0 & 0 & 0 & cdots & 0 vdots & vdots & ddots & vdots & vdots & ddots & vdots & 0 0 & 0 & cdots & 1 & 0 & c &ots & 1 & 0 & c & }}.}$

S touto notací se i-th subresultantní polynom je determinant maticového produktu PROTI_iT_i. Jeho koeficient stupně j je determinant čtvercové submatice T_i spočívající v jeho m + n − 2i - 1 první řádek a (m + n − i − j)-házet.

Náčrt důkazu

Není zřejmé, že podle definice mají subresultanti požadované vlastnosti. Důkaz je nicméně poměrně jednoduchý, pokud se spojí vlastnosti lineární algebry a vlastností polynomů.

Jak je definováno, sloupce matice T_i jsou vektory koeficientů některých polynomů patřících k obrazu ${displaystyle varphi _ {i}}$. Definice i-tý subresultantní polynom S_i ukazuje, že vektor jeho koeficientů je lineární kombinací těchto sloupcových vektorů, a tím i S_i patří k obrazu ${displaystyle varphi _ {i}.}$

Pokud je stupeň GCD větší než i, pak Bézoutova identita ukazuje, že každý nenulový polynom na obrázku ${displaystyle varphi _ {i}}$ má stupeň větší než i. To z toho vyplývá S_i=0.

Pokud je naopak stupeň GCD i, pak Bézoutova identita opět umožňuje dokázat, že násobky GCD, které mají stupeň nižší než m + n − i jsou v obraze ${displaystyle varphi _ {i}}$. Vektorový prostor těchto násobků má rozměr m + n − 2i a má základnu polynomů párových různých stupňů, ne menších než i. To znamená, že submatice m + n − 2i první řádky sloupce echelon forma T_i je matice identity a tím i to s_i není 0. Tedy S_i je polynom v obraze ${displaystyle varphi _ {i}}$, což je násobek GCD a má stejný stupeň. Je tedy největším společným dělitelem.

GCD a hledání kořenů

Faktorizace bez čtverců

Většina algoritmy hledání kořenů chovat se špatně s polynomy, které mají více kořenů. Je proto užitečné je detekovat a odstranit před vyvoláním algoritmu hledání kořenů. Výpočet GCD umožňuje detekci existence více kořenů, protože více kořenů polynomu jsou kořeny GCD polynomu a jeho derivát.

Po výpočtu GCD polynomu a jeho derivace poskytují další výpočty GCD úplnost faktorizace bez čtverců polynomu, což je faktorizace

${displaystyle f = prod _ {i = 1} ^ {deg (f)} f_ {i} ^ {i}}$

kde, pro každého i, polynom F_i buď je 1, pokud F nemá žádný kořen multiplicity i nebo je polynom bez čtverců (tj. polynom bez více kořenů), jehož kořeny jsou přesně kořeny multiplicity i z F (vidět Yunův algoritmus ).

Faktorizace bez čtverců tedy redukuje hledání kořenů polynomu s více kořeny na hledání kořenů několika bezřadných polynomů nižšího stupně. Faktorizace bez čtverců je také většinou prvním krokem polynomiální faktorizace algoritmy.

Sturmova sekvence

The Sturmova sekvence polynomu se skutečnými koeficienty je sekvence zbytků poskytovaná variantou Euklidova algoritmu aplikovaného na polynom a jeho derivát. Pro získání Sturmovy sekvence stačí instrukci nahradit

${displaystyle r_ {i + 1}: = operatorname {rem} (r_ {i-1}, r_ {i})}$

Euklidova algoritmu od

${displaystyle r_ {i + 1}: = - operatorname {rem} (r_ {i-1}, r_ {i}).}$

Nechat PROTI(A) je počet změn znaků v posloupnosti, když se vyhodnotí v bodě A. Sturmova věta to tvrdí PROTI(A) − PROTI(b) je počet skutečných kořenů polynomu v intervalu [A, b]. Sekvence Sturm tedy umožňuje vypočítat počet skutečných kořenů v daném intervalu. Rozdělením intervalu, dokud každý podinterval nebude obsahovat nejvýše jeden kořen, získáte algoritmus, který vyhledá skutečné kořeny v intervalech libovolně malé délky.

GCD přes prsten a jeho pole zlomků

V této části uvažujeme polynomy nad a jedinečná faktorizační doména R, obvykle kruh celých čísel a nad ním pole zlomků F, obvykle pole racionálních čísel, a označujeme R[X] a F[X] kroužky polynomů v sadě proměnných nad těmito kroužky.

Faktorizace primitivního obsahu části

The obsah polynomu p ∈ R[X], označeno „pokračování (p) ", je GCD svých koeficientů. Polynom q ∈ F[X] mohou být psány

${displaystyle q = {frac {p} {c}}}$

kde p ∈ R[X] a C ∈ R: to stačí vzít za C násobek všech jmenovatelů koeficientů q (například jejich produkt) a p = CQ. The obsah z q je definován jako:

${displaystyle operatorname {cont} (q) = {frac {operatorname {cont} (p)} {c}}.}$

V obou případech je obsah definován až do násobení a jednotka z R.

The primitivní část polynomu v R[X] nebo F[X] je definováno

${displaystyle operatorname {primpart} (p) = {frac {p} {operatorname {cont} (p)}}.}$

V obou případech se jedná o polynom v R[X] to je primitivní, což znamená, že 1 je GCD svých koeficientů.

Tedy každý polynom v R[X] nebo F[X] může být faktorizováno jako

${displaystyle p = operatorname {cont} (p), operatorname {primpart} (p),}$

a tato faktorizace je jedinečná až do násobení obsahu jednotkou R a primitivní části inverzí této jednotky.

Gaussovo lemma znamená, že produkt dvou primitivních polynomů je primitivní. Z toho vyplývá, že

${displaystyle operatorname {primpart} (pq) = operatorname {primpart} (p) operatorname {primpart} (q)}$

a

${displaystyle operatorname {cont} (pq) = operatorname {cont} (p) operatorname {cont} (q).}$

Vztah mezi GCD nad R a znovu F

Vztahy z předchozí části znamenají silný vztah mezi GCD v R[X] a v F[X]. Aby nedocházelo k nejasnostem, notacegcd"bude v následujícím indexován indexem, ve kterém je vypočítána GCD.

Li q₁ a q₂ patřit k F[X], pak

${displaystyle operatorname {primpart} (gcd _ {F [X]} (q_ {1}, q_ {2})) = gcd _ {R [X]} (operatorname {primpart} (q_ {1}), operatorname { primpart} (q_ {2})).}$

Li p₁ a p₂ patřit k R[X], pak

${displaystyle gcd _ {R [X]} (p_ {1}, p_ {2}) = gcd _ {R} (operatorname {cont} (p_ {1}), operatorname {cont} (p_ {2})) gcd _ {R [X]} (operatorname {primpart} (p_ {1}), operatorname {primpart} (p_ {2})),}$

a

${displaystyle gcd _ {R [X]} (operatorname {primpart} (p_ {1}), operatorname {primpart} (p_ {2})) = operatorname {primpart} (gcd _ {F [X]} (p_ { 1}, p_ {2})).}$

Výpočet polynomiálních GCD je tedy v podstatě stejný problém F[X] a více R[X].

U jednorozměrných polynomů nad racionálními čísly si člověk může myslet, že Euclidův algoritmus je pohodlnou metodou pro výpočet GCD. Zahrnuje však zjednodušení velkého počtu zlomků celých čísel a výsledný algoritmus není efektivní. Z tohoto důvodu byly navrženy metody k úpravě Euklidova algoritmu pro práci pouze s polynomy přes celá čísla. Spočívají v nahrazení euklidovské divize, která zavádí zlomky, tzv pseudo rozdělenía nahrazení zbývající sekvence Euklidova algoritmu tzv sekvence pseudo-zbytku (vidět níže ).

Důkaz, že GCD existuje pro vícerozměrné polynomy

V předchozí části jsme viděli, že GCD polynomů v R[X] lze odvodit z GCD v R a v F[X]. Bližší pohled na důkaz ukazuje, že to nám umožňuje dokázat existenci GCD v R[X], pokud existují v R a v F[X]. Zejména pokud GCD existují v R, a pokud X je redukován na jednu proměnnou, což dokazuje, že v GCD existují R[X] (Euklidův algoritmus dokazuje existenci GCD v F[X]).

Polynom v n proměnné lze považovat za jednorozměrný polynom přes kruh polynomů v (n - 1) proměnné. Rekurze na počet proměnných tedy ukazuje, že pokud GCD existují a lze je vypočítat R, pak existují a mohou být vypočítány v každém vícerozměrném polynomiálním kruhu R. Zejména pokud R je kruh celých čísel nebo pole, pak v něm existují GCD R[X₁,..., X_n] a to, co předchází, poskytuje algoritmus pro jejich výpočet.

Důkaz, že polynomiální kruh nad jedinečnou faktorizační doménou je také jedinečnou faktorizační doménou, je podobný, ale neposkytuje algoritmus, protože neexistuje žádný obecný algoritmus, který by faktoroval jednorozměrné polynomy nad polem (existují příklady polí, pro která existuje neexistuje žádný faktorizační algoritmus pro jednorozměrné polynomy).

Sekvence pseudo-zbytku

V této části uvažujeme o integrální doména Z (obvykle prsten Z celých čísel) a jeho pole zlomků Q (obvykle pole Q racionálních čísel). Vzhledem k tomu, dva polynomy A a B v jednorozměrném polynomiálním kruhu Z[X], euklidovská divize (přes Q) z A podle B poskytuje podíl a zbytek, který nemusí patřit Z[X].

Protože pokud použijeme Euklidův algoritmus na následující polynomy ^[3]

${displaystyle X ^ {8} + X ^ {6} -3X ^ {4} -3X ^ {3} + 8X ^ {2} + 2X-5}$

a

${displaystyle 3X ^ {6} + 5X ^ {4} -4X ^ {2} -9X + 21,}$

po sobě jdoucí zbytky Euklidova algoritmu jsou

${displaystyle {egin {aligned} & - {frac {5} {9}} X ^ {4} + {frac {1} {9}} X ^ {2} - {frac {1} {3}}, & - {frac {117} {25}} X ^ {2} -9X + {frac {441} {25}}, & {frac {233150} {19773}} X- ​​{frac {102500} {6591}} , & - {frac {1288744821} {543589225}}. konec {zarovnáno}}}$

Jeden vidí, že navzdory malému stupni a malé velikosti koeficientů vstupních polynomů je třeba manipulovat a zjednodušit celočíselné zlomky poměrně velké velikosti.

The pseudo rozdělení byl zaveden, aby umožnil variantu Euklidova algoritmu, ke které patří všechny zbytky Z[X].

Li ${displaystyle deg (A) = a}$ a ${displaystyle deg (B) = b}$ a A ≥ b, pseudo-zbytek pseudo-rozdělení A podle B, označeno prem (A,B) je

${displaystyle operatorname {prem} (A, B) = operatorname {rem} (operatorname {lc} (B) ^ {a-b + 1} A, B),}$

kde lc (B) je hlavní koeficient B (koeficient X^b).

Pseudo-zbytek pseudo-rozdělení dvou polynomů v Z[X] patří vždy Z[X].

A sekvence pseudozbytku je sekvence (pseudo) zbytků r_i získána nahrazením instrukce

${displaystyle r_ {i + 1}: = operatorname {rem} (r_ {i-1}, r_ {i})}$

Euklidova algoritmu od

${displaystyle r_ {i + 1}: = {frac {operatorname {prem} (r_ {i-1}, r_ {i})} {alpha}},}$

kde α je prvek Z který rozdělí přesně každý koeficient čitatele. Různé možnosti α dát různé sekvence pseudo-zbytku, které jsou popsány v následujících podsekcích.

Protože společné dělitele dvou polynomů se nezmění, pokud jsou polynomy vynásobeny invertibilními konstantami (v Q), poslední nenulový termín v sekvenci pseudo-zbytku je GCD (v Q[X]) vstupních polynomů. Sekvence pseudozbytku proto umožňují výpočet GCD Q[X] bez zavedení zlomků do Q.

V některých kontextech je nezbytné řídit znaménko vedoucího koeficientu pseudo-zbytku. To je obvykle případ při práci na počítači výslednice a subresultants, nebo pro použití Sturmova věta. Tuto kontrolu lze provést buď nahrazením lc (B) jeho absolutní hodnotou v definici pseudo-zbytku nebo ovládáním znaménka α (li α rozdělí všechny koeficienty zbytku, totéž platí pro –α).^[1]

Triviální sekvence pseudo-zbytku

Nejjednodušší (definovat) zbytek sekvence spočívá v braní vždy α = 1. V praxi to není zajímavé, protože velikost koeficientů exponenciálně roste se stupněm vstupních polynomů. To se jasně ukazuje na příkladu předchozí části, pro kterou jsou po sobě jdoucí pseudozbytky

${displaystyle -15, X ^ {4} + 3, X ^ {2} -9,}$

${displaystyle 15795, X ^ {2} + 30375, X-59535,}$

${displaystyle 1254542875143750, X-1654608338437500,}$

${displaystyle 12593338795500743100931141992187500.}$

Počet číslic koeficientů po sobě jdoucích zbytků se při každé iteraci algoritmu více než zdvojnásobí. Toto je typické chování triviálních pseudo-zbytkových sekvencí.

Primitivní sekvence pseudo-zbytku

The primitivní sekvence pseudozbytku spočívá v převzetí α obsah čitatele. Tak všechny r_i jsou primitivní polynomy.

Primitivní sekvence pseudo-zbytku je sekvence pseudo-zbytku, která generuje nejmenší koeficienty. Vyžaduje však výpočet počtu GCD v Z, a proto není dostatečně efektivní pro použití v praxi, zvláště když Z je sám polynomiální kruh.

Se stejným vstupem jako v předchozích částech jsou postupné zbytky po rozdělení podle obsahu

${displaystyle -5, X ^ {4} + X ^ {2} -3,}$

${displaystyle 13, X ^ {2} + 25, X-49,}$

${displaystyle 4663, X-6150,}$

${displaystyle 1.}$

Malá velikost koeficientů skrývá skutečnost, že byla vypočítána celá řada celých čísel GCD a dělení GCD.

Subresultantní sekvence pseudo-zbytku

Subresultantní sekvenci lze také vypočítat s pseudo-zbytky. Proces spočívá ve výběru α takovým způsobem, že každý r_i je subresultantní polynom. Překvapivě výpočet α je velmi snadné (viz níže). On the other hand, the proof of correctness of the algorithm is difficult, because it should take into account all the possibilities for the difference of degrees of two consecutive remainders.

The coefficients in the subresultant sequence are rarely much larger than those of the primitive pseudo-remainder sequence. As GCD computations in Z are not needed, the subresultant sequence with pseudo-remainders gives the most efficient computation.

With the same input as in the preceding sections, the successive remainders are

${displaystyle 15,X^{4}-3,X^{2}+9,}$

${displaystyle 65,X^{2}+125,X-245,}$

${displaystyle 9326,X-12300,}$

${displaystyle 260708.}$

The coefficients have a reasonable size. They are obtained without any GCD computation, only exact divisions. This makes this algorithm more efficient than that of primitive pseudo-remainder sequences.

The algorithm computing the subresultant sequence with pseudo-remainders is given below. In this algorithm, the input (A, b) is a pair of polynomials in Z[X]. The r_i are the successive pseudo remainders in Z[X], the variables i a d_i are non negative integers, and the Greek letters denote elements in Z. Funkce deg() a rem() denote the degree of a polynomial and the remainder of the Euclidean division. In the algorithm, this remainder is always in Z[X]. Finally the divisions denoted / are always exact and have their result either in Z[X] or in Z.

${displaystyle { egin{aligned}r_{0}:=a
_{1}:=bend{aligned}}}$pro (${displaystyle i:=1}$; ${displaystyle r_{i}eq 0}$; ${displaystyle i:=i+1;}$) dělat    ${displaystyle { egin{aligned}d_{i}&:=deg(r_{i-1})-deg(r_{i})gamma _{i}&:=operatorname {lc} (r_{i})end{aligned}}}$    -li ${displaystyle i=1}$ pak        ${displaystyle { egin{aligned} eta _{1}&:=(-1)^{d_{1}+1}psi _{1}&:=-1end{aligned}}}$    jiný        ${displaystyle { egin{aligned} eta _{i}&:=-gamma _{i-1}psi _{i}^{d_{i}}psi _{i}&:={frac {(-gamma _{i-1})^{d_{i-1}}}{psi _{i-1}^{d_{i-1}-1}}}end{aligned}}}$    skončit, pokud    ${displaystyle r_{i+1}:={frac {operatorname {rem} (gamma _{i}^{d_{i}+1}r_{i-1},r_{i})}{ eta _{i}}}}$end do.

Note: "lc" stands for the leading coefficient, the coefficient of the highest degree of the variable.

This algorithm computes not only the greatest common divisor (the last non zero r_i), but also all the subresultant polynomials: The remainder r_i je (deg(r_i−1) − 1)-th subresultant polynomial. Li deg (r_i) < deg(r_i−1) − 1, deg (r_i)-th subresultant polynomial is lc(r_i)^{deg (r_i−1)−deg(r_i)−1}r_i. All the other subresultant polynomials are zero.

Sturm sequence with pseudo-remainders

One may use pseudo-remainders for constructing sequences having the same properties as Sturm sequences. This requires to control the signs of the successive pseudo-remainders, in order to have the same signs as in the Sturm sequence. This may be done by defining a modified pseudo-remainder as follows.

Li ${displaystyle deg(A)=a}$ a ${displaystyle deg(B)=b}$ a A ≥ b, the modified pseudo-remainder prem2(A, B) of the pseudo-division of A podle B je

${displaystyle operatorname {prem2} (A,B)=-operatorname {rem} (|operatorname {lc} (B)|^{a-b+1}A,B),}$

where |lc(B) | is the absolute value of the leading coefficient of B (the coefficient of X^b).

For input polynomials with integer coefficients, this allows retrieval of Sturm sequences consisting of polynomials with integer coefficients. The subresultant pseudo-remainder sequence may be modified similarly, in which case the signs of the remainders coincide with those computed over the rationals.

Note that the algorithm for computing the subresultant pseudo-remainder sequence given above will compute wrong subresultant polynomials if one uses ${displaystyle -mathrm {prem2} (A,B)}$ namísto ${displaystyle operatorname {prem} (A,B)}$.

Modular GCD algorithm

Li F a G are polynomials in F[X] for some finitely generated field F, the Euclidean Algorithm is the most natural way to compute their GCD. However, modern počítačová algebra systems only use it if F is finite because of a phenomenon called intermediate expression swell. Although degrees keep decreasing during the Euclidean algorithm, if F není konečný then the bit size of the polynomials can increase (sometimes dramatically) during the computations because repeated arithmetic operations in F tends to lead to larger expressions. For example, the addition of two rational numbers whose denominators are bounded by b leads to a rational number whose denominator is bounded by b², so in the worst case, the bit size could nearly double with just one operation.

To expedite the computation, take a ring D pro který F a G jsou v D[X], and take an ideal Já takhle D/Já is a finite ring. Then compute the GCD over this finite ring with the Euclidean Algorithm. Using reconstruction techniques (Čínská věta o zbytku, racionální rekonstrukce, etc.) one can recover the GCD of F a G from its image modulo a number of ideals Já. One can prove^[4] that this works provided that one discards modular images with non-minimal degrees, and avoids ideals Já modulo which a leading coefficient vanishes.

Předpokládat ${displaystyle F=mathbb {Q} ({sqrt {3}})}$, ${displaystyle D=mathbb {Z} [{sqrt {3}}]}$, ${displaystyle f={sqrt {3}}x^{3}-5x^{2}+4x+9}$ a ${displaystyle g=x^{4}+4x^{2}+3{sqrt {3}}x-6}$. Pokud vezmeme ${displaystyle I=(2)}$ pak ${displaystyle D/I}$ je finite ring (not a field since ${displaystyle I}$ is not maximal in ${displaystyle D}$). The Euclidean algorithm applied to the images of ${displaystyle f,g}$ v ${displaystyle (D/I)[x]}$ succeeds and returns 1. This implies that the GCD of ${displaystyle f,g}$ v ${displaystyle F[x]}$ must be 1 as well. Note that this example could easily be handled by any method because the degrees were too small for expression swell to occur, but it illustrates that if two polynomials have GCD 1, then the modular algorithm is likely to terminate after a single ideal ${displaystyle I}$.

Viz také

• List of polynomial topics
• Multivariate division algorithm

Reference

• Basu, Saugata; Pollack, Richard; Roy, Marie-Françoise (2006). Algorithms in real algebraic geometry, chapter 4.2. Springer-Verlag.CS1 maint: ref = harv (odkaz)
• Davenport, James H.; Siret, Yvon; Tournier, Évelyne (1988). Počítačová algebra: systémy a algoritmy pro algebraický výpočet. Z francouzštiny přeložili A. Davenport a J.H. Davenport. Akademický tisk. ISBN  978-0-12-204230-0.CS1 maint: ref = harv (odkaz)
• van Hoeij, M.; Monagan, M.B. (2004), Algorithms for polynomial GCD computation over algebraic function fields, pp. 297–304
• Javadi, S.M.M.; Monagan, M.B. (2007), A sparse modular GCD algorithm for polynomials over algebraic function fields, pp. 187–194
• Knuth, Donald E. (1969). The Art of Computer Programming II. Addison-Wesley. pp. 370–371.CS1 maint: ref = harv (odkaz)
• Knuth, Donald E. (1997). Seminumerical Algorithms. The Art of Computer Programming. 2 (Třetí vydání.). Reading, Massachusetts: Addison-Wesley. pp. 439–461, 678–691. ISBN  0-201-89684-2.CS1 maint: ref = harv (odkaz)
• Loos, Rudiger (1982), "Generalized polynomial remainder sequences", in B. Buchberger; R. Loos; G. Collins (eds.), Computer Algebra, Springer Verlag