Lagrangepolynom (Operationen) < Numerik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:04 Fr 17.01.2020 | | Autor: | teskiro |
| Aufgabe | Aufgabe 1
________
Bestimmen Sie die Anzahl der Rechenoperationen (jeweils die Anzahl der Additionen bzw. Multiplikationen), die für die Berechnung eines Interpolationspolynoms in Lagrange - Darstellung nötig sind.
Aufgabe 2
_________
Bestimmen Sie die Anzahl der Rechenoperationen bei dividierten Differenzen - Verfahren mit Newton - Polynomen.
Vergleichen Sie diese mit der aus Aufgabe 1.
Was ist — abgesehen von weniger Rechenschritten — der Vorteil gegenüber dem Lagrange-Ansatz? |
Ich denke nicht, dass die Aufgabe schwierig ist, aber ich bin mir nicht sicher, ob ich die Rechenschritte richtig zähle.
Mein Ansatz zur Aufgabe 1 ist folgender:
Zu Aufgabe 1:
Das Lagrangsche Interpolationspolynom ist definiert durch [mm] $P_{n}(x) [/mm] = [mm] \sum\limits_{i = 0}^{n} y_{i} \cdot L_{i}^{(n)}(x)$, [/mm] wobei [mm] $L_{i}^{(n)}(x) [/mm] = [mm] \prod\limits_{j = 0, j \neq i}^{n}\frac{x - x_{j}}{x_{i} - x_{j}}$.
[/mm]
Schauen wir uns zunächst das $i$ - te Lagrangsche Basispolynom [mm] $L_{i}^{(n)}(x) [/mm] = [mm] \prod\limits_{j = 0, j \neq i}^{n}\frac{x - x_{j}}{x_{i} - x_{j}}$ [/mm] an.
Der Bruch [mm] $\frac{x - x_{j}}{x_{i} - x_{j}}$ [/mm] besteht aus den Differenzen $x - [mm] x_{j}$, $x_{i} [/mm] - [mm] x_{j}$ [/mm] und einer Division [mm] $\frac{x - x_{j}}{x_{i} - x_{j}}$. [/mm]
Um den Bruch [mm] $\frac{x - x_{j}}{x_{i} - x_{j}}$ [/mm] zu berechnen, benötigen wir also $3$ Rechenoperationen; 2 Differenzen und eine Division.
Das $i$ - te Lagrangsche Basispolynom [mm] $L_{i}^{(n)}(x) [/mm] = [mm] \prod\limits_{j = 0, j \neq i}^{n}\frac{x - x_{j}}{x_{i} - x_{j}}$ [/mm] ist die Multiplikation $n$ solcher Brüche.
Um die $n$ Brüche zu berechnen, benötigen wir also $3n$ Rechenoperationen.
Dann multiplizieren wir diese $n$ Brüche miteinander und wir haben dann $n - 1$ Multiplikationen.
Insgesamt müssen wir also $3n + (n - 1) = 4n - 1$ Rechenoperationen durchführen, um das $i$ - te Lagrangsche Basispolynom [mm] $L_{i}^{(n)}(x)$ [/mm] zu bestimmen.
Das Polynom [mm] $y_{i} L_{i}^{(n)}(x) [/mm] $ erfordert dann $ 4n - 1 + 1 = 4n$ Schritte, weil dazu noch eine Multiplikation kommt.
Von den Polynomen [mm] $y_{i} L_{i}^{(n)}(x) [/mm] $ gibt es $n + 1$ Stück.
D.h, um alle $n + 1$ Polynome [mm] $y_{i} L_{i}^{(n)}(x) [/mm] $ zu berechnen, brauchen wir $(n + 1) [mm] \cdot [/mm] 4n = [mm] 4n^{2} [/mm] + 4n$ Rechenoperationen.
Das Lagrangsche Interpolationspolynom [mm] $P_{n}(x) [/mm] = [mm] \sum\limits_{i = 0}^{n} y_{i} \cdot L_{i}^{(n)}(x)$ [/mm] ist die Summe von $n + 1$ solcher Polynome [mm] $y_{i} \cdot L_{i}^{(n)}(x)$. [/mm] Die Summe besteht also aus $n$ Additionen.
Um also das Polynom [mm] $P_{n}(x)$ [/mm] zu berechnen, brauchen wir insgesamt [mm] $4n^{2} [/mm] + 4n + n = [mm] 4n^{2} [/mm] + 5n$ Rechenoperationen.
Würde das so stimmen? Ich habe das mehrmals kontrolliert, aber ich finde keinen Fehler. Aber es kann auch gut sein, dass ich etwas übersehen habe.
Mein Ansatz zur Aufgabe 2 poste ich morgen, da es gerade zeitlich nicht reicht.
Ich freue mich auf einen Feedback!
Schönen Abend noch
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:54 Sa 18.01.2020 | | Autor: | felixf |
Moin!
> Würde das so stimmen? Ich habe das mehrmals kontrolliert,
> aber ich finde keinen Fehler. Aber es kann auch gut sein,
> dass ich etwas übersehen habe.
Sieht richtig aus.
LG Felix
|
|
|
|
