Technische Universität Berlin Wintersemester 07/08 Fakultät II – Institut für Mathematik PD Dr. M. Ehrhardt Dipl.–Ing. C. Schröder

7. Übungsblatt zur VL “Numerik für Informatiker” (Polynominterpolation)

\underline{1. Aufgabe} (5 Punkte)

Gesucht ist das Polynom p(x) = α_{n}x^{n} + α_{n−1}x^{n−1} + … + α_{1}x + α_{0} minimalen Grades, das folgende Bedingungen erfüllt p(x_{i}) = f_{i}, wobei

\begin{matrix}x_{i} & −1 & 1 & 2 & 4 \\ f_{i} & 0 & 4 & 15 & 85 \end{matrix}

a) Stellen Sie ein lineares Gleichungssystem dessen Lösung der Vektor der Polynomkoeffizienten [α_{n}, α_{n−1}, …, α_{1}, α_{0}]^{⊤} ist. Lösen Sie es und geben Sie das Interpolationspolynom an.

b) Geben Sie die Lagrange-Darstellung an

p(x) = ∑_{i=0}^{n} f_{i}ℓ_{i}(x), wobei ℓ_{i}(x) := ∏_{\begin{matrix}j=0 \\ j≠i \end{matrix}}^{n} \frac{x − x_{j}}{x_{i} − x_{j}} .

Vereinfachen Sie die Polynome ℓ_{i}(x) soweit, dass Sie die Form z.B. ℓ_{i}(x) = \frac{(x−1)(x−5)(x+12.5)}{23} besitzen. (Die Zahlen und deren Anzahl sind ausgedacht). Hinweis: Aufgabe b) erfordert fast kein Rechnen.

\underline{2. Aufgabe} (8 Punkte)

a) Berechnen Sie per Hand die dividierten Differenzen folgender Wertepaare: a.1) die Paare aus der 1. Aufgabe,

a.2) \begin{matrix}x_{i} & −1 & 0 & 2 \\ f_{i} & −3 & −2 & 36 \end{matrix} a.3) \begin{matrix}x_{i} & 1 & −2 & −1 & 0 & 2 \\ f_{i} & 1 & 16 & −3 & −2 & 36 \end{matrix}

Hinweis: Bei Aufgabe a.3) kann man von einer vorherigen Aufgabe profitieren. Dies ist als Übung für die Praktische Aufgabe gedacht.

b) Geben Sie Newtonform der Interpolationspolynome an.

c) Werten Sie folgendes in Newtonform gegebenes Polynom mittels Horner Schema an der Stelle x = 0.5 aus!

p(x) = 2 + 3(x − 1) + (x − 1)(x + 2) − 4(x − 1)(x + 2)x + 2(x − 1)(x + 2)x(x − 2)

\underline{3. Aufgabe} (5 Punkte)

Angenommen die Funktion f(x) = sin(x) wurde an den Stellen x_{i} ∈ {0, 1, 2, 3, 4, 5} ausgewertet, dann aus den entstandenen Wertepaaren das Interpolationspolynom p(x) gebildet, welches schließlich an der Stelle x = 2.5 ausgewertet wurde.

Gilt die Abschätzung |p(2.5) − sin(2.5)| ≤ 5 · 10^{−3}? Begründen Sie Ihre Antwort.

\underline{4. Aufgabe} (2 Punkte)

Wahr oder falsch (ohne Begründung; Antwort richtig: 0.5 Punkte, falsch: −0.5 Punkte)

a) Die Auswertung eines Polynoms in Lagrangedarstellung benötigt O(n) Flops.

b) Die Auswertung eines Polynoms in Newtonform benötigt O(n^{2}) Flops.

c) Jedes Polynom p(x) vom Grad n kann als Produkt von n linearen Faktoren (den evtl. komplexen Nullstellen) geschrieben werden.

d) Das Horner-Schema ist speziell geeignet für die Lagrangedarstellung des Interpolationspolynoms.

\underline{Praktische Aufgabe} (10 Punkte)

a) Schreiben Sie eine Routine divdiff, die zwei gleichlange Vektoren x = [x_{0}, x_{1}, …, x_{n}] und f = [f_{0}, f_{1}, …, f_{n}] bekommt, wobei f_{i} den Funktionswert f(x_{i}) einer Funktion an der Stelle x_{i} enthält. Die Routine überschreibt f mit den dividierten Differenzen wie folgt: f_{i} ← f[x_{0}, …, x_{i}]. Implementieren Sie die Routine inplace und ohne lokale Arrays. Die Routine sollte eine Komplexität von O(n^{2}) haben und eine Fehlermeldung ausgeben, falls x zwei gleiche Elemente enthält. Hinweis: x bleibt konstant; im Wesentlichen besteht die Routine aus zwei geschachtelten for-Schleifen.

b) Schreiben Sie eine Routine horner, die zwei gleichlange Vektoren x = [x_{0}, x_{1}, …, x_{n}] und f = [f_{0}, f_{1}, …, f_{n}], wie von Aufgabe a) berechnet, und eine Zahl a bekommt und das Interpolationspolynom an der Stelle a auswertet. Implementieren Sie die Routine ohne lokale Arrays. Hinweis: x, f bleiben konstant; im Wesentlichen besteht die Routine aus einer for-Schleife.

c) Schreiben Sie eine Routine divdiff2, die zwei Vektoren x, f der Länge n + 1 sowie eine Zahl 0 ≤ m ≤ n entgegennimmt. An Stelle f_{i} steht der Funktionswert f(x_{i}) einer Funktion an der Stelle x_{i}, falls 0 ≤ i ≤ m und die dividierte Differenz f[x_{m}, x_{m+1}, …, x_{i}], falls m < i ≤ n. Die Routine überschreibt f_{i} mit f_{i} ← f[x_{0}, …, x_{i}] und soll eine Komplexität von O(mn) haben. Hinweis: Aufgabe a) kann als Spezialfall von c) für m = n verstanden werden. Für diese Aufgabe eignen sich Sprachen, die die Vektorindizierung bei Null beginnen. Ansonsten müssen alle Indizes um 1 geshiftet werden.

Abgabe - in der Vorlesung am 7. Dezember oder

- vorher im Briefkasten zwischen den Räumen MA470, MA471

Besprechung im Tutorium am 10. Dezember