Approximation stückweise linearer Funktionen

Question

Gegeben:

n Paare von Punkten (x_i, f(x_i)) ∈ ℝ²    , i = 1, ...., n    wobei x_{1 <} x_{2 < ... <} x_n  für eine Funktion f : ℝ → ℝ

Es soll nun eine möglichst einfache Funktion g approximiert werden, für die g(x_i) = f(x_i)  für manche, aber nicht unbedingt alle x_i gilt und die zwischen diesen x_i linear ist.

Es soll also für geg. Parameter α, β > 0 den Ausdruck:

α * Anzahl linearer Segmente von g + β * ∑ von i = 2 bis (n-1) von |f(x_i) - g(x_i)|²

über alle Funktionen g minimieren, mit folgenden Eigenschaften:

g(x_{1) =} f(x₂), g(x_{n) =} f(x_n)

g ist stückweise linear und Ecken von g sitzen nur auf Punkten (x_i, f(x_i))

Aufgabe:

a): Es soll nun gezeigt werden, dass sich aus diesem Problem auch ein graphentheoretisches Problem formulieren lässt und es soll beschrieben werden, wie es sich lösen lässt

b): Das Problem soll für α = β = 1
und (x₁, f(x₁)) = (0, 0)    (x₂, f(x₂)) = (5, 5)   (x₃, f(x₃)) = (10, 2)    (x₄, f(x₄)) = (15, 0)

gelöst werden.