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

Taylorpolynome