Vértice de un n-paralelepípedo más cercano a un punto. Método exhaustivo.

 

Sea $\mathcal{F}$ un n-paralelepípedo (sólido) generado por el conjunto de vectores linealmente independientes $B = \{\vec{b}_1,...,\vec{b}_n\}$. Sea $P\in\mathcal{F}$ un punto de dicho n-paralelepípedo. ¿Cuál es el vértice del n-paralelepípedo más cercano a $P$?

 Estrategia 1. Método exhaustivo.

Podemos calcular las coordenadas de todos los vértices del n-paralelepípedo.

Por ejemplo, en $\mathbb{R}^3$, los 8 vértices del paralelepípedo son:

$V_1 = \vec{0} = (0,0,0)$

$V_2 = \vec{b}_1$

$V_3 = \vec{b}_2$

$V_4 = \vec{b}_3$

$V_5 = \vec{b}_1 + \vec{b}_2$

$V_6 = \vec{b}_1 + \vec{b}_3$

$V_7 = \vec{b}_2 + \vec{b}_3$

$V_8 = \vec{b}_1 + \vec{b}_2 + \vec{b}_3$ 

Después calculamos la distancia de cada uno de ellos al punto $P$

$$d_i = \|P-V_i\|$$ 

 Y nos quedamos con el que tenga menor distancia (puede haber más de uno).

 

Ejemplo: Hagamos este método con un caso muy sencillo en $\mathbb{R}^2$.

$B=\{(30, 3), (5, 0)\}$ y el punto del paralelogramo $Q=(25.5, 2.5)$. Queremos hallar el vértice del paralelogramo más cercano a $Q$.

Los vértices del paralelogramo son:

$V_1=(0, 0); V_2=(30, 3); V_3=(5, 0); V_4=(35, 3)$

Y las correspondientes distancias al punto $Q$:

$d_1 \simeq 25.622255950637914$

$d_2 \simeq 4.527692569068709$

$d_3 \simeq 20.65187642806338$

$d_4 \simeq 9.513148795220223$ 

Por tanto, el vértice con menor distancia al punto $Q$ es $V_2=(30, 3)$.

 

Los cálculos han sido realizados con wxMaxima:

 

Contras del método exhaustivo.

Para dimensiones pequeñas el método exhaustivo es rápido y muy eficiente, pero para dimensiones grandes el coste computacional se incrementa exponencialmente, dado que el número de vértices de un n-paralelogramo es $2^n$.

Por ejemplo, en $\mathbb{R}^{100}$ tenemos $2^{100} = 1267650600228229401496703205376$ vértices.

 

 

 

 

 

 

Medir la ortogonalidad de una base

En la entrada anterior hice un repaso rápido de qué son las bases ortogonales. Ahora voy a tratar el siguiente tema:

¿Hay alguna manera de cuantificar si una base está cerca o lejos de ser ortogonal?

La respuesta es sí.

Una manera de hacerlo es utilizando una aplicación de la desigualdad de Hadamard.

Dada una base $B = \{ \vec{b}_1, ..., \vec{b}_n \}$ del espacio euclídeo $\mathbb{R}^n$:

$$|det(B)| \leq \prod_{i=1}^{n}\|\vec{b}_i\|$$

Desde el punto de vista geométrico, la desigualdad anterior nos aporta una cota superior del volumen del n-paralelepídedo formado por $B$.

Pero para el caso que nos ocupa, es muy útil conocer que dicha desigualdad se convierte en igualdad cuando la base es ortogonal por lo que nos permite definir la siguiente "razón de ortogonalidad de Hadamart":

$$\frac{|det(B)|}{\prod_{i=1}^{n}\|\vec{b}_i\|} $$

 Dicho valor estará comprendido en el intervalo $(0,1]$ y será exactamente 1 cuando la base sea ortogonal. Cuanto más "cerca" esté una base de ser ortogonal, más cerca de 1 estará el valor de la razón anterior. Cuanto más "lejos" esté una base de ser ortogonal, más cerca de 0 estará dicho valor.

Desde un punto de vista intuitivo e informal, estamos diciendo que si fijamos el módulo de los vectores que generan un n-paralelepídedo entonces el volumen es máximo cuando estos son ortogonales (en el momento en el que variamos alguno de los ángulos el volumen del n-paralelepípedo baja). Por tanto, si comparamos el volumen del n-paralelepípedo generado por los vectores de la base con el volumen máximo (caso ortogonal) podemos tener una idea de si la base está "cerca" o "lejos" de ser ortogonal.

Vamos a calcular dicha razón en los ejemplos de la entrada anterior en $\mathbb{R}^3$.

Comenzamos con la base canónica $C = \{(1,0,0),(0,1,0),(0,0,1)\}$:

 

 $|det(C)|=1$

 $\|(1,0,0)\|=\sqrt{1^2+0^2+0^2}=1$ 

 $\|(0,1,0)\|=\sqrt{0^2+1^2+0^2}=1$ 

 $\|(0,0,1)\|=\sqrt{0^2+0^2+1^2}=1$

Por tanto,

$$\frac{|det(C)|}{\prod_{i=1}^{n}||\vec{c}_i||} = \frac{1}{1} = 1$$

Es decir, como el valor da 1 podemos afirmar que la base es ortogonal.

 

En el caso de la otra base utilizada, $D = \{(1,0,0),(1,1,1),(0,2,1)\}$ 

 $|det(D)|=1$

 $\|(1,0,0)\|=\sqrt{1^2+0^2+0^2}=1$ 

 $\|(1,1,1)\|=\sqrt{1^2+1^2+1^2}=\sqrt{3}$ 

 $\|(0,2,1)\|=\sqrt{0^2+2^2+1^2}=\sqrt{5}$

 Por tanto,

$$\frac{|det(D)|}{\prod_{i=1}^{n}\|\vec{d}_i\|} = \frac{1}{\sqrt{15}} = \frac{\sqrt{15}}{15} \simeq 0.2581$$

Da un valor alejado de 1 por lo que podemos afirmar que la base "está lejos" de ser ortogonal. 

 

En realidad resultaría de utilidad tener una "medida" normalizada y comparable entre dimensiones. Si añadimos una raíz n-ésima tendremos una especie de "media geométrica del grado de normalidad por vector". Así pues, es más frecuente utilizar la siguiente expresión cuando se habla de la razón de ortogonalidad de Hadamart:

$$H(B) = \sqrt[n]{\frac{|det(B)|}{\prod_{i=1}^{n}\|\vec{b}_i\|}} $$

Otros autores hablan del defecto de ortogonalidad de una base definiéndola de la siguiente manera:

$$\vartriangle(B) = \frac{\prod_{i=1}^{n}\|\vec{b}_i\|}{|det(B)|} $$

de manera que cuánto mayor es el cociente "menor" es la ortogonalidad de la base (que sigue siendo 1 para bases ortogonales).

PD: Entrada de Wikipedia sobre el matemático francés Jacques Hadamard. 

Bases ortogonales

Es sabido que en el espacio euclídeo $\mathbb{R}^n$ un conjunto de $n$ vectores linealmente independientes forman una base del espacio.

Decimos que una base es ortogonal cuando los vectores de la base son ortogonales dos a dos, es decir, que su producto escalar es 0:

$$ b_{i} · b_{j} = 0; \forall i,j \in \{1,...,n\} \mid i \neq j$$

Por ejemplo, en $\mathbb{R}^3$ la base canónica $\{(1,0,0),(0,1,0),(0,0,1)\}$ es una base ortogonal. Todos los productos escalares dan 0:

$(1,0,0)·(0,1,0)=0+0+0=0$

$(1,0,0)·(0,0,1)=0+0+0=0$

$(0,1,0)·(0,0,1)=0+0+0=0$

Los vectores forman ángulos rectos entre ellos.

Sin embargo, la base $\{(1,0,0),(1,1,1),(0,2,1)\}$ no es una base ortogonal. Por ejemplo, el siguiente producto escalar no da 0:

$(1,1,1)·(0,2,1)=0+2+1=3 \neq 0$

Existen vectores que no forman un ángulo recto.