Príklad na symetrické polynómy
Posted: Tue May 07, 2013 9:40 am
Toto je presne príklad, ktorý sme robili včera na cviku.
Dávam ho sem hlavne ako zámienku na to, aby som pripomenul, že sa oplatí vždy si vyskúšať, či výsledok (a medzivýsledky) fungujú pre nejaké konkrétne hodnoty. (Pretože pri tomto type výpočtov sa dá ľahko pomýliť.) Mal som to spomenúť včera na cviku, nejako som na to zabudol.
Úloha: Vyjadriť pomocou základných symetrických polynómov:
$f(x_1,x_2,x_3)=\sum x_1^3x_2=x_1^3x_2+x_1x_2^3+x_1^3x_3+x_1x_3^3+x_2^3x_3+x_2x_3^3$.
Pre 3 premenné máme 3 základné symetrické polynómy.
$$\begin{align*}
A_1&=x_1+x_2+x_3\\
A_2&=x_1x_2+x_1x_3+x_2x_3\\
A_3&=x_1x_2x_3
\end{align*}$$
Riešenie metódov neurčitých koeficientov.
Pretože $f$ je homogénny polynóm stupňa 4, stačí nám skúšať homogénne polynómy. Ďalej vieme, že nemusíme používať $A_1^4$, keďže tento polynóm má vedúci člen v lexikografickom usporiadaní vyšší ako $x_1^3x_2$. Dokonca vieme, že vedúci člen vznikne z $A_1^2A_2$, teda tento polynóm sa bude vo vyjadrení vyskytovať s koeficientom $1$. (Rovnaký koeficient ako má vedúci člen.)
Hľadáme teda $b$ a $c$ tak, aby platilo:
$$f=A_1^2A_2+bA_2^2+cA_1A_3.$$
Keď za $(x_1,x_2,x_3)$ dosadíme $(1,1,1)$ a $(1,1,0)$, tak dostaneme sústavu
$$\begin{align*}
6&=27+9b+3c,\\
2&=4+b,
\end{align*}$$
ktorej riešením získame $b=-2$ a $c=-1$.
Teda
$$f=A_1^2A_2-2A_2^2-A_1A_3.$$
Riešenie pomocou algoritmu z dôkazu.
Ak chceme dostať ako vedúci člen $x_1^3x_2$, tak použijeme $A_1^2A_2$. Skúsme to roznásobiť
$$\begin{align*}
A_1^2A_2&=(x_1+x_2+x_3)^2(x_1x_2+x_1x_3+x_2x_3)\\
&=(x_1^2+x_2^2+x_3^2+2x_1x_2+2x_1x_3+2x_2x_3)(x_1x_2+x_1x_3+x_2x_3)\\
&=\sum x_1^3x_2 + 2\sum x_1^2x_2^2+5\sum x_1^2x_2x_3
\end{align*}$$
Poznámka. Keďže pri takýchto úpravách sa dá vcelku ľahko pomýliť, možno sa oplatí vždy po takomto kroku skúsiť dosadiť zopár konkrétnych hodnôt, pre ktoré sa obe strany zrátajú ľahko. Keď vyskúšame niekoľko možností pre $x_1$, $x_2$, $x_3$, je veľmi pravdepodobné, že nájdeme chybu.
Napríklad ak vyskúšame $x_1=x_2=x_3=1$, tak $A_1=A_2=3$ a ľavá strana je $27$. Na pravej strane dostaneme $6+2\cdot 3+5\cdot 3=27$. (Ďalšie možnosti, kde sa hodnoty $A_1$, $A_2$, $A_3$ vyrátajú vcelku ľahko, sú napríklad $(1,1,0)$, $(1,0,0)$.)
Teraz by sme radi našli niečo, čo má vedúci člen $x_1^2x_2^2$. Máme
$$A_2^2=(x_1x_2+x_1x_3+x_2x_3)^2=\sum x_1^2x_2^2 + 2\sum x_1^2x_2x_3.$$
Podobne môžeme zrátať
$$A_1A_3=(x_1+x_2+x_3)x_1x_2x_3=\sum x_1^2x_2x_3.$$
Teraz už stačí tieto pomocné výpočty spojiť dokopy a dostaneme
$$f=A_1^2A_2-2A_2^2-A_1A_3.$$
Dávam ho sem hlavne ako zámienku na to, aby som pripomenul, že sa oplatí vždy si vyskúšať, či výsledok (a medzivýsledky) fungujú pre nejaké konkrétne hodnoty. (Pretože pri tomto type výpočtov sa dá ľahko pomýliť.) Mal som to spomenúť včera na cviku, nejako som na to zabudol.
Úloha: Vyjadriť pomocou základných symetrických polynómov:
$f(x_1,x_2,x_3)=\sum x_1^3x_2=x_1^3x_2+x_1x_2^3+x_1^3x_3+x_1x_3^3+x_2^3x_3+x_2x_3^3$.
Pre 3 premenné máme 3 základné symetrické polynómy.
$$\begin{align*}
A_1&=x_1+x_2+x_3\\
A_2&=x_1x_2+x_1x_3+x_2x_3\\
A_3&=x_1x_2x_3
\end{align*}$$
Riešenie metódov neurčitých koeficientov.
Pretože $f$ je homogénny polynóm stupňa 4, stačí nám skúšať homogénne polynómy. Ďalej vieme, že nemusíme používať $A_1^4$, keďže tento polynóm má vedúci člen v lexikografickom usporiadaní vyšší ako $x_1^3x_2$. Dokonca vieme, že vedúci člen vznikne z $A_1^2A_2$, teda tento polynóm sa bude vo vyjadrení vyskytovať s koeficientom $1$. (Rovnaký koeficient ako má vedúci člen.)
Hľadáme teda $b$ a $c$ tak, aby platilo:
$$f=A_1^2A_2+bA_2^2+cA_1A_3.$$
Keď za $(x_1,x_2,x_3)$ dosadíme $(1,1,1)$ a $(1,1,0)$, tak dostaneme sústavu
$$\begin{align*}
6&=27+9b+3c,\\
2&=4+b,
\end{align*}$$
ktorej riešením získame $b=-2$ a $c=-1$.
Teda
$$f=A_1^2A_2-2A_2^2-A_1A_3.$$
Riešenie pomocou algoritmu z dôkazu.
Ak chceme dostať ako vedúci člen $x_1^3x_2$, tak použijeme $A_1^2A_2$. Skúsme to roznásobiť
$$\begin{align*}
A_1^2A_2&=(x_1+x_2+x_3)^2(x_1x_2+x_1x_3+x_2x_3)\\
&=(x_1^2+x_2^2+x_3^2+2x_1x_2+2x_1x_3+2x_2x_3)(x_1x_2+x_1x_3+x_2x_3)\\
&=\sum x_1^3x_2 + 2\sum x_1^2x_2^2+5\sum x_1^2x_2x_3
\end{align*}$$
Poznámka. Keďže pri takýchto úpravách sa dá vcelku ľahko pomýliť, možno sa oplatí vždy po takomto kroku skúsiť dosadiť zopár konkrétnych hodnôt, pre ktoré sa obe strany zrátajú ľahko. Keď vyskúšame niekoľko možností pre $x_1$, $x_2$, $x_3$, je veľmi pravdepodobné, že nájdeme chybu.
Napríklad ak vyskúšame $x_1=x_2=x_3=1$, tak $A_1=A_2=3$ a ľavá strana je $27$. Na pravej strane dostaneme $6+2\cdot 3+5\cdot 3=27$. (Ďalšie možnosti, kde sa hodnoty $A_1$, $A_2$, $A_3$ vyrátajú vcelku ľahko, sú napríklad $(1,1,0)$, $(1,0,0)$.)
Teraz by sme radi našli niečo, čo má vedúci člen $x_1^2x_2^2$. Máme
$$A_2^2=(x_1x_2+x_1x_3+x_2x_3)^2=\sum x_1^2x_2^2 + 2\sum x_1^2x_2x_3.$$
Podobne môžeme zrátať
$$A_1A_3=(x_1+x_2+x_3)x_1x_2x_3=\sum x_1^2x_2x_3.$$
Teraz už stačí tieto pomocné výpočty spojiť dokopy a dostaneme
$$f=A_1^2A_2-2A_2^2-A_1A_3.$$