Mètodes numèrics: bisecció, Newton-Raphson, trapezis i Simpson

Gairebé cap equació que surt d'un problema real d'enginyeria es pot resoldre amb una fórmula, i moltes integrals no tenen primitiva elemental. Els mètodes numèrics substitueixen la solució exacta per una successió d'aproximacions amb l'error controlat, i són el que fa servir qualsevol calculadora o programa quan li demanes una arrel o una integral. En aquesta pàgina veuràs els quatre mètodes bàsics que s'estudien a primer curs: el mètode de la bisecció i el mètode de Newton-Raphson (amb la secant com a variant) per resoldre $f(x) = 0$, i les regles compostes dels trapezis i de Simpson per aproximar $\int_a^b f(x)\,dx$. Per a cadascun, la fórmula, què garanteix, quan falla i un exemple amb la taula d'iteracions.

Per què calen mètodes numèrics

L'equació $x^3 - x - 1 = 0$ té una única arrel real, però la fórmula de Cardano que la dona és inservible a la pràctica; $\cos x = x$ ni tan sols té fórmula. I integrals com $\int_0^1 e^{-x^2}\,dx$ o $\int_0^\pi \sqrt{1 + \cos^2 x}\,dx$ (una longitud d'arc) no tenen primitiva expressable amb funcions elementals. Un mètode numèric és un algorisme que, a partir de la funció i d'un punt o interval de partida, produeix aproximacions $x_1, x_2, \ldots$ i, sobretot, una fita de l'error que permet aturar-se quan la precisió és suficient. Sense fita de l'error, un nombre amb molts decimals no és un resultat.

Els mètodes d'aquesta pàgina complementen la resolució exacta que has vist a límits, continuïtat i derivada (el teorema de Bolzano és el fonament de la bisecció) i a mètodes d'integració.

Mètode de la bisecció

Un interval $[a, b]$ amb canvi de signe s'anomena un bracket de l'arrel. La bisecció consisteix a partir el bracket per la meitat i quedar-se amb la meitat que conserva el canvi de signe: si $m = (a + b)/2$ i $f(a)\,f(m) < 0$, l'arrel és a $[a, m]$; si no, és a $[m, b]$. Cada pas divideix la longitud del bracket per dos, de manera que la convergència està garantida (només cal continuïtat) i l'error és previsible:

on $m_n$ és el punt mitjà del pas $n$. Si vols error menor que una tolerància $\varepsilon$, n'hi ha prou amb

Amb $b - a = 1$: $10$ passos per a $\varepsilon = 10^{-3}$ i $20$ passos per a $\varepsilon = 10^{-6}$. És lent (cada pas guanya un bit, uns $0{,}3$ decimals), però mai no falla.

Mètode de Newton-Raphson

Newton canvia la garantia de la bisecció per velocitat. La idea és substituir $f$ per la seva recta tangent al punt actual $x_n$ i prendre com a aproximació següent el punt on la tangent talla l'eix. La tangent és $y = f(x_n) + f'(x_n)(x - x_n)$, i s'anul·la a

Quan falla Newton

El mètode és local: prop d'una arrel simple és imbatible, però lluny d'ella no hi ha cap garantia.

• Derivada nul·la o molt petita. Si $f'(x_n) = 0$ la tangent és horitzontal i no talla l'eix. Per a $f(x) = x^3 - x - 1$, els punts $x = \pm 1/\sqrt{3}$ són prohibits, i prop seu el pas $f/f'$ és enorme.
• Mala llavor. Amb $x_0 = 0$, la mateixa equació dona $x_1 = -1$, $x_2 = -0{,}5$, $x_3 = -3$: la successió surt del bracket i triga a tornar. Per això es recomana obtenir primer un bracket amb Bolzano i triar $x_0$ dins seu.
• Cicles i canvi d'arrel. Si l'equació té diverses arrels, Newton pot oscil·lar entre dos valors o convergir a una arrel diferent de la que busques.
• Arrel múltiple ($f'(r) = 0$). El mètode convergeix, però només linealment: es perd l'avantatge.

El control pràctic és doble: vigilar el residu $|f(x_n)|$ i la diferència $|x_{n+1} - x_n|$, i aturar-se quan tots dos són menors que la tolerància. Una diferència petita entre iterats no demostra per si sola que s'ha convergit, però combinada amb un residu petit i un bracket previ és un criteri fiable.

Mètode de la secant

Si la derivada és cara o no està disponible, se substitueix la tangent per la secant que passa pels dos últims iterats:

Cal partir de dos punts, $x_0$ i $x_1$. La convergència és superlineal (d'ordre aproximadament $1{,}618$, el nombre d'or): més lenta que Newton però sense derivades. Per a $x^3 - x - 1 = 0$ amb $x_0 = 1$ i $x_1 = 2$, els iterats són $1{,}1667$, $1{,}2531$, $1{,}3372$, $1{,}3239$, $1{,}32471$, $1{,}3247180$: sis passos per a set decimals correctes.

Integració numèrica

Per aproximar $I = \int_a^b f(x)\,dx$ es divideix $[a, b]$ en $n$ subintervals d'amplada $h = (b - a)/n$, amb nodes $x_i = a + ih$, i es substitueix $f$ per una funció fàcil d'integrar en cada tros.

Regla dels trapezis composta

En cada subinterval s'aproxima $f$ per la recta que uneix $(x_i, f(x_i))$ i $(x_{i+1}, f(x_{i+1}))$: l'àrea és la d'un trapezi, $\tfrac{h}{2}\big(f(x_i) + f(x_{i+1})\big)$. Sumant,

Els pesos són $\tfrac{1}{2}, 1, 1, \ldots, 1, \tfrac{1}{2}$. L'error és d'ordre $h^2$: doblar $n$ divideix l'error per $4$.

Regla de Simpson composta

Simpson aproxima $f$ per una paràbola en cada parell de subintervals consecutius (per tant $n$ ha de ser parell):

Els pesos són $1, 4, 2, 4, \ldots, 2, 4, 1$: $4$ als índexs senars, $2$ als parells interiors. L'error és d'ordre $h^4$: doblar $n$ divideix l'error per $16$. A més, Simpson és exacte per a polinomis de grau $\leq 3$, no només de grau $2$, perquè l'error de la cúbica es cancel·la per simetria.

Protocol de resolució

Per a una equació $f(x) = 0$:

1. Escriu l'equació en la forma $f(x) = 0$ i estudia $f$: continuïtat, signe, monotonia.
2. Troba un bracket $[a, b]$ amb $f(a)\,f(b) < 0$ i justifica la unicitat de l'arrel dins seu si cal.
3. Si et demanen una precisió $\varepsilon$ amb bisecció, calcula el nombre de passos $n \geq \log_2\frac{b - a}{\varepsilon}$ abans de començar.
4. Si fas Newton, tria $x_0$ dins del bracket, escriu la fórmula d'iteració simplificada i fes una taula amb $x_n$, $f(x_n)$ i $|x_{n+1} - x_n|$.
5. Atura't quan el residu i la diferència entre iterats siguin menors que $\varepsilon$, i dona el resultat amb els decimals que la fita justifica.

Per a una integral:

1. Comprova que la integral és pròpia (integrand continu i fitat a $[a, b]$); si no, els mètodes d'aquesta pàgina no s'apliquen directament.
2. Fixa $n$ (parell per a Simpson), calcula $h$ i fes una taula amb els nodes $x_i$, els valors $f(x_i)$ i els pesos.
3. Aplica la fórmula i, si te la demanen, la fita de l'error amb el màxim de $|f''|$ o $|f^{(4)}|$.
4. Comprova el signe de l'error amb la concavitat (trapezis sobreestimen les funcions convexes) i l'ordre de magnitud del resultat.

Exercicis proposats

Exercici 1. Demostra que l'equació $\cos x = x$ té una única solució real i aproxima-la amb bisecció (5 passos a partir de $[0, 1]$) i amb Newton (a partir de $x_0 = 1$, fins a tenir 8 decimals estables).

Exercici 2. Calcula $\sqrt{2}$ amb el mètode de Newton aplicat a $f(x) = x^2 - 2$ partint de $x_0 = 1$. Escriu la fórmula d'iteració simplificada i fes 4 iteracions.

Exercici 3. Aproxima $\displaystyle\int_0^1 \frac{4}{1 + x^2}\,dx$ amb trapezis i Simpson per a $n = 4$, i compara amb el valor exacte.

Aquests mètodes són la porta d'entrada al càlcul numèric que faràs servir a les assignatures d'enginyeria amb MATLAB o Python. Els resultats que aproximen (arrels d'equacions, integrals definides) són els que has estudiat de manera exacta a mètodes d'integració i a àrees, volums i integrals dobles; i a un nivell més bàsic, a les integrals de selectivitat. Per a funcions de diverses variables, el mètode de Newton es generalitza substituint la derivada pel gradient i el hessià que veus a diverses variables.