{"id":1429,"date":"2023-08-27T20:35:40","date_gmt":"2023-08-27T18:35:40","guid":{"rendered":"https:\/\/intsight.com\/?p=1429"},"modified":"2023-08-27T20:35:40","modified_gmt":"2023-08-27T18:35:40","slug":"austra-polysolve","status":"publish","type":"post","link":"https:\/\/intsight.com\/index.php\/2023\/08\/27\/austra-polysolve\/","title":{"rendered":"Austra PolySolve"},"content":{"rendered":"

C’est la vie<\/span>: elle est dure et souvent courte.<\/p>\n

Es imposible escribir sobre ecuaciones algebraicas sin mencionar a \u00c9variste Galois, quien no s\u00f3lo cerr\u00f3 una larga historia de intentos de soluci\u00f3n de este tipo de ecuaciones, sino que adem\u00e1s tuvo una vida corta y tr\u00e1gica.<\/p>\n

Dicen que los egipcios y los babilonios eran capaces de resolver las ecuaciones de segundo grado y, por supuesto, las lineales. Las de tercer y cuarto grado tuvieron que esperar al Renacimiento Italiano. Y luego, la teor\u00eda se estanc\u00f3: nadie era capaz de resolver una ecuaci\u00f3n de quinto grado general; s\u00f3lo algunas versiones restringidas.<\/p>\n

Lagrange estuvo a punto de demostrar que las ecuaciones de quinto grado y superiores no ten\u00edan una soluci\u00f3n general. Fue Ruffini quien lo consigui\u00f3, aunque con algunos peque\u00f1os errores, que m\u00e1s tarde corrigi\u00f3 Abel. De todos modos, la teor\u00eda que Galois puso por escrito en 1830, cuando s\u00f3lo ten\u00eda 18 a\u00f1os, ten\u00eda un alcance mucho mayor, y ofrec\u00eda una estructura m\u00e1s completa y vers\u00e1til para estudiar las ecuaciones algebraicas. Mientras que el teorema de Ruffini-Abel se centraba en la solubilidad de ecuaciones algebraicas por medio de funciones elementales (como exponentes, logaritmos, etc.), la criatura que invent\u00f3 nuestro h\u00e9roe introdujo los llamados grupos de Galois para analizar la solubilidad y las simetr\u00edas en un marco m\u00e1s general. No solo abord\u00f3 la solubilidad de ecuaciones, sino que la teor\u00eda es aplicable tambi\u00e9n en otras \u00e1reas de las matem\u00e1ticas, como la teor\u00eda de n\u00fameros y la geometr\u00eda algebraica.<\/p>\n

Por desgracia, el art\u00edculo presentado en 1830 por nuestro h\u00e9roe no tuvo el \u00e9xito que merec\u00eda. Cauchy le pas\u00f3 la patata caliente a Poisson, y Poisson no entendi\u00f3 ni papa del tema. El rechazo cabre\u00f3 a Galois, pero aprovech\u00f3 para rescribir la demostraci\u00f3n, y fue esta modificaci\u00f3n la que finalmente fue reconocida, entre otros, por el propio Cauchy. Eso s\u00ed: tras la muerte de Galois…<\/p>\n

Galois ten\u00eda una cabecita muy loca, le pirraba la pol\u00edtica, y para colmo, estaba algo deprimido por la muerte de su padre. 1832 fue un a\u00f1o dif\u00edcil para el chico. Estuvo en prisi\u00f3n un par de veces, por ciscarse en Louis Philippe, el pen\u00faltimo rey de Francia. Al salir de la c\u00e1rcel por segunda vez, se enred\u00f3 en un duelo absurdo, te\u00f3ricamente por una coquette<\/em>, aunque no es descartable que todo fuese una trampa de sus enemigos pol\u00edticos. Se pas\u00f3 la noche anterior al duelo escribiendo una carta sobre sus \u00faltimos avances matem\u00e1ticos. Al d\u00eda siguiente, interpuso su abdomen en la trayectoria de una bala, y sus contrincantes lo dejaron tirado sobre la hierba como a un chien<\/em>. Un transe\u00fante lo vio y lo llev\u00f3 al hospital, pero al d\u00eda siguiente se reuni\u00f3 con su Creador, probablemente por culpa de una peritonitis.<\/p>\n

And all the king’s horses and all the king’s men, couldn’t put \u00c9variste together again.<\/p>\n

Ra\u00edces reales<\/h4>\n

Mi curiosidad por estos temas viene de cuando ten\u00eda unos diez u once a\u00f1os: encontr\u00e9 la soluci\u00f3n razonada de las ecuaciones de segundo grado, en un libro de electr\u00f3nica, y me dio por intentar resolver por mi cuenta el problema de las c\u00fabicas. No lo consegu\u00ed. Tropec\u00e9 por casualidad con la sustituci\u00f3n de Vieta, pero no consegu\u00ed algo mucho m\u00e1s sencillo: c\u00f3mo eliminar el t\u00e9rmino cuadr\u00e1tico, que suele ser el primer paso de la soluci\u00f3n. Pero compr\u00e9 un libro que explicaba la f\u00f3rmula c\u00fabica y la cu\u00e1rtica, y me convert\u00ed en un friqui de las mates.<\/p>\n

Volv\u00ed a enredar con ecuaciones algebraicas en 2005, cuando me dio por probar si se pod\u00eda escribir un ray tracer<\/em><\/a> decente en C#. Es bastante frecuente tener que resolver ecuaciones de tercer y cuarto grado para calcular intersecciones entre rayos de luz y determinados tipos de objetos. La particularidad es que, en este contexto, s\u00f3lo se necesitan las soluciones reales. Cuando las cosas se ponen feas, existe una t\u00e9cnica para encontrar las ra\u00edces reales de cualquier polinomio utilizando las secuencias de Sturm<\/a>. Naturalmente, este algoritmo es una s\u00f3lo una aproximaci\u00f3n iterativa.<\/p>\n

Ra\u00edces complejas, todas<\/h4>\n

Cuando est\u00e1s escribiendo una librer\u00eda como AUSTRA, te interesa resolver el problema m\u00e1s general, que es encontrar todas las ra\u00edces, ya sean complejas o reales, de un polinomio arbitrario. \u00bfSe acuerda de los valores propios<\/a>? El m\u00e9todo que utilizo en AUSTRA est\u00e1 basado en ellos.<\/p>\n

Supongamos que queremos resolver la ecuaci\u00f3n:<\/p>\n

$$c_0 + c_1x + c_2x^2 + \\cdots + c_{n-1}x^{n-1} + x^n$$El t\u00e9rmino de mayor grado est\u00e1 normalizado para que su coeficiente sea la unidad. Ahora formamos la siguiente matriz, conocida como \u00abmatriz de Frobenius\u00bb:<\/p>\n

$$F=\\pmatrix{0&0&0&\\cdots&0&-c_0\\cr
\n1&0&0&\\cdots&0&-c_1\\cr
\n0&1&0&\\cdots&0&-c_2\\cr
\n\\vdots&\\vdots&\\vdots&\\ddots&\\vdots&\\vdots\\cr
\n0&0&0&\\cdots&1&-c_{n-1}}$$Nos planteamos entonces encontrar los valores propios de $F$, que deben cumplir esta igualdad:<\/p>\n

$$F\\vec{v} = \\lambda\\vec{v}$$donde $\\vec{v}$ es uno de los vectores propios. Si reordenamos los t\u00e9rminos, nos encontramos con esto:<\/p>\n

$$(F-\\lambda I)\\vec{v}=0$$donde $I$ es la matriz identidad. Para que esta igualdad se cumpla, el determinante de $(F-\\lambda I)$ debe ser igual a cero. Y resulta que el determinante de $(F-\\lambda I)$ es, precisamente, la ecuaci\u00f3n original. Qu\u00e9 listo era Frobenius.<\/p>\n

AUSTRA tiene un m\u00e9todo muy eficiente para calcular valores propios, incluso en casos como estos, en los que la matriz no es sim\u00e9trica. Por lo tanto, para resolver un polinomio primero lo normalizamos, luego creamos su matriz de Frobenius, y finalmente calculamos sus valores propios. La funci\u00f3n global polySolve<\/em> es la que se encarga de la implementaci\u00f3n, en el lenguaje funcional de AUSTRA. En la aplicaci\u00f3n de consola, podemos teclear lo siguiente:<\/p>\n

\n> set v = [5, 4, 3, 2, 1]\nans \u220a \u211d(5)\n5  4  3  2  1\n> polysolve(v)\nans \u220a \u2102(4)\n<0,137832; 0,678154>   <-0,537832; 0,358285>\n<0,137832; -0,678154>  <-0,537832; -0,358285>\n<\/pre>\n
polySolve<\/em> puede recibir tanto un vector con los coeficientes, como los coeficientes sueltos. En este caso, estamos resolviendo la ecuaci\u00f3n de cuarto grado $5x^4+4x^3+3x^2+2x+1=0$, y el resultado son cuatro n\u00fameros complejos, conjugados a pares.<\/p>\n
\u00bfQuiere comprobar que las ra\u00edces son realmente soluciones de la ecuaci\u00f3n? Hagamos esto entonces:<\/p>\n
\n> polysolve(v).map(c => polyeval(c, v))\nans \u220a \u2102(4)\n<-1,33227E-15; -7,77156E-16>   <-1,33227E-15; 4,44089E-16>\n <-1,33227E-15; 7,77156E-16>  <-1,33227E-15; -4,44089E-16>\n<\/pre>\n
polyEval<\/em> sirve para evaluar un polinomio para un argumento complejo o real, y el m\u00e9todo map<\/em> crea un nuevo vector complejo calculando sus entradas con una funci\u00f3n lambda, al estilo del m\u00e9todo Select<\/em> de LINQ. Incluso tenemos una funci\u00f3n poliDerivative<\/em> que, con los mismos argumentos que polyEval<\/em>, eval\u00faa la derivada del polinomio que le pasamos en la coordenada que le digamos. Esto, a su vez, es muy conveniente para buscar ra\u00edces reales con el m\u00e9todo de Newton-Raphson… que tambi\u00e9n ofrece AUSTRA (funci\u00f3n solve<\/em>, a secas).<\/p>\n
\u00bfLibrer\u00eda o lenguaje?<\/h4>\n
Por supuesto, todo esto ser\u00eda igual de f\u00e1cil, eficiente y elegante, o quiz\u00e1s un poco m\u00e1s, si simplemente enchuf\u00e1semos el package<\/em> Austra.Library a un proyecto en .NET Core y utiliz\u00e1semos directamente las clases. Pero he querido mostrar este ejemplo en el lenguaje de f\u00f3rmulas de AUSTRA como demostraci\u00f3n de un caso de uso importante para el lenguaje: es una forma r\u00e1pida y sencilla de poner a prueba la funcionalidad de la librer\u00eda.<\/p>\n
Y hay m\u00e1s casos de uso, que explicar\u00e9 m\u00e1s adelante.<\/p>\n","protected":false},"excerpt":{"rendered":"
C’est la vie: elle est dure et souvent courte. Es imposible escribir sobre ecuaciones algebraicas sin mencionar a \u00c9variste Galois, quien no s\u00f3lo cerr\u00f3 una larga historia de intentos de soluci\u00f3n de este tipo de ecuaciones, sino que adem\u00e1s tuvo una vida corta y tr\u00e1gica. Dicen que los egipcios y los babilonios eran capaces de […]<\/p>\n","protected":false},"author":1,"featured_media":1428,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[4],"tags":[15,73,77,21,82,80,81],"class_list":["post-1429","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-c","tag-algorithms","tag-austra","tag-complex-numbers","tag-eigenvalues","tag-galois","tag-polynomial","tag-roots"],"jetpack_featured_media_url":"https:\/\/i0.wp.com\/intsight.com\/wp-content\/uploads\/2023\/08\/galois.png?fit=450%2C451&ssl=1","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/intsight.com\/index.php\/wp-json\/wp\/v2\/posts\/1429","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/intsight.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/intsight.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/intsight.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/intsight.com\/index.php\/wp-json\/wp\/v2\/comments?post=1429"}],"version-history":[{"count":43,"href":"https:\/\/intsight.com\/index.php\/wp-json\/wp\/v2\/posts\/1429\/revisions"}],"predecessor-version":[{"id":1474,"href":"https:\/\/intsight.com\/index.php\/wp-json\/wp\/v2\/posts\/1429\/revisions\/1474"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/intsight.com\/index.php\/wp-json\/wp\/v2\/media\/1428"}],"wp:attachment":[{"href":"https:\/\/intsight.com\/index.php\/wp-json\/wp\/v2\/media?parent=1429"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/intsight.com\/index.php\/wp-json\/wp\/v2\/categories?post=1429"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/intsight.com\/index.php\/wp-json\/wp\/v2\/tags?post=1429"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}