Minimización global de un polinomio en la recta real

Q¨ UESTII ´ O,vol. 23, 1, p. 85-109, 1999 MINIMIZACI ´ ON GLOBAL DE UN POLINOMIO EN LA RECTA REAL C. BELTR ´ AN ROYO Universitat Polit`ecnica de Catalunya  En este art´ ıculo presentamos y probamos num´ ericamente un nuevo algoritmo para la minimizaci´ on global de un polinomio de grado par. El algoritmo est´ a basado en la simple idea de trasladar verticalmente el grafo del polinomio hasta que el eje OX sea tangente al grafo del polinomio trasladado. En esta privilegiada posici´ on, cualquier ra´ ız real del polinomio trasladado es un m´ ınimo global del polinomio original. Globally minimizing a polynomial on the real line. Palabras clave: Optimizaci´on global, m´aximo com´un divisor de polinomios, algoritmo de Euclides, secuencia de Sturm, divisi´on sint´etica de dos polinomios. Clasificaci´ on AMS (MSC 2000): 49J05 *Dept. d’Estad´ıstica i Investigaci´o Operativa. Secci´o d’Inform`atica. Universitat Polit`ecnica de Catalunya. Pau Gargallo, 5. 08028 Barcelona (Espanya). –Recibido en octubre de 1997. –Aceptado en julio de 1998. 85 1. RESUMEN Dado un polinomio P ( x ) de grado par, queremos resolver el problema de minimizar globalmente P ( x ) en el conjunto de los reales (problema P-1). Para resolver el problema hemos dise˜nado un algoritmo o m´etodo nuevo denominado m´etodo del m´aximo com´un divisor (MCD). El algoritmo del m´aximo com´un divisor se basa en: a) Conocer el n´umero de ra´ıces reales diferentes del polinomiosin tener que calcularlas (m´etodo de Sturm). b) En el c´alculo del m´aximo com´un divisor de dos polinomios que denotamos por MCD. La idea del m´etodo es trasladar verticalmente el polinomio P hasta conseguir que el eje O X sea tangente al grafo de P trasladado (denotamos por P  este P trasladado). Una vez ya tenemos P  calculamos el m´aximo com´un divisor de P  y su derivada P  0 ( Q = MCD ( P  ; P  0 )) que en la mayor´ıa de los casos ser´a un polinomio de grado uno. Finalmente, cualquier ra´ız del polinomio Q es un m´ınimo global del polinomio P . Para poner en pr´actica el anterior esquema usaremos conocidos m´etodos y algoritmos: a) V´ıa m´etodo de Sturm podemos conocer el n´umero de ra´ıces reales distintas de P y un uso iterativo de esta informaci´on nos conducir´a a P  . b) V´ıa el algoritmo de Euclides calcularemos Q . c) La divisi´on sint´etica de dos polinomios ser´a requerida para aplicar el algoritmo de Euclides. d) Finalmente usaremos el m´etodo de Birge-Vieta para obtener una ra´ız de Q . 2. PRECEDENTES En el art´ıculo Goldstein (1971) resuelven el problema P-1 de forma directa i.e. se obtiene un m´ınimo global extrayendo de P cada m´ınimo local encontrado v´ıa divisi´on de polinomios. Esta estrategia puede llevar a tener que resolver un gran n´umero de minimizaciones locales, adem´as de que si no se hace minimizaci´on local exacta, los errores acumulados pueden degradar muy seriamente la soluci´on. Otros autores, resuelven el problema P-1 localmente i.e. minimizan globalmente P ( x ) en un intervalo pero no en todo R (denominamos este problema P-2). Repasemos tres trabajos: 86 1) En el art´ıculo Wingo (1985) se propone un algoritmo sencillo para el problema P-2 que no requiere la evaluaci´on de derivadas. 2) En el art´ıculo Floudas (1992) se resuelve el problema P-2 v´ıa programaci´on lineal con restricciones no lineales. La idea del m´etodo es cambiar en el polinomio cada potencia de x en una nueva variable. As´ı pasan de la minimizaci´on unidimensional de P ( x ) en un intervalo ( a; b ) , a la minimizaci´on de una funci´on lineal c 0 x en un dominio de R n +1 . 3) En elart´ıculo Bromberg(1992)se proponeunalgoritmoparala minimizaci´onglobal de una funci´on f ( x ) en un intervalo ( a; b ) . La idea de su m´etodo consiste en reducir el intervalo inicial ( a; b ) aplicando t´ecnicas de minimizaci´on local. Por lo tanto, a excepci´on del trabajo de Goldstein (1971), ninguno de los trabajos citados resuelve el problema de minimizar P ( x ) en toda la recta real (problema P-1). El m´etodo que ahora se propone resuelve el problema P-1 completamente. 3. NOTACI ´ ON  Consideramos polinomios P ( x ) = a 1  x n + a 2  x n ? 1 +  + a n  x + a n +1 de coeficientes reales y variable real.  Con P ( x; c ) denotemos el polinomio que tiene a n +1 = c i.e. P ( x; c ) = a 1  x n + a 2  x n ? 1 + a 3  x n ? 2 +  + a n  x + c  Conjunto de las ra´ıces reales del polinomio P Ra´ıces ( P ) = f x de R =P ( x ) = 0 g  Cardinal de ra´ıces( P ) #Ra´ıces ( P )  Grafo de un polinomio grafo( P ) = f ( x; P ( x )) en R 2 =x en R g  Semiespacio positivo S + = f ( x; y ) de R 2 =y posititivo g  Semiespacio negativo S ? = f ( x; y ) en R 2 =y negativo g 4. MODELO PROPIO - RESULTADOS TE ´ ORICOS En todo el trabajo se est´a presuponiendo: ? La minimizaci´on de un polinomio P ( x ) de grado par, dado que un polinomio de grado impar no est´a acotado inferiormente en R . Por la misma raz´on, supondremos que el coeficiente a 1 es positivo. 87 ? La minimizaci´on de P ( x ) se hace en todo R . ? Todas las ra´ıces de P ( x ) que se consideran son reales. ? Un polinomio puede alcanzar el m´ınimo global en m´as de un punto. El m´etodo desarrollado da como resultado solamente uno de estos puntos, aunque el m´etodo f´acilmente se puede adaptar para dar todos los puntos donde el polinomio alcanza el m´ınimo absoluto. A continuaci´on veremos unas definiciones, unos procedimientos y unos resultados que est´an demostrados en el reporte de investigaci´on Beltran (1997) y que usaremos en el algoritmo del MCD. La idea del algoritmo es en s´ıntesis: dado un polinomio P ( x ) de grado par, siempre podemos trasladarlo verticalmente de forma que Grafo( P ) sea tangente al eje O X obteniendo as´ı el polinomio P  ( x ) . Este ´ultimo polinomio tiene la caracter´ıstica de que cualquiera de sus ra´ıces reales es un punto de m´ınimo global de P  ( x ) y de P ( x ) en todo R . La forma de buscar una ra´ız cualquiera de P  ( x ) se hace teniendo en cuenta que en cada punto donde se anula P  ( x ) tambi´en se anula su derivada P  0 ( x ) . Dado que los ceros comunes de P  ( x ) y P  0 ( x ) coinciden con los ceros del polinomio MCD( P  ; P  0 ) , cualquier cero de este ´ultimo polinomio ser´a un m´ınimo global de P  ( x ) y por tanto de P ( x ) . 4.1. Polinomios pobres, ricos y buenos Definici´ on DES-1 (polinomio pobre, rico y bueno): Consideremos un polinomio de grado par y con a 1 > 0 : P ( x ) = a 1  x n + a 2  x n ? 1 + a 3  x n ? 2 +  + a n  x + a n +1  P ( x ) es pobre si el eje O X no corta el grafo( P ) (escribiremos P ? ).  P ( x ) es rico si el eje O X corta el grafo ( P ) (escribiremos P + ).  P ( x ) es bueno si el eje O X es tangente al grafo( P ) (escribiremos P  ). Corolario DES1. Dado un polinomio P ( x ) de grado n : a) Siempre existe una traslaci´ on vertical de P ( x ) que lo convierte en polinomio bueno P  ( x ) . Adem´ as P ( x ) difiere de P  ( x ) solamente en el coeficiente a n +1 . b) x  es un ´ optimo global de P  ( x ) si y solo si x  es un ´ optimo global de P ( x ) . Por tanto podemos limitar la b´ usqueda de ´ optimos globales en el caso de polinomios buenos. 88 EJEMPLO REP-1. P ( x; c ) = x 4 + 4 x 3 ? 11 x 2 ? 36 x + c P ( x; 68) polinomio bueno (1 ra´ız real) P ( x; 18) polinomio rico (4 ra´ıces reales) P ( x; 118) polinomio pobre (0 ra´ıces reales) -100,0 -50,0 0,0 50,0 100,0 150,0 200,0 250,0 300,0 350,0 400,0 -6 -5,4 -4,8 -4,2 -3,6 -2,9 -2,3 -1,7 -1,1 -0,5 0,1 0,7 1,3 2,0 2,6 3,2 3,8 P(x , 68) P(x , 18 ) P(x , 118) 4.2. Obtenci´ on de un ´ optimo global de un polinomio bueno P  ( x ) P  ( x ) P  ( x ) Teorema DES-1. (caracterizaci´ on de ´ optimo global v´ ıa MCD) Sean: P  ( x ) polinomio bueno y P  0 ( x ) su derivada, M ( x ) polinomio definido como el MCD ( P  ; P  0 ) ; x  punto de R : Entonces: M ( x  ) = 0 sii x  m´ ınimo global de P  ( x ) : 89 EJEMPLO REP-2. Continuamos con el polinomio del ejemplo REP-1. P  ( x ) = x 4 + 4 x 3 ? 11 x 2 ? 36 x + 68 P  0 ( x ) = 4 x 3 + 12 x 2 ? 22 x ? 36 M ( x ) = MCD ( P  ; P  0 ) = ( x ? 2) En el siguiente gr´afico se ve como:  x = 2 es el m´ınimo global de P ( x; 68) .  x = 2 es el ´unico real donde se anula simult´aneamente P  y P  0 .  por lo tanto ( x ? 2) es un factor de M (en realidad el ´unico) y as´ı M (2) = 0 .  Podemos concluir que x  = 2 ´optimo global de P  ( x ) y por lo tanto de P ( x ) . NOTA: En lugar de representar y = M ( x ) hemos representado y = 30  M ( x ) , pues la representaci´on de M ( x ) queda casi pegada al eje O X . -400,0 -300,0 -200,0 -100,0 0,0 100,0 200,0 300,0 400,0 -6 -5,4 -4,8 -4,2 -3,6 -2,9 -2,3 -1,7 -1,1 -0,5 0,1 0,7 1,3 2,0 2,6 3,2 3,8 P(x , 68) P'(x,68) M(x) 4.3. Obtenci´ on del polinomio bueno P  P  P  asociado a un polinomio P P P Tenemos dos tipos de informaci´on que usaremos en el algoritmo OGP. 4.3.1. Primera informaci´ on - #Ra´ ıces( P ) El siguiente resultado puede encontrarse en Henrici (1974) p´ag. 448. 90 Teorema de Sturm DES-2. (N´ umero de ceros reales y distintos de P ( x ) en ( a; b ) ). Definimos P 0 ( x ) := P ( x ) y P 1 ( x ) := P 0 ( x ) . Sea f P 0 ; P 1 ; P 2 ; : : : ; P m g la secuencia de polinomios obtenidos mediante el algoritmo de Euclides para calcular el MCD( P 0 ; P 1 ) (ver ap´ endice). Entonces: El n´ umero de ceros reales y distintos de P 0 en el intervalo ( a; b ) es igual a la diferencia entre el n´ umero de cambios de signo en f P 0 ( a ) ; P 1 ( a ) ; P 2 ( a ) ; : : : ; P m ( a ) g y el n´ umero de cambios de signo en f P 0 ( b ) ; P 1 ( b ) ; P 2 ( b ) ; : : : ; P m ( b ) g suponiendo que P 0 ( a )  P 0 ( b ) sea diferente de cero. Definici´ on DES-2. (Secuencia de Sturm asociada a un polinomio). El conjunto de polinomios f P 0 ; P 1 ; P 2 ; : : : ; P m g que aparece en el enunciado del teorema anterior, se denomina secuencia de Sturm asociada a P 0 . Escribiremos Sturm( P ) para hacer referencia a la secuencia de Sturm asociada al polinomio P ( x ) . EJEMPLO REP-3. Contin´ua del ejemplo REP-2. P  ( x ) = x 4 + 4 x 3 ? 11 x 2 ? 36 x + 68 Veamos Sturm( P  ): P 0 ( x ) := P  ( x ) = x 4 + 4 x 3 ? 11 x 2 ? 36 x + 68 P 1 ( x ) := P  0 ( x ) = 4 x 3 + 12 x 2 ? 22 x ? 36 P 2 ( x ) = 8 : 5 x 2 ? 21 : 5 x ? 77 P 3 ( x ) = ? 9 : 4 x + 18.8 = ? 9 : 4  ( x ? 2) P 4 ( x ) = 0 N ( ?1 ) : = Cambios de signo en f P 0 ( ?1 ) , P 1 ( ?1 ) , P 2 ( ?1 ) , P 3 ( ?1 ) , P 4 ( ?1 ) g = = Cambios de signo en f + , ? , + , + , 0 g = = 2 N ( 1 ) : = Cambios de signo en f P 0 ( 1 ) , P 1 ( 1 ) , P 2 ( 1 ) , P 3 ( 1 ) , P 4 ( 1 ) g = = Cambios de signo en f + , + , + , ? , 0 g = = 1 Entonces por el teorema de Sturm tenemos que #Ra´ıces( P  ) = N ( ?1 ) ? N ( 1 ) = 1 y podemos asegurar que P  es polinomio bueno. Podemos ver la representaci´on de P  ( x ) = P ( x; 68) en Ejemplo REP-1 donde efectivamente se ve que P  tiene una sola ra´ız real. N´oteseque alser P 4 ( x ) = 0 entonces P 3 ( x ) = ? 9 : 4  ( x ? 2) nosdael MCD( P  ; P  0 ) = ( x ? 2) . 91 4.3.2. Segunda informaci´ on - la funci´ on residuo Definici´ on DES-4. (funci´ on residuo asociada a un polinomio).Dada la familia de polinomios F = f P ( x; c ) : c de R g definimos la funci´ on residuo R P ( c ) asociada a F , como el resto de la divisi´ on P m ? 1 ( x; c ) : P m ( x; c ) donde P m ? 1 y P m son los dos ´ ultimos polinomios no constantes de Sturm ( P ( x; c ) ). Corolario DES-4. (Car´ acter de un polinomio v´ ıa funci´ on residuo).Sea c  la mayor ra´ ız real de R P ( c ) . Entonces: a) P ( x; c ) pobre sii c > c  . b) P ( x; c ) bueno sii c = c  . c) P ( x; c ) rico sii c < c  . EJEMPLO REP-4. Contin´ua del ejemplo REP-3. P ( x; c ) = x 4 + 4 x 3 ? 11 x 2 ? 36 x + c Con la ayuda del paquete «Mathematica»(Wolfram (1992)) hemos calculado R P ( c ) obteniendo la fracci´on algebraica siguiente: R P ( c ) = A ( c ) =B ( c ) donde A ( c ) = 289  (16 c 3 ? 1256 c 2 ? 483 c + 809676) B ( c ) = (68 c ? 3255) 2 En la siguiente representaci´on de R P ( c ) se ve como su mayor ra´ız real es c  = 68 , que confirma el hecho de que P ( x; 68) sea un polinomio bueno (como vimos en el ejemplo REP-1). -1600 -1400 -1200 -1000 -800 -600 -400 -200 0 200 400 -100 -84 -68 -52 -36 -20 -4 12 28 44 60 76 92 108 124 140 156 172 188 204 220 236 252 268 284 R(c) 92 5. M´ ETODO DEL MCD PARA LA MINIMIZACI ´ ON GLOBAL DE UN POLINOMIO Dado un polinomio de grado par P ( x ) , buscamos un x  m´ınimo global de P ( x ) en R . Las etapas del m´etodo del MCD se explican en 5.1, 5.2 y 5.3. Entonces, en virtud del teorema DES-1, x  es un ´optimo global de P ( x ) en R . 5.1. Obtenci´ on del polinomio bueno P  ( x ) P  ( x ) P  ( x ) asociado a un polinomio P ( x ) P ( x ) P ( x ) Aplicando el corolario DES-4 es suficiente encontrar c  ra´ız m´axima de la funci´on residuo R P ( c ) y entonces P ( x; c  ) polinomio bueno asociado a P  . Estamos interesados, pues, en un intervalo ( a 0 ; b 0 ) que contenga c  . Dado P ( x ) hacemos: 5.1.1. C´alculo del intervalo inicial ( a 0 ; b 0 ) . 5.1.2. C´alculo de c  . 5.1.1. C´ alculo del intervalo inicial tal que contenga c  V´ıa el teorema de Sturm, podemos conocer #Ra´ıces( P ( x; c k )) k = 0 ; 1 ; 2 ; 3 ;::: y as´ı determinar el car´acter rico, pobre o bueno de cada P ( x; c k ) . Podemos incrementar c k hasta que lleguemos a un P ( x; c p ) polinomio pobre y as´ı tendremos garantizado c  < c p . Tomaremos b 0 = c p como extremo superior del intervalo inicial. En resumen, hemos empobrecido el polinomio inicial P ( x; c 0 ) para buscar b 0 . Por otra parte, dado que P ( x; 0) siempre tiene una ra´ız real en x = 0 , podemos tomar como extremo inferior del intervalo inicial, cualquier valor a 0 positivo, lo m´as cerca de b 0 posible y de forma que P ( x; a 0 ) sea un polinomio rico. EJEMPLO REP-5. Contin´ua del ejemplo REP-4. Dado que P ( x; 18) es un polinomio rico, despu´es de 2 iteraciones de la rutina EMPOBRINT, obtenemos P ( x; 72) que es un polinomio pobre. De esta forma tenemos que 18 < c  < 72 con lo cual podemos tomar (18 ; 72) como intervalo inicial. 93  x = 2 es el m´ınimo global de P ( x; 68) .  x = 2 es el ´unico punto donde se anulan simult´aneamente P  ( x ) y P  0 ( x ) .  Por lo tanto ( x ? 2) es un factor de M (en realidad el ´unico) y as´ı M (2) = 0 .  Podemos concluir que x  = 2 es el ´optimo global de P  ( x ) y por lo tanto de P ( x ) . NOTA. En lugar de representar y = M ( x ) , hemos representado y = 30  M ( x ) pues la representaci´on de M ( x ) no se distinguir´ıa del eje O X . 6.1.2. Resultados con el programa OGP.EXE Paracorrer el programaOCP.EXE necesitamosel fichero de datos OGP.DAT que consta de tres partes:  Grado del polinomio (entero positivo).  Precisi´on exigida (por ejemplo 0.0001).  El polinomio que queremos minimizar escrito en forma de columna. EJEMPLO REP-6. Para introducir el polinomio P ( x ) = x 4 + 4 x 3 ? 36 x + 18 crear´ıamos un fichero OGP.DAT con el siguiente contenido. 4 (Grado del polinomio) 0.0001 (Precisi´on exigida) 1.1 ( a 1 ) 4.0 ( a 2 ) 0.0 ( a 3 ) ? 36.0 ( a 4 ) 18.0 ( a 5 ) Dado que P ( x; 18) es un polinomio rico, despu´es de 2 iteraciones de la rutina «empobrint»obtenemos P ( x; 72) que es un polinomio pobre. A continuaci´on tenemos Sturm ( P ( x; 72) ) ************************************************** EMPOBRINT 0 Polinomio a optimizar P ( x; 18) 1.00 4.00 ? 11.00 ? 36.00 18.00 OGP/out sturm 1.00 4.00 ? 11.00 ? 36.00 72.00 P 0 .00 4.00 12.00 ? 22.00 ? 36.00 P 1 .00 .00 8.50 1.50 ? 81.00 P 2 .00 .00 .00 11.36 18.06 P 3 .00 .00 .00 .00 25.30 P 4 ************************************************** EMPOBRINT 2 100 El intervalo inicial donde se encuentra c  es (36, 72). La rutina BISSECCI ´ O encuentra c* con 8 iteraciones del m´etodo de la secante. Al final tenemos Sturm ( P ( x; 68)) : ************************************************** BISSECCI ´ O c k R P ( c k ) 36.0000 ? 39.4913 72.0000 25.3022 57.9418 ? 198.6757 70.4119 16.4875 69.4563 10.4699 67.7938 ? 1.6308 68.0178 .1392 68.0002 .0017 68.0000 .0000 BIS/SEC iter 8 OGP/out sturm 1.00 4.00 ? 11.00 ? 36.00 68.00 P 0 .00 4.00 12.00 ? 22.00 ? 36.00 P 1 .00 .00 8.50 21.50 ? 77.00 P 2 .00 .00 .00 ? 9.47 18.95 P 3 .00 .00 .00 .00 .00 P 4 ************************************************** BISSECCI ´ O La rutina BIRGE calcula la ´unica ra´ız de M ( x ) = ? 9 : 47 x + 18 : 95 que es x = 2 . En consecuencia ya tenemos el ´optimo global de P(x) i.e. x  = 2 . ************************************************** BIRGE 0 OGP/in mcd ? 9.47 18.95 OGP/out OPTIM 2.0000 ************************************************** BIRGE 1 101 6.2. Pruebas con otros polinomios A continuaci´on definimos unos polinomios que nos servir´an para poner a prueba el m´etodo del MCD descrito anteriormente. Dado un polinomio P ( x ) = a 1  x n + a 2  x n ? 1 + a 3  x n ? 2 +  + a n  x + a n +1 le haremos corresponder el vector formado por sus coeficientes P ( x ) = ( a 1 ; a 2 ; : : : ; a n +1 ) : La etiqueta del polinomio nos dir´a el grado y el n´umero de identificaci´on del polinomio. Por ejemplo con 4POL1, designamos un polinomio de grado 4 y que identificamos con el n´umero 1. 4POL 1 = ( 1. 0. 0. 0. ? 1. ) 4POL 2 = ( 1. 4. ? 11. ? 36. 18. ) 4POL 3 = ( 1. ? 3. ? 1.5 10. 0. ) 4POL 4 = ( 1. ? 4. 4. 0. 0. ) 6POL 1 = ( 1. ? 6. 15. ? 20. 15. ? 6. 1. ) 6POL 2 = ( 1. 0. ? 14. 0. 49. 0. ? 36. ) 6POL 3 = ( 0.16666 ? 2.08 0.4875 7.1 ? 3.95 ? 1. 0.1 ) 8POL 1 = ( 0.001 0. ? 0.102 0.096 3.009 ? 5.520 ? 23.068 65.904 ? 40.320 ) 8POL 2 = ( 1. 0. 0. ? 20.320. 12.6 1. 0. ? 13. ) 10 POL 2 = (0.001 0.019 ? 0.012 ? 1.842 ? 4.347 60.291 142.862 ? 869.188 ? 864.264 5165.28 ? 3628.8) En las siguientes tablas se muestra la informaci´on m´as relevante obtenida al minimizar los polinomios anteriores con una tolerancia = 0.0001. Hemos de notar que:  La rutina Birge hace normalmente una sola iteraci´on al tener que resolver una ecuaci´on de primer grado (caso de un ´unico ´optimo global).  La precisi´on obtenida es buena con unas pocas iteraciones. 102 4POL1 1POL2 4POL3 4POL4 6POL1 ´ Optimos globales exactos 0,0000 2,0000 -1,0000 0,0000 1,0000 2,0000 ´ Optimo calcultado 0,0000 2,0000 -0,9999 0,0000 1,0351 Iteraciones «EMPOBRINT»1 2 1 1 1 Iteraciones «BISSECCI´ O»  Primer intento secante 2 8 5 2 2  Segundo intento secante Iteraciones «BIRGE»1 1 1 1 1290 Comentarios (1) (2) 6POL2 6POL3 8POL1 8POL2 10POL2 ´ Optimos globales exactos -2,6457 10,0000 -7,3400 2,2744 6,4347 0,0000 2,6457 ´ Optimo calcultado 0,0000 10,0004 -7,3416 2,2400 6,4347 Iteraciones «EMPOBRINT»1 14 4 6 4 Iteraciones «BISSECCI´ O»  Primer intento secante 2 7 14 4 27  Segundo intento secante 11 Iteraciones «BIRGE»1 1 1 1 1 Comentarios (1) (3) Comentarios: (1) Hay polinomios con m´as de un ´optimo global. (2) Aqu´ı, excepcionalmente, la rutina BIRGE necesita 1290 iteraciones para alcanzar una aproximaci´on al ´optimo. Esto es debido a que 6POL1 es ( x ? 1) 6 polinomio de curvatura pr´acticamente nula en un entorno amplio del ´optimo x  = 1 . El m´etodo Birge no es pues adecuado para este tipo de casos. (3) Aqu´ı el m´etodo del MCD con 14 iteraciones ha calculado una primera ra´ız de R P ( c ) que no es la mayor; seguidamente, con 11 iteraciones m´as ya ha calculado la ra´ız m´axima de R P ( c ) . 103 7. CONCLUSIONES Hemos presentado un nuevo algoritmo para minimizar globalmente en el conjunto de los reales un polinomio de grado par. La caracter´ıstica m´as importante del algoritmo es el uso de informaci´on global de la funci´on a minimizar (n´umero de ra´ıces reales y funci´on residuo) a diferencia de los m´etodos cl´asicos basados en informaci´on local (derivada en un punto). El enfoque aqu´ı presentado parece m´as adecuado que m´etodos anteriores aunque falta hacer una prueba comparativa. Num´ericamente el algoritmo se ha mostrado eficiente y robusto. 8. AP´ ENDICE 8.1. Algoritmo Euclides para calcular el m´ aximo com´un divisor de dos polinomios MCD( P 0 ; P 1 P 0 ; P 1 P 0 ; P 1 ) Dividimos P 0 entre P 1 y denotamos el resto ? P 2 . Seguidamente dividimos P 1 entre P 2 y denotamos el residuo ? P 3 . Continuamos este procedimiento hasta que obtengamos un resto igual a cero. Al final del algoritmo podremos establecer las siguientes relaciones: P 0 = Q 1  P 1 ? P 2 P 1 = Q 2  P 2 ? P 3 . . . P m ? 2 = Q m ? 1  P m ? 1 ? P m P m ? 1 = Q m  P m Entonces P m = MCD ( P 0 ; P 1 ) 8.2. (Divisi´ on sint´ etica) Generalizaci´ on de la «Regla de Ruffini»para dividir P 0 P 0 P 0 entre P 1 P 1 P 1 Escribimos horizontalmente los coeficientes del dividendo en orden decreciente (como en el m´etodo de Ruffini). Seguidamente colocamos verticalmente los coeficientes del divisor cambiados de signo (como en el m´etodo de Ruffini) con el coeficiente de m´aximo grado normalizado (igual a uno). Una referencia m´as detallada puede encontrarse en Acton (1990) pag. 181. EJEMPLO APEN-1. Supongamos que queremos dividir P 1 entre P 2 con: P 1 ( x ) = 2 x 4 ? 4 x 3 + x 2 + 3 P 2 ( x ) = x 3 ? 2 x 2 ? x + 1 104 Escribimos en forma de tabla: P 2 P 1 2 ? 4 1 0 3 +2 * 4 0 * * +1 * * 2 0 * ? 1 * * * ? 2 0 Cociente( x ) 2 0 3 ? 2 3 Resto( x ) Cociente ( x ) = 2 x 3 x 2 ? 2 x + 3 = Resto ( x ) La regla de formaci´on es: 1. Sumamos la columna. 2. Multiplicamos el resultado del paso 1 por cada coeficiente de P 2 , empezando por arriba, colocando el producto en sucesivas columnas hacia la derecha y en la misma fila que el coeficiente de P 2 correspondiente. 3. Volvemos alpaso 1, pero omitiendoel paso 2 despu´es de haber calculadoel cociente. Al final, tendremos dos tri´angulos en blanco que en el ejemplo hemos marcado con «*». 8.3. M´ etodo de la secante para el c´ alculo de ra´ıces reales Queremos resolver g ( x ) = 0 . Este m´etodo es una variante del m´etodo de Newton, donde en lugar de usar g 0 ( x k ) , usamos una aproximaci´on ( g ( x k ) ? g ( x k ? 1 )) = ( x k ? x k ? 1 ) . 0. Partimos del intervalo inicial ( a; b ) que contiene la ra´ız buscada. 1. Inicializamos x 0 = a x 1 = b . 2. Mientras ( =x k ? x k ? 1 = >  ) hacer: paso = g ( x k )  f ( x k ? x k ? 1 ) = ( g ( x k ) ? g ( x k ? 1 )) g x k +1 = x k ? paso. Final mientras. 8.4. M´ etodo de Birge-Vieta para calcular una ra´ız de un polinomio Queremos resolver P ( x ) = 0 siendo P ( x ) un polinomio. 105 Este m´etodo es una especializaci´on del m´etodo de Newton, donde calculamos P ( x k ) y P 0 ( x k ) de forma muy eficiente, aprovechando las propiedades algebraicas de los polinomios. Teorema del residuo. Consideramos P ( x ) y suponemos que expresamos P ( x ) = ( x ? x 0 )  Q ( x ) + R 1 . Entonces: a) P ( x 0 ) coincide con el residuo R 1 del cociente P ( x ) : ( x ? x 0 ) b) P 0 ( x 0 ) coincide con el residuo R 2 del cociente Q ( x ) : ( x ? x 0 ) ALGORITMO. (M´etodo Birge-Vieta) 0. Partimos del intervalo inicial ( a; b ) . 1. Inicializamos x 0 = a x 1 = b . 2. Mientras ( =x k ? x k ? 1 = >  ) hacer paso = R 1 =R 2 x k +1 = x k ? paso. Final mientras. BIBLIOGRAF´ IA [1] Acton, F.S. (1990). «Numerical Methods that Work», EEUU, The Mathematical Association of America, 2aEd., 1990. [2] Beltran, C. (1997). «Globally Minimizing Even Degree Polynomials on the Real Line».ResearchReport97/01of the StatisticsandOperationsResearchDepartmentUPC. Date 2/97. [3] Bromberg, M. and Chang, T. (1992). «One Dimensional Global Optimization Using Linear Lower Bonds»from the book Recent Advances in Global Optimization, New Jersey, EEUU, Princeton University Press, 1992, pp. 201-220. [4] Floudas, C.A. and Visweswaran, V. (1992). «Global Optimization of Problems with Polinomial Functions in one Variable»from the book Recent Advances in Global Optimization, New Jersey, EEUU, Princeton University Press, 1992, pp. 164-197. [5] Goldstein, A.A. and Price, J.F. (1971). «On descent from local minima»,Mathematics of Computation,25, 569-574. [6] Henrici, P. (1974). «Applied and Computational Complex Analysis». Volume I, EEUU, John Wiley & Sons, 1974. 106 [7] Wingo, D.R. (1985). «Globaly Minimizing Polinomials Without Evaluating Derivatives»,International Journal of Computer Mathematics,17, 287. [8] Wolfram, S. (1992). «Mathematica: A System for Doing Mathematics by Computer», EEUU, Addison-Wesley Publishing Company, 2aEd. 107 ENGLISH SUMMARY GLOBALLY MINIMIZING A POLYNOMIAL ON THE REAL LINE C. BELTR ´ AN ROYO Universitat Polit`ecnica de Catalunya  An algorithm for globally minimizing an even degree polynomial on the real line is proposed and tested. The algorithm is based on the idea of translating the polynomial graph vertically, until the O X axis is tangent to the graph of the translated polynomial. At this point, any root of the translated polynomial is a global minimizer of the original polynomial. Keywords: Global optimization, greatest common divisor of two polynomials, Euclides algorithm, Sturm sequence, synthetic division of two polynomials. AMS Classification (MSC 2000): 49J05 *Dept. d’Estad´ıstica i Investigaci´o Operativa. Secci´o d’Inform`atica. Universitat Polit`ecnica de Catalunya. Pau Gargallo, 5. 08028 Barcelona (Espanya). –Received October 1997. –Accepted July 1998. 108 The objective of this work is to minimize an even degree polynomial globally i.e. we want to solve the problem: min f P ( x ) : x 2 R g Traditionally this problem has been solved using local information such as the first derivative. Our approach will use global information (the total number of different real zeros of P ( x ) in R ). This approach avoids an exhaustive search into an interval ( a; b ) carried out by local information based algorithms. The algorithm is based on the idea of translating the polynomial graph vertically until the O X axis is tangent to the graph of the translated polynomial. At this point, any root of the translated polynomial is a global minimizer of the original polynomial. First of all we define a rich polynomial as a polynomial that crosses the O X axis, a good polynomial as a polynomial that is tangent to the O X axis and a poor polynomial as a polynomial that does not intersect the O X axis. The main results we have proved are: a) If P  ( x ) is a good polinomial, P  0 ( x ) its derivative and GCD( P  ; P  0 ) their greatest common divisor, then, the set of global minimizers of P  ( x ) is the set of real zeros of the GCD( P  ; P  0 ). b) Given the polynomial P ( x; c ) = a 1  x n + a 2  x n ? 1 +  + a n  x + c we define an associated funci´on R P ( c ) called the residual function. Then P ( x; c  ) is a good polynomial if and only if c  is the greatest real zero of the residual function R P ( c ) . The GCD method for finding a global minimizer of P ( x ) is: 1) P ( x ) = P ( x; a n +1 ) is translated vertically until it becomes a good polynomial. We use two sources of information: first, Sturm theorem tells us the total number of different real zeros of P ( x; c ) in R and second, solving the equation R P ( c ) = 0 we find c  the exact translation that converts P ( x; a n +1 ) into a good polynomial P  ( x ) = P ( x; c  ) . 2) Solving the equation M ( x ) = 0 where M ( x ) is the GCD( P ; P  ) , we will have a global minimizer of P ( x ) . Computational experience has shown that the GCD method is an efficient and reliable method for globally minimizing a polynomial. 109