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.)

Das Polynom heißt normiert, wenn $a_n=1$ ist.

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

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)$ .

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

Ein Polynom ist irreduzibel, wenn es sich nicht als Produkt zweier Polynome schreiben lässt. Für Polynome über Körpern gilt:

Polynome vom Grad 1 sind irreduzibel.
In einem algebraisch abgeschlossenen Körper (z.B. $\mathbb{C}$ ) haben alle irreduziblen Polynome Grad 1.
In $\mathbb{R}$ haben alle irreduziblen Polynome Grad 1 oder 2. (Weil der algebraische Abschluss $\mathbb{C}$ den Grad 2 über $\mathbb{R}$ hat.)
In anderen Körpern sind Polynome vom Grad 2 oder 3 dann irreduzibel, wenn sie keine Nullstellen haben.

Komposition

Nullstellen und Faktorisierung

Zu jedem normierten Polynom

$$p(x) = x^n+a_{n-1}x^{n-1}+\ldots+a_1x+a_0$$

gibt es eindeutig bestimmte Zahlen $\lambda_1,\ldots,\lambda_n\in\mathbb{C}$ , so dass das Polynom äquivalent in seine Linearfaktorzerlegung umgeformt werden kann:

$$p(x) = (x-\lambda_1)\cdots(x-\lambda_n)$$

Das sind genau die Nullstellen des Polynoms, d.h. für jedes $\lambda$ gilt:

$$p(\lambda) = \lambda^n+a_{n-1}\lambda^{n-1}+\ldots+a_1\lambda+a_0 = 0$$

D.h. $\lambda$ ist eine Nullstelle genau dann, wenn $(x-\lambda)$ ein Faktor des Polynoms ist.

Die Nullstellen müssen nicht verschieden sein, ein Polynom $n$ -ten Grades hat also höchstens $n$ Nullstellen. Wie oft eine Nullstelle in einem Faktor vorkommt, nennt man ihre Vielfachheit.

Vor allem müssen die Nullstellen nicht reell sein, d.h. in $\mathbb{R}$ kann es sein, dass eine Faktorisierung nur unvollständig möglich ist: Ist $r$ eine reelle Nullstelle des Polynoms $p(x)$ , dann ist $p(x)=(x-r)q(x)$ eine Faktorisierung des Polynoms (wobei $q(x)$ wieder ein Polynom ist).

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

Fundamentalsatz der Algebra: $\mathbb{C}$ ist algebraisch abgeschlossen.

( $\mathbb{N},\mathbb{Z}, \mathbb{Q},\mathbb{R}$ sind alle nicht algebraisch abgeschlossen. Z.B. hat das Polynom $x^2 + 1$ in keinem dieser Körper eine Nullstelle, weil $x^2 + 1 = 0$ bedeutet, dass $x = \sqrt{-1}$ .)

Mitternachtsformel: Ein Polynom $ax^2 + bx + c$ hat folgende Nullstellen: $$x_{1,2} = \frac{-b\pm\sqrt{b^2-4ac}}{2a}$$ Für komplexe Zahlen interpretiert man $\pm\sqrt{b^2-4ac}$ als die Zahlen $z$ , für die gilt $z^2=b^2-4ac$ .

Approximation mit Polynomen

Jede stetige Funktion kann durch ein Polynom approximiert werden (Interpolation).

Satz von Weierstrass: Für jede Funktion $f\in\mathbb{C}[a,b]$ und ein beliebiges $\varepsilon > 0$ gibt es ein Polynom $p$ , so dass $\| f-p \|_\infty < \varepsilon$ (mit $\|f\|_\infty = \max_{x\in[ab]}|f|$ die Maximumnorm).

Analog kann jede periodische Funktion (unter gewissen Voraussetzungen) durch ein trigonometrisches Polynom beliebig genau approximiert werden. $$c + \sum_{i=0}^n a_i \sin(it) + \sum_{i=0}^n b_i \cos(it)$$

Polynomfunktionen sind für Approximationen besonders geeignet, weil sie einfach zu differenzieren und integrieren sind und ihre Nullstellen durch Standardalgorithmen bestimmt werden können. Welche Polynomfunktionen für welche Anwendungen geeignet sind, richtet sich u.a. nach dem Approximationsfehler und danach, wie sich dieser Fehler verteilt.