\documentclass[11pt,a4paper]{report}
\usepackage[utf8]{inputenc}
\usepackage[czech]{babel}
\usepackage[T1]{fontenc}
\usepackage{mathptmx}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{a4wide}
\usepackage{opakuj}
\makeatletter
\let\newmcodes@\relax
\makeatother

\usepackage{enumerate}
%\parindent=0mm
\usepackage{pgf,tikz}
\usetikzlibrary{arrows}
\usepackage{enumerate}
\usepackage{paralist}
\usepackage{xypic}

\usepackage{verbatim}

\usepackage[pdftex]{hyperref}
\hypersetup{hidelinks}

\DeclareMathOperator{\tg}{tg}
\DeclareMathOperator{\cotg}{cotg}
\DeclareMathOperator{\ch}{ch}
\DeclareMathOperator{\sh}{sh}
\DeclareMathOperator{\tgh}{tgh}
\DeclareMathOperator{\cotgh}{cotgh}
\DeclareMathOperator{\LM}{LM}
\DeclareMathOperator{\LT}{LT}
\DeclareMathOperator{\LC}{LC}
\newcommand{\dx}{\,\mathrm{d}x}
\newcommand{\dt}{\,\mathrm{d}t}
\newcommand{\ds}{\,\mathrm{d}s}

\newcommand{\I}{{\rm i}}
\newcommand{\N}{\ensuremath{\mathbb{N}}}
\newcommand{\Z}{\ensuremath{\mathbb{Z}}}
\newcommand{\R}{\ensuremath{\mathbb{R}}}
\newcommand{\Q}{\ensuremath{\mathbb{Q}}}
\newcommand{\ce}[1]{\ensuremath{\left(#1 \right)}}
\newcommand{\cce}[1]{\ensuremath{\left[#1 \right]}}

\newcommand{\pp}[1]{\ensuremath{\left|#1\right|}}
\newcommand{\zk}[1]{\ensuremath{\left(#1 \right)}}
\newcommand{\zs}[1]{\ensuremath{\left<#1 \right>}}
\newcommand{\zh}[1]{\ensuremath{\left[#1 \right]}}
\newcommand{\zm}[1]{\ensuremath{\left\{#1 \right\}}}
\newcommand{\dcc}[1]{\ensuremath{\left\lfloor #1 \right\rfloor}}

\newcommand{\kon}[3]{\ensuremath{{#1} \equiv {#2}\pmod{#3}}}
\newcommand{\imp}{\ensuremath{\Rightarrow}}
\newcommand{\ekv}{\ensuremath{\Leftrightarrow}}
\newcommand{\bu}{\ensuremath{\bold{u}}}
\newcommand{\bv}{\ensuremath{\bold{v}}}

\newcommand{\psl}[1]{\ensuremath{\{{#1 }_n\}_{n=1}^\infty}}

\newtheorem{veta}{Věta}[chapter]
\newtheorem{lemma}[veta]{Lemma}
\theoremstyle{definition}
\newtheorem{definice}[veta]{Definice}
\newtheorem{dusledek}[veta]{Důsledek}
\newtheorem{prikl}{Příklad}[chapter]
\newtheorem{prikl*}[prikl]{*Příklad}
\newtheorem*{priklad}{Příklad}
\renewcommand{\qedsymbol}{$\blacksquare$}
\newtheorem{pr}{Návodný příklad}[chapter]
\newtheorem*{hint}{Hint}
\theoremstyle{remark}
\newtheorem{pozn}[veta]{Poznámka}

\overfullrule=2cm

\let\WITHSOLUTION 0 % added \usepackage{verbatim}
\newenvironment{reseni}
{ \ifx\WITHSOLUTION 1 \begin{proof}[Řešení]\else \comment \fi }
{ \ifx\WITHSOLUTION 1 \end{proof}\else \endcomment \fi }

\newenvironment{ilpr}
{ \ifx\WITHSOLUTION 1 \begin{priklad}\else \comment \fi }
{ \ifx\WITHSOLUTION 1 \end{priklad}\else \endcomment \fi }

\begin{document}
\setcounter{chapter}{9}
\chapter*{Soustavy polynomiálních rovnic s~konečným počtem řešení}
\section*{Gröbnerova báze a Buchbergerův algoritmus}
%Budeme se zabývat problémem jak převést soustavu polynomiálních rovnic na ekvivalentní soustavu, kterou však bude možné řešit přímo (pokud umíme řešit polynom jedné proměnné vyššího stupně). Soustavu rovnic budeme uvažovat jako množinu polynomů a~naším cílem bude nalézt společnou množinu nulových bodů všech těchto polynomů. Nově získané ekvivalentní množině polynomů budeme říkat Gröbnerova báze, kterou budeme moci ještě upravit na tzv. redukovanou Gröbnerovu bázi, což je nejmenší (a jednoznačně daná) ekvivalentní množina s~původními polynomy. K~nalezení těchto bazí budeme využívat Buchbergerův algoritmus, který je zobecněním Gaussovy eliminace pro lineární systém rovnic. Gröbnerova báze pak odpovídá schodovitému tvaru a~redukovaná báze zase redukovanému schodovitému tvaru. Zásadním rozdílem je však to, že v~rámci algoritmu budeme naše bázové polynomy přinásobovat vhodnými monomy, což není invertibilní operace a může nám potenciálně zvětšit množinu řešení. Z~toho důvodu budeme nově vzniklé polynomy přidávat do již existující báze místo toho, aby jen nahradily polynomy již existující. Případnou redukci počtu polynomů budeme provádět až při přechodu na redukovanou bázi. Nicméně i~redukovaná Gröbnerova báze může obsahovat více polynomů než systém polynomů, ze kterého jsme vyšli.

%Gröbnerova báze i~algoritmus samotný potřebují zadat uspořádání na polynomech. Jak bylo zmíněno výše, báze nemusí obsahovat nejmenší možný počet polynomů, nicméně bude obsahovat co nejmenší polynomy v~daném uspořádání. Budeme proto využívat lexikografického uspořádání. Poznamenejme na závěr, že tento algoritmus může být potenciálně hodně časově náročný a~měl by se používat spíše jako poslední možnost. 

%Nyní budeme definovat několik pojmů, ukážeme si, jak funguje lexikografické uspořádání na polynomech, a popíšeme vlastní algoritmus.

\subsection*{Základní definice}
\begin{definice}
\begin{itemize}
\item \emph{Monomem} rozumíme polynom s~jediným členem, u něhož je koeficient 1.
\item Pro \emph{lexikografické uspořádání}, kde $x_1 > x_2 > \dots > x_n$ klademe 
\[
x_1^{a_1}x_2^{a_2}\dots x_n^{a_n} > x_1^{b_1}x_2^{b_2}\dots x_n^{b_n} \quad\Leftrightarrow\quad \exists i \in \{1,2,\dots,n\} ~ \forall j< i \colon \ce{a_j = b_j \wedge a_i > b_i}.
\]
\item Vedoucím monomem polynomu $f$ rozumíme monom, který se v~$f$ vyskytuje (s~nenulovým koeficientem) a~je největší v~daném uspořádání. Značíme $\LM f$.
\item Vedoucím koeficientem rozumíme (nenulový) koeficient u~vedoucího monomu. Značíme $\LC f$.
\item Vedoucím členem rozumíme součin vedoucího monomu s~vedoucím koeficientem. Značíme $\LT f$.
\item Nechť $f,g$ jsou polynomy. \emph{S-polynomem} polynomů $f,g$ rozumíme polynom daný předpisem
\[
S(f,g) = \frac{[\LM f, \LM g]}{\LT f}\cdot f - \frac{[\LM f, \LM g]}{\LT g}\cdot g,
\]
kde monom $[\LM f, \LM g]$ je nejmenší společný násobek vedoucích monomů polynomů $f$ a~$g$.
\end{itemize}
\end{definice}
%\begin{pozn}
%Lexikografické uspořádání, které jsme zavedli na monomech lze přirozeným způsobem rozšířit na polynomy. Nejprve porovnáme uspořádání vedoucích monomů, pokud jsou stejné, pokračujeme se stále menšími a~menšími monomy. Abychom se v~provádění operací v~algoritmu neztratili, budeme navíc vždy členy v~polynomu zapisovat od největšího k~nejmenšímu.
%
%Poznamenejme ještě, že pracujeme nad reálnými čísly, takže násobení nenulovou konstantou je invertibilní operace. Všechny bázové polynomy i~$S$-polynomy budeme proto moci vhodně vynásobit, aby se nám s~nimi lépe pracovalo.
%\end{pozn}
\begin{ilpr}
Uvažme polynomy
\[
f = 5x^2y - 16xy^{12} + 3xy^6z^{13}, \quad g = x^2z^3 - 2xy.
\]
Pak $\LT f = 5x^2y$, $\LM f = x^2t$, $\LC f = 5$.
\[
S(f,g) = \frac{x^2yz^3}{5x^2y} \cdot \ce{5x^2y - 16xy^{12} + 3xy^6z^{13}} - \frac{x^2yz^3}{x^2z^3} \cdot \ce{x^2z^3 - 2xy} = \frac15 z^3 f - yg.
\]
Vidíme, že $S$-polynom dává nejekonomičtější možnost, jak pronásobit polynomy $f,g$, aby měly stejný vedoucí člen, který po odečtení zmizí.
\end{ilpr}

\newpage %%%%% Odstranit po přidání zapoznámkovaných částí


\subsection*{Algoritmus}
Vstup: $f_1, \dots, f_r$\\
Výstup: Gröbnerova báze\\
\begin{enumerate}
\item Pro $i < j$ spočítáme $S(f_i, f_j)$.\label{alg1}
\item Pokud dostaneme nenulový polynom, budeme od něj postupně odečítat vhodné násobky bázových polynomů tak, abychom při každém odečtení přesně zrušili vedoucí člen. Pokud další odečtení není možné (tj. žádný vedoucí monom bázových polynomů nedělí vedoucí monom redukovaného polynomu) a~vzniklý polynom je nenulový, přidáme jej do báze.\label{alg2}
\item Provádíme postupně pro všechny dvojice $i<j$ (tedy počítáme $S$-polynomy i~pro ty nově přidané). Skončíme ve chvíli, kdy všechny $S$-polynomy jsme schopni pomocí bázových zredukovat na nulu.
\end{enumerate}

\begin{definice}
Výsledné množině polynomů budeme říkat \emph{Gröbnerova báze}. Řekneme navíc, že tato báze je \emph{redukovaná}, jestliže žádný monom libovolného polynomu není dělitelný vedoucím monomem jiného polynomu.
\end{definice}
%\begin{pozn}
%Klasická definice Gröbnerovy báze je o něco složitější, nicméně pro naše potřeby si s~předchozí definicí vystačíme. Definice redukované báze nám navíc dává návod na to, jak ji nalézt.
%\end{pozn}

\subsection*{Usnadnění výpočtu}
\begin{ilpr}
Uvažme
\[
f = x^2 + y + z, \quad g = y^2-y-z^2+z
\]
Počítejme $S$-polynom, který se poté budeme snažit redukovat
\begin{multline*}
S(f,g) = y^2 f - x^2 g = x^2y + x^2z^2 - x^2z + y^3 + y^2z \stackrel{-yf}{\leadsto}  x^2z^2 - x^2z + y^3 + y^2z - y^2 - yz \stackrel{-z^2f}{\leadsto}\\
\stackrel{-z^2f}{\leadsto} -x^2z + y^3 + y^2z - y^2 - yz^2 - yz - z^3 \stackrel{+zf}{\leadsto} y^3 + y^2z - y^2 - yz^2 - z^3 + z^2 \stackrel{-yg}{\leadsto}\\
\stackrel{-yg}{\leadsto} y^2z - yz - z^3 + z^2 \stackrel{-zg}{\leadsto} 0
\end{multline*}
Všimněme si, jaké úpravy jsme postupně dělali. Na začátku jsme měli $y^2f - x^2g$ a~postupně jsme upravovali do tvaru $gf - fg = 0$. Toto půjde udělat vždy, když jsou vedoucí monomy nesoudělné. Nelze však takto postupovat zcela obecně! V~rámci algoritmu totiž upravujeme $S$-polynom pomocí bázových výhradně tak, abychom vždy odstranili vedoucí člen.\\

Poznamenejme ještě, že i~různé volby, kterými bázovými polynomy redukujeme $S$-polynom mohou vést k~různým výsledkům (dokonce může být rozdíl, zda dostaneme nulový polynom či nikoli). Avšak ve chvíli, kdy máme Gröbnerovu bázi a~existuje nějaká posloupnost redukcí na nulový polynom, zredukuje jej na nulu každá jiná volba.
\end{ilpr}
V~rámci provádění algoritmu si můžeme práci usnadnit následujícím způsobem
\begin{itemize}
\item Pro každou dvojici $\ce{i,j}$ stačí počítat polynom $S(f_i,f_j)$ pouze jednou.
\item Pořadí, ve kterém počítáme $S$-polynomy není fixní. Volíme proto nejprve takové dvojice, aby byl příslušný $S$-polynom co možná nejmenší v~našem uspořádání (můžeme ušetřit desítky zbytečných polynomů v~neredukované bázi, čemuž odpovídá i~několik hodin práce, pokud počítáme pouze na papíře).
\item Mají-li polynomy nesoudělné vedoucí koeficienty, nemusíme počítat příslušný $S$-polynom. Po redukci pomocí polynomů, ze kterých byl $S$-polynom tvořen, nám vždy vyjde nula.
\item Pokud mají dva polynomy stejný vedoucí monom (tj. $S$-polynom vznikne jen jako jejich rozdíl s~případným vynásobením číselnou konstantou) a~některý z~nich jsme ještě nepoužili při žádné redukci, můžeme tento polynom z~báze zcela vyřadit a~dát místo něj příslušný $S$-polynom (respektive ten, který dostaneme po jeho redukci).
\item Pokud nám jde pouze o~hledání řešení soustavy, nepotřebujeme nutně (redukovanou) Gröbnerovu bázi, ale stačí nám, když obdržíme nějaký polynom o~jedné proměnné. Je-li množina řešení soustavy konečná, vždy po nějaké době dostaneme dostatečně malý polynom v~lexikografickém uspořádání, který bude polynomem o~jedné (té nejmenší) proměnné.
\end{itemize}

\newpage
\section*{Příklady}
\begin{prikl}
Nalezněte (redukovanou) Gröbnerovu bázi a~pomocí ní vyřešte soustavu
\begin{align*}
x^3 - 2xy &= 0,\\
x^2y + x - 2y^2 &= 0.
\end{align*}
\end{prikl}
\begin{reseni}
Položme
\begin{align*}
f_1 &= x^3 - 2xy,\\
f_2 &= x^2y + x - 2y^2.
\end{align*}
$
S(f_1,f_2) = yf_1 - xf_2 = -x^2
$
\[
f_3 = x^2
\]
$
S(f_1,f_3) = f_1 - xf_3 = -2xy
$
\[
f_4 = xy.
\]
$
S(f_2,f_4) = f_2 - xf_4 = x - 2y^2
$
\[
f_5 = x - 2y^2
\]
$
S(f_1,f_4) = yf_1 - x^2f_4 = -2xy^2 \stackrel{+2y f_4}{\leadsto} 0
$\\
$
S(f_4,f_5) = f_4 - yf_5 = 2y^3
$
\[
f_6 = y^3.
\]
Dá se ukázat, že již máme bázi. Redukovanou bází je pak
\[
\ce{f_5,f_6} = \ce{x-2y^2, y^3},
\]
nicémně pro řešení původní soustavy nám stačí původní polynomy $f_1, f_2$ a~polynom $f_6$. Z~$f_6$ vidíme, že nutně $y = 0$, což po dosazení do $f_1$ dá $x = 0$. Zřejmě je toto řešení soustavy (ověření je potřeba udělat buď pro původní soustavu nebo libovolnou Gröbnerovu bázi).\\

Jediné řešení soustavy je
\[
(x,y) = (0,0).
\]
\end{reseni}


\begin{prikl}
Řešte soustavu
\begin{alignat*}{4}
&x^2 &+ &y &+ &z  &= &1\\
&x&+&y^2&+&z &=&1\\
&x&+&y&+&z^2 &=&1
\end{alignat*}
\end{prikl}
\begin{reseni}
Položme
\begin{align*}
f_1 &= x^2 + y + z -1\\
f_2 &= x+y^2+z-1\\
f_3 &= x+y+z^2-1
\end{align*}
$
S(f_2,f_3) = f_2 - f_3 = y^2 - y  - z^2 + z
$\\
vidíme, že $S(f_2,f_3)$ vznikl jako rozdíl dvou polynomů přičemž žádný nebyl použit k redukci, proto například polynom $f_2$ můžeme vypustit z báze a nahradíme jej
\[
f_4 = y^2 - y  - z^2 + z
\]
Protože $f_4$ má nesoudělný vedoucí monom s~vedoucími monomy ostatních polynomů, nemusíme tyto $S$-polynomy počítat. Máme jedinou možnost výběru:
\begin{multline*}
S(f_1,f_3) = f_1 - xf_3 = -xy - xz^2 + x + y + z - 1 \stackrel{+yf_3}{\leadsto} -xz^2 + x + y^2 + yz^2 + z - 1 \stackrel{+z^2f_3}{\leadsto}\\
\stackrel{+z^2f_3}{\leadsto} x + y^2 + 2yz^2 + z^4 - z^2 + z - 1 \stackrel{-f_3}{\leadsto} y^2 + 2yz^2 - y + z^4 - 2z^2 + z \stackrel{-f_4}{\leadsto} 2yz^2 + z^4 - z^2
\end{multline*}
\[
f_5 = 2yz^2 + z^4 - z^2
\]
Díky nesoudělnosti máme opět jedinou možnost výběru
\begin{multline*}
2\cdot S(f_4,f_5) = 2z^2f_4 - yf_5 = -yz^4 - yz^2 - 2z^4 + 2z^3 \stackrel{+\frac12 z^2 f_5}{\leadsto} -yz^2 + \frac{z^6}{2} - \frac{5z^4}2 + 2z^3 \stackrel{+\frac12 f_5}{\leadsto}\\
\stackrel{+\frac12 f_5}{\leadsto} \frac12 \ce{z^6 - 4z^4 + 4z^3 - z^2}
\end{multline*}
\[
f_6 = z^6 - 4z^4 + 4z^3 - z^2 = z^2 \cdot (z-1)^2 \cdot (z^2+2z-1)
\]
Dostáváme kořeny polynomu $f_6$. Víme tedy, že $z \in \{0,1,-1\pm\sqrt2\}$.
\begin{itemize}
\item Dosazením $z = 0$ do $f_4$ dostáváme, že $y \in \{0,1\}$. To dosazením do $f_3$ dá řešení $(1,0,0)$ a $(0,1,0)$.
\item Dosazení $z = 1$ do $f_5$ dá $y = 0$, což po dosazení do $f_3$ dá řešení $(0,0,1)$.
\item Dosazením $-1\pm\sqrt2$ do $f_5$ a výsledku do $f_3$ dostáváme řešení $(-1\pm\sqrt2,-1\pm\sqrt2,-1\pm\sqrt2)$.
\end{itemize}
\end{reseni}


\begin{prikl}
Řešte soustavu
\begin{alignat*}{4}
&x^2 &+&y^2&+&z&= &2\\
&x&+&y^2&+&z^2 &=&2\\
&x^2&+&y&+&z^2 &=&2
\end{alignat*}
\end{prikl}
\begin{reseni}
Položme
\begin{align*}
f_1 &= x^2 + y^2 + z -2\\
f_2 &= x+y^2+z^2-2\\
f_3 &= x^2+y+z^2-2
\end{align*}
$
S(f_1,f_3) =f_1-f_3 = y^2 - y - z^2 + z
$\\
přitom polynom $f_1$ odstraníme z~báze.
\[
f_4 = y^2 - y - z^2 + z
\]
\begin{multline*}
S(f_2,f_3) = xf_2 - f_3 = xy^2 + xz^2 - 2x - y - z^2 + 2 \stackrel{-y^2f_2}{\leadsto} xz^2 - 2x - y^4 - y^2z^2 + 2y^2 - y -z^2 + 2 \stackrel{-z^2f_2}{\leadsto}\\
\stackrel{-z^2f_2}{\leadsto} -2x - y^4 - 2y^2z^2 + 2y^2 - y - z^4 + z^2 + 2 \stackrel{+2f_2}{\leadsto} -y^4 - 2y^2z^2 + 4y^2- y - z^4 + 3z^2 - 2 \stackrel{+y^2f_4}{\leadsto}\\
\stackrel{+y^2f_4}{\leadsto} -y^3 - 3y^2z^2 + y^2z + 4y^2 - y -z^4 + 3z^2 - 2 \stackrel{+yf_4}{\leadsto}\\
\stackrel{+yf_4}{\leadsto} -3y^2z^2 + y^2z + 3y^2 - yz^2 + yz - y - z^4 + 3z^2 - 2 \stackrel{+3z^2f_4}{\leadsto}\\
\stackrel{+3z^2f_4}{\leadsto} y^2z + 3y^2 - 4yz^2 + yz - y - 4z^4 + 3z^3 + 3z^2 - 2 \stackrel{-zf_4}{\leadsto}\\
\stackrel{-zf_4}{\leadsto} 3y^2 - 4yz^2 + 2yz - y - 4z^4 + 4z^3 + 2z^2 - 2 \stackrel{-3f_4}{\leadsto}\\
\stackrel{-3f_4}{\leadsto} -4yz^2 + 2yz + 2y - 4z^4 + 4z^3 + 5z^2 - 3z - 2
\end{multline*}
\[
f_5 = 4yz^2 - 2yz - 2y + 4z^4 - 4z^3 - 5z^2 + 3z + 2
\]
\begin{multline*}
4\cdot S(f_4,f_5) = 4z^2f_4 - yf_5 = 2y^2z + 2y^2 - 4yz^4 + 4yz^3 + yz^2 - 3yz - 2y - 4z^4 + 4z^3 \stackrel{-2zf_4}{\leadsto}\\
\stackrel{-2zf_4}{\leadsto} 2y^2 - 4yz^4 + 4yz^3 + yz^2 - yz - 2y - 4z^4 + 6z^3 - 2z^2 \stackrel{-2f_4}{\leadsto}\\
\stackrel{-2f_4}{\leadsto} -4yz^4 + 4yz^3 + yz^2 - yz - 4z^4 + 6z^3 - 2z \stackrel{+z^2f_5}{\leadsto}\\
\stackrel{+z^2f_5}{\leadsto} 2yz^3 - yz^2 - yz + 4z^6 - 4z^5 - 9z^4 + 9z^3 + 2z^2 - 2z \stackrel{-\frac12 zf_5}{\leadsto}\\
\stackrel{-\frac12 zf_5}{\leadsto} 4z^6 - 6z^5 - 7z^4 + \frac{23}{2}z^3 + \frac12 z^2 - 3z
\end{multline*}
\[
f_6 = 8z^6 - 12z^5 - 14z^4 + 23z^3 + z^2 - 6z
\]
přitom odštěpením racionálních kořenů dostáváme rozklad
\[
f_6 = z \cdot (z-1) \cdot (2z + 1) \cdot (2z - 3) \cdot (2z^2 + z - 2).
\]
Dostáváme tedy kořeny $z \in \left\{0,1,-\frac12, \frac32, \frac{-1\pm\sqrt{17}}4\right\}$. Dosaďme
\begin{gather*}
f_5(y,0) = 2-2y,\quad f_5\ce{y,1} = 0, \quad f_5\ce{y,-\frac12} = 0,\\
f_5\ce{y,\frac32} = 4y+2, \quad f_5\ce{y,\frac{-1\pm\sqrt{17}}4} = y\ce{3 \mp \sqrt{17}} + \ce{5\mp\sqrt{17}}.
\end{gather*}
Hodnoty $z = $ a~$z = -\frac12$ je potřeba dosadit do $f_4$:
\[
f_4(y,1) = y^2-y, \quad f_4\ce{y,-\frac12} = y^2-y-\frac34.
\]
Dostáváme přípustné dvojice
\[
\ce{y,z} \in \left\{\ce{0,1},\ce{1,0},\ce{1,1},\ce{-\frac12,-\frac12},\ce{\frac32,-\frac12},\ce{-\frac12,\frac32},\ce{\frac{-1\pm\sqrt{17}}4, \frac{-1\pm\sqrt{17}}4} \right\}.
\]
Dosadíme do $f_2$, což je polynom vždy lineární v~$x$ a~dostáváme množinu řešení
\begin{gather*}
\ce{\frac{-1+\sqrt{17}}4,\frac{-1+\sqrt{17}}4,\frac{-1+\sqrt{17}}4},\ce{\frac{-1-\sqrt{17}}4,\frac{-1-\sqrt{17}}4,\frac{-1-\sqrt{17}}4},\\
\ce{-\frac12,-\frac12,\frac32},\ce{-\frac12,\frac32,-\frac12}, \ce{\frac32,-\frac12,-\frac12},\ce{1,1,0},\ce{1,0,1},\ce{0,0,1}.
\end{gather*}
\end{reseni}
%%%%% Alternativní řešení ve 3. kapitole, 1. soutěžní příklad -  Matematická liga 2014/2015


\begin{prikl}
Dokažte, že nulové body původních (zadaných) polynomů a~polynomů Gröbnerovy (respektive redukované Gröbnerovy) báze jsou stejné. Tedy soustava vzniklá z~nalezené báze je ekvivalentní soustavě původní.
\end{prikl}
\begin{reseni}
Protože nově přidané polynomy získáváme jako kombinace polynomů původních vynásobené nějakými polynomy, jistě budou mít takové polynomy stejné nulové body jako původní soustava. Mohou mít nějaké nulové body navíc. Protože však při generování Gröbnerovy báze Buchbergerovým algoritmem polynomy pouze přidáváme, nemůže se nám množina řešení zvětšit. Proto výsledná soustava má stejné řešení jako soustava původní.\\

Označme $f_j$ polynomy Gröbnerovy báze a~$g_i$ polynomy redukované Gröbnerovy báze. Protože pomocí redukované Gröbnerovy báze můžeme vyjádřit libovolný polynom báze původní (a~jistě i~naopak, vždyť tak redukovanou bázi konstruujeme), existují polynomy $r_j$ a $s_i$ takové, že
\begin{align*}
g_i = \sum f_j \cdot r_j,\\
f_j = \sum g_i \cdot s_i.
\end{align*}
Buď $p$ společný nulový bod původní báze, pak
\[
g_i(p) = \sum\underbrace{f_j(p)}_{=0} \cdot r_j(p) = 0,
\]
tedy $p$ je společný nulový bod i~redukované báze. Stejnou úvahou dostáváme, že to platí i~opačně. Tedy řešení původního systému jsou právě řešení systému vzniklého z~Gröbnerovy báze a~to jsou právě řešení systému vzniklého z~redukované Gröbnerovy báze.
\end{reseni}



\begin{prikl*}
Řešte soustavu
\begin{align*}
xy + yz &= 1,\\
yz + zw &= 1,\\
zw + wx &= 1,\\
wx + xy &= 1
\end{align*}
\end{prikl*}
\begin{reseni}
Budeme uvažovat uspořádání $w>x>y>z$. Protože rovnice jsou lineárně závislé (máme $1.+3. = 2.+4.$), můžeme jednu z nich vypustit. Jelikož třetí rovnice je v~tomto uspořádání největší, vypustíme právě tuto. Položme proto
\begin{gather*}
f_1 = xy+yz-1,\\
f_2 = wz+yz - 1,\\
f_3 = wx+xy-1.
\end{gather*}
Vidíme, že $S(f_1,f_2)$ nemá smysl počítat, neboť vedoucí koeficienty těchto polynomů jsou nesoudělné. Zkusme proto\\
$
S(f_2,f_3) = xf_2 - zf_3 = -x+z
$
\[
f_4 = x-z
\]
$
S(f_1,f_3) = wf_1 - yf_3 =  wyz - w - xy^2 + y \stackrel{-yf_2}{\leadsto} -w-xy^2-y^2z+2y
$
\[
f_5 = w+xy^2+y^2z-2y
\]
$
S(f_1,f_4) = f_1 - yf_4 = 2yz-1
$
\[
f_6 = 2yz - 1
\]
$
2\cdot S(f_1,f_6) = 2zf_1 - xf_6 = x+2yz^2-2z \stackrel{-f_4}{\leadsto} 2yz^2 - z \stackrel{-zf_6}{\leadsto} 0
$\\
Nyní máme spočítané všechny $S$-polynomy, kde vystupuje $f_1$. Pro $f_2$ máme $S(f_2,f_3)$ a~jediný další polynom s~nesoudělným vedoucím koeficientem dává\\
$
S(f_2,f_5) = f_2 - zf_5 = -xy^2z - y^2z^2 + 3yz - 1 \stackrel{+yzf_1}{\leadsto} 2yz-1 \stackrel{-f_6}{\leadsto} 0.
$\\
Pro $f_3$ má smysl uvažovat\\
$
S(f_3,f_4) = f_3 - wf_4 = wz+xy - 1 \stackrel{-f_2}{\leadsto} xy-yz \stackrel{-yf_4}{\leadsto} 0,
$\\
$
S(f_3, f_5) = f_3 - xf_5 = -x^2y^2 - xy^2z + 3xy-1 \stackrel{+xyf_1}{\leadsto}2xy - 1 \stackrel{-2f_1}{\leadsto} -2yz+1 \stackrel{+f_6}{\leadsto}0.
$\\
Pro další polynomu již nemusíme počítat nic. Máme tedy Gröbnerovu bázi. Nyní ji budeme redukovat. Pro přehlednost označme nalezené polynomy redukované báze $g_i$.\\
Berme postupně co nejmenší polynomy v~lexikografickém uspořádání. Polynomy $f_6$ a~$f_4$ jsou jistě v pořádku. Položme proto
\begin{align*}
g_1 &= 2yz - 1,\\
g_2 &= x-z.
\end{align*}
Polynom $f_1$ má vedoucí člen dělitelný $\LM g_2$ a~člen $yz$ dělitelný $\LM g_1$, proto\\
$
f_1 = xy+yz-1 \stackrel{-yg_2}{\leadsto} 2yz - 1 \stackrel{-g_1}{\leadsto} 0
$\\
Další polynom v~našem uspořádání je $f_5$. Počítejme\\
$
f_5 = w+xy^2+y^2z-2y \stackrel{-y^2g_2}{\leadsto} w + 2y^2z - 2y \stackrel{-yg_1}{\leadsto} w-y
$
\[
g_3 = w-y
\]
$
f_2 = wz+yz-1 \stackrel{-zg_3}{\leadsto} 2yz - 1 \stackrel{-g_1}{\leadsto} 0
$\\
A konečně\\
$
f_3 = wx+xy-1 \stackrel{-xg_3}{\leadsto} 2xy-1 \stackrel{-2yg_2}{\leadsto} 2yz-1 \stackrel{-g_1}{\leadsto} 0.
$\\
Dostáváme tedy redukovanou Gröbnerovu bázi tvořenou polynomy
\[
2yz - 1, \quad x-z, \quad w-y.
\]
Vidíme, že $x = z$, $y=w$ a $yz = \frac12$, proto řešení je
\[
\ce{\frac{1}{2t},t,\frac{1}{2t},t} \quad t \in \R \setminus \{0\}.
\]
\end{reseni}
\end{document}