6 votos

Algoritmo de alfa máxima más beta mínima para tres números

Existe un algoritmo rápido para aproximar la longitud del vector 2D - Algoritmo de alfa máxima más beta mínima .

Dice que $\alpha\cdot\max(x,y)+\beta\cdot\min(x,y)\approx\sqrt{x^2+y^2}$ para algunas constantes $\alpha$ y $\beta$ .

También existen constantes $\alpha_0$ y $\beta_0$ que dan la mayor aproximación (menor error).

$$\alpha_0 = \frac{2 \cos \frac{\pi}{8}}{1 + \cos \frac{\pi}{8}},\ \beta_0 = \frac{2 \sin \frac{\pi}{8}}{1 + \cos \frac{\pi}{8}}$$

Me parece que existe un algoritmo similar para aproximar la longitud del vector 3D con una fórmula: $$\sqrt{x^2+y^2+z^2}\approx\alpha\cdot\max(x,y,z)+\beta\cdot \text{medium}(x,y,z)+\gamma\cdot\min(x,y,z)$$

Me pregunto qué valores $\alpha_0$ , $\beta_0$ y $\gamma_0$ tienen y cómo encontrarlos.

3voto

uranix Puntos 3824

Suponiendo que $\max(x, y, z), \min(x,y,z), \operatorname{med}(x,y,z)$ son realmente $|\max(x, y, z)|, |\min(x, y, z)|, |\operatorname{med}(x, y, z)|$ .

No es una prueba real, sólo un esbozo. Como la fórmula es simétrica bajo permutaciones de $x, y, z$ Supongamos que $0 \leq x \leq y \leq z$ Así que $$ \sqrt{x^2 + y^2 + z^2} = \alpha x + \beta y + \gamma z. $$ Ya que estamos interesados en relativa error, considere un punto en el círculo unitario. $z^2 = 1 - x^2 - y^2$ . El error es la desviación absoluta entre $\alpha x + \beta y + \gamma z$ y uno. La condición $0 \leq x \leq y \leq z$ en el círculo unitario es equivalente a las siguientes condiciones $$ 0 \leq x \leq y\\ \sqrt{1-x^2-y^2} \geq y \Leftrightarrow x^2 + 2y^2 \leq 1 $$ Así que llegamos a un problema minimax $$ \begin{aligned} \operatorname{minimize}\limits_{\alpha, \beta, \gamma} \max_{\substack{x \geq 0\\y \geq x\\x^2 + 2y^2 \leq 1}} \big|1 - \alpha x - \beta y - \gamma \sqrt{1-x^2-y^2}\big| \end{aligned} $$ Eso es difícil.

Podemos Supongamos que que la desviación máxima es igual en las tres esquinas y opuesta a la desviación en el extremo local en el interior.

El extremo interior es simple debido al significado geométrico. Es igual a la distancia del plano dada por $C = \alpha x + \beta y + \gamma z$ al origen de la esfera restado uno (radio de la esfera). Así que la desviación en el extremo es $$ \Delta = \sqrt{\alpha^2 + \beta^2 + \gamma^2} - 1. $$ La desviación en las esquinas $(0,0),\,(0,\frac{1}{\sqrt{2}}),(\frac{1}{\sqrt{3}},\frac{1}{\sqrt{3}}))$ se calcula fácilmente: $$ \Delta_1 = 1 - \gamma\\ \Delta_2 = 1 - \frac{\beta + \gamma}{\sqrt{2}}\\ \Delta_3 = 1 - \frac{\alpha+\beta+\gamma}{\sqrt{3}} $$ Resolver $\Delta = \Delta_1 = \Delta_2 = \Delta_3$ para $\alpha, \beta, \gamma$ obtenemos $$\begin{aligned} \alpha = \frac{1}{4} \left(2 \sqrt{14+6 \sqrt{2}+3 \sqrt{3}}-\left(2+\sqrt{2}\right) \left(1+\sqrt{3}\right)\right) &\approx 0.29870618761437979596\\ \beta = \operatorname{root}_6(1 - 4 z - 14 z^2 + 32 z^3 + 45 z^4 - 20 z^5 - 20 z^6 + 4 z^7 + z^8) &\approx 0.38928148272372526647\\ \gamma = \operatorname{root}_8(1 - 4 z - 2 z^2 + 20 z^3 - 3 z^4 - 32 z^5 + 4 z^6 + 16 z^7 + z^8) &\approx 0.93980863517232523127 \end{aligned} $$ El error $1 - \gamma$ está ligeramente por encima de $6\%$ . Tenga en cuenta que accidentalmente he invertido su $\alpha. \beta, \gamma$ . Este resultado parece prometedor, pero puede ser erróneo. Tenga en cuenta que $\beta$ y $\gamma$ se acercan bastante a los óptimos 2D.

He hecho un simple Mathematica script para echar un vistazo al problema minimax. Aquí está

Manipulate[
 ContourPlot[\[Alpha] x + \[Beta] y + \[Gamma] Sqrt[1 - x^2 - y^2] - 
   1, {x, 0, 1}, {y, 0, 1}, 
  RegionFunction -> Function[{x, y}, x <= y && x^2 + 2 y^2 <= 1],
  Contours -> Range[-0.2, 0.2, 0.01]
  ]
 , {{\[Alpha], 0.2987061876143797`}, 0, 
  1}, {{\[Beta], 0.38928148272372454`}, 0, 
  1}, {{\[Gamma], .9398086351723256`}, 0, 1}]

Así que parece que la sugerencia es sana y que hemos encontrado al menos el óptimo local del problema.

2voto

Jan Heldal Puntos 31

La aproximación dada por @uranix es bonita, pero se puede mejorar ligeramente, porque sabemos que la hipotenusa nunca es más corta que la mayor de las tres entradas.

Así que, tomando prestadas las bonitas constantes dadas por @uranix y asumiendo $0<=z<=y<=x$ :

const double alphaMax = 0.9398086351723256, betaMed = 0.38928148272372454, gammaMin = 0.2987061876143797;
double hypotenuse = Max(x, alphaMax * x + betaMed * y + gammaMin * z);

Esto bloquea los errores cuando x es relativamente mucho mayor que y y z; un caso especial común en el que los errores, de otro modo, serían relativamente grandes y perceptibles.

Nota al margen: Como las multiplicaciones son con constantes, se pueden aproximar con desplazamientos de bits y sumas. Esto es muy útil cuando se utiliza la aritmética de punto fijo en los sistemas embebidos, donde el punto flotante y las multiplicaciones pueden ser caras.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X