2: Polynomy

Polynomy, Vandermondova matice, Lagrangeova interpolace

definuj: polynom

Polynom stupně n v proměnné x nad tělesem T je výraz p(x) = a_nxⁿ + a_n−1xⁿ⁻¹ + · · · + a₂x² + a₁x + a0, kde a_n ≠ 0 a a_n, . . . , a₀∈T. Píšeme p ∈ T(x).

definuj: operace s polynomy

polynomy $p\left(x\right)=\sum_{i=0}^{n}a_{i}x^{i},q\left(x\right)=\sum_{i=0}^{m}b_{i}x^{i}$

• sčítání, odečítání: $\left(p\pm q\right)\left(x\right)=\sum_{i=0}^{\max\left\lbrace n,m\right\rbrace}\left(a_{i}\pm b_{i}\right)x^{i}$

• skalární násobek pro $t\in T:\left(tp\right)\left(x\right)=\sum_{i=0}^{n}\left(ta_{i}\right)x^{i}$

• součin $\left(pq\right)\left(x\right)=\sum_{i=0}^{n+m}c_{i}x^{i}$ , kde $c_{i}=\sum_{j=0}^{i}a_{j}b_{i-j}$

• dělení se zbytkem — existují jedinečné polynomy s,r ∈ T(x) takové, že p = qs + r, kde stupeň r je menší než stupeň q.

definuj: kořen polynomu

Kořen polynomu p ∈ T(x) je r ∈ T takové, že p(r) = 0.

Pozorování: Prvek r ∈ T je kořenem polynomu p, právě když lineární dvoučlen x − r dělí p beze zbytku.

definuj: násobnost kořene

Násobnost kořene r z p∈T(x) je největší kladné celé číslo k takové, že (x − r)^k dělí p.

zformuluj větu: Malá Fermatova věta

.

Vyslovte a dokažte malou Fermatovu větu (6/8).

Pro prvočíslo p a každé a∈{1,...,p−1} platí a^p−1 ≡ 1 (mod p).

dokaž větu: Malá Fermatova věta:

Pro prvočíslo p a každé a∈{1,...,p−1} platí a^p−1 ≡ 1 (mod p).

.

Vyslovte a dokažte malou Fermatovu větu (6/8).

Zobrazení f_a : x→ax je v Z_p bijekcí na {1,...,p−1}.

Proto v Z_p platí:

$$\prod_{x=1}^{p-1}x=\prod_{x=1}^{p-1}f_{a}\left(x\right)=\prod_{x=1}^{p-1}ax=a^{p-1}\prod_{x=1}^{p-1}x$$

$\prod_{x=1}^{p-1}x=a^{p-1}\prod_{x=1}^{p-1}x$ lze zkrátit na 1 = a^p−1

zformuluj větu: základní věta algebry

Každý polynom p ∈ C(x) mí alespoň jeden kořen.

Důsledek: Každý polynom p ∈ C(x) lze rozložit na součin lineárních faktorů, t.j. na polynomy prvního stupně.

definuj: algebraicky uzavřené těleso

Pokud každý polynom p ∈ T(x) stupně alespoň jedna má alespoň jeden kořen, pak je těleso T algebraicky uzavřené.

definuj: reprezentace polynomů stupně n

• koeficienty a₀, . . . ,a_n

• v algebraicky uzavřených tělesech pomocí koeficientu a_n a n kořenů r₁, . . . ,r_n

• hodnotami polynomu v n + 1 různých bodech

definuj: Vandermondova matice

Problém: Dáno n + 1 dvojic (x_i , y_i) pro i = 0, . . . , n, určete p ∈ T(x) stupně nejvýše n takový, že p(x_i) = y_i pro každé i.

Pozorování: Koeficienty a₀, . . . , a_n z p jsou řešením soustavy: $\begin{pmatrix}1 & x_0 & x_0^2 & \cdots & x_0^n \\1 & x_1 & x_1^2 & \cdots & x_1^n \\\vdots & \vdots & \vdots & \ddots & \vdots \\1 & x_n & x_n^2 & \cdots & x_n^n \\\end{pmatrix}\begin{pmatrix}a_0 \\a_1 \\\vdots \\a_n \\\end{pmatrix}=\begin{pmatrix}y_0 \\y_1 \\\vdots \\y_n \\\end{pmatrix}$

Definice: Matice této soustavy je Vandermondova matice V_n+1(x₀, . . . , x_n)

zformuluj větu: o Vandermondově matici

.

Vyslovte a dokažte větu o Vandermondově matici (6/10).

Vandermondova matice V_n+1(x₀, . . . , x_n) je regulární, právě když x₀, . . . , x_n jsou navzájem různá.

dokaž větu: Vandermondova matice V_n+1(x₀, . . . , x_n) je regulární, právě když x₀, . . . , x_n jsou navzájem různá.

.

Vyslovte a dokažte větu o Vandermondově matici (6/10).

\det\big(V_{n+1}(x_0, \ldots, x_n)\big) = \det\big(V_n(x_1, \ldots, x_n)\big) \prod_{i=1}^n (x_i - x_0) = \prod_{i < j} (x_j - x_i)

zformuluj: Lagrangeova interpolace

.

Uveďte a dokažte správnost Lagrangeovy interpolace (8/10).

1) Určíme n + 1 pomocných polynomů $p_0,\ldots,p_{n}$ stupně n:

$$p_{i}(x)=\frac{(x - x_0) \cdots(x - x_{i-1})(x - x_{i+1}) \cdots(x - x_n)}{(x_i - x_0) \cdots(x_i - x_{i-1})(x_i - x_{i+1}) \cdots(x_i - x_n)}=\frac{\prod_{{j\neq i}}^{n}x-x_{j}}{\prod_{{j\neq i}}^{n}x_{i}-x_{j}}.$$

2) Hledaný polynom p(x) získáme lineární kombinací:

$$p(x)=\sum_{i=0}^{n}y_{i}p_{i}(x)$$

dokaž: Lagrangeova interpolace

1) Určíme n + 1 pomocných polynomů $p_0,\ldots,p_{n}$ stupně n:

$$p_{i}(x)=\frac{(x - x_0) \cdots(x - x_{i-1})(x - x_{i+1}) \cdots(x - x_n)}{(x_i - x_0) \cdots(x_i - x_{i-1})(x_i - x_{i+1}) \cdots(x_i - x_n)}=\frac{\prod_{{j\neq i}}^{n}x-x_{j}}{\prod_{{j\neq i}}^{n}x_{i}-x_{j}}.$$

2) Hledaný polynom p(x) získáme lineární kombinací:

$$p(x)=\sum_{i=0}^{n}y_{i}p_{i}(x)$$

.

Uveďte a dokažte správnost Lagrangeovy interpolace (8/10).

Pomocné polynomy splňují:

$$p_{i}(x_{i})=1\quad\text{a pro}\quad i\neq j:\quad p_{i}(x_{j})=0$$

Potom platí:

$$p(x_{j})=\sum_{i=0}^{n}y_{i}p_{i}(x_{j})=y_{j}p_{j}(x_{j})=y_{j},$$

protože ve všech ostatních sčítancích je $p_{i}(x_{j})=0$