Problem der Bestimmung einer besten Approximationen durch Splines mit freien Knoten, die nicht notwendigerweise stetig sind.

Es bezeichne C[a, b] die Menge der stetigen Funktionen auf einem Intervall [a, b], P_m den Raum der Polynome vom Grad m, und PP_m,k die Menge der Splines vom Grad m mit k freien Knoten, d. h. \begin{eqnarray}\begin{array}{l}P{P}_{m,k}=\{s:[a,b]\mapsto {\mathbb{R}}:\text{es gibt}\\\qquad a={x}_{0}\lt {x}_{1}\lt \cdots \lt {x}_{k}\lt {x}_{k+1}=b\\\qquad \text{so, da}{\unicode {x00df}}\,s{|}_{[{x}_{j},{x}_{j+1})}\in {P}_{m},j=0,\mathrm{\ldots},k-1,\\\qquad \text{und}\,s{|}_{[{x}_{k},{x}_{k+1}]}\in {P}_{m}\}.\end{array}\end{eqnarray} Das Problem der besten Approximation aus PP_m,k hinsichtlich der Maximumnorm ||·||_∞ ist wie folgt definiert: Für vorgegebenes f ∈ C[a, b] bestimme man s_f ∈ PP_m,k so, daß \begin{eqnarray}||f-{s}_{f}|{|}_{\infty}=\inf \{||f-s|{|}_{\infty}:s\in P{P}_{m,k}\}\end{eqnarray} gilt. In diesem Fall wird s_f beste Approximation an f aus PP_m,k genannt und die zu sf gehörigen Knoten \(a={x}_{0}\lt {x}_{1}\lt \cdots \lt {x}_{k}\lt {x}_{k+1}=b\) heißen optimale Knotenmenge von f. Der Ausdruck \begin{eqnarray}d(f,P{P}_{m,k})=\inf \{||f-s|{|}_{\infty}:s\in P{P}_{m,k}\}\end{eqnarray} heißt Minimalabweichung von f zu PP_m,k.

Bei der Segment-Approximation geht es um die Bestimmung von besten Approximationen s_f aus PP_m,k. Wichtig ist in diesem Zusammenhang der Begriff einer ausgeglichenen Knotenmenge von f. Dies sind Knoten \(a={x}_{0}\le {x}_{1}\le \cdots \le {x}_{k}\le {x}_{k+1}=b\) mit der Eigenschaft \begin{eqnarray}d(f,{P}_{m}[{x}_{i-1},{x}_{i}])=d(f,{P}_{m}[{x}_{i},{x}_{i+1}])\end{eqnarray} für alle i ∈ {0,…,k}, wobei d(f, P_m, I) die Minimalabweichung von f zu P_m auf der Menge I bezeichnet.

1986 wurde von G. Nürnberger, M. Sommer und H. Strauß der nachfolgend beschriebene Algorithmus zur Bestimmung einer besten Approximation aus PP_m,k entwickelt. Er basiert auf dem folgenden Satz, dessen Inhalt in der Literatur Lawson-Prinzip genannt wird.

Es sei f ∈ C[a, b]. Dann gilt:

Im ersten Schritt des o. g. Algorithmus zur Segment-Approximation wählt man eine (Start-)Knotenmenge \begin{eqnarray}a={x}_{0, 1}\lt {x}_{1, 1}\lt \cdots \lt {x}_{k,1}\lt {x}_{k+1, 1}=b,\end{eqnarray} berechnet mit dem Remez-Algorithmus die Werte \begin{eqnarray}{d}_{i,1}=d(f,{P}_{m},[{x}_{i,1},{x}_{i+1, 1}],i=0,\ldots, k,\end{eqnarray} und setzt \({10}^{\alpha_1}={\min}_{i}{d}_{i,1}\), sowie \({10}^{\beta_1}={\min}_{i}{d}_{i,1}\). Im allgemeinen Schritt bestimmt man zunächst sukzessiv eine Knotenmenge \begin{eqnarray}\begin{array}{ll}a={x}_{0,p+1} & \lt {x}_{1,p+1}\lt \cdots \lt {x}_{k,p+1}\\ & \lt {x}_{{j}_{p+1}}{}_{1,p+1}=\cdots ={x}_{k+1,p+1}=b\end{array}\end{eqnarray} so, daß \begin{eqnarray}{10}^{\frac{{\alpha}_{p}+{\beta}_{p}}{2}}=d(f,{P}_{m},[{x}_{i},{x}_{i+1},p])\end{eqnarray} für alle \(i\in \{0,\mathrm{\ldots},{j}_{p+1}-1\}\). Hierzu verwendet man den Remez-Algorithmus in Kombination mit der Regula falsi. Danach setzt man \begin{eqnarray}\begin{array}{l}{10}^{{\alpha}_{p+1}}=\max \{{10}^{{\alpha}_{p}},\min \{{10}^{\frac{{\alpha}_{p}+{\beta}_{p}}{2}},d(f,{P}_{m},I)\}\}\\ {10}^{{\beta}_{p+1}}=\min \{{10}^{{\beta}_{p}},\max \{{10}^{\frac{{\alpha}_{p}+{\beta}_{p}}{2}},d(f,{P}_{m},I)\}\},\end{array}\end{eqnarray} wobei \(I=[{x}_{k,p+1},{x}_{k+1,p+1}]\), und iteriert das Verfahren.

Der Algorithmus erzeugt induktiv für vorgegebenes f ∈ C[a, b] eine ausgeglichene Knotenmenge von f, und die Folge \(10\frac{{\alpha}_{p}+{\beta}_{p}}{2},p\in {\mathbb{N}}\), konvergiert gegen die Minimalabweichung von f zu PP_m,k.

In der Literatur wird vorgeschlagen, diesen Algorithmus mit einem für Splines mit festen Knoten entwickelten Remezalgorithmus zu kombinieren, um gut approximierende Splines mit freien Knoten zu bestimmen.

Mitte der 90er Jahre wurden von G. Meinardus, G. Nürnberger und G. Walz ähnliche Verfahren zur bivariate Segment-Approximation entwickelt.

[1] Nürnberger G.: Approximation by Spline Functions. Springer-Verlag Heidelberg/Berlin, 1989.