Exercicis d'algorismes d'optimització

La iteració.

$x_{k+1} = x_k - \alpha\cdot 32x_k = (1-32\alpha)\,x_k$

La condició. És una progressió geomètrica: convergeix a zero si i només si el mòdul de la raó és menor que $1$:

$|1-32\alpha| < 1 \quad\Longleftrightarrow\quad 0 < \alpha < \frac{1}{16} \approx 0.0625$

Coincideix amb la teoria general. La constant de Lipschitz del gradient és $L = 32$, i la condició general era $\alpha < 2/L$, que dona exactament aquest valor.

El pas òptim. Amb $\alpha = \frac{1}{32}$ la raó val zero i s'arriba al mínim en un sol pas. No és casualitat: aquest és l'invers de la segona derivada, és a dir el pas de Newton, que per a una quadràtica encerta sempre a la primera.

El càlcul.

$x_1 = \frac{1}{2}\left(6 + \frac{31}{6}\right) = \frac{1}{2}\left(6 + 5.166667\right) = 5.583333$

D'on surt la iteració. El pas de Newton és $x - f(x)/f'(x)$; amb $f(x) = x^{2}-31$ i $f'(x) = 2x$, se simplifica a la mitjana d'aquests dos números.

Quantes xifres guanyes. El valor exacte és $\sqrt{31} \approx 5.567764$, i aquesta primera iterada ja hi és a prop. La convergència és quadràtica: el nombre de xifres correctes es duplica a cada pas, de manera que en tres o quatre iteracions tens tota la precisió de la màquina.

Aquest és el mètode que han fet servir les calculadores durant dècades per a l'arrel quadrada, i té més de dos mil anys.

La iteració.

$x_{k+1} = x_k - \alpha\cdot 60x_k = (1-60\alpha)\,x_k$

La condició. És una progressió geomètrica: convergeix a zero si i només si el mòdul de la raó és menor que $1$:

$|1-60\alpha| < 1 \quad\Longleftrightarrow\quad 0 < \alpha < \frac{1}{30} \approx 0.0333$

Coincideix amb la teoria general. La constant de Lipschitz del gradient és $L = 60$, i la condició general era $\alpha < 2/L$, que dona exactament aquest valor.

El pas òptim. Amb $\alpha = \frac{1}{60}$ la raó val zero i s'arriba al mínim en un sol pas. No és casualitat: aquest és l'invers de la segona derivada, és a dir el pas de Newton, que per a una quadràtica encerta sempre a la primera.

El càlcul.

$x_1 = \frac{1}{2}\left(6 + \frac{41}{6}\right) = \frac{1}{2}\left(6 + 6.833333\right) = 6.416667$

D'on surt la iteració. El pas de Newton és $x - f(x)/f'(x)$; amb $f(x) = x^{2}-41$ i $f'(x) = 2x$, se simplifica a la mitjana d'aquests dos números.

Quantes xifres guanyes. El valor exacte és $\sqrt{41} \approx 6.403124$, i aquesta primera iterada ja hi és a prop. La convergència és quadràtica: el nombre de xifres correctes es duplica a cada pas, de manera que en tres o quatre iteracions tens tota la precisió de la màquina.

Aquest és el mètode que han fet servir les calculadores durant dècades per a l'arrel quadrada, i té més de dos mil anys.

La iteració.

$x_{k+1} = x_k - \alpha\cdot 80x_k = (1-80\alpha)\,x_k$

La condició. És una progressió geomètrica: convergeix a zero si i només si el mòdul de la raó és menor que $1$:

$|1-80\alpha| < 1 \quad\Longleftrightarrow\quad 0 < \alpha < \frac{1}{40} \approx 0.0250$

Coincideix amb la teoria general. La constant de Lipschitz del gradient és $L = 80$, i la condició general era $\alpha < 2/L$, que dona exactament aquest valor.

El pas òptim. Amb $\alpha = \frac{1}{80}$ la raó val zero i s'arriba al mínim en un sol pas. No és casualitat: aquest és l'invers de la segona derivada, és a dir el pas de Newton, que per a una quadràtica encerta sempre a la primera.

El càlcul.

$x_1 = \frac{1}{2}\left(7 + \frac{50}{7}\right) = \frac{1}{2}\left(7 + 7.142857\right) = 7.071429$

D'on surt la iteració. El pas de Newton és $x - f(x)/f'(x)$; amb $f(x) = x^{2}-50$ i $f'(x) = 2x$, se simplifica a la mitjana d'aquests dos números.

Quantes xifres guanyes. El valor exacte és $\sqrt{50} \approx 7.071068$, i aquesta primera iterada ja hi és a prop. La convergència és quadràtica: el nombre de xifres correctes es duplica a cada pas, de manera que en tres o quatre iteracions tens tota la precisió de la màquina.

Aquest és el mètode que han fet servir les calculadores durant dècades per a l'arrel quadrada, i té més de dos mil anys.

La iteració.

$x_{k+1} = x_k - \alpha\cdot 120x_k = (1-120\alpha)\,x_k$

La condició. És una progressió geomètrica: convergeix a zero si i només si el mòdul de la raó és menor que $1$:

$|1-120\alpha| < 1 \quad\Longleftrightarrow\quad 0 < \alpha < \frac{1}{60} \approx 0.0167$

Coincideix amb la teoria general. La constant de Lipschitz del gradient és $L = 120$, i la condició general era $\alpha < 2/L$, que dona exactament aquest valor.

El pas òptim. Amb $\alpha = \frac{1}{120}$ la raó val zero i s'arriba al mínim en un sol pas. No és casualitat: aquest és l'invers de la segona derivada, és a dir el pas de Newton, que per a una quadràtica encerta sempre a la primera.

El càlcul.

$x_1 = \frac{1}{2}\left(8 + \frac{65}{8}\right) = \frac{1}{2}\left(8 + 8.125000\right) = 8.062500$

D'on surt la iteració. El pas de Newton és $x - f(x)/f'(x)$; amb $f(x) = x^{2}-65$ i $f'(x) = 2x$, se simplifica a la mitjana d'aquests dos números.

Quantes xifres guanyes. El valor exacte és $\sqrt{65} \approx 8.062258$, i aquesta primera iterada ja hi és a prop. La convergència és quadràtica: el nombre de xifres correctes es duplica a cada pas, de manera que en tres o quatre iteracions tens tota la precisió de la màquina.

Aquest és el mètode que han fet servir les calculadores durant dècades per a l'arrel quadrada, i té més de dos mil anys.

La iteració.

$x_{k+1} = x_k - \alpha\cdot 160x_k = (1-160\alpha)\,x_k$

La condició. És una progressió geomètrica: convergeix a zero si i només si el mòdul de la raó és menor que $1$:

$|1-160\alpha| < 1 \quad\Longleftrightarrow\quad 0 < \alpha < \frac{1}{80} \approx 0.0125$

Coincideix amb la teoria general. La constant de Lipschitz del gradient és $L = 160$, i la condició general era $\alpha < 2/L$, que dona exactament aquest valor.

El pas òptim. Amb $\alpha = \frac{1}{160}$ la raó val zero i s'arriba al mínim en un sol pas. No és casualitat: aquest és l'invers de la segona derivada, és a dir el pas de Newton, que per a una quadràtica encerta sempre a la primera.

El càlcul.

$x_1 = \frac{1}{2}\left(3 + \frac{3}{3}\right) = \frac{1}{2}\left(3 + 1.000000\right) = 2.000000$

D'on surt la iteració. El pas de Newton és $x - f(x)/f'(x)$; amb $f(x) = x^{2}-3$ i $f'(x) = 2x$, se simplifica a la mitjana d'aquests dos números.

Quantes xifres guanyes. El valor exacte és $\sqrt{3} \approx 1.732051$, i aquesta primera iterada ja hi és a prop. La convergència és quadràtica: el nombre de xifres correctes es duplica a cada pas, de manera que en tres o quatre iteracions tens tota la precisió de la màquina.

Aquest és el mètode que han fet servir les calculadores durant dècades per a l'arrel quadrada, i té més de dos mil anys.