<<

. 7
( 63 .)



>>

SCHRITT 4 f0 := f1 , f1 := f gehe zu SCHRITT 2 .
AUS f0 , f1 mit: f0 = ggT (m, n), f1 = 0 .


Der Schritt 3 ist nichts anderes als eine Umformulierung der Division von f0 durch f1 mit
¯
einem Rest f kleiner als f0 .

Die Veri¬kation, daß der Algorithmus den gr¨ßten gemeinsamen Teiler d von m, n berech-
o
net (Nachweis der Korrektheit des Algorithmus), stutzt sich auf folgende Beobachtun-
¨
gen:

(a) Ist f1 > 0 , so gilt:
f0
ggT (f0, f1 ) = ggT (f1 , f0 ’ | |f1) .

f1 ’
(b) Ist f0 > f1 > 0 , so gilt:
f0
¯
f := f0 ’ | ’ 1 < f0 .
|f

f1
(c) Eine (bezuglich <) abnehmende Folge naturlicher Zahlen enth¨lt nur endlich viele
a
¨ ¨
Elemente.


Das Wort Algorithmus leitet sich vom Namen des Mathematikers al-Charismi (oder al-
Khowarizmi) aus Bagdad (um 830) ab. Er beschrieb in seinem Werk “Al-jabr wa™l Muqabalah“
als erster die elementare Algebra und trug damit erheblich dazu bei, daß die Algebra nach Europa
kam. Das Wort“Algebra“ leitet sich aus dem Buchtitel ab.
Eine wichtige Aussage im Zusammenhang mit dem Euklidischen Algorithmus halten wir
fest in


Bemerkung 1.31
Analysiert man den Euklidischen Algorithmus, so stellt man fest, daß der gr¨ßte gemein-
o
same Teiler d von m, n stets eine Darstellung d = um + vn mit u, v ∈ Z besitzt. Dies
Z
korrespondiert mit der Tatsache, daß in Z jedes Ideal ein Hauptideal ist und daß das von
Z
m, n erzeugte Ideal durch d erzeugt wird. (Genaueres erf¨hrt man hierzu etwa in einer
a
2
Algebravorlesung.)
Baumeister: Lineare Algebra I / Stand: August 1996 22


Beispiel 1.32
Man bestimme den gr¨ßten gemeinsamen Teiler von 3293 und 2405.
o
Wir schreiben jeweils SCHRITT 3 auf:

·
3293 = 1 2405 + 888
·
2405 = 2 888 + 629
·
888 = 1 629 + 259
·
629 = 2 259 + 111
·
259 = 2 111 + 37
·
111 = 3 37 + 0

Also ggT (3293, 2405) = 37 .
Wir stellen fest, daß die Zahlenfolge

a1 = 3293, a2 = 2405, a3 = 888, a4 = 629, a5 = 259, a6 = 111, a7 = 37

folgender Abschatzung genugt:
¨ ¨

ai+2 ¤ ai /2 , i = 1, . . . , 5 .

Laßt sich eine entsprechende Aussage allgemein beweisen? Diese und ahnliche Fragen
¨ ¨
werden in der Komplexitatstheorie (Diskrete Mathematik, Mathematische Informatik)
¨
2
untersucht.

Damit ist der euklidische Algorithmus fur naturliche Zahlen erkl¨rt, die Erweiterung auf
a
¨ ¨
ganze Zahlen ist o¬ensichtlich. Er hat seine Entsprechung bei den Polynomen.


De¬nition 1.33
Sei IK ∈ {Z , Q, IR}. Ein Polynom mit Koe¬zienten in IK ist eine Funktion
Z
m
x ’’ aixi ∈ IK
p : IK
i=0

Hierbei heißt die Zahl m der Grad von p, falls am = 0 . (Den Grad des Nullpolynoms
(a0 = . . . = am = 0) setzen wir mit ’1 fest.) Wir schreiben f¨r den Grad m von p :
u
m := deg p .
2
In der obigen De¬nition haben wir den analytischen Standpunkt, ein Polynom als Ab-
bildung aufzufassen, eingenommen. Die algebraische Sicht besteht darin, ein Polynom als
Objekt in einer Unbekannten zu betrachten. In Kapitel 3 gehen wir darauf ein.
Polynome haben uberragende Bedeutung als interessanter Gegenstand in der Algebra (all-
¨
gemeine Arithmetik), in der Analysis auf Grund der Tatsache, daß jede stetige Funktion
(lokal) gut durch Polynome approximiert werden kann, und in der numerischen Mathe-
matik, da Polynome daruberhinaus einfach durch ihre Koe¬zienten abgespeichert werden
¨
Baumeister: Lineare Algebra I / Stand: August 1996 23


k¨nnen. Bei den Polynomen ist auch eine Division mit Rest, die ja beim Euklidischen Al-
o
goritmus zentral war, erkl¨rt.
a


Satz 1.34
Sei q ein Polynom mit Koe¬zienten in IK ∈ {Q, IR} mit deg q ≥ 0 . Dann gibt es
zu jedem Polynom p mit Koe¬zienten in IK eindeutig bestimmte Polynome f, r mit

p = f q + r , deg r < deg q .
Beweis:
Eindeutigkeit:
Sei p = f1 q + r1 , deg r1 < deg q , p = f2 q + r2 , deg r2 < deg q . Dann folgt (f1 ’ f2 ) q =
(r1 ’ r2 ) . Da deg(r1 ’ r2 ) < deg q ist, kann diese Identit¨t nur dann erfullt sein, wenn
a ¨
f1 ’ f2 und r1 ’ r2 Nullpolynome sind.
Existenz: n m
ai xi , x ∈ IK , mit an = 0, bm = 0 .
ai xi , q(x) :=
Sei p(x) :=
i=0 i=0
Wir fuhren den Existenzbeweis durch vollst¨ndige Induktion nach n .
a
¨
n = 0 : Ist m = 0, setze f := an /bm , r := 0 . Ist m > 0, setze f := 0, r := p .
n + 1 : Ist deg p < deg q, setze f := 0, r := p . Ist deg p ≥ deg q, setze z(x) :=
an+1 b’1 xn+1’m , x ∈ IK . Dann ist deg(f ’ zq) < n + 1 und aus der Induktionsan-
m
nahme folgt die Existenz von Polynomen f1 , r mit p ’ zq = f1 q + r , deg r < deg q . Also:
p = (z + f1 )q + r , deg r < deg q .

Die formale De¬nition fur den großten gemeinsamen Teiler wollen wir nicht nochmal
¨ ¨
aufschreiben; sie sollte klar sein. Soviel sei allerdings festgehalten: Er ist hier nur bis auf
Vielfache mit Elementen = 0 aus dem zugrundegelegten Koe¬zientenbereich (siehe oben)
festgelegt.


Euklidischer Algorithmus bei Polynomen:

Polynome p, q mit deg p ≥ deg q ≥ 0 .
EIN
SCHRITT 1 f0 := p , f1 := q .
SCHRITT 2 Ist deg f1 < 0 , gehe zu END .
¯ ¯
SCHRITT 3 Division mit Rest: f0 = gf1 + f , wobei deg f < deg f1 .
¯
SCHRITT 4 f0 := f1 , f1 := f gehe zu SCHRITT 2.
AUS f0 , f1 mit: f0 = ggT (p, q) , deg f1 < 0 .


Vollig entsprechend zum skalaren Fall bestatigt man, daß das Polynom f0 , das vom Al-
¨ ¨
gorithmus ermittelt wird, einen großten gemeinsamen Teiler von p, q darstellt.
¨
Baumeister: Lineare Algebra I / Stand: August 1996 24


Beispiel 1.35
Betrachte fur IK := Q die Polynome
¨

p(x) := x3 + 3x2 + 6x + 5 , q(x) := 3x2 + 6x + 6 .

Der Durchlauf des euklidischen Algorithmus sieht so aus:
p(x) := x3 + 3x2 + 6x + 5 , q(x) := 3x2 + 6x + 6 .
EIN
SCHRITT 1 f0 := p , f1 := q .
¯
SCHRITT 3 f(x) = 2x + 3 denn
(x3 + 3x2 + 6x + 5) : (3x2 + 6x + 6) = 1/3 x + 1/3 mit Rest 2x + 3 .
SCHRITT 4 f0 (x) = 3x2 + 6x + 6 , f1(x) = 2x + 3 .
¯
SCHRITT 3 f(x) = 15/4 denn
(3x2 + 6x + 6) : (2x + 3) = 3/2 x + 3/4 mit Rest 15/4 .
SCHRITT 4 f0 (x) = 2x + 3 , f1 (x) = 15/4 .
¯
SCHRITT 3 f(x) = 0 denn
(2x + 3) : 15/4 = 8/15 x + 4/5 mit Rest 0 .
SCHRITT 4 f0 (x) = 15/4 , f1 (x) = 0 .
AUS f0 (x) = 15/4 , f1 (x) = 0 .
Also ist das Polynom d(x) := 15/4 ein gr¨ßter gemeinsamer Teiler der Polynome p, q .
o
Wir nennen die Polynome auf Grund der Tatsache, daß der gr¨ßte gemeinsame Teiler ein
o
Polynom vom Grad 0 und dieser ja nur bis auf solche Polynome eindeutig bestimmt ist,
teilerfremd. Dies korrespondiert mit der Tatsache, daß q keine reelle Nullstelle hat und
2
selbst kein Teiler von p ist, wie die obige Rechnung gezeigt hat.


Teilbarkeit und Primfaktorzerlegung spielen eine große Rolle in der Algebra. Welch inter-
essante Vielfalt Polynome dabei schon aufzeigen, sieht man etwa an dem Polynom

p(x) := x4 ’ 7 .

Betrachtet man das Polynom uber dem K¨rper Q, so hat es keine Nullstelle und man
o
¨
kann es nicht echt in ein Produkt von Polynomen mit Koe¬zienten in Q zerlegen; man
nennt es daher irreduzibel.
Betrachtet man das Polynom in IR, so zerf¨llt es in Faktoren
a
√ √
p(x) = (x ’ 7)(x + 7)
2 2


und man kann zwei reelle Nullstellen ablesen:

x = ± 4 7.

Beachte, daß in IR 4“te Wurzeln aufgrund der Vollst¨ndigkeit von IR wohlde¬niert sind.
a
Betrachtet man das Polynom in C “ wir haben komplexe Zahlen noch nicht eingefuhrt,
¨
wir erw¨hnen dies nur der Vollst¨ndigkeit halber “, so hat p die Nullstellen
a a
√ √
x = ± 7 , x = ±i 7 ,
4 4
Baumeister: Lineare Algebra I / Stand: August 1996 25


und es zerf¨llt in Linearfaktoren:
a
√ √ √ √
p(x) = (x ’ 7)(x + 7)(x ’ i 7)(x + i 7) .
4 4 4 4



Dies korrespondiert mit der Aufteilung des Kreises mit Radius 4 7 in vier Sektoren. Im
Abschnitt 3.2 uber Korper kommen wir darauf zuruck.
¨ ¨ ¨
Kapitel 2

Lineare Gleichungssysteme

Wir betrachten lineare Gleichungssysteme mit “Zahlen“ als Koe¬zienten. Wir nehmen
dabei Bezug auf den Abschnitt 1.5, in dem wir als Zahlbereich IK ∈ {Q, IR} betrach-
tet haben. In den Kapiteln uber Vektorraume und lineare Abbildungen ordnen wir die
¨ ¨
Betrachtungen in einen allgemeineren Kontext ein.


2.1 Beispiele und Einfuhrung
¨
Sei IK ∈ {Q, IR}. Die Addition in IK schreiben wir mit + , die Multiplikation mit · ,

<<

. 7
( 63 .)



>>