Successioni, funzioni quadratiche e metodo di Newton

Successioni e punti limite

Un algoritmo genera una successione $\{x_k\}$ di punti di $\mathbb R^n$, cioè una funzione dai naturali a $\mathbb R^n$, e si vuole che converga, di solito alla soluzione del problema. Per questo conta come si comporta una successione.

• Convergente: per $k\to\infty$ tende a un unico punto $\bar x$, il limite: $\lim_{k\to\infty}x_k=\bar x$. Il limite è per $k\to\infty$ perché l'infinito è il punto di accumulazione dei naturali.
• Divergente: tende all'infinito.
• Irregolare: non è né convergente né divergente.
• Limitata: esiste una costante $M$ con $\|x_k\|\le M$ per ogni $k$.

Una sottosuccessione si ottiene scegliendo un insieme di indici $K\subseteq\{0,1,\dots\}$ e tenendo solo gli $x_k$ con $k\in K$. Se esiste $K$ tale che

$$\lim_{\substack{k\in K\\k\to\infty}}x_k=\hat x$$

allora $\hat x$ è un punto limite. Il limite riguarda tutta la successione, il punto limite una sua sottosuccessione: sono concetti distinti.

Esempio in $\mathbb R^2$, con gli indici pari e dispari:

$$x_k=\begin{cases} \begin{pmatrix}\dfrac1{k+1}\\[0.5em]0\end{pmatrix} & k=0,2,4,\dots\\[1.4em] \begin{pmatrix}-2\\[0.2em]\dfrac1{k^2+1}\end{pmatrix} & k=1,3,5,\dots \end{cases}$$

Con $K_1=\{0,2,4,\dots\}$ e $K_2=\{1,3,5,\dots\}$:

$$\begin{gathered} \lim_{\substack{k\in K_1\\k\to\infty}}x_k=\begin{pmatrix}0\\0\end{pmatrix}\\[0.6em] \lim_{\substack{k\in K_2\\k\to\infty}}x_k=\begin{pmatrix}-2\\0\end{pmatrix} \end{gathered}$$

Due punti limite distinti: la successione non converge, perché un limite è unico, e non diverge. È quindi irregolare.

Una successione con due punti limite

Indici

TuttiPari: $K_1$Dispari: $K_2$

$x_0$$x_1$$x_2$

Funzioni lineari

Una funzione $f:\mathbb R^n\to\mathbb R^m$ è lineare se, per ogni $x,y\in\mathbb R^n$ e ogni $\alpha,\beta\in\mathbb R$, vale il principio di sovrapposizione degli effetti:

$$f(\alpha x+\beta y)=\alpha f(x)+\beta f(y)$$

Ciò equivale a $f(x)=Ax$, con $A$ di dimensione $m\times n$. Se $f:\mathbb R^n\to\mathbb R$, è lineare quando $f(x)=c^\top x$, il prodotto scalare fra il vettore dei coefficienti e quello delle variabili.

Per esempio $f(x_1,x_2,x_3,x_4)=-3x_1+2x_2-6x_3+4x_4$ è lineare:

$$f(x)=\begin{pmatrix}-3&2&-6&4\end{pmatrix}\begin{pmatrix}x_1\\x_2\\x_3\\x_4\end{pmatrix}$$

Invece $f(x_1,x_2)=e^{3x_1+4x_2}$ non lo è. L'argomento dell'esponenziale è lineare, ma la funzione no: non si scrive come $c^\top x$, e per esempio vale $1$ nell'origine, dove una funzione lineare vale $0$.

Forme e funzioni quadratiche

In una variabile, $f(x)=ax^2$ è una forma quadratica: un polinomio omogeneo di secondo grado. Con un termine lineare e uno costante, $f(x)=ax^2+cx+b$, è una funzione quadratica. Una funzione lineare più un termine costante è invece affine: una lineare traslata.

In $\mathbb R^2$ una forma quadratica si scrive in tre modi equivalenti:

$$\begin{aligned} f(x_1,x_2)&=a_{11}x_1^2+a_{12}x_1x_2+a_{21}x_2x_1+a_{22}x_2^2\\ &=\sum_{i=1}^{2}\sum_{j=1}^{2}a_{ij}\,x_ix_j\\ &=\begin{pmatrix}x_1&x_2\end{pmatrix} \begin{pmatrix}a_{11}&a_{12}\\a_{21}&a_{22}\end{pmatrix} \begin{pmatrix}x_1\\x_2\end{pmatrix}\\ &=x^\top Ax \end{aligned}$$

Poiché $x_1x_2=x_2x_1$, conta solo la somma $a_{12}+a_{21}$ dei coefficienti misti. Nello stesso esempio la forma resta la stessa se i coefficienti $2$ e $4$ diventano $1$ e $5$, oppure $3$ e $3$:

$$\begin{gathered} -3x_1^2+2x_1x_2+4x_2x_1+6x_2^2,\quad A=\begin{pmatrix}-3&2\\4&6\end{pmatrix}\\[0.6em] -3x_1^2+x_1x_2+5x_2x_1+6x_2^2,\quad A=\begin{pmatrix}-3&1\\5&6\end{pmatrix}\\[0.6em] -3x_1^2+3x_1x_2+3x_2x_1+6x_2^2,\quad A=\begin{pmatrix}-3&3\\3&6\end{pmatrix} \end{gathered}$$

Le tre matrici danno la stessa funzione, e l'ultima è simmetrica: $A=A^\top$. Ogni forma quadratica si può scrivere con una matrice simmetrica senza cambiare i suoi valori.

La forma dipende solo dalla somma dei coefficienti misti

angolo

• forma $x^{\top }Ax$
• termine $a_{12}{x}_1{x}_2$
• termine $a_{21}{x}_2{x}_1$

$a_{12}-a_{21}$

−2

$a_{12}+a_{21}$

6

In $\mathbb R^n$ una funzione quadratica è

$$\begin{gathered} f:\mathbb R^n\to\mathbb R\\ f(x)=x^\top Ax+c^\top x+b \end{gathered}$$

con $A\in\mathbb R^{n\times n}$, $c\in\mathbb R^n$ e $b\in\mathbb R$. Per $n=3$, per esempio:

$$A=\begin{pmatrix}5&2&1\\3&6&4\\0&3&1\end{pmatrix},\quad c=\begin{pmatrix}3\\-2\\4\end{pmatrix},\quad b=6$$

Simmetrizzare la matrice

Se $A$ non è simmetrica, si può sostituirla con la media $(A+A^\top)/2$, che è simmetrica e dà gli stessi valori della forma. Non si afferma che le due matrici siano uguali: lo sono i valori delle due forme quadratiche.

La dimostrazione usa due fatti. Il prodotto $x^\top A^\top x$ è uno scalare, quindi coincide con il proprio trasposto, e la trasposta di un prodotto è $(ABC)^\top=C^\top B^\top A^\top$:

$$x^\top A^\top x=\bigl(x^\top A^\top x\bigr)^\top=x^\top Ax$$

Allora

$$\begin{aligned} x^\top\Bigl(\tfrac12(A+A^\top)\Bigr)x&=\tfrac12\,x^\top Ax+\tfrac12\,x^\top A^\top x\\ &=\tfrac12\,x^\top Ax+\tfrac12\,x^\top Ax=x^\top Ax \end{aligned}$$

Per la matrice $3\times3$ di prima:

$$\tfrac12(A+A^\top)=\tfrac12\begin{pmatrix}10&5&1\\5&12&7\\1&7&2\end{pmatrix} =\begin{pmatrix}5&\tfrac52&\tfrac12\\[0.3em]\tfrac52&6&\tfrac72\\[0.3em]\tfrac12&\tfrac72&1\end{pmatrix}$$

Una matrice simmetrica si memorizza con la sola diagonale e una metà. Gli elementi da tenere sono

$$n+(n-1)+\dots+1=\frac{n(n+1)}2$$

Il metodo di Newton

Si cerca $\bar x\in\mathbb R$ tale che $f(\bar x)=0$, con $f:\mathbb R\to\mathbb R$ non lineare. Se $f$ fosse lineare, basterebbe risolvere un'equazione di primo grado. L'idea è sostituire $f$ con la sua approssimazione lineare in un punto iniziale $x_0$, una funzione affine:

$$\hat f(x)=f(x_0)+f'(x_0)(x-x_0)$$

Si pone $\hat f(x_1)=0$, cioè $f(x_0)+f'(x_0)(x_1-x_0)=0$, e, se $f'(x_0)\ne0$:

$$x_1=x_0-\frac{f(x_0)}{f'(x_0)}$$

Geometricamente $x_1$ è l'intersezione con l'asse delle ascisse della tangente nel punto $(x_0,f(x_0))$. Non è detto che $x_1$ annulli $f$, ma si può ripetere da $x_1$ e ottenere $x_2$, e così via:

$$x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}$$

Il metodo genera una successione $\{x_k\}$, e studiarlo significa studiare questa successione: si vuole che $x_k$ converga a un $\bar x$ con $f(\bar x)=0$. Le idee degli algoritmi di ottimizzazione partono dal caso lineare o quadratico, che si sa trattare, e si adattano poi al caso generale.

Due passi del metodo di Newton

$x_0$$x_1$$x$

• $f(x)=x^2-2$
• $\hat{f}$: tangente in $x_0$
• tangente in $x_1$

$x_0$

2,5

Convergenza del metodo

Convergenza locale. Se $f'(\bar x)\ne0$, condizione naturale perché la derivata sta al denominatore, e se $x_0$ è sufficientemente vicino a $\bar x$, la successione converge a $\bar x$ con una certa rapidità. Se $f'$ è continua, resta diversa da zero in un intorno di $\bar x$, quindi le iterazioni che partono lì sono ben definite. Quanto vicino debba essere $x_0$ è una condizione teorica, difficile da riconoscere in pratica. Un metodo con questa proprietà è localmente convergente; uno globalmente convergente converge anche partendo da punti lontani.

Strategia multi-start. In una variabile il grafico suggerisce un punto iniziale vicino alla soluzione. In più variabili la funzione non si vede, quindi si provano più punti iniziali generati a caso, sperando che uno cada in una zona da cui il metodo converge.

Asintotica e finita. La convergenza asintotica vuol dire $x_k\to\bar x$ per $k\to\infty$. Più forte è la convergenza finita: la soluzione si raggiunge in un numero finito di iterazioni. Vale solo per poche classi di problemi.

Due risultati sulle successioni reali

Sia $\{x_k\}:\mathbb N\to\mathbb R$.

1. Se è monotona, allora $\lim_{k\to\infty}x_k=\bar x\in\mathbb R^*$: il limite esiste ed è finito, $+\infty$ o $-\infty$. Non si estende a $\mathbb R^n$, perché da $\mathbb R^2$ in poi manca l'ordinamento totale.
2. Se è limitata, ammette almeno una sottosuccessione convergente (teorema di Bolzano-Weierstrass per successioni). Si estende a $\mathbb R^n$.

Premessa. Una successione in $\mathbb R^n$ è limitata se e solo se sono limitate le successioni delle sue componenti. Per esempio

$$x_k=\begin{pmatrix}\dfrac1{k+1}\\[0.5em]2\\[0.2em]-1\\[0.2em]\dfrac1{k^2+1}\end{pmatrix}$$

ha tutte le componenti limitate, quindi è limitata. Se la seconda componente fosse $k$, sarebbe illimitata, e con lei la successione.

Dimostrazione in $\mathbb R^n$. Sia $\{x_k\}$ limitata e $x_k^{(i)}$ la sua componente $i$.

1. $\{x_k^{(1)}\}$ è limitata, quindi per il risultato in $\mathbb R$ esiste $K_1\subseteq\{0,1,\dots\}$ con $\lim_{k\in K_1}x_k^{(1)}=\bar x^{(1)}$.
2. Su $K_1$ anche $\{x_k^{(2)}\}$ è limitata, quindi esiste $K_2\subseteq K_1$ con $\lim_{k\in K_2}x_k^{(2)}=\bar x^{(2)}$.
3. Si procede così fino alla componente $n$, ottenendo insiemi annidati $K_n\subseteq\dots\subseteq K_2\subseteq K_1$ e $\lim_{k\in K_n}x_k^{(n)}=\bar x^{(n)}$.

Ogni $K_i$ è contenuto nei precedenti, quindi lungo $K_n$ le prime componenti continuano a convergere ai loro limiti. Convergono tutte le componenti, dunque converge il vettore:

$$\lim_{\substack{k\in K_n\\k\to\infty}}x_k=\bar x$$

Il punto delicato è proprio la catena di insiemi di indici annidati.