Hľadanie racionálnych koreňov

[Martin Sleziak]

Spomeniem tu vec, ktorá je občas užitočná pri hľadaní koreňov vyšších stupňov.

Ak máme polynóm s celočíselnými koeficientami, tak všetky jeho racionálne korene vieme nájsť na základe nasledujúcej vety (rational root theorem).

Veta. Ak $f(x)=a_n x^n + a_{n-1}x^{n-1} \dots +a_1x+a_0\in\mathbb Z[x]$ je polynóm s celočíselnými koeficientami a racionálne číslo $c=\frac{p}q$ je koreň polynómu $f(x)$ $($pričom $\gcd(p,q)=1$, t.j. racionálne číslo $c$ je zapísané v základnom tvare$)$, tak $$p\mid a_0\qquad\text{ a }\qquad q\mid
a_n.$$

Túto vetu (aj s dôkazom) môžete nájsť na rôznych miestach a ešte sa s ňou určite stretnete. Spomeniem napríklad knihu Algebra a teoretická aritmetika a tiež poznámky k predmetom Algebra 2 pre odbor informatika či pre odbor matematika. (V oboch nájdete aj nejaké prepočítané príklady.)

Ukážme si na dvoch príkladoch, či nám táto veta môže pomôcť nájsť aspoň niektoré korene polynómu. (Ak sa pozeráte na tento typ výpočtu najmä v súvislosti s hľadaním vlastných čísel, je pre vás podstatný najmä druhý z týchto dvoch príkladov. Takže v takom prípade prvý z nich môžete pokojne preskočiť - uviedol som ho tu skôr pre úplnosť, resp. ak vás zaujímajú i iné prípady.)

[Martin Sleziak]

Príklad 1. Hľadajme racionálne korene polynómu $f(x)=6x^4+5x^3-16x^2-10x+8$.

Ak $c=\frac pq$ je koreňom, tak $p\mid 8$ a $q\mid 6$.
Teda $p\in\{\pm1,\pm2,\pm4,\pm8\}$ a $q\in\{\pm1,\pm2,\pm3,\pm6\}$.
Z toho dostaneme všetky možnosti pre racionálne korene:
$c\in\{\pm1,\pm2,\pm4,\pm8,
\pm\frac12,
\pm\frac13,\pm\frac23,\pm\frac43,\pm\frac83,
\pm\frac16\}$

Je ich síce pomerne veľa, ale je to iba konečne veľa možností, ktoré stačí skúšať. Či sú korene môžeme overovať pomocou Hornerovej schémy: viewtopic.php?t=1092

Poďme skúsiť dosadiť niekoľko hodnôt - môžeme napríklad začať s malými celými číslami - s nimi sa nám bude počítať ľahko:
$$
\begin{array}{c|ccccc|}
& 6 & 5 &-16 &-10 & 8 \\
1 & & 6 & 11 & -5 &-15 \\ \hline
& 6 &11 & -5 &-15 &-7
\end{array}
$$

$$
\begin{array}{c|ccccc|}
& 6 & 5 &-16 &-10 & 8 \\
-1 & &-6 & 1 & 15 &-5\\ \hline
& 6 &-1 &-15 & 5 & 3
\end{array}
$$

$$
\begin{array}{c|ccccc|}
& 6 & 5 &-16 &-10 & 8 \\
2 & &12 & 34 & 36 &52\\ \hline
& 6 &17 & 18 & 26 &60
\end{array}
$$

$$
\begin{array}{c|ccccc|}
& 6 & 5 &-16 &-10 & 8 \\
-2 & &-12& 14 & 4 &12 \\ \hline
& 6 &-7 & -2 & -6 &20
\end{array}
$$

Zatiaľ sme nenašli koreň a nenájdeme ho ani medzi ostatnými celými číslami z nášho zoznamu. Nevyhneme sa teda rátaniu so zlomkami.
Môžeme si však všimnúť že hodnota v nule $f(0)=8$ je kladná. Vypočítali sme, že $f(1)<0$ a $f(2)>0$.
Z vety o strednej hodnote teda vieme, že tento polynóm má aspoň jeden koreň v intervale $(0,1)$ a aspoň jeden koreň v intervale $(1,2)$.
Nie je zaručené, že tieto korene sú racionálne. (V tomto konkrétnom prípade je racionálny jeden z nich.)
Ale možno je vcelku zmysluplný pokus hľadať nejaké korene medzi číslami, ktoré sú v tomto intervale. Poďme teda začať skúšať čísla z nášho zoznamu, ktoré sú medzi nulou a dvojkou. (Vieme, že tam sú dva koreň - ak by to vyšlo tak, že ani jeden z nich nie je racionálny, tak máme smolu a musíme skúšať ďalšie čísla.)

Začnem napríklad od najmenšieho:
$$
\begin{array}{c|ccccc|}
& 6 & 5 &-16 &-10 & 8 \\
\frac16& & 1 & 1 &-\frac53& \\ \hline
& 6 & 6 &-10 & &
\end{array}
$$
Azda je užitočné spomenúť (tu bez dôkazu) takúto vec.
Fakt 1. Ak nám pri výpočte v Hornerovej schéme vyjdú zlomky, už nemusíme rátať ďalej - dané číslo nie je koreňom.
V našom prípade sme sa môžeme zastaviť, keď vidíme, že v treťom riadku dostaneme $-10-\frac53$. (Čo nie je celé číslo.)


$$
\begin{array}{c|ccccc|}
& 6 & 5 &-16 &-10 & 8 \\
\frac13& & 2 & \frac73 & & \\ \hline
& 6 & 7 & & &
\end{array}
$$
Teda $\frac13$ nie je koreň.

$$
\begin{array}{c|ccccc|}
& 6 & 5 &-16 &-10 & 8 \\
\frac12& & 3 & 4 & -6 &-8 \\ \hline
& 6 & 8 &-12 &-16 & \boxed{0}
\end{array}
$$

Zistili sme, že $\frac12$ je koreňom tohoto polynómu.
Súčasne sme dostali rozklad $f(x)=(x-\frac12)(6x^3+8x^2-12x-16)=2(x-\frac12)(3x^2+4x-6x-8)$.

Teraz už stačí opakovať rovnaký postup pre polynóm $g(x)=3x^2+4x-6x-8$.
Máme dve výhody - už máme polynóm nižšieho stupňa. A vďaka tomu, že sme mohli vyňať dvojku, už stačí skúšať $p\mid 8$ a $q\mid 2$, teda sa nám zmenší počet kandidátov na racionálne korene (počet čísel, ktoré treba vyskúšať). Samozrejme, nemusíme znovu skúšať čísla, pre ktoré sme už zistili že nie sú koreňmi $f(x)$.

Ak si to naozaj vyskúšate, tak zistíte, že $\frac34$ je koreňom a podarí sa vám dostať rozklad $f(x)=6(x-\frac12)(x+\frac43)(x-\sqrt2)(x+\sqrt2)$.

[Martin Sleziak]

Na tomto mieste to spomínam hlavne kvôli tomu, že polynómy vyšších stupňov sa môžu vyskytnúť pri hľadaní vlastných čísel. Tie hľadáme ako korene polynómu $\det(xI-A)$ resp. $\det(A-xI)$, ktorý môže mať vedúci koeficient iba $a_n=\pm1$.
Teda z vety, ktorú sme spomenuli, vyplýva, že menovateľ racionálneho koreňa musí byť $\pm1$ a stačí nám skúšať delitele absolútneho člena $a_0$. (Teda kandidáti na racionálne korene budú celé čísla.)
Vlastne takýto špeciálny prípad spomenutej vety - hovoriaci o tom, ktoré celé čísla môžu byť korene polynómu kde vedúci koeficient je rovný jednej - je asi ešte o čosi jednoduchšie dokázať.

Znovu pripomeniem, že je určite výhodnejšie, ak sa nám podarí vypočítať charakderistický polynóm takým spôsobom, že pritom nájdeme aspoň jeden koreň: viewtopic.php?t=890
Ale ak sa nám to nepodarí a dostaneme polynóm vyššieho stupňa, tak nám môže pomôcť niečo takéto.

Príklad 2. Hľadajme racionálne korene polynómu $f(x)=x^3-48x+128$.

Z vety o racionálnych koreňoch vidíme, že stačí skúšať delitele čísla $128$, teda $\pm1,\pm2\pm4,\pm7,\pm8,\pm14,\pm16,\pm28,\pm56,\pm128$.
Navyše si môžeme všimnúť, že $f(x)=x(x^2-48)+128$ bude určite kladné ak $x>0$ a $x^2\ge48$. (Dokonca vtedy máme $f(x)\ge128$.) Takže čísla také, že $x\ge8$ môžeme vylúčiť.

Môžeme teda začať skúšať dosadzovať tieto čísla pomocou Hornerovej schémy.

$$
\begin{array}{c|cccc|}
& 1 & 0 &-48 &128\\
1 & & 1 & 1 &-47 \\ \hline
& 1 & 1 &-47 &81
\end{array}
$$

$$
\begin{array}{c|cccc|}
& 1 & 0 &-48 &128\\
2 & & 2 & 4 &-88 \\ \hline
& 1 & 2 &-44 & 40
\end{array}
$$

$$
\begin{array}{c|cccc|}
& 1 & 0 &-48 &128\\
4 & & 4 & 16 &-128\\ \hline
& 1 & 4 &-32 & \boxed{0}
\end{array}
$$
Zistili sme, že číslo $4$ je koreňom a tiež že $f(x)=(x-4)(x^2+4x-32)$.

Teraz už stačí nájsť korene kvadratického polynómu $x^2+4x-32$.
Ak ich vyrátame, zistíme že sú to čísla $4$ a $-8$ a máme $f(x)=(x-4)^2(x+8)$.

[Martin Sleziak]

Pridám sem ešte jeden príklad, len aby som ilustroval, že niekedy vieme ešte trochu obmedziť možných kandidátov na korene na základe znamienka.
Chceme nájsť racionálne korene polynómu $$f(x)=6x^4-7x^3+8x^2-7x+2.$$

Môžeme si všimnúť, že pre $x\le 0$ máme $x^4\ge 0$, $x^2\ge 0$, teda aj $6x^4+8x^2\ge 0$.
Súčasne ale aj $x^3\le 0$ a $x\le 0$, čo znamená, že $-7x^3\ge0$ a $-7x\ge0$.
Spolu dostaneme, že pre $x\le0$ máme $f(x)=6x^4-7x^3+8x^2-7x+2\ge 2$. To znamená, že spomedzi reálnych čísel môžu byť koreňom iba kladné čísla, záporné skúšať nemusíme.

Máme $p\mid 2$, $q\mid 6$. Kandidáti na racionálne korene sú teda: $\pm1$, $\pm2$, $\pm\frac12$, $\pm\frac13$, $\pm\frac23$, $\pm\frac16$.
Ako sme však už spomenuli, spomedzi nich stačí skúšať iba kladné čísla.

$$\begin{array}{|c|c|c|c|c|c|c|}
\hline
& 6 & -7 & 8 & -7 & 2 \\ \hline
\frac12 & & 3 & -2 & 3 & -2 \\ \hline
& 6 & -4 & 6 & -4 & \boxed{0} \\ \hline
\end{array}$$

$$f(x)=2(x-1/2)(3x^3-2x^2+3x-2)=(2x-1)(3x-2)(x^2+1)$$