Polinomio de ajuste donde el polinomio debe ser monótona creciente

Question

Dado un conjunto de monótonamente creciente de puntos de datos (en 2D), quiero ajustar un polinomio a los datos que es monótonamente creciente sobre el dominio de los datos. Si el mayor valor de x es de 100, no me importa lo que la pendiente de la polinomio es en x=101.

También me gustaría mantener el grado del polinomio por debajo de 7. Mis datos por lo general tiene sobre 20 (x,y) pares. Menos plazas de ajuste es probablemente el mejor, pero estoy abierto a otras técnicas.

Estaba pensando que tal vez yo podría crear una b-spline, muestra que el b-spline (generar, digamos, otro de 100 puntos de datos), luego de realizar un polinomio de ajuste. Hace que el enfoque de sonido?

Answer 1

Creo que el problema no es, precisamente, declaró: su claro lo de "minimizar el grado del polinomio, mientras se ajusta bastante bien a los datos" significa (lo que es "bastante bien?").

De todos modos, fijo de grado, esto puede ser formulado como un semidefinite programa que puede ser resuelto aproximadamente en el polinomio de tiempo; hay un montón de programas por ahí que puede resolver semidefinite programas de manera muy eficiente, por ejemplo, sedumi.

En efecto, supongamos que los puntos de datos se $(x_1,y_1), (x_2,y_2), \ldots, (x_n,y_n)$. Deje $y$ ser el vector que acumula el $y_i$ y deje $V$ ser la matriz de Vandermonde $$V = \begin{pmatrix} 1 & x_1 & x_1^2 & \cdots& x_1^n \\ 1 & x_2 & x_2^2 & \cdots & x_2^n \\ \vdots & \vdots & \vdots & & \vdots \\ 1 & x_n & x_n^2 & \cdots & x_n^n \end{pmatrix}$$ Then, you'd like the minimize $||y-Vp||_2^2$ subject to the constraint that the entries of the vector $p$, which we will call $p_i$, correspond to a monotonic polynomial on your domain $[a,b]$, or, in other words, $p'(x) \geq 0$ on $[a,b]$: $$ p_1 + 2p_1 x + 3 p_2^2 + \cdots n p_n x^{n-1} \geq 0 ~~~ \mbox{ for all } x \in [a,b].$$ Esta última restricción puede ser escrito como una semidefinite programa,como se indica en estas notas de la conferencia. Voy a describir brevemente la idea.

Un polinomio univariado que es no negativa tiene una representación como una suma de los cuadrados de polinomios. En particular, si $p'(x) \geq 0$$[a,b]$, y su grado $d$ es, a decir, incluso, puede ser escrito como $$p'(x) = s(x) + (x-a)(b-x) t(x),~~~~~~~~(1)$$ where $s(x), t(x)$ are sums of squares of polynomials (this is Theorem 6 in the above-linked lecture notes; a similar formula is available for odd degree). The condition that a polynomial $s(x)$ is a sum of squares is equivalent to saying there is a nonnegative definite matrix $Q$ such that $$ s(x) = \begin{pmatrix} 1 & x & \cdots x^{d/2} \end{pmatrix} Q \begin{pmatrix} 1 \\ x \\ x^2 \\ \vdots \\ x^{d/2} \end{pmatrix}.$$ Este es el Lema 3 en las mismas notas de la conferencia.

Poniendo todo junto, lo que nos optimizar son las entradas de las matrices de $Q_1,Q_2$ que hacen los polinomios $s(x)=x^T Q_1 x,t(x)=x^T Q_2 x$ sumas de cuadrados, lo que significa que la imposición de las restricciones de $Q_1 \geq 0, Q_2 \geq 0$. A Continuación, Eq. (1) es lineal y restricción en las entradas de las matrices de $Q_1,Q_2$. Esto le da a usted tiene un semidefinite programa puede ingresar a su SDP solver.

Answer 2

Ignorando la pregunta de minimizar el grado, es ciertamente posible.

Uno puede encontrar una función positiva $f$ para que, si $p'$ está cerca de a $f$ en todo el intervalo, a continuación, $p = \int^x f(t) dt$ (con integración constante elegido para que $p(x_1)$ está cerca de a$x_1$), $p(x)$ aproximado de los puntos de datos dada la precisión. Elija algunos de positividad preservar esquema de aproximación, tales como los polinomios de Bernstein para obtener un positivo polinomio $p'$ dentro de cualquier distancia deseada de $f'$ en un intervalo que contiene a todos los $x_i$. Integrar a producir $p$.

Answer 3

Bueno, definitivamente no es la mejor respuesta desde el punto de vista práctico, sin embargo, hace dos cosas. En primer lugar, se demuestra la existencia de dicho polinomio. En segundo lugar, por el trabajo de algunas constantes, uno puede tratar de obtener un límite superior en el grado.

Supongamos que recibimos $x_0<x_2<...x_n$ $y_0<y_2<...y_n$ y estamos en busca de un aumento de la polinomio tal que $P(x_i)=y_i,$ $0\le i\le n.$ Es fácil construir un $C^1[x_0,x_n]$ función de $f,$ tal que $f(x_i)=y_i$ $f'(x)\ge\delta>0$ de $\delta.$ Por cada $\varepsilon > 0$ existe un polinomio $P_{\varepsilon}$ tal que $$\|f'-P_{\varepsilon}\|\le \varepsilon.$$ Considerar $$Q_{\varepsilon}(x)=y_0+\int_{x_0}^{x}P_{\varepsilon}(t)dt.$$ Then, $\|f-Q_{\varepsilon}\|\le \varepsilon (x_n-x_0).$ Let $R_{\varepsilon}$ be the Lagrange polynomial, which interpolates $R_{\varepsilon}(x_i)=y_i-Q_{\varepsilon}(x_i),$ $0\le i\le n.$ Consider a liner operator $A: \mathbb{R}^{n+1}\\mathbb{R}^m,$ such that $A(z_0,z_1,...z_n)=R'(z_0,...z_n),$ where $R'(z_0,...z_n)$ is a derivative of Lagrange polynomial $R,$ such that $R(x_i)=z_i.$ Since this operator is a linear operator between two finite dimensional spaces, there is a constant $C,$ such that $\|R'\|\le C\max |z_k|.$ Elija $\varepsilon > 0 $ tal que $C(x_n-x_0)\varepsilon+\varepsilon \le \delta.$ $R_{\varepsilon}=R_{\varepsilon}(y_0-Q_{\varepsilon}(x_0)...y_n-Q_{\varepsilon}(x_n)),$ tenemos $\|R'\|\le \delta-\varepsilon$ y es fácil ver que $R_{\varepsilon}+Q_{\varepsilon}$ satisface todos los requerimientos.

Answer 4

Estoy suponiendo que ya te dijo "ajuste", el polinomio no tiene que pasar a través de sus puntos dados.

Yo diría que LS de hecho es lo suficientemente bueno para sus propósitos. Usted puede hacer las cosas paso a paso (si se ajustan mediante polinomios ortogonales, esto es bastante fácil de hacer) y el monitor de su polinomios gráficamente (ver grácos de su polinomio y los puntos originales) o monitor de cantidades como la (ajustado) $R^2$ a medida que aumente el grado de su polinomio de ajuste.