Mètode de Newton i el seu fractal

El mètode de Newton és, probablement, l'algorisme més usat de la història del càlcul científic: hi ha una versió seva dins de gairebé tot el que calcula alguna cosa, des del teu processador fins als models climàtics. La seva idea cap en una frase, la seva velocitat és espectacular, i tanmateix pot fallar de maneres tan estranyes que van fer falta cent anys i el descobriment dels fractals per entendre-les.

1. El problema, i per què no hi ha fórmula

Volem resoldre f(x) = 0. Per a polinomis de grau 2 hi ha fórmula; per als de grau 3 i 4 també, tot i que horribles. A partir del grau 5 no n'hi ha cap, i això no és una limitació temporal sinó un teorema —el d'Abel–Ruffini, que trobaràs demostrat conceptualment a la càpsula de Teoria de Galois.

I això només parlant de polinomis. Per a equacions com cos x = x, o x·eˣ = 1, no hi ha ni tan sols l'esperança d'una fórmula amb funcions elementals.

La conclusió pràctica és que, per a la immensa majoria d'equacions del món real, no hi ha resposta exacta escrivible. El que hi ha és una resposta calculable amb tanta precisió com vulguis. I la manera d'obtenir-la és el tema d'aquesta càpsula.

2. La idea: si no saps resoldre-ho, aproxima-ho per una recta

La intuïció és aquesta: les corbes són difícils, les rectes són fàcils. Si a prop del punt on som la corba s'assembla a una recta, resolguem el problema de la recta i acceptem la seva resposta com a millor aproximació.

Concretament: som a x₀. Tracem la tangent a la corba en aquell punt —la recta que millor l'aproxima localment. Aquesta recta sí que sabem on talla l'eix. Aquell punt de tall és el nostre x₁. Repetim.

Res més. Tot el mètode és aquesta línia. La divisió per f′ té una lectura clara: si el pendent és gran, el salt és petit (la corba baixa de pressa, no cal anar gaire lluny); si el pendent és petit, el salt és enorme (la corba és gairebé plana i l'eix queda molt lluny). Això ja anuncia el problema que veurem al punt 4.

3. Convergència quadràtica: per què és tan bo

Aquí hi ha el motiu pel qual aquest mètode ha sobreviscut 350 anys. Quan funciona, el nombre de xifres correctes es duplica a cada pas.

La raó és que l'error del pas següent és proporcional al quadrat de l'error actual: si eₙ és l'error, eₙ₊₁ ≈ C·eₙ². Si tens 3 xifres correctes (error ~10⁻³), el pas següent en tindrà ~6, i el següent ~12.

D'on surt el quadrat? De Taylor. Prop de l'arrel r, f(r) = 0, i desenvolupant f al voltant de xₙ es veu que els termes de primer ordre s'anul·len exactament per la construcció del mètode, i el primer que sobreviu és el de segon ordre, proporcional a (xₙ−r)². El mètode és quadràtic perquè la tangent captura tota la informació de primer ordre.

4. Quan falla, i com de malament pot fallar

«Quan funciona» és la clau, i les maneres de fallar són instructives.

Derivada zero

Si f′(xₙ) = 0, la tangent és horitzontal i no talla mai l'eix: la fórmula divideix per zero i el mètode s'atura en sec. A la càpsula, l'aplicació t'ho diu explícitament quan passa.

Divergència

Si comences massa lluny o la funció té la forma equivocada, els salts poden allunyar-te en lloc d'acostar-te, i escapar cap a l'infinit.

Cicles

Aquest és el més inquietant. El mètode pot quedar atrapat saltant entre uns pocs punts per sempre, sense divergir ni convergir. La càpsula en té l'exemple clàssic:

Pots reproduir-ho exactament a la càpsula escrivint x₀ = 0 al camp numèric i prement «Següent pas» unes quantes vegades. Amb el ratolí seria pràcticament impossible encertar el 0 exacte; per això hi ha el camp.

5. El pla complex: on el fracàs es fa bonic

Aquí ve el gir. La fórmula de Newton no necessita que x sigui real: només cal saber derivar, restar i dividir, i els nombres complexos permeten fer-ho tot. Així que apliquem-la al pla complex.

Prenem z³ − 1 = 0. Té tres arrels, les tres arrels cúbiques de la unitat, situades als vèrtexs d'un triangle equilàter (exactament el que veuries a la càpsula del Pla d'Argand). Cada punt de partida del pla convergeix cap a una de les tres. La pregunta natural és: cap a quina?

La pregunta la va plantejar Arthur Cayley el 1879. Va resoldre el cas quadràtic sense dificultat —el pla es parteix en dos semiplans per la mediatriu, net i avorrit— i després va escriure que el cas cúbic «sembla presentar dificultats considerables». Va abandonar-lo.

Tenia raó. Si pintes cada punt del pla segons quina arrel «guanya», no surten tres regions amb fronteres suaus: surt un fractal de complexitat infinita. I la seva frontera té una propietat que costa d'assimilar:

Això vol dir que, a prop de la frontera, la pregunta «cap a quina arrel convergeix?» és numèricament impossible de respondre amb seguretat: qualsevol error d'arrodoniment, per petit que sigui, pot canviar la resposta. Un mètode completament determinista, amb una fórmula d'una sola línia i cap atzar enlloc, produeix un comportament impredictible en la pràctica.

6. Què fem a l'element interactiu

Vista 1D, pas a pas. Tries f(x), fixes x₀ (clicant la gràfica o escrivint-lo) i prems «Següent pas». Es dibuixa la tangent i el salt fins a l'eix. La narració de sota et dona el valor de x, de f(x) i de f′(x) a cada iteració, que és el que et permet veure la convergència quadràtica: mira com f(x) es va apropant a zero afegint zeros de cop.

Vista del pla complex. Tries un polinomi i cliques (o escrius) un punt de partida: es dibuixa el camí complet de convergència, salt a salt. El botó «Revela el fractal» calcula, per a cada punt d'una graella de tot el pla visible, quina arrel guanya —són desenes de milers d'iteracions de Newton fetes a l'instant, no una imatge pregravada. Un cop revelat, pots seguir clicant punts per superposar-hi camins concrets.

7. Aparicions fora de les matemàtiques

Dins del teu processador. Molts processadors no tenen circuit de divisió: calculen 1/a amb Newton aplicat a f(x) = 1/x − a, que dona la iteració xₙ₊₁ = xₙ(2 − a·xₙ) —només multiplicacions i restes. Les arrels quadrades es fan igual. Cada divisió que fa el teu ordinador pot ser, literalment, unes quantes iteracions de Newton.

La famosa «fast inverse square root». El codi del motor de Quake III per calcular 1/√x combinava un truc de bits amb una sola iteració de Newton per refinar-lo. Va ser prou eficaç per fer possible la il·luminació en temps real als ordinadors de finals dels 90, i el fragment de codi és probablement el més comentat de la història dels videojocs.

Optimització i aprenentatge automàtic. Trobar el mínim d'una funció és trobar on la derivada s'anul·la: Newton aplicat a f′. Els mètodes de segon ordre i les seves aproximacions (quasi-Newton, BFGS, L-BFGS) són eines estàndard, i tot l'entrenament de models s'hi basa en algun grau.

Enginyeria i simulació. Els mètodes implícits per a equacions diferencials rígides (vegeu la càpsula de Camp de pendents) requereixen resoldre una equació no lineal a cada pas, i ho fan amb Newton. El mateix per als simuladors de circuits, els solucionadors d'elements finits i els models de flux de potència a les xarxes elèctriques.

Finances. Calcular la taxa interna de retorn (TIR) d'un flux de caixa, o la volatilitat implícita d'una opció a partir del seu preu, són equacions sense solució tancada que es resolen amb Newton.

8. Curiositats

Newton no el va escriure així. El mètode que Newton va descriure cap al 1669 no feia servir derivades ni era iteratiu en el sentit modern: era un procediment algebraic per a polinomis. Joseph Raphson el va simplificar el 1690, i Thomas Simpson el 1740 va ser el primer a donar-li la forma general amb f′ i a aplicar-lo a sistemes d'equacions. El nom just seria «mètode de Newton–Raphson–Simpson», però la història és injusta amb els noms.

El fractal de Newton és anterior al concepte de fractal. Cayley va topar amb el problema el 1879. Fatou i Julia en van desenvolupar la teoria cap al 1918-1920, sense poder-ne veure mai una imatge. Va caldre esperar als ordinadors dels anys 70 i 80 perquè algú pogués mirar allò que havien descrit. Mandelbrot va explicar que veure aquelles imatges va ser el que el va convèncer que hi havia una geometria per descobrir.

Hi ha punts de partida que no van enlloc. A més dels cicles, existeixen punts inicials des dels quals el mètode no convergeix mai a cap arrel. Per al fractal de Newton, el conjunt d'aquests punts és precisament la frontera fractal, que té mesura zero (és «infinitament prim») però és infinitament complicat i està a tot arreu.

La convergència quadràtica té lletra petita. Només es dona si l'arrel és simple. Si f té una arrel doble (com x² a f(x)=x²), la convergència passa a ser només lineal i el mètode perd tot el seu avantatge. Hi ha una versió modificada que recupera la velocitat si saps la multiplicitat de l'arrel.

Es pot fer servir per calcular π. Aplicant Newton a f(x) = sin x amb x₀ = 3 s'obté 3,141592653589793… en només dues o tres iteracions, perquè sin té una arrel simple a π i la seva derivada allà val −1, cosa que fa la constant d'error molt favorable.

El mètode de la secant és Newton per als mandrosos. Si no vols (o no pots) calcular f′, la pots aproximar amb el pendent entre els dos últims punts. La convergència baixa d'ordre 2 a ordre 1,618… —el nombre auri, que apareix aquí per una raó completament diferent de la de la càpsula de Fraccions contínues.

9. Connexió amb altres àrees

Amb el Joc del caos forma una parella perfecta i complementària: allà s'itera una regla aleatòria i n'apareix una figura ordenada; aquí s'itera una regla completament determinista i n'apareix una frontera impredictible. Junts diuen que la complexitat no ve de l'atzar sinó de la iteració.

Amb el Pla d'Argand la connexió és literal: la vista complexa d'aquesta càpsula viu en aquell pla, i les arrels que hi busca (les de zⁿ−1) són exactament les arrels de la unitat que allà es dibuixen com un polígon regular.

Amb Teoria de Galois hi ha una relació de causa i efecte: allà es demostra que no pot existir una fórmula per al grau 5; aquí es veu què es fa a la pràctica quan no n'hi ha. Els dos resultats són les dues cares de la mateixa moneda.

I amb Camp de pendents comparteix l'esperit de l'anàlisi numèrica: mètodes iteratius, ordres de convergència, i la consciència que un mètode pot donar-te un número perfectament formatat que sigui completament equivocat si no en respectes les condicions d'ús.