Links und Funktionen
Sprachumschaltung

Navigationspfad
Sie sind hier: Startseite / Lehre / SS 2017 / Logik und Diskrete Strukturen / Material / K05 Polynome


Inhaltsbereich

K05 Polynome

Entspricht Kapitel 3.3 aus A.Steger: Polynome, Polynomdivision, Fundamentalsatz der Algebra

Plain Text icon K05_Polynome.txt — Plain Text, 4 KB (5091 bytes)

Dateiinhalt

Persönliche Notizen zur Vorbereitung der LDS Vorlesung. Diese Notizen waren 
ursprünglich nicht zur Herausgabe gedacht und sind entsprechend mit Vorsicht 
zu genießen. Es wird dringend empfohlen, dass Buch zu verwenden:

Angelika Steger: Diskrete Strukturen. 
Band 1: Kombinatorik, Graphentheorie, Algebra.
2. Auflage, Springer 2007, 978-3-540-46660-4





=======================================================
 Polynome über einer Veränderlichen (Buch Kapitel 3.3)
=======================================================

Def.: Ein Polynom über einer Variablen x ist ein Term
  mit +,∙, reellen Konstanten und dieser Variablen.
  
Bsp.: p(x) = x+(x²-5)∙(x³-7)

Zwei Polynome sind _gleich_, wenn sie mit den üblichen 
Rechenregeln ineinander überführt werden können.
(z.B. Distributivgesetz, Assoziativgesetz, etc.)

Bsp.: x+(x²-5)∙(x³-7) = x⁵-5x³-7x²+x+35 
 (Zwei verschiedene Repräsentanten der gleichen Äquivalenzklasse.)

Polynome lassen sich miteinander addieren und multiplizieren.

Def.: _Polynomfunktion_: Jedes Polynom p(x) definiert eine Abbildung fₚ:ℝ→ℝ
  mit fₚ(x)=p(x) durch Einsetzen und ausrechnen.
Bsp.: fₚ(7)=  14721

NB.: p und fₚ sind nicht dasselbe: p ist _ein_ Repräsentant der Äquivalenzklasse, während fₚ eine Funktion ist.
  Es gilt aber, dass fₚ=fₕ genau dann wenn p und h in der gleichen Äquivalenzklasse liegen.
  In die Funktion können nur reelle Zahlen eingesetzt werden, 
  aber ins Polynom könnte man auch eine Matrix oder Terme einsetzen.
  
Def.: Normalform & Grad eines Polynoms
  Jedes Polynom p(x) kann geschrieben werden in der Form 
    p(x)= aₙ∙x^n + a_(n-1)∙x^(n-1) + … + a₁∙x¹ + a₀
  mit n∈N und aₙ,…,a₀ Konstanten, aₙ≠0. 
  (Meist aᵢ∈ℝ, aber ℚ,ℂ,ℤₙ, etc. auch möglich)
  
  Die aᵢ heißen _Koeffizienten.
  
  n ist der Grad des Polynoms p, geschrieben grad(p)=n (engl. deg(p)).
  Konstante Polynome p(x)=a₀ mit a₀≠0 haben Grad 0.  
  Der Grad des Nullpolynoms p(x)=0 bleibt oft undefiniert oder wird als -1 definiert.
    
Berechnung der Normalform durch ausmultiplizieren und sortieren der Potenzen.

Lemma:
  grad(p∙q)=grad(p)+grad(q)      (falls p,q≠0)
  grad(p+q)≤max(grad(p),grad(q))

Bsp.:  
  a(x)=x²-3x+5, b(x)=4x+2
  grad(a)=2, grad(b)=1, 
  grad(a∙b)=grad(4x³-10x²+14x+10)=3
  grad(a+b)=grad(x²+x+7)=2
  
  c(x)=x²-3x+5, d(x)=-x²+4x+2
  grad(c)=2, grad(d)=2, 
  grad(c∙d)=grad(-x⁴+7x³-15x²+14x+10)=4
  grad(c+d)=grad(x+7)=1
  
Satz(Polynomdivision):
  Gegeben zwei Polynome a,b mit b≠0, dann
  gibt es eindeutige bestimmte Polynome q,r mit 
    a=q∙b+r 
  und grad(r) < grad(b) (oder r=0)
  
Beweis: 
  Existenz durch Algorithmus (bekannt aus der Schule)
  Eindeutigkeit: Angenommen a=t₁∙b+r₂ und a=t₂∙b+r₂
  mit grad(r₁)<grad(b) und grad(r₂)<grad(b)  
  Es gilt 0 = (a-a) = (t₁-t₂)∙b+(r₁-r₂) also auch 
  (t₁-t₂)∙b = r₂-r₁
  Falls (t₁-t₂)≠0 dann wäre aber wegen 
  grad(r₁)<grad(b) und grad(r₂)<grad(b)  
  auch grad((t₁-t₂)∙b) ≩ grad(r₂-r₁);
  dies wäre ein Widerspruch, also t₁=t₂ und r₁=r₂.
  □
Beispiel:
  a(x)=2x⁴+x³+x+3   b(x)=x²+x-1
  
  2x⁴+ x³    +x+3 : x²+x-1 = 2x²-x+3
-(2x⁴+2x³-2x²)
      -x³+2x²+x+3
    -(-x³- x²+x)
          3x²  +3
        -(3x²+3x-3)
            -3x+6

Es gilt also a = (2x²-x+3)∙b + (-3x+6)
                  = q            = r
mit grad(r)=1<2=grad(b).

Teilbarkeit, ggT, erweiterte Euklidischer Algorithmus können ganz analog für Polynome definiert werden.

Def.(Nullstellen von Polynomen):
Eine Zahl α mit fₚ(α)=0 (bzw. p(α)=0), also α eine Nullstelle
der Polynomfunktion, heißt Nullstelle des Polynoms p.

Lemma:
  Ist α eine Nullstelle von p≠0, so gibt es q mit grad(q)=grad(p)-1
  und p(x)=(x-α)∙q(x).
Beweis:
  Schreibe mit Polynomdivision
    p(x)=q(x)∙(x-α)+r(x) 
  mit grad(x-α)=1. Aus grad(r)<grad(x-a) folgt grad(r)=0 
  alsi ist r ein konstantes Polynom: r(x)=c für ein c. 
  Wegen 0=p(α)=q(α)∙(α-α)+c=c folgt c=0, 
  also gilt r(x)=0 und damit die Behauptung.
  □              
  
Satz:
  Ein Polynom p≠0 mit grad(p)=n hat höchstens n Nullstellen.
Beweis:
  Durch Induktion über n.
  Für n=0 ist p konstant. Wegen p≠0 gibt es keine Nullstelle.  
  Gelte die Behauptung für ein festes aber beliebiges n₀ und
  sei grad(p)=n₀+1.
  Wenn p keine Nullstelle hat, so folgt die Behauptung trivialerweise.
  Sonst sei α eine Nullstelle von p. Schreibe
    p(x)=q(x)∙(x-α) mit grad(q)=n₀
  Für jede Nullstelle β von p mit β≠α gilt q(β)=0.
  Nach Verwendung der Induktionshypothese gibt es höchstens n₀ solche β,
  α ist eine weitere Nullstelle, also insgesamt höchstens n₀+1 Nullstellen.
  □
Beispiele:
  x²-2x+1 hat eine Nullstelle,  nämlich 1 (doppelt)
  x²-1    hat zwei Nullstellen, nämlich 1, -1
  x²+1    hat keine Nullstellen in R (in C: i,-i)

Nullstellen können mehrfach vorkommen.

Fundamentalsatz der Algebra:
  Jedes Polynom p mit p≠0 und grad(p)=n hat 
  in den komplexen Zahlen n Nullstellen.

Artikelaktionen


Funktionsleiste