1

Vorkurs Mathematik für Informatiker

-- 1 Potenzen und Polynome --

Thomas Huckle Stefan Zimmer (Stuttgart)

30.9.2015

2

3

Vorwort

• Es sollen Arbeitstechniken vermittelt werden für das Informatikstudium • Der wesentliche Teil ist das Bearbeiten der Übungsaufgaben

• Aufgaben, die man nicht lösen konnte, kann man vergessen, daher gibt es keine „Musterlösungen“: „learning by doing“ • Stoffauswahl: - Wiederholung von Schulstoff - Informatik-relevante Mathematik - aber insgesamt relativ willkürlich, aber interessant

4

Vorgehensweise

Mathematik: Definition von Objekten und Operationen.

Frage nach Eigenschaften der definierten Strukturen!

Vorlesung verstehen? Nacharbeiten!

Typischer Lösungsweg für Übungsaufgaben: Aus aktuellem Teil des Skripts/der Vorlesung die Definitionen anschauen, umformulieren, zusammenfügen Lösung

Jeder Zeit Fragen stellen! Anwesenheit!

Verschiedene Schwierigkeitsstufen.

Serlo: https://de.serlo.org/mathe/universitaet/tu-muenchen/vorkurs-mathematik-informatiker/44328

5

„Potenzen“ bzgl. Addition Einführung der Zahloperationen, basierend auf 0 und 1: „Potenzen“ bezgl. „+“:

n=++++ 11...11

n-mal

Mächtigkeit einer Menge mit n Elementen (Äpfeln)

Addition: n+1 = (1+1+..+1+1) + 1 als Nachfolger von n

Multiplikation: nnnnmn ++++=⋅ ...

m-mal

als wiederholte Addition in Paketen oder Mächtigkeit von m Mengen der Mächtigkeit n

6

Potenzen bzgl. Multiplikation Potenz als wiederholte Multiplikation:

nxxxxx :=⋅⋅⋅⋅

n-mal

als abkürzende Definition/Schreibweise „:=„

( ) ( ) mnnm xxxxxxxxxxxxxxx +=⋅⋅=⋅⋅⋅⋅⋅=⋅

m-mal n-mal m+n-mal

( ) ( ) ( ) ( )( ) ( )mmm xyxyxyyyxxyx ==⋅=⋅

m-mal m-mal m-mal

( ) ( ) ( ) mnmmnm xxxxxxxx ===

n-mal m-mal m-mal

n-mal

7

Rekursive Definition

>⋅=

=+

00

:1

nfürxxnfürx

x nn

Präzise mathematische Definition:

Als Computer-Programm:

function Potenz( x: Real; n: Integer): Real; begin if n=1 then Potenz := x else Potenz := x ∙ Potenz(x, n-1) end;

Rekursives Programm (Ausführung von oben her)

8

Loop programm

Induktives Programm (Ausführung von unten her)

function Potenz ( x: Real; n: Integer ) : Real ; var p: Real ; i : Integer ; begin p := 1.0 ; for i := 1 to n do p := p ∙ x ; Potenz := p ; end ;

9

Brüche als Exponent Definition: Für eine positive Zahl x ϵ IR und n ϵ IN ist x1/n diejenige positive Zahl y, für die gilt yn = x .

Für n=2 bekommen wir die üblichen Wurzeln √¯¯

Entsprechend ist die n-te Wurzel definiert durch

nnn xxx11

: ==

Damit diese Definition vernünftig ist, sollte es nur eine solche Zahl y geben!

xyxy nn =⇔= 1

10

Rechenregeln

Die Definition von x1/n wurde genau so gewählt, dass die alte Regel (xm)n = xm∙n weiter gilt:

( ) ?1 =nnx

( ) xxxxn

nnn ===⋅ 1

11

Somit hebt der Exponent 1/n die Wirkung des Exponenten n auf, bzw. Exponent n hebt 1/n auf. Daher ist xn die Umkehrfunktion von y1/n (und umgekehrt).

( ) qpp

qp

qqp

xxxx 111

: =

==

⋅

11

Ziel: Erweiterung des Potenzierens auf reelle Zahlen Brüche (positive rationale Zahlen), schon geschafft. Erweiterung jeweils so, dass die alten Regeln weiter gelten. Negative Exponenten:

nmnm xxx +=⋅ für m = 0: nnn xxxx ==⋅ +00

Daher muss x0 = 1 sein.

0xxxx nnnn ==⋅ +−−nmnm xxx +=⋅ für m = − n:

Daher muss sein wegen nn

xx 1:=− 1=⋅− nn xx

Später soll natürlich auch xy für definiert sein. ,0,, >∈ xRyx

12

Polynome - Definitionen

Ein Term der Form xn heißt Monom (in x); x є ǀR: Unbekannte; n є ǀN: Potenz

Die ai , i=0,1,…,n, heißen Koeffizienten des Polynoms.

Entsprechend heißt ein Term

ein Polynom (in x).

01

10

axaxaxa nn

n

i

ii +++=∑

=

Das Summenzeichen Σ dient der einfacheren Notation

nn

n

ii aaaaaa +++++= −

=∑ 1210

0

13

Polynom als Code program Polynom; const n = 3; var a: array [0 . . n] of Real = (4.0 , 0.0 , 7.0 , 15.0 ); x: Real = 2.0; sum: Real; i: Integer; begin sum := 0.0; for i := 0 to n do sum := sum + a[i] * (x ** i); WriteLn (sum); end;

14

Diskussion Das Programm wertet das Polynom aus. Man gibt also eine Stelle x ein und erhält dafür den Wert des Polynoms sum an dieser Stelle x.

Das Programm ist eigentlich ein schwerer Kunstfehler. Aufwändig und teuer! Es geht wesentlich geschickter!

Beispiele für Polynome:

1 (nach 0 das einfachste)

7 x + 3

15 x3 + 7 x2 + 4 ( ein „innerer“ Koeffizient ist 0)

15

Grad eines Polynoms

Der Grad eines Polynoms ist „das größte i“ mit ai ≠ 0

Notation: nxn =:)deg(

Allgemein: nxan

i

ii ≤

∑=0

deg (= n, falls an ≠ 0).

Aufgabe: deg(1)=?, deg(7x+3)=?, deg(15x3+7x2+4)=?

deg(1)=0; deg(7x+3)=1; deg(15x3+7x2+4)=3;

deg(0)=?

16

deg(0)? Rechenregeln für deg: Sei pn Polynom vom Grad n.

deg(pn ∙ pm) = n + m = deg(pn) + deg(pm) deg(pn+pm) <= max{n,m} = max{deg(pn),deg(pm)}

Speziell für pn=0 soll daher auch gelten:

deg(0∙pm) = deg(0) + m = deg(0) deg(0+pm) = max{deg(0),m} = m

→ deg(0) = ̶ ∞

Manchmal auch deg(0) = -1 in der Computeralgebra.

Also deg(0)<m, so dass deg(0)+1=deg(0)

17

( ) ( ) ?312 22 =+−+++ xxxx

Addieren und Multiplizieren von Polynomen

Funktioniert mit den üblichen Rechenregeln.

( ) ( ) 42312 222 ++=+−+++ xxxxxx

Multiplizieren:

( ) ( ) ?312 22 =+−⋅++ xxxx

( ) ( )352363

22

312

234

2

23

234

22

+++++++

−−−++

=+−⋅++

xxxxxx

xxxxxx

xxxx

=

18

Polynomdivision (mit Rest) Naheliegend: (x+1) : (x+1) = 1 (Vorsicht mit x=-1) oder p(x) = 2x+2 = 2(x+1) = 2q(x) p:q=2

Ähnlich: (x2-1) : (x+1) = (x-1) oder x2 - 1 = (x-1) (x+1)

( )( )( ) 13312

)13(35242222

234234

+−+−++=

=+−+++++=++++

xxxxxxxxxxxxxx

sieht man

Aus dem vorigen Beispiel ( ) ( )( )312352 22234 +−++=++++ xxxxxxxx

Formale Definition? Berechnung?

19

Division mit Rest für lN Zu n,m ϵ lN gibt es eindeutig bestimmte q,r ϵ lN mit r<m, so dass n = q∙m + r gilt. Dabei ist q das Ergebnis und r der Rest der ganzzahligen Division von n durch m, n/m.

Übertragung auf Polynome:

Zu zwei Polynomen N und M mit Koeffizienten aus lR gibt es eindeutig bestimmte Polynome Q, R mit Koeffizienten aus lR mit deg(R) < deg(M), so dass N = Q∙M + R. Dabei ist Q das Ergebnis und R der Rest der Polynomdivision von N durch M, N : M.

20

Beispiel

3x x+ 1+ )1/(121: 2 +−+−=+ xxxx)( 23 xx +−

2x−)( 2 xx −−−

x2)22( +− x1− (-1 ist der Rest)

( ) ( )

21

Lineare Polynome

Wichtige Spezialfälle: Polynome von kleinem Grad

Im Fall deg(P) ≤ 1 heißt P linear und ist eine Gerade. P von der Form

bxaxPP +⋅== )(

z.B. in linearen Gleichungen: a∙x + b = 0

Ist leicht zu lösen, so lange a ≠ 0 ist.

22

Quadratische Polynome Im Fall deg(P) ≤ 2 heißt P quadratisch, ist also von der Form P = P(x) = a∙x2 + b∙x + c (eine Parabel)

Dazu gehören die quadratischen Gleichungen (oBdA a=1): 02 =++ qpxx

mit den Lösungen qppx −±−=

42

2

21

so lange p2 ≥ 4q ist (andernfalls komplexe Lösungen!)

Aufgabe: 2x2 – 14x + 24 = 0. Lösungen? x=3, x=4.

23

Nullstellensuche Die Nullstellen x1 , x2 eines quadratischen Polynomes liefern eine Zerlegung in Linearfaktoren:

).)(( 212 xxxxqpxx −−=++

Sei P ein beliebiges Polynom vom Grad n mit Nullstelle x1. Dann kann man den Linearfaktor x – x1 abspalten durch Polynomdivision:

)()()( 1xxxQxP −⋅=

mit einem Polynom Q vom Grad n-1.

Die Nullstellen von P sind nun x1 und die Nullstellen von Q.

Hauptsatz der Algebra: Polynom zerfällt in n Linearfaktoren.

24

Beispiele

Polynome P und rationale Funktionen P/Q sind wichtige Klassen von Beispielfunktionen und dienen als Baukasten, um kompliziertere Funktionen anzunähern (Potenzreihe, Computergraphik, Bildverarbeitung)

Annäherung der Exponentialfunktion bei x=0 durch Polynome wach- senden Grads.