Polynome

Arithmetik, Nullstellen, Approximation.

Ein Polynom $p\in\mathbb{K}[x]$ über einen Körper $\mathbb{K}$ und eine Variable $x$ ist ein Ausdruck der Form

$$\sum_{i=0}^n a_ix_i=a_nx^n+a_{n-1}x^{n-1}+\ldots+a_1x+a_0,$$

wobei die Koeffizienten $a_0,\ldots,a_n\in\mathbb{K}$ sind. Der Grad eines solchen Polynoms ist das $i\neq 0$ des größten Koeffizienten ungleich 0. (Der Grad des Nullpolynoms wird als -1 definiert.)

Polynomfunktionen sind Funktionen der Form $$p(x)=\sum_{i=0}^n a_ix_i=a_nx^n+a_{n-1}x^{n-1}+\ldots+a_1x+a_0.$$

Jedes Polynom liefert also eine Polynomfunktion $f:\mathbb{R}\to\mathbb{R}$ . Für alle $r\in\mathbb{K}$ ist $p(r)$ das Resultat davon, $r$ in $p$ einzusetzen (d.h. $p(r) = \sum_{i=0}^n a_ir^i$ ).

Arithmetische Operationen

many of our algorithms apply (with small modifications) to both the integer and polynomial cases: multiplication, division with remainder, gcd and Chinese remainder computation. (Aber nicht: Faktorisierung)

Polynome können wie ganze Zahlen addiert, subtrahiert und multipliziert werden. Das Ergebnis ist erneut ein Polynom.

Addition

Die Addition erfolgt komponentenweise.

Multiplikation

Das Produkt zweier Polynome $p=\sum_{i=0}^n a_ix_i$ und $q=\sum_{i=0}^m b_ix_i$ in $\mathbb{K}[x]$ ist definiert durch: $$pq=\sum_{k=0}^{m+n}c_kx^k$$ Mit den Koeffizienten: $$c_k=\sum_{\mathclap{0\leq i\leq n,\, 0\leq j\leq m,\, i+j=k}}a_ib_j$$ Zum Beispiel:

$c_0 = a_0b_0$
$c_1 = a_0b_1 + a_1b_0$
$c_2 = a_0b_2 + a_1b_1 + a_2b_0$
$\ldots$ (Denn für alle $a_ib_j$ mit $i+j=k$ ist der variable Term $x^k$ .)

Dabei gilt $\text{Grad}(pq) = \text{Grad}(p) + \text{Grad}(q)$ .

Faktorisierung

Polynome können äquivalent umgeformt werden als Produkt von Polynomen. Zum Beispiel:

$x^2-a^2=(x+a)(x-a)$
$x^3-2x^2-x+1=(x-2)(x+1)(x-1)$

Division mit Rest

Im Gegensatz zu Addition, Subtraktion und Multiplikation von Polynomen, ergibt die Division von Polynomen nicht notwendig wieder ein Polynom. Z.B. ist $\frac{p}{q}=\frac{1}{x}$ für $p=1$ und $q=x$ kein Polynom. Es gibt aber eindeutig bestimmte Polynome $s,r$ , so dass $$p=sq+r$$ mit $\text{Grad}(r)<\text{Grad}(q)$ . Hier ist ein Algorithmus, um $s,r$ zu bestimmen:

function euclidian_division(p, q)
  s = 0;
  r = p;
  d = degree(q);
  c = leading_coefficient(q);

  while degree(r) >= d
    t = leading_coefficient(r)/c * x^(degree(r) - d);
    s = s + t;
    r = r - t * q;
  end

  return (s, r);
end

Den größten gemeinsamen Teiler zweier Polynome erhält man dann durch wiederholte Division, bis der Rest 0 ist:

function gcd(p1, p2)
  (q, r) = euclidian_division(p1, p2);

  # Which means:
  # p1 = q * p2 + r

  if (r == 0)
    return q;
  else
    return gcd(r, q);
  end
end

Algebraischer Abschluss

Ein Körper $K$ heißt algebraisch abgeschlossen, wenn jedes nicht-konstante Polynom $p\in \mathbb{K}[T]$ (d.h. jedes Polynom in $\mathbb{K}[T]\backslash\mathbb{K}$ ) eine Nullstelle in $K$ besitzt. Das ist äquivalent dazu, dass es in Linearfaktoren zerfällt (d.h. es gibt $a,z_1,\ldots,z_n\in\mathbb{K}$ , so dass $p = a(T-z_1)\cdots(T-z_n)$ ), denn hat ein Polynom eine Nullstelle $a$ , so ist es ohne Rest durch $T-a$ teilbar.

Komposition

Nullstellen

Ein Polynom $n$ -ten Grades hat höchstens $n$ Nullstellen. $r$ ist eine Nullstelle genau dann, wenn $(x-r)$ ein Faktor des Polynoms ist. D.h. wenn $r_1,\ldots,r_n$ die Nullstellen des Polynoms $p(x)$ sind, ist
$$p(x)=a_n(x-r_n)(x-r_{n-1})\cdots(x-r_2)(x-r_1)q(x)$$ eine Faktorisierung des Polynoms (wobei $q(x)$ wieder ein Polynom ist).

Gleichungen

Approximation mit Polynomen