Courant-Fischer

Data $A \in \mathbb{R}^{n \times n}$ simmetrica e $x \in \mathbb{R}^n, x \neq 0$ .

§ Definizione. Il quoziente di Rayleigh è l’applicazione

 $r : \mathbb{R}^n \setminus \{0\} \to \mathbb{R}, \quad x \mapsto \frac{x^T A x}{x^T x}$

Osservazione. Il gradiente del quoziente di Rayleigh è

 $\nabla(r(x)) = \frac{2}{x^T x} (A - \lambda I)x, \quad \lambda = r(x)$

Ovvero i punti stazionari di $r$ sono gli autovettori di $A$ e i valori assunti sono gli autovalori.

§ Teorema. Siano $\lambda_1 \ge \dots \ge \lambda_n$ gli autovalori di $A$ . Allora

 $\max_{x \neq 0} r(x) = \lambda_1, \quad \min_{x \neq 0} r(x) = \lambda_n$

Vale anche una generalizzazione di questo teorema a sottospazi di dimensione $k$ .

§ Teorema (Courant-Fischer). Siano $\lambda_1 \ge \dots \ge \lambda_n$ gli autovalori di $A$ . Sia $V_k \subseteq \mathbb{R}^n$ un sottospazio di dimensione $k$ . Allora:

 $\min_{\substack{V_k \subset \mathbb{R}^n \\ \dim V_k = k}} \max_{x \in V_k \setminus \{0\}} r(x) = \lambda_{n-k+1} \quad \forall k$

 $\max_{\substack{V_k \subset \mathbb{R}^n \\ \dim V_k = k}} \min_{x \in V_k \setminus \{0\}} r(x) = \lambda_k \quad \forall k$

Dimostrazione. Vediamo la versione $\max$ - $\min$ : esiste una base $x_i$ di autovettori ortonormali di $A$ . Sia $S := \text{span}\{ x_k, \dots, x_n \}$ . Allora per ogni sottospazio $V_k$ (con $\dim V_k = k$ ) vale $S \cap V_k \neq 0$ per motivi di dimensione $\Rightarrow \exists x \in S \cap V_k$ . Possiamo scrivere $x = \sum_{i=k}^n \alpha_i x_i$ . Allora vale:

 $\frac{x^T A x}{x^T x} = \frac{\sum_{i=k}^n \alpha_i^2 \lambda_i}{\sum_{i=k}^n \alpha_i^2} \le \lambda_k \frac{\sum_{i=k}^n \alpha_i^2}{\sum_{i=k}^n \alpha_i^2} = \lambda_k$

Quindi $\min_{x \in V_k} r(x) \le \lambda_k$ ed anche $\max_{V_k} \min_{x \in V_k} r(x) \le \lambda_k$ . Resta da vedere che esiste un $\hat{V}_k$ per cui si ottiene l’uguaglianza. Poniamo

 $\hat{V}_k := \text{span}\{ x_1, \dots, x_k \}$

In tal caso per ogni $x \in \hat{V}_k$ , $x = \sum_{i=1}^k \alpha_i x_i$ per cui:

 $\frac{x^T A x}{x^T x} = \frac{\sum_{i=1}^k \lambda_i \alpha_i^2 x_i^T x_i}{\sum_{i=1}^k \alpha_i^2 x_i^T x_i} \ge \lambda_k \frac{\sum \alpha_i^2}{\sum \alpha_i^2} = \lambda_k$

Quindi il minimo su $\hat{V}_k$ è proprio $\lambda_k$ . $\square$

§ Corollario (Teorema di separazione di Cauchy). Sia $A$ una matrice reale simmetrica $n \times n$ con autovalori $\alpha_1 \ge \dots \ge \alpha_n$ . Sia $U \in \mathbb{R}^{n \times (n-1)}$ tale che $U^T U = I_{n-1}$ , allora gli autovalori di $B = U^T A U$ sono $\beta_1 \ge \dots \ge \beta_{n-1}$ e vale:

 $\alpha_1 \ge \beta_1 \ge \alpha_2 \ge \dots \ge \beta_{n-1} \ge \alpha_n$

Si dice che gli autovalori di $B$ separano quelli di $A$ .

Dimostrazione. Sia $W_k$ un sottospazio di $\mathbb{R}^{n-1}$ di dimensione $k$ . Vale

 $\beta_k = \max_{\dim W_k = k} \min_{y \in W_k \setminus \{0\}} \frac{y^T B y}{y^T y}$

Sia $\hat{W}_k$ il sottospazio su cui si ottiene il massimo. Allora:

 $\min_{y \in \hat{W}_k \setminus \{0\}} \frac{y^T B y}{y^T y} = \min_{y \in \hat{W}_k \setminus \{0\}} \frac{y^T U^T A U y}{y^T U^T U y}$

Poniamo ora $\hat{V}_k := \{ x \in \mathbb{R}^n \mid x = U y, y \in \hat{W}_k \}$ . Poiché $U$ ha rango pieno, $\dim \hat{V}_k = k$ . Inoltre

 $\frac{y^T U^T A U y}{y^T y} = \frac{x^T A x}{x^T x}$

per cui

 $\beta_k = \min_{y \in \hat{W}_k \setminus \{0\}} \frac{y^T U^T A U y}{y^T y} = \min_{x \in \hat{V}_k \setminus \{0\}} \frac{x^T A x}{x^T x} \le \max_{V_k \in \mathbb{R}^n} \min_{x \in V_k \setminus \{0\}} \frac{x^T A x}{x^T x} = \alpha_k$

Dunque $\alpha_k \ge \beta_k$ . Per ottenere $\beta_k \ge \alpha_{k-1}$ si applica lo stesso ragionamento a $-B$ e $-A$ . $\square$

§ Corollario. Sia $A$ una matrice tridiagonale simmetrica $n \times n$ . Allora gli autovalori di una qualsiasi sottomatrice principale di $A \in \mathbb{R}^{(n-1) \times (n-1)}$ separano gli autovalori di $A$ .

§ Teorema. Gli zeri del polinomio ortogonale $p_n(x)$ separano strettamente gli zeri di $p_{n+1}(x)$ per ogni $n \ge 1$ .

Dimostrazione. Segue dal corollario precedente e osservando che se $p_n$ e $p_{n+1}$ avessero uno zero in comune allora induttivamente, usando la ricorrenza a 3 termini, si avrebbe che tale zero sarebbe zero anche di $p_0(x)$ , il che è assurdo poiché $p_0(x)$ è una costante non nulla. $\square$