Direkt zum Inhalt

Lexikon der Mathematik: Segment-Approximation

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], Pm den Raum der Polynome vom Grad m, und PPm,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 PPm,k hinsichtlich der Maximumnorm ||·|| ist wie folgt definiert: Für vorgegebenes fC[a, b] bestimme man sfPPm,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 sf beste Approximation an f aus PPm,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 PPm,k.

Bei der Segment-Approximation geht es um die Bestimmung von besten Approximationen sf aus PPm,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, Pm, I) die Minimalabweichung von f zu Pm 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 PPm,k entwickelt. Er basiert auf dem folgenden Satz, dessen Inhalt in der Literatur Lawson-Prinzip genannt wird.

Es sei fC[a, b]. Dann gilt:

  • Für alle Knotenmengen \(a={x}_{0}\le {x}_{1}\le \cdots \le {x}_{k}\le {x}_{k+1}=b\)ist \begin{eqnarray}\mathop{\text{min}}\limits_{i}d(f,{P}_{m},[{x}_{i},{x}_{i+1}])\le d(f,P{P}_{m,k})\\\le \mathop{\text{max}}\limits_{i}d(f,{P}_{m},[{x}_{i},{x}_{i+1}]).\end{eqnarray}
  • Es existiert eine optimale Knotenmenge f, welche ausgeglichene Knotenmenge von f ist.
  • Jede ausgeglichene Knotenmenge von f ist optimale Knotenmenge von f.
  • 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 fC[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 PPm,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.

    Lesermeinung

    Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

    • Die Autoren
    - Prof. Dr. Guido Walz

    Partnerinhalte