(953) - Polinomios de Bernstein

El teorema de aproximación polinómica de Weierstrass indica que toda función continua en un intervalo cerrado se puede aproximar uniformememte por una sucesión de polinomios. Por ejemplo, podemos usar los polinomios de Bernsteins para aproximar $f(x)$ en $[a,b]$. $$ B_N(x) = \sum_{k=0}^N f\left(a+\frac{b-a}{N}k\right)\binom{N}{k} \frac{(x-a)^k(b-x)^{N-k}}{(b-a)^N} \qquad B_N(x) = \sum_{k=0}^N \beta_k B_{N,k}(x) ;$$
Como se puede ver, se ha aproximado por un polinomio como una combinación lineal de los elementos de una base polinómica (los polinomios de Bernstein), con $(N+1)$ polinomios de grado $N$ , $\Big\{ B_{N,k}(x)\Big\}_{k=0}^N$ vienen dados por: $$ B_{N,k}(x) = \binom{N}{k} \frac{(x-a)^k(b-x)^{N-k}}{(b-a)^N} \qquad \beta_k = f\left(a+\frac{b-a}{N}k\right) $$ Donde $\beta_k$ son los coeficientes de Bernstein-Bézier

Tras una normalización donde se define la nueva variable $t=\displaystyle \frac{x-a}{b-a}$, ahora $t\in[0,1]$, por lo que se simplifican las expresiones: $$ B_N(t) = \sum_{k=0}^N f\left(\frac{k}{N}\right)\binom{N}{k} t^k(1-t)^{N-k} $$

Los polinomios satisfacen estas relaciones $$ \binom{N}{k} \left(\frac{k}{N}\right)^k\left(1-\frac{k}{N}\right)^{N-k} = \binom{N}{k}\frac{k^k (N-k)^{N-k}}{N^N} \geqslant B_{N,k}(t) \geqslant 0 \implies \frac{N!}{2^N \displaystyle \left(\frac{N}{2}\right)!^2} \geqslant B_{N,\frac{N}{2}}(t) \geqslant 0 $$ Nótese que los polinomios tienen cierta simetría: $$ B_{N,k}(t)=B_{N,N-k}(1-t) $$
En particular se satisface: $$ 0 \leqslant t \leqslant 1 \implies \sum_{k=0}^N B_{N,k}(t) = 1 $$ Veamos algunos ejemplos:

Autor: Đɑvɪẟ Ƒernández-De la Cruʒ.

(683) - Polinomios logarítmicos y series logarítmicas

Supongamos que tenemos un número $x$ y queremos saber de qué número $t$ es su logaritmo [natural], $x=\ln(t)$ : sería tan fácil como hallar $t=e^x$ . Sin embargo, supongamos que tenemos una calculadora muy básica que solo suma, resta, divide y multiplica; no tiene necesariamente potencias y el número $e$ ni está, la típica calculadora en cotabilidad. ¿Cómo hallaríamos la solución? La solución viene dado por una serie de polinomios logarítmicos (donde podemos obtener el grado de aproximación que queramos con una suma parcial): $$\sum_{n=0}^\infty \frac{1}{n!}\ln^n(x) = x \qquad \sum_{n=0}^\infty \frac{(-1)^n}{n!}\ln^n(x) = \frac{1}{x}$$ Es más, siguiendo este resultado, uno puede ver cómo expresar cualquier polinomio “clásico” de grado $N$ , $P_N(x)$ , con coeficientes $\big(a_k\big)_{k=0}^N$ , como un polinomio logarítmico_$$P_N(x) = \sum_{k=0}^N a_k x^k = \sum_{k=0}^N a_k \sum_{n=0}^\infty \frac{k^n}{n!}\ln^n(x) = \sum_{n=0}^\infty \frac{\ln^n(x)}{n!}\sum_{k=0}^N a_k k^n$$ ¿Cómo se obtienen estas relaciones? Muchas se sacan usando series de Taylor y sustituyendo $x\mapsto\ln(t)$ . Por ejemplo si tomamos la del coseno y seno hiperbólicos:
$$\sum_{n=0}^\infty \frac{1}{(2n)!}\ln^{2n}(x) = \frac{x^2+1}{2x} \qquad \sum_{n=0}^\infty \frac{1}{(2n+1)!}\ln^{2n+1}(x) = \frac{x^2-1}{2x}$$Es más, siquiendo este razonamiento uno puede hallar una expresión cerrada en términos únicamente de logaritmos del logaritmo integral: $\displaystyle \operatorname{li} \overset{\text{def}}{=}―\hspace{-11.5pt}\int_0^x \frac{1}{\ln t} \;\text{d}t$ a través de la expresión $\operatorname{li}(x)\triangleq\operatorname{Ei}\big(\ln(x)\big)$ , de una función íntimamente relacionada, la exponencial integral $\displaystyle \operatorname{Ei}(x) \overset{\text{def}}{=}―\hspace{-11.5pt}\int_{-\infty}^x\frac{e^t}{t}\;\text{d}t$ : $$\operatorname{li}(x) = \gamma+\ln\!\big|\!\ln(x)\big| + \sum_{n=1}^\infty \frac{1}{n \, n!}\ln^n(x)$$ Uno puede ver fácilmente que lo que hemos estado haciendo hasta hora es buscar expresiones “bomitas” que tengan alguna exponencial de por medio, y haciendo un cambio de variable tontorrón obtenemos expresiones en términos que nos interesan, es decir, pasamos de series polinómicas en $ \mathbb{R}[x]$ tras un cambio de variable a series polinómicas logarítmicamente en $ \mathbb{R}\big[\ln(t)\big] \cong \mathbb{R}[x]/(t-e^x) \cong \mathbb{R}[x]/\big(\ln(t)-x\big) $ . Es más, $\big\{ \ln^k(t) \big\}_{k=0}^N$ conforman una base de $\mathbb{C}_N\big[\ln(t)\big]$ para cualquier $N$ .
Además esto es tan importante que en notación asitótica si uno pone una virgulilla, $ \widetilde{\mathcal{O}} , \widetilde{ {\scriptstyle \mathcal{O}} }, \widetilde{\Omega},\cdots$ , significa que no está acotado por dicha función como tal sino como dicha función por la $\alpha$-ésima potencia del logaritmo de dicha función para algún $\alpha$ , es decir: $$g(x) \in \widetilde{\mathcal{O}}\Big(f(x)\Big) \!\overset{\;\Delta}{\iff} g(x) \in \mathcal{O}\Big(f(x)\,\ln^\alpha\!\!\big(f(x)\big)\Big) \\ g(x) \in \widetilde{{\scriptstyle \mathcal{O}}}\Big(f(x)\Big) \!\overset{\;\Delta}{\iff} g(x) \in {\scriptstyle \mathcal{O}}\Big(f(x)\,\ln^\alpha\!\!\big(f(x)\big)\Big) \\ g(x) \in \widetilde{\Omega}\Big(f(x)\Big) \!\overset{\;\Delta}{\iff} g(x) \in \Omega\Big(f(x)\,\ln^\alpha\!\!\big(f(x)\big)\Big)$$ Veamos dos ejemplos

1. El algoritmo bitonic sort tiene un coste operacional de $\widetilde{\mathcal{O}}(n)$ , en particular, de $\mathcal{O}\Big(n\ln^2(n)\Big)$ .
2. El estimador de medianas repetidas (Spiegel): por fuerza bruta tiene un coste operativo de $\mathcal{O}(n^2) \subsetneq \widetilde{\mathcal{O}}(n^2)$ ; usando téctinas sofisticadas, $\mathcal{O}\big(n \ln^2(n)\big) \subsetneq \widetilde{\mathcal{O}}(n)$ ; en tiempo esperado randomizado, $\mathcal{O}\big(n \ln(n)\big) \subsetneq \widetilde{\mathcal{O}}(n)$ ; pero en un algoritmo on-line con un tiempo de actualización $\mathcal{O}\big(n\big) \subsetneq \widetilde{\mathcal{O}}(n)$ .

Un alumno de matemáticas ya se estará preguntando cómo aplicar esto y a raíz de qué sale este artículo. El Teorema de Aproximación polinómica de Weierstraß nos asegura que para una función continua $f(x)$ en el compacto $I=[a,b]\subset\mathbb{R}$ existe una sucesión de polinomios “clásicos” $ \big\{P_n(x)\big\}_{n=1}^\infty$ que converge uniformemente en $I$ hacia $f(x)$ (se pueden tomar una subsucesión de estos polinomios “clásicos” para que sean de grado ascendente estrictamente) . En particular, dado $\varepsilon > 0$ , existe un polinomio “clásico” $P(x)$ tal que: $$\Big|f(x) − P(x)\Big| < \varepsilon \qquad \forall x\in I=[a,b]$$ Es decir, que si repetimos el cambio de variable $x\mapsto\ln(t)$ , y denotando $\varphi(t) = f\big(\ln(t)\big) = \big(f\circ\ln\big)(t) $ $$\Big|\varphi(t) − P\big(\ln(t)\big)\Big| < \varepsilon \qquad \forall t\in J=e^I=\big[e^a,e^b\big] \iff \ln(t)\in I$$ El razonamiento que hemos hecho aquí es muy similar al que se suele hacer para introducir los polinomios trigonométricos, sin embargo, en estos últimos se sustituía la $n$-ésima potencia por el $n$-ésimo armónico (ya que el $n$-ésima potencia se podía escribir como una suma de los $k$-ésimos armónicos con $k=1,\cdots,n$ y es más fácil entender y trabajar con una onda como suma de armónicos) . Con los logaritmos no podemos hacer lo mismo ya que $\log(ab)=\log(a)+\log(b)$ por lo que tenemos que $ \big\{ \ln(kt) \big\}_{k=1}^N \cong \{1\} \cup\hspace{ -6.5pt }\raise-.25ex{\shortmid}\hspace{3pt} \{\ln t\}$ . Como último comentario hay ciertas propiedades compartidas: tanto la serie de Taylor de un polinomio “clásico” como la serie de Fourier de un polinomio trigonométrico tienen un número finito de términos, asimismo con un polinomio logarítmico con su expansión logarítmica. Sin embargo, si bien la derivada y/o la integral de un polinomio “clásico” y de un polinomio trigonométrico siguen siendo un polinomio “clásico” y de un polinomio trigonométrico (respectivamente), no se conserva para polinomios logarítmicos: $$ \frac{\text{d}}{\text{d}x} \ln^N(x) = N\frac{\ln^{N-1}(x)}{x} \qquad \int \ln^N(x)\;\text{d}x = x\sum_{k=0}^N (-1)^{N-k} \frac{N!}{k!}\ln^k(x)$$ Las series logarítmicas tienen un estudio en el intervalo $t\in\left[\frac{1}{e},e\right]\implies\ln(t)\in[-1,1]$ muy útil y fácilmente manejable (tipos de convergencia): $$\Bigg| \sum_{n=0}^\infty \lambda_n \ln^n(x) \Bigg| \leqslant \sum_{n=0}^\infty \Big|\lambda_n \ln^n(x) \Big| \leqslant \sum_{n=0}^\infty |\lambda_n |$$ Como curiosidad, se puede expresar la exponencial, $e^t$ , como una doble serie logarítmica. Es más, si una función tiene desarrollo de Taylor, se puede expresar como una serie logarítmica: $$e^t = \sum_{n=0}^\infty \frac{1}{n!} \sum_{k=0}^\infty \frac{n^k}{k!} \ln^k(t)$$

Autor: Đɑvɪẟ Ƒernández-De la Cruʒ.

(449) - El postulado perdido de Euclides. El Axioma de Pasch.

En el día de hoy traemos una entrega bastante curiosa, un postulado imprescindible que se le pasó al mismo Euclides. Como nota aclaratoria no se va a discutir sobre la importancia de los cinco postulados originales, ni de la trascendencia del V, sino de uno que estuvo "desaparecido" durante más de 22 siglos.

Los V postulados originales eran (puestos en terminología actual):

I)   Dos puntos cualesquiera definen una recta.

II)  Un segmento de recta se puede extender indefinidamente en una línea recta.

III) Se puede trazar una circunferencia dados un centro y un radio cualesquiera.

IV) Todos los ángulos rectos son congruentes entre sí.

V) Si una línea recta corta a otras dos, tal que la suma de los dos ángulos interiores del mismo lado sea menor que uno llano, las otras dos rectas se cortan, al prolongarse, por el lado donde están los ángulos menores que uno llano.

Este VI postulado lo descubrió Moritz Pasch (1843-1930), un matemático germanojudío que fue alumno del gran Weierstraß, el padre del análisis moderno. Pasch fue el primero en establecer una geometría axiomática. 

La diferencia entre axioma, y postulado es bastante sutil: Ambas son verdades que se consideran como absolutas, y a veces obvias, que se tienen que asumir como tales para seguir construyendo la materia en cuestión, por lo que no son demostrables. Los postulados se suelen diferenciar de los axiomas por ser relevantes a cierta materia, ciencia o contexto en particular, más que una verdad absoluta y general, que sería el axioma.

Por ello, el V Postulado de Euclides al ser solo válido para Geometría Euclídea, es un postulado, y no un axioma.

El axioma establece, de manera algo informal, que una línea que se interseca con un lado de un triángulo, y evita los tres vértices se interseca también con uno de las otros dos lados.

En rojo el triángulo original. En azul las prolongaciones de los segmentos del triángulo.
En negro las rectas que al cortar un lado sin pasar por el vértice, han de cortar otro.

David Hilbert utiliza el axioma de Pasch en su obra magna Fundamentos de Geometría (Grundlagen der Geometrie - 1903), que tiene una base axiomática de la geometría euclídea. Dependiendo de la edición aparece como 2.4, o como 2.5.

Este axioma se publicó en 1882, cuando Pasch no tenía ni 40 años. Pasch demostró que toda la geometría hasta entonces, tanto euclídea como no-euclídea, estaba, de algún modo, incompleta. La última vez que había ocurrido esto a niveles similares fuera cuando Newton corrigió a Aristóteles (finales del siglo XVII), y posteriormente, cuando Einstein corrigió a Newton (principios del siglo XX).

Dicho de otro modo, Pasch ha sido a Euclides, Gauß, Riemann, y Lobachevsky lo que Newton hubo sido a Aristóteles, y lo que Einstein fue a Newton.

Curiosamente el Teorema de Melenao se basa en el axioma de Pasch, y es bastante intuitivo. La falta de "intuición" matemática y rigorismo se ve en parte también en los Elementos de Euclides.

Autor: Đɑvɪẟ Ƒernández-De la Cruʒ.