Nächste Seite: 2025-07-18 ...before ...genlzvexcersize20250705.sh Aufwärts: The 11 ... Vorherige Seite: 2025-07-18 ...before ...bin20250716.txt
Die schnelle fourier transformation
fast fourier transformation
anwendung, wesentliche oerationen bei der signalverarbeitung
erhoehung der effizienz von algorithmen
fuer hauefig auftretende arithmetische probleme
Multiplikation von Polynomen
benoetigte zeit fuer die multiplikation von polynomen
polynom multiplikation
algorithmus nutzt teile- und herrsche prinzip
berechnen, multiplizieren, interpolieren
berechnen
multiplizieren
interpolieren
polynom-multiplikation
verbesserte methode der polynom-multiplikation
die strategie die verbesserten methode der polynom-multiplikation
ein polynom vom Grad N-1 ist durch seine werte in N verschiedenen
Punkten vollstaendig beschrieben
1. ein polynom vom Grad N-1 ist durch seine werte in N verschiedenen
Punkten vollstaendig beschrieben
2. Zwei polynome vom Grad N-1 miteinander multiplizieren, erhalten wir polynom
vom Grad 2N-2
Zwei Regeln:
1. ein polynom vom Grad N-1 ist durch seine werte in N verschiedenen
Punkten vollstaendig beschrieben
2. Zwei polynome vom Grad N-1 miteinander multiplizieren, erhalten wir polynom
vom Grad 2N-2
dieses polynom vom grad 2N-2 ist vollstaendig bestimmt wenn man 2N-1 Punkte bestimmen
kann.
logisch: ein Polynom vom Grad N-1 ist durch N punkte vollstaendig bestimmt
zwei polynome des Grades N-1 multipliziert haben Grad 2N-2
dieses polynom ist durch 2N-1 Punkte vollstaendig beschrieben
wert des resultierenden polynoms
wert des resultierenden polynoms in beliebingen punkt bestimmen
beliebiger punkt
wert des resultierenden polynoms bestimmen
die werte der zu multiplizierenden polynome
die werte der zu multiplizierenden polynome in diesem punkt bestimmen
die werte der zu multiplizierenden polynome in diesem punkt bestimmen,
indem die werte der beiden zu multiplizierenden polynome in diesem punkt berechnen
...
die werte der zu multiplizierenden polynome bestimmen, no problem
werte des polynoms bestimmen, no problem
aber: werte der zu multiplizierenden polynome in diesem punkt bestimmen und dann selber miteinander bestimmen
ganz easy
die werte der zu multiplizierneden polynomen in diesem punkt berechnen und dann miteinander muliplizieren
ist der werte des polynoms was aus multiplizieren beider polynome hervorging in diesem punkt
drei sachen
polynome vom grad N-1 ergeben multipliziert Grad 2N-2
polynom vom Grad N-1 ist durch N Stellen,Werte ... definiert
zwei polynome, deren werte in der stelle x0 jeweils bestimmt sind, ergeben multipliziert
den wert an dieser stelle beim multiplizieren der beiden polynome als polynom
Das steht jetzt auch bei robert Sedgewick
Berechne
Multipliziere
Interpoliere
Berechne: die werte der ausgangspolynome in 2N-1 Punkten (*1
Multipliziere die beiden fuer jeden Punkt erhaltenen Werte
Interpoliere zwecks bestimmung des eindeutigen resultierenden polynoms das in den gegebenen
punkten die gegeben werte annimmt.
p(x)
q(x)
r(x)
r(x) = p(x)q(x)
p(x) = x^2 + x + 1
q(x) = x^2 + x - 2
Mitternachtsnachtsformel
ausprobieren
x_(1/2) = (-b +/- SQRT (b^2-4ac))/(2a)
a1 = 1
b1 = 1
c1 = 1
a2 = 1
b2 = 1
c2 = -2
1 +/- SQURT (1-4)
zaehler/nenner, begriff lernen
dividend/divisor, gelernt
aber bitte zaehler/nenner
dann: diskriminante,
p(x) = x^2 + x + 1
q(x) = x^2 + x - 2
x^2 + x + 1 = 100
...
Mitternachtsformel, die stelle bei so und so...
also, das war eine Gegenueberstellung
natuerlich lohnt es sich die Mitternachtsformel immer wieder zu lernen
aber die brauchen wir hier nicht
es ist der umgekehrte weg
1.) suche beliebige stellen und berechne die werte
2.) bei gegebenen werten berechne die stellen, die die werte ergeben, in einem
gegebenen polynom
normalerweise gilt trivialerweise sage ich mal (2.) als der angesehenere weg
dies mal ist es aber anders herum, es lohnt sich
das jetzt zu sagen, damit keine verwechslungen auftreten was zu tun ist
und ausserdem, mitternachtsformel lohnt sich immer
[p(-2),p(-1),p(0),p(1),p(2)] = [3,1,1,3,7]
[q(-2),q(-1),q(0),q(1),q(2)] = [8,4,2,2,4]
jetzt multiplizieren,
1.) berechne die werte
2.) multipliziere
3.) interpoliere
[r(-2),r(-1),r(0),r(1),r(2)] = [24,4,2,6,28]
langrasche formel
also, hier von wegen mitternachtsformel
die mitternachtsformel sollte man kennen, hinweis im nachhinein, warum laesst sich:
1 +/- SQURT (1-4)
nicht berechnen, eine imaginaere zahl, komisch naechstes kapitel gleich
nein, die antwort ist ganz einfach, das ist hier gar nicht gefragt,
aber an dieser stelle ist keine loesung uebrigens, bei mitternachtsformel:
x^2 + x + 1 = 0
und 1 ist der Koeffizient c
also x^2 .. x^1 .. x^0
x^0 = 1
x^2 + x + 1 = 0
wenn aber c != ...
und hinten nicht gleich 0
dann ..
dann
x^2 + x = 5
und dann
x^2 + x -5 = 0
und so richtig, so kommt c zustande nebenbei, aber jetzt naechstes
dann weiss man trotzdem
x^2 + x + 2 = 3
an dem wert 3 ist das polynom
x^2 + x + 2, stelle x1/2...
gut, langrage, no idea
bitte gucken goldener schnitt
Polynominterpolation
langrasche formel
+1 -0 -1 -2
+2 -0 -1 -2
+2 +1 -1 -2
+2 +1 -0 -2
+2 +1 -0 -1
kurz und gut
l
l_i(x)
das ist besonders wichtig das l
das l ist wiederum ein produkt von
j=0 bis n
und zwar geht das so, eine quasi,
sagen wir:
Produktformel
und eine, die das produkt quasi auseinandernimmt
hier muessen wir aufpassen, das ist selbsterklaerend
die selbe formel, schreiben wir das produkt auseinander
werden wir etwas bemerken...
die Produktformel geht so,
l_i(x) = PROD_{j=0}^n (x-x_j)/(x_i-x_j)
vorsicht was taucht auf.
znaechst haben wir verschiedene x_i, das sind verschiedenen stellen
vergegenwaertigen wir uns, ein polynom vom grad vier, braucht 5
punkte um vollstaendig beschrieben zu sein
jetzt muessen wir uns fragen:
stellen oder
werte
die antwort lautet: beides
punkt := (stelle, werte)
wir muessen die 5 werte haben, koennte man sagen, :-) schoen aber wo
wir koennten umgekehrt, die 5 stellen haben, damit ist alles gesagt
also brauchen wir 5 punkte, stelle und wert
das heisst, ausrechnen, wo sind die, wieviele sind es
ganz einfach:
ein polynom vom grad 4 ist durch 5 punkte beschrieben
jetzt muss ich in die
formel fuer das langrage polynom anwenden
vorsicht das langrage polynom selber ist nicht das polynom
was ich als ziel berechne, sondern das polynom mit dem
ich aus den gegebenen punkten die koeffizienten des
polynoms angebe
angenommen,
ich habe ein polynom vom grad 4, ich brauche 5 punkte
ich habe ein polynom vom grad 27, ich brauche 28 punkte
dabei habe ich z.B. 28 "x-stellen" und 28 "y-werte"
die eine formel des langrage polynoms, ich glaube das ist die bessere ist:
l_i(x) PROD_{j=0}^n = (x-x_j)/(x_i-x_j)
ist das alles?
no, eben nicht, in wirklichkeit heisst es
l_i(x) PROD_{j=0,j!=i}^n = (x-x_j)/(x_i-x_j)
was notwendig ist, weil, wenn j=i, steht da x_i-x_j
im nenner was in jedem fall null ist, was nicht sein darf
so oder so
wobei l_i(x)
der koeffizient an der stelle i im polynom ist
auffaellig ist, dass sowohl im nenner als auch zaehler
des langrage polynoms -x_j steht, am ende, vielleicht einfach zu merken
die formel aufgedroeselt ergibt wohl
(x-x_0)/(x_i-x_0) * ... * (x-x_{i-1})/(x_i-x_{i-1})*(x-x_{i+1})/(x_i-x_{i+1}) * .. (x-x_n)/(x_i-x_n)
sie werden mich angucken, ist das spannend?
nein, leider alles andere als das. guckt man in robert sedgewick?
nein, das ist nur das produkt ausgeschrieben, aber man muss eben an einer stelle aufpassen,
solange
j != i
und das heisst eben, das steht eben in der mitte
j-1
j+1
nichts anderes
da ist nichts spannendes dabei, es ist nur das produkt
so in wikipedia.
Das polynom selbst ist
P(x) = SUM_{i=0^}f_il_i(x)
gut, l_i(x) haben wir soeben berechnet
aber, was zum teufel ist f_i
kurz und gut, das wissen wir nicht, naemlich ein stuezwert
es gibt wieder drei dinge
stuetzwert
stuetzzstelle
stuetzpunkt
selbst wenn das wort im mathematik unterricht auftauchte es ist
teil der numerischen mathematik und selbst, wenn sie mich
anhand der graphik da ueberzeugen wollen, die ich mir nicht angucke
das sei schnell erklaert, ich wuerde mir das nicht erklaeren
fuer das problem reicht einfach aus
wir muessen darauf achten
l_i(x)
wo in unserem Polynom P sind unsere x gelandet
und was ist l_i(x)
x bleibt einfach uebrig
und die f_i sind einfach unsere
stuetzwerte in dem falle
also nicht stuetzstellen, die x'e die stellen
an denen wir y berechnet haben
sondern die stuetzwerte selber
dann mal los.