Aproximación polinómica del círculo o la elipse

Question

Lo intento de nuevo, con una pregunta que suena algo más sencilla, ya que mi anterior ( Generalizaciones del criterio de equi-oscilación ) no obtuvo ninguna respuesta:

Dejemos que $F:[0,1] \to R^2$ sea una curva polinómica paramétrica de grado $m$ . Quiero ajustar los coeficientes de $F$ para que esté lo más cerca posible del círculo unitario, $C$ . Más concretamente, quiero tener $F(0) = (1,0)$ y $F(1) = (0,1)$ y quiero la máxima distancia $$E_1 = \max \{dist(F(t),C): t \in [0,1]\}$$ para ser minimizado.

Estaría bien minimizar el siguiente error $E_2$ en su lugar, si es más fácil:

$$ E_2 = \max \{ \big| F_x^2(t) + F_y^2(t) - 1 \big|: t \in [0,1]\}$$

¿Y si sustituyo el círculo unitario por una elipse (por ejemplo)?

Dos preguntas concretas:

(1) ¿Podemos demostrar que la mejor aproximación es equi-oscilante, en algún sentido?

(2) ¿Cómo se puede calcular la mejor aproximación?

Este sitio http://spencermortensen.com/articles/bezier-circle/ tiene un buen resultado para el caso de un círculo con ( $m=3$ ).

También se podría pensar en esto como una pregunta sobre las curvas de Bézier de grado $m$ . Claramente, sería una buena idea establecer el primer punto de control igual a $(1,0)$ y el último igual a $(0,1)$ . A continuación, sólo hay que ajustar los demás puntos de control hasta conseguir un ajuste óptimo.

Una versión algebraica simple del problema: Encuentra dos polinomios $x(t)$ y $y(t)$ tal que $x(0)=1$ , $x(1)=0$ , $y(0)=0$ , $y(1)=1$ y $x(t)^2 + y(t)^2 - 1$ es pequeño para todos $t \in [0,1]$ .

Answer 1

Existe un procedimiento general para un círculo que minimiza $\max |p^2+q^2-1|$ . En lo que sigue es conveniente hacer dos ligeras modificaciones a su problema:

1. La parametrización se definirá en un intervalo $[-\alpha, \alpha] \subset [-1,1]$ en lugar de $[0,1]$ .
2. La aproximación es para otro arco de longitud $\tfrac{\pi}{2}$ .

La primera modificación es sólo una sustitución de parámetros y la segunda una rotación, por lo que resolver este problema claramente también resolverá el problema original.

Dejemos que $n > 0$ sea algún grado. Entonces queremos encontrar polinomios $p$ y $q$ de grado como máximo $n$ tal que $\max |p^2+q^2-1|$ se minimiza en el intervalo $[-1,1]$ . Tenga en cuenta que $p^2+q^2-1$ tendrá un grado como máximo $2n$ . Es bien sabido que el Polinomio de Chebyshev del primer tipo $T_{2n}$ resuelve el problema minimax en $[-1,1]$ entre todos los polinomios de grado como máximo $2n$ con coeficiente principal $2^{2n-1}$ . Por lo tanto, la mejor solución sería de la forma

$$ p^2+q^2 = 1 + \lambda T_{2n} $$

para algún parámetro $\lambda \in [0,1)$ que debe ser lo más pequeño posible. Dicha solución puede ser encontrada basándose en la factorización explícita

$$ \begin{eqnarray} 1 + \frac{T_{2n}(x)}{\cosh(2n\,t)} &=& \frac{2^{2n-1}}{\cosh(2n\, t)} \prod_{k=1}^{2n}\left(x - \cos\left(\tfrac{(2k-1) \pi}{2n} - t\,i\right)\right) \\ &=& \frac{2^{2n-1}}{\cosh(2n\, t)} \prod_{k=1}^{2n}\left(x - \cos\left(\tfrac{(2k-1) \pi}{2n}\right)\cosh(t) - \sin\left(\tfrac{(2k-1) \pi}{2n}\right) \sinh(t)\,i\right) \end{eqnarray}$$

para todos $t \in \mathbb{R}$ . (Ver el editar más adelante para una derivación de esta factorización). Como el LHS es un polinomio real, las raíces de la expresión anterior tienen simetría conjugada. Tomemos ahora $t > 0$ y definir el polinomio complejo $r(x)$ de grado $n$ incluyendo sólo las raíces en el medio plano superior:

$$ r(x) = \frac{2^n}{\sqrt{2 \cosh(2n\,t)}} \prod_{k=1}^{n}\left(x - \cos\left(\tfrac{(2k-1) \pi}{2n} - t\,i\right)\right).$$

Entonces $r(-x) = (-1)^n \,\overline{r}(x)$ donde $\overline{r}$ significa $r$ con coeficientes conjugados. Escribe $r = p + q\,i$ para polinomios reales $p$ y $q$ entonces

$$p^2+q^2 = (p + q\,i)(p - q\, i) = r \,\overline{r} = 1 + \frac{T_{2n}}{\cosh(2n\, t)}.$$ Así que, de hecho, encontramos una familia de un parámetro de buenas aproximaciones al círculo en el intervalo $[-1,1]$ . (Más grande $t$ dan mejores aproximaciones). La cuestión es qué significa este parámetro y qué valor de $t$ realmente resuelve nuestro problema tal y como está planteado.

Dado que todas las raíces de $r$ están en el semiplano superior su restricción a $\mathbb{R}$ es una curva compleja con argumento estrictamente creciente, por lo que envuelve la línea real alrededor del origen en dirección contraria a las agujas del reloj. Se puede demostrar que $p$ y $q$ tienen títulos $n$ y $n-1$ respectivamente, ambos tienen sólo raíces reales y las raíces de $q$ separar los de $p$ . El parámetro $t$ controla la "rapidez" con la que la curva rodea el origen, donde valores mayores de $t$ dan curvas "más lentas" que se mantienen más cerca del círculo unitario en $[-1,1]$ .

Las únicas restricciones que nos impiden tomar valores aribrados de $t$ son que la curva debe comenzar y terminar en el círculo unitario y cubrir un ángulo de exactamente $\tfrac{\pi}{2}$ en algún intervalo contenido en $[-1,1]$ . Los ceros más grandes de $T_{2n}$ son $\pm \cos(\tfrac{\pi}{4n})$ por lo que si $\alpha = \cos(\tfrac{\pi}{4n})$ y restringimos $r$ al intervalo $[-\alpha, \alpha]$ entonces al menos comienza y termina en el círculo unitario. Dado que $r(-\alpha) = (-1)^n \, \overline{r}(\alpha)$ el punto final se obtiene reflejando el punto inicial en el eje real (para incluso $n$ ) o el eje imaginario (para impar $n$ ). Por lo tanto, si tomamos $t$ máximo tal que $r(\alpha)^2$ es puramente imaginario, por lo que $p(\alpha) = \pm q(\alpha)$ entonces la curva abarca un ángulo de precisamente $\tfrac{\pi}{2}$ .

Para resumir los resultados de esta historia bastante larga:

1. Para obtener un título $n$ aproximación considere el polinomio $r(x)$ definida anteriormente que depende de un parámetro real auxiliar $t>0$ .
2. Dejemos que $\alpha = \cos(\tfrac{\pi}{4n})$ . Determinar el valor máximo $t>0$ para lo cual $r(\alpha)^2 \in i\,\mathbb{R}$ .
3. Entonces $|r(-\alpha)| = |r(\alpha)| = 1$ y $\left|\,|r(x)|^2 - 1\,\right| \leq \tfrac{1}{\cosh(2n \, t)}$ para $x \in [-\alpha, \alpha]$ . Además $r$ es la mejor aproximación de un cuarto de círculo en el intervalo $[-\alpha, \alpha]$ .

Las primeras aproximaciones encontradas de esta manera son:

$$ \begin{array}{c|c|c|c} n & \alpha & t & \max \, \left| \, |r|^2-1 \, \right| \\ \hline 1 & 0.70710678 & 0.65847895 & 0.5 \\ 2 & 0.92387953 & 1.2149195 & 0.015505028 \\ 3 & 0.96592583 & 1.5982608 & 0.0001368784 \\ 4 & 0.98078528 & 1.8786122 & 5.9437783 \times 10^{-7} \\ 5 & 0.98768834 & 2.098419 & 1.5406786 \times 10^{-9} \\ 6 & 0.99144486 & 2.2789419 & 2.6561189 \times 10^{-12} \\ 7 & 0.99371221 & 2.4320125 & 3.2665949 \times 10^{-15} \\ 8 & 0.99518473 & 2.5648448 & 3.0106701 \times 10^{-18} \\ 9 & 0.9961947 & 2.6821493 & 2.1570627 \times 10^{-21} \\ 10 & 0.99691733 & 2.7871679 & 1.2359399 \times 10^{-24} \end{array} $$

Editar: Así es como se puede encontrar la factorización. La propiedad clave es que $$T_{2n}\left(\frac{x+x^{-1}}{2}\right) = \frac{x^{2n}+x^{-2n}}{2}$$ para todos $x \neq 0$ . Así que $$1 + \frac{T_{2n}\left(\frac{x+x^{-1}}{2}\right)}{\cosh(2n\,t)} = \frac{2 \cosh(2n\,t) + x^{2n}+x^{-2n}}{2 \cosh(2n\,t)}$$ y esto desaparece cuando $x^{2n} = -e^{\pm 2n \, t}$ . Por lo tanto, las raíces son $$ x= \exp\left(\frac{(2k-1)\pi\,i}{2n} \pm t\right)$$ para $k \in \{1, \dotsc, 2n\}$ y para tal raíz tenemos $$\frac{x+x^{-1}}{2} = \cos\left(\frac{(2k-1)\pi}{2n}\mp t\, i\right).$$ Desde $\cos$ es incluso esto da $2n$ raíces del polinomio $$1+\frac{T_{2n}}{\cosh(2n \, t)}$$ de grado $2n$ . Después de fijar el coeficiente principal adecuado, la factorización es la siguiente.

Answer 2

Una propuesta: Presente su arco circular en forma $$\eqalign{ x(t)&={1\over\sqrt{2}}(\cos t-\sin t) ={1\over\sqrt{2}}\left(1-t-{t^2\over2}+{t^3\over6}+{t^4\over 24}-{t^5\over120}-\ldots\right) \cr y(t)&={1\over\sqrt{2}}(\cos t+\sin t) ={1\over\sqrt{2}}\left(1+t-{t^2\over2}-{t^3\over6}+{t^4\over 24}+{t^5\over120}-\ldots\right) \cr}\qquad\left(-{\pi\over4}\leq t\leq{\pi\over4}\right)$$ y utilizar tantos términos como sean necesarios para la precisión requerida. La siguiente figura muestra una superposición del círculo exacto y la aproximación polinómica anterior hasta ${t^5\over120}$ :

Answer 3

La respuesta completa puede ser difícil, pero al contrario que el OP, no veo ninguna dificultad en plantear la pregunta y generalizar el concepto de equi-oscilación al caso bidimensional. Sea $V_n$ denotan el espacio afín de todos los pares $v=(x_n,y_n)$ de polinomios de grado cada uno $\leq n$ con $v(0)=(1,0)$ y $v(1)=(0,1)$ . Tenga en cuenta que $V_n$ tiene dimensión $2(n-1)$ . Para $v=(x_n,y_n)\in V$ poner

$$ || v ||=\sup_{t\in[0,1]} \bigg| x_n(t)^2+y_n(t)^2-1\bigg| $$

Entonces defina $\mu_n={\sf inf}(|| v |||, v \in V_n)={\sf min}(|| v |||, v \in V_n)$ . Digamos que un $v\in V_n$ es óptimo si $||v||=\mu_n$ .

Definición Dejemos que $\varepsilon>0$ . Decimos que un par $v=(x_n,y_n)\in V_n$ es $\varepsilon$ -oscilante si hay una secuencia creciente de $1+{\sf dim}(V_n)$ elementos $t_1<t_2< \ldots<t_{1+{\sf dim}(V_n)}$ en $[0,1]$ tal que la secuencia $w_i=x_n(t_i)^2+y_n(t_i)^2-1$ es alternativo (es decir $w_{i+1}=-w_i$ para todos $i$ ) y $|w_i|=\varepsilon$ para todos $i$ .

Tenga en cuenta que $1+{\sf dim}(V_n)=2n-1$ arriba.

Conjetura 1 A $v\in V_n$ es óptimo si y sólo si es $\mu_n$ -oscilante.

Conjetura 2 Existe una única solución óptima para cada $n$ .

Estas conjeturas son ciertas cuando $n=2$ . De hecho, en este caso un genérico $v\in V_2$ puede escribirse $$v(a,b,t)=(1-t+at(1-t),t+bt(1-t))$$ . Pongamos también

$$ F(a,b,t)=1-t+at(1-t))^2+(t+bt(1-t))^2-1 \tag{1} $$

Dejemos que $\theta$ sea la mayor raíz real de $T=X^4+4X^3-8X^2+8X-4$ para que $\theta$ es aproximadamente $0,85 \ldots$ . Afirmo entonces que $v(\theta,\theta,.)$ es la única solución óptima.

Dejemos que $G(t)=F(\theta,\theta,t)$ y $$\mu=G(1/2)=\frac{\theta^2}{8}+\frac{\theta}{2}-\frac{1}{2} \approx 0,015 \tag{3} $$

Tenemos entonces las identidades

$$ \mu-G(t)=\big(t-\frac{1}{2}\big)^2 \bigg(\frac{\theta^2}{2}+2\theta-2+2\theta^2t(1-t) \bigg) \tag{4} $$

$$ \mu+G(t)=2\theta^2 \bigg(t(1-t)-\frac{\theta-1}{2\theta^2} \bigg)^2 \tag{5} $$

Obsérvese que el polinomio $Q(t)=t(1-t)-\frac{\theta-1}{2\theta^2}$ tiene dos raíces en $[0,1]$ , $\alpha$ y $1-\alpha$ donde $\alpha \approx 0,12 \ldots$ . Esto demuestra que $G$ es $\mu$ -oscilante.

Dejemos que $(a,b)$ sea cualquier par tal que $||v(a,b,.)|| \leq \mu $ . Entonces

$$ F(a,b,\alpha) \geq -\mu, \ F(a,b,\frac{1}{2}) \leq \mu, \ F(a,b,1-\alpha) \geq -\mu \tag{6} $$

Estas tres desigualdades bastarán para forzar $(a,b)=(\theta,\theta)$ mostrando optimalidad y unicidad. En efecto, consideremos en el plano los puntos $A,B,C,S$ con las siguientes coordenadas :

$$ A(-\frac{1}{\alpha},-\frac{1}{1-\alpha}), \ B(-2,-2), \ C(-\frac{1}{1-\alpha},-\frac{1}{\alpha}), \ S(\theta,\theta) $$

También hay que tener en cuenta el disco $D_A$ con centro $A$ y el radio $\frac{\sqrt{\mu}}{\alpha(1-\alpha)}$ , el disco $D_B$ con centro $B$ y el radio $4\sqrt{1+\mu})$ y el disco $D_C$ con centro $C$ y el radio $\frac{\sqrt{\mu}}{\alpha(1-\alpha)}$ .

Entonces un par $(a,b)$ satisface (6) si el punto con dichas coordenadas está dentro de $D_C$ pero fuera $D_A$ y $D_B$ . La figura siguiente muestra que $S$ es el único punto de este tipo, qed.

Answer 4

Tal vez pueda obtener su respuesta aquí:

http://jimherold.com/2012/04/20/least-squares-bezier-fit/

http://www.google.com.br/url?sa=t&rct=j&q=Optimal+ajuste+de+las+curvas+de+bezier&source=web&cd=1&cad=rja&ved=0CCsQFjAA&url=https%3A%2F%2Fece. uwaterloo.ca%2F~dwharder%2FMaplesque%2FBezier%2FBestFittingBezierCurves.ppt&ei=tnXxUK_UDZOe8gTko4H4Cw&usg=AFQjCNFkMNXviJSzFCBIqbTL3EWZcgTpA

http://www.google.com.br/url?sa=t&rct=j&q=Optimal+ajuste+de+curvas+de+bezier&source=web&cd=9&cad=rja&ved=0CGkQFjAI&url=http%3A%2F%2Fwww.dtic.mil%2Fcgi-bin%2FGetTRDoc%3FAD%3DADA350611&ei=tnXxUK_UDZOe8gTko4H4Cw&usg=AFQjCNGW_AP5QddfGugn_5WzoIUDIMJ7ng

Answer 5

Para empezar, existe el conocido ajuste racional exacto de $(2t/(1+t^2), (1-t^2)/(1+t^2)$ . (Porque $(2t)^2 + (1-t^2)^2 = 4t^2 + 1 - 2t^2 + t^4 = 1 + 2t^2 + t^4 = (1+t^2)^2$ ).

Si escribe $1/(1+t^2) = 1-t^2+t^4 ...\pm t^{2k} ...$ , se puede obtener una aproximación polinómica inicial.