Betrachten Sie das folgende Problem: Gegeben den Koeffizientenvektor
a = (a0, a1, . . . , an)T ∈ℝn+1 und t ∈ ℝ, werte das durch a definierte Polynom n-ten Grades
pn(x) := anx n + an−1x n−1 + · · · + a1x + a0 = ∑nk=0 akxk
an der Stelle x = t aus.
Um dieses Problem zu lösen bekommen Sie die folgende Algorithmus zur Verfügung gestellt:
Algorithmus Poly
Eingabe: a ∈ ℝn+1, t ∈ ℝ
Rückgabe: P = pn(t)
1: P ← an
2: Für k = 1, . . . , n
3: P ← P · t + an−k
4: [Ende] Für
5: Gib P zurück
a.) Zeigen Sie (z.B. induktiv), dass Algorithmus tatsächlich für jedes n ∈ ℕdas Polynom pn(t) korrekt auswertet.
