Question

Interpolationspolynom

Aufrufe: 145 Aktiv: 15.01.2024 um 21:43

0

Sei p ∈ Pn das Interpolationspolynom zu den n+1 paarweise verschiedenen Stützstellen t0, ..., tn mit den zugehörigen Werten y0, ..., yn Bestimmen Sie die Anzahl der benötigten Operationen

- zur Berechnung der Koeffizienten von p
- und zur Auswertung von p an einer beliebigen Stelle t = ξ
(a) bezüglich der Lagrange-Basis,
(b) bezüglich der Newton-Basis und
(c) bezüglich der Monom-Basis.
Hinweis: Die sehr naive Auswertung des Polynoms p(t) = a0 + a1+t + ... +an t^n (in der MonomBasis) erfordert O(n²) Mutliplikationen und n Additionen. Dagegen wird beim Hornerschema p(t) = a0 + (t · (a1 + t · (. . .(an-1 + t · ). . .)))

von innen nach außen ausgewertet. Wieviele Additionen und Multiplikationen sind dafür notwendig?

meine Lösung lautet /

(a) Lagrange-Basis:

Berechnung der Koeffizienten:
$L_{i} (t)=\prod_{j=0,j\neq i}^{n} \frac{t-t_{j}}{t_{i}t_{j}}$ Hierbei benötigt man für jeden Koeffizienten ai.n multiplikationen und n Divisionen,da dies für jeden Koeffizienten durchgeführt werden muss, sind insgesamt n² multiplikationen und n² divisionen erforderlich.Auswertung von p an ξ: p (t) = $\sum _{i=0}^{n}y_{i}.l_{i}(t)$ Hierbei sind für jede Lagrange-Basis li(t) n Multiplikationen und n Additionen notwendig. Da dies für jeden Term in der Summe geschieht,sind insgesamt n² Multiplikationen und n²Additionen erforderlich.

(b)Newton-Basis:Berechnung der Koeffizienten: Die Newton-Koeffizienten werden durch die dividierten Differenzen berechnet. Die Berechnung jeder dividierten Differenz erfordert eine Division und eine Addition. Da es n dividierte differenzen gibt,sind insgesamt n divisionen und n additionen notwendigAuswertung von p an ξ: $P(t)= a^{_{0}} + (t-t_{0}) . \left [ a_{1}+ \right (t-t_{1})].\left [ a_{n-1} + (t-t_{n-1})\right.a_{n} ]$

Hierbei sind für jeden Term $a_{i} + (t - t_{i}) \cdot$ jeweils eine Multiplikation und eine Addition notwendig. Da es $n$ solcher Terme gibt, erfordert dies $n$ Multiplikationen und $n$ Additionen. Insgesamt sind also n² Multiplikationen und n² Additionen notwendig.
c) Monom-Basis:

Berechnung der Koeffizienten: Die Berechnung der Monom-Koeffizienten erfolgt durch Lösen eines linearen Gleichungssystems. Dies erfordert in etwa $O (n³)$ Operationen, da die Invertierung der Vandermonde-Matrix notwendig ist.
Auswertung von p an ξ:

Die naive Auswertung des Polynoms benötigt

O (n²)

Multiplikationen und

O (n)

Additionen. Das Horner-Schema hingegen erfordert

O (n)

Multiplikationen und

O (n)

Additionen.

Das Horner-Schema ermöglicht somit eine effizientere Auswertung von Polynomen im Vergleich zur naiven Methode, die

O (n²)

Multiplikationen und

O (n)

Additionen erfordern würde. Mit dem Horner-Schema reduziert sich der Aufwand auf

O (n)

für beide Operationen, was besonders vorteilhaft ist, wenn

n

groß ist.

kann jemand mir sahen ob die lösung so Richtig ?

Vielen Dank
Abdull

Teilen Diese Frage melden

gefragt 15.01.2024 um 14:10

abdull
Punkte: 48

1

Bitte nachbearbeiten (oben "Frage bearbeiten") bez. Lesbarkeit. Außerdem stimmt die Formel für die Formel für die L_i (die Du auch mal als l_i) bezeichnest, nicht. Und was soll ai.n sein? Bitte sorgfältig, wenn wir das lesen sollen. ─ mikn 15.01.2024 um 16:23

Kommentar schreiben

1 Antwort

m.simon.539 · Accepted Answer · 2024-01-15T21:43:30Z

Bei Deiner Formel für $L_i$ fehlt im Nenner ein "-".

Meiner Meinung nach braucht es zum Aufstellen des Interpolations-Polynoms gar keine Operationen, da die Lagrange-Basispolynome erst bei der Auswertung ausgerechnet werden. Man kann zwar den konstanten Faktor Lagrange-Basispolynome, also $\displaystyle \frac{y_i}{ \displaystyle\prod_{j=0, j\not=i}^n (t_j-t_j)}$, einmalig ausrechnen, ich würde das aber aus numerischen Gründen lassen.

Die Auswertung eines Lagrange-Basispolynoms kosten 2n Subtraktionen und n Divisionen pro Basispolynom. Hinzu kommen nochmal n Multiplikationen mit den Stützwerten.

Mal nennst Du die Lagrange-Basispolynome $l_i$, mal $L_i$.

Bei der Newton-Interpolation hat man ein Dreieck-Tableau mit (n+1) + n + (n-1) + ... + 1 Zahlen. Die ersten (n+1) Zahlen sind die Stützwerte und müssen nicht berechnet werden, die anderen sind eine dividierte Differenzen, und jede dividierte Differenz braucht zwei Subtraktionen und eine Division.
Macht drei Operationen pro dividierte Differenz, und es gibt n + (n-1) + ... + 1 dividierte Differenzen.

Die Auswertung besteht aus n Schritten der Form $y_k = y_{k-1} + a_k(x-x_k)$, k=1...n. Macht pro Schritt eine Addition, eine Subtraktion und eine Multiplikation.

Ja, bei der Monom-Basis sind $O(n^3)$ Schritte zur Lösung des Gleichungsystemes erforderlich. Jetzt weiß ich nicht, ob $O(n^3)$ nicht zu ungenau ist. Allerdings solltest Du auch ein paar Worte zum Aufwand zum Aufstellen der Vandermonde-Matrix verlieren: $n(n-1)$ Multiplikationen, wenn man es schlau macht.

Die Aufwände für die naive Auswertung $O(n^2)$ und die Auswertung beim Horner-Schema $O(n)$ sind richtig, allerdings weiß ich nicht, ob hier die Antworten genau genug sind.