Appendice C — Confronto fra splitting e velocità di convergenza

Autore/Autrice

Affiliazione

Enrico Bertolazzi

University of Trento, Department of Industrial Engineering

Questo capitolo studia le proprietà degli splitting di una matrice e, a partire da esse, confronta la velocità di convergenza dei metodi iterativi che ne derivano. Il punto di partenza è un risultato sugli autovalori del prodotto di due matrici, valido anche quando le matrici sono singolari.

C.1 Autovalori del prodotto

Lemma C.1 Siano \bm{A} e \bm{B} due matrici quadrate, allora \bm{A}\bm{B} e \bm{B}\bm{A} hanno gli stessi autovalori ed in particolare

\varrho(\bm{A}\bm{B})=\varrho(\bm{B}\bm{A})

Dimostrazione. sia \bm{A} non singolare e \lambda autovalore del prodotto \bm{A}\bm{B} allora

0=\det{\lambda\bm{I}-\bm{A}\bm{B}} =\det{\bm{A}}\det{\lambda\bm{A}^{-1}-\bm{B}} = \det{\lambda\bm{A}^{-1}-\bm{B}}\det{\bm{A}} = \det{\lambda\bm{I}-\bm{B}\bm{A}}

quindi \lambda è autovalore del prodotto \bm{B}\bm{A} e di conseguenza anche i raggi spettrali coincidono. Sia \bm{A} singolare allora per \mu\neq 0 sufficientemente piccolo la matrice \bm{A}_\mu=\mu\bm{I}+\bm{A} è non singolare quindi

\varrho(\bm{A}_\mu\bm{B})=\varrho(\bm{B}\bm{A}_\mu)

e per continuità segue la tesi.

C.2 Splitting convergente

Definizione C.1 La decomposizione \bm{A}=\bm{P}-\bm{Q} è detta splitting convergente se \bm{P} è non singolare e \varrho(\bm{P}^{-1}\bm{Q})<1.

Questa definizione di splitting richiede di conoscere il raggio spettrale della matrice \varrho(\bm{P}^{-1}\bm{Q}). Vogliamo quindi individuare condizioni sufficienti che garantiscano la convergenza dello splitting associato a una matrice. Introduciamo a questo scopo le definizioni seguenti.

C.3 Splitting vari

Definizione C.2 La decomposizione \bm{A}=\bm{P}-\bm{Q} è detta \

• splitting regolare
  se:
  1. \bm{P} è monotona cioè \bm{P}^{-1}\geq 0
  2. \bm{Q}\geq 0.
• splitting non negativo
  se:
  1. \bm{P} è monotona
  2. \bm{P}^{-1}\bm{Q}\geq 0 e \bm{Q}\bm{P}^{-1}\geq 0.
• splitting debolmente non negativo
  se:
  1. \bm{P} è monotona
  2. \bm{P}^{-1}\bm{Q}\geq 0 oppure \bm{Q}\bm{P}^{-1}\geq 0.
• splitting debole
  se:
  2. \bm{P} è non singolare
  3. \bm{P}^{-1}\bm{Q}\geq 0 oppure \bm{Q}\bm{P}^{-1}\geq 0.

Osserviamo che valgono le seguenti implicazioni \begin{array}{c} \text{splitting regolare} \\\\ \Downarrow \\\\ \text{splitting non negativo} \\\\ \Downarrow \\\\ \text{splitting debolmente non negativo} \\\\ \Downarrow \\\\ \text{splitting debole } \end{array} ## Applicazione del teorema di Perron-Frobenius agli splitting

Studiamo ora le proprietà degli splitting mediante la teoria di Perron-Frobenius. Il teorema di Perron-Frobenius permette di confrontare i raggi spettrali di matrici \bm{A} e \bm{B} nel caso \bm{A}\geq\left\lvert\bm{B}\right\rvert\geq 0. Confronti di questo tipo sono molto utili nello studio dei metodi iterativi che derivano da splitting. Infatti in questo modo si riesce a confrontare il raggio spettrale della matrice di iterazione e quindi la convergenza dei metodi.

C.4 Confronto raggio spettrale

Lemma C.2 Siano \bm{A} e \bm{B} due matrici con \bm{A}\geq\left\lvert\bm{B}\right\rvert\geq 0 allora \varrho(\bm{A})\geq \varrho(\bm{B})

la disuguaglianza è stretta se la matrice \bm{B} è irriducibile.

Dimostrazione. osserviamo che dai teoremi di Perron-Frobenius segue immediatamente che

\begin{aligned} \varrho(\bm{A})\geq\varrho(\left\lvert\bm{B}\right\rvert) & \qquad\text{se $\bm{B}$ è riducibile} \\ \varrho(\bm{A})>\varrho(\left\lvert\bm{B}\right\rvert) & \qquad\text{se $\bm{B}$ è irriducibile} \end{aligned}

quindi basta dimostrare che \varrho(\left\lvert\bm{B}\right\rvert)\geq\varrho(\bm{B}). Per fare questo basta osservare che

\left|\left|\bm{B}^k\right|\right|_2=\left|\left|\left\lvert\bm{B}^k\right\rvert\right|\right|_2\leq\left|\left|\left\lvert\bm{B}\right\rvert^k\right|\right|_2 \quad\implies\quad \left|\left|\bm{B}^k\right|\right|_2^{\tfrac{1}{k}}\leq\left|\left|\left\lvert\bm{B}\right\rvert^k\right|\right|_2^{\tfrac{1}{k}} \quad\implies\quad \varrho(\bm{B})\leq\varrho(\left\lvert\bm{B}\right\rvert)

per la formula di Gelfand¹, Corollario 25.1.

Diamo ora un lemma che sarà utile nello studio dei metodi iterativi

C.5 Splitting e inversa

Lemma C.3 Sia \bm{A}=\bm{P}-\bm{Q} uno splitting di \bm{A}. Se \bm{A} ed \bm{P} sono non singolari allora \bm{P}^{-1}\bm{Q}\bm{A}^{-1}=\bm{A}^{-1}\bm{Q}\bm{P}^{-1}

e di conseguenza la matrice \bm{P}^{-1}\bm{Q} commuta con la matrice \bm{A}^{-1}\bm{Q} e la matrice \bm{Q}\bm{P}^{-1} commuta con la matrice \bm{Q}\bm{A}^{-1}.

Dimostrazione. basta osservare che

\begin{aligned} \bm{P}^{-1}=(\bm{A}+\bm{Q})^{-1} &=\bm{A}^{-1}(\bm{I}+\bm{Q}\bm{A}^{-1})^{-1}\\ &=(\bm{I}+\bm{A}^{-1}\bm{Q})^{-1}\bm{A}^{-1} \end{aligned}

da cui si ha

\begin{array}{ll} \bm{A}^{-1}&=\bm{P}^{-1}+\bm{P}^{-1}\bm{Q}\bm{A}^{-1}\\ \bm{A}^{-1}&=\bm{P}^{-1}+\bm{A}^{-1}\bm{Q}\bm{P}^{-1} \end{array} \quad\implies\quad \bm{P}^{-1}\bm{Q}\bm{A}^{-1}=\bm{A}^{-1}\bm{Q}\bm{P}^{-1}

e moltiplicando a desta e a sinistra per \bm{Q}

\begin{array}{ll} \bm{Q}\bm{P}^{-1}\bm{Q}\bm{A}^{-1}&=\bm{Q}\bm{A}^{-1}\bm{Q}\bm{P}^{-1}\\ \bm{P}^{-1}\bm{Q}\bm{A}^{-1}\bm{Q}&=\bm{A}^{-1}\bm{Q}\bm{P}^{-1}\bm{Q} \end{array} \quad\implies\quad \begin{array}{ll} (\bm{Q}\bm{P}^{-1})(\bm{Q}\bm{A}^{-1})&=(\bm{Q}\bm{A}^{-1})(\bm{Q}\bm{P}^{-1})\\ (\bm{P}^{-1}\bm{Q})(\bm{A}^{-1}\bm{Q})&=(\bm{A}^{-1}\bm{Q})(\bm{P}^{-1}\bm{Q}) \end{array}

otteniamo la tesi.

C.6 Monotonia e splitting debole

Teorema C.1 Sia \bm{Q}=\bm{P}-\bm{Q} uno splitting debole. Se \bm{A} è monotona allora

\bm{A}^{-1}\geq\bm{P}^{-1} \tag{C.1}

Dimostrazione. utilizzando il lemma Lemma B.2 Se \bm{P}^{-1}\bm{Q}\geq 0 allora vale

\bm{A}^{-1}=\bm{P}^{-1}+\bm{P}^{-1}\bm{Q}\bm{A}^{-1}\geq \bm{P}^{-1}

Se \bm{Q}\bm{P}^{-1}\geq 0 allora vale

\bm{A}^{-1}=\bm{P}^{-1}+\bm{A}^{-1}\bm{Q}\bm{P}^{-1}\geq \bm{P}^{-1}

in ogni caso la C.1 è soddisfatta.

Proprietà splitting debole

Teorema C.2 Sia \bm{A}=\bm{P}-\bm{Q} uno splitting debolmente non negativo. Se \bm{A} è monotona allora

1. \bm{A}^{-1}\geq\bm{P}^{-1}

2. \varrho(\bm{P}^{-1}\bm{Q})=\varrho(\bm{Q}\bm{P}^{-1})<1

3. \bm{P}^{-1}\bm{Q}\geq 0\quad\implies\quad\bm{A}^{-1}\bm{Q}\geq\bm{P}^{-1}\bm{Q} ed \bm{Q}\bm{P}^{-1}\geq 0\quad\implies\quad\bm{Q}\bm{A}^{-1}\geq\bm{Q}\bm{P}^{-1}

4. \varrho(\bm{P}^{-1}\bm{Q})=\dfrac{\varrho(\bm{A}^{-1}\bm{Q})}{1+\varrho(\bm{A}^{-1}\bm{Q})}

5. viceversa se \varrho(\bm{P}^{-1}\bm{Q})=\varrho(\bm{Q}\bm{P}^{-1})<1 allora \bm{A}^{-1}\geq 0.

Dimostrazione. 1 segue dal teorema Teorema C.1.

2 Assumiamo che \bm{P}^{-1}\bm{Q}\geq 0.

Possiamo scrivere allora

\begin{aligned} \bm{A}^{-1} &=\bm{P}^{-1}+\bm{P}^{-1}\bm{Q}\bm{A}^{-1}\\ &=\bm{P}^{-1}+\bm{P}^{-1}\bm{Q}(\bm{P}^{-1}+\bm{P}^{-1}\bm{Q}\bm{A}^{-1})\\ &=\bm{P}^{-1}+\bm{P}^{-1}\bm{Q}\bm{P}^{-1}+\bm{P}^{-1}\bm{Q}\bm{P}^{-1}\bm{Q}\bm{A}^{-1})\\ &=\bm{P}^{-1}+\bm{P}^{-1}\bm{Q}\bm{P}^{-1}+(\bm{P}^{-1}\bm{Q})^2(\bm{P}^{-1}+\bm{P}^{-1}\bm{Q}\bm{A}^{-1})\\ &=\bm{P}^{-1}+\bm{P}^{-1}\bm{Q}\bm{P}^{-1}+(\bm{P}^{-1}\bm{Q})^2\bm{P}^{-1}+(\bm{P}^{-1}\bm{Q})^3\bm{A}^{-1}\\ &\vdots\\ &=(\bm{I}+\bm{P}^{-1}\bm{Q}+\cdots+(\bm{P}^{-1}\bm{Q})^{k})\bm{P}^{-1}+ (\bm{P}^{-1}\bm{Q})^{k+1}\bm{A}^{-1} \end{aligned}

e di conseguenza la serie

(\bm{I}+\bm{P}^{-1}\bm{Q}+\cdots+(\bm{P}^{-1}\bm{Q})^k)\bm{P}^{-1} =\bm{A}^{-1}-(\bm{P}^{-1}\bm{Q})^{k+1}\bm{A}^{-1}\leq\bm{A}^{-1}

è monotona crescente e limitata, quindi convergente. Per il lemma Lemma 25.1 si ha \varrho(\bm{P}^{-1}\bm{Q})<1.\ 3 Dal lemma Lemma 25.1 per la convergenza della serie

\bm{I}+\bm{P}^{-1}\bm{Q}+\cdots+(\bm{P}^{-1}\bm{Q})^k+\cdots= (\bm{I}-\bm{P}^{-1}\bm{Q})^{-1}\geq \bm{I}

Analogamente

\bm{I}+\bm{Q}\bm{P}^{-1}+\cdots+(\bm{Q}\bm{P}^{-1})^k+\cdots= (\bm{I}-\bm{Q}\bm{P}^{-1})^{-1}\geq \bm{I}

e quindi se \bm{P}^{-1}\bm{Q}\geq 0

\bm{A}^{-1}\bm{Q}=(\bm{P}-QQ)^{-1}\bm{Q}=(\bm{I}-\bm{P}^{-1}\bm{Q})^{-1}\bm{P}^{-1}\bm{Q} \geq\bm{P}^{-1}\bm{Q}.

Del resto, se \bm{Q}\bm{P}^{-1}\geq 0

\bm{Q}\bm{A}^{-1}=\bm{Q}(\bm{P}-\bm{Q})^{-1}=\bm{Q}\bm{P}^{-1}(\bm{I}-\bm{Q}\bm{P}^{-1})^{-1} \geq\bm{Q}\bm{P}^{-1}

4 Osserviamo che

\bm{A}^{-1}\bm{Q}=(\bm{P}-QQ)^{-1}\bm{Q}=(\bm{I}-\bm{P}^{-1}\bm{Q})^{-1}\bm{P}^{-1}\bm{Q} =\sum_{i=1}^\infty (\bm{P}^{-1}\bm{Q})^i

Osserviamo inoltre che \varrho\left(\sum_{i=1}^\infty(\bm{P}^{-1}\bm{Q})^i\right) \leq\sum_{i=1}^\infty(\bm{P}^{-1}\bm{Q})^i =\dfrac{\varrho(\bm{P}^{-1}\bm{Q})}{1-\varrho(\bm{P}^{-1}\bm{Q})}

Poiché \bm{P}^{-1}\bm{Q}\geq 0 per il teorema di Perron-Frobenius esiste un autovalore \lambda=\varrho(\bm{P}^{-1}\bm{Q})^i)<1 e quindi

\Gamma=\sum_{i=1}^\infty\varrho(\bm{P}^{-1}\bm{Q})^i= \dfrac{\varrho(\bm{P}^{-1}\bm{Q})}{1-\varrho(\bm{P}^{-1}\bm{Q})}

è un autovalore di \sum_{i=1}^\infty(\bm{P}^{-1}\bm{Q})^i per cui

\varrho\left(\sum_{i=1}^\infty(\bm{P}^{-1}\bm{Q})^i\right) \geq\dfrac{\varrho(\bm{P}^{-1}\bm{Q})}{1-\varrho(\bm{P}^{-1}\bm{Q})}

il che implica

\varrho(\bm{A}^{-1}\bm{Q})= \dfrac{\varrho(\bm{P}^{-1}\bm{Q})}{1-\varrho(\bm{P}^{-1}\bm{Q})}

5 sia ora \varrho(\bm{P}^{-1}\bm{Q})=\varrho(\bm{Q}\bm{P}^{-1})<1. Allora la serie positiva

\bm{I}+\bm{P}^{-1}\bm{Q}+\cdots+(\bm{P}^{-1}\bm{Q})^k+\cdots= (\bm{I}-\bm{P}^{-1}\bm{Q})^{-1}\geq \bm{I}

è convergente e quindi

\bm{A}^{-1}=(\bm{I}-\bm{P}^{-1}\bm{Q})^{-1}\bm{P}^{-1}\geq 0

Questo teorema in sostanza stabilisce che, se \bm{A} è una matrice monotona, allora uno splitting debolmente non negativo è convergente. Viceversa, se la matrice \bm{A} ha uno splitting debolmente non negativo che converge, allora è monotona.

C.7 Splitting debolemente non negativi

Teorema C.3 Siano \bm{A}=\bm{P}_1-\bm{Q}_1=\bm{P}_2-\bm{Q}_2 due splitting debolmente non negativi di una matrice monotona \bm{A}. Se vale una delle seguenti disuguaglianze

\begin{aligned} \bm{A}^{-1}\bm{Q}_2\geq\bm{A}^{-1}\bm{Q}_1\geq 0, & \bm{A}^{-1}\bm{Q}_2\geq\bm{Q}_1\bm{A}^{-1}\geq 0 \\ \bm{Q}_2\bm{A}^{-1}\geq\bm{Q}_1\bm{A}^{-1}\geq 0, & \bm{Q}_2\bm{A}^{-1}\geq\bm{A}^{-1}\bm{Q}_1\geq 0 \end{aligned}

allora

\varrho(\bm{P}_1^{-1}\bm{Q}_1)\leq\varrho(\bm{Q}_2\bm{P}_2^{-1})<1

Dimostrazione. dimostriamolo ad esempio per la prima disuguaglianza. Per il teorema di Perron-Frobenius

\bm{A}^{-1}\bm{Q}_2\geq\bm{A}^{-1}\bm{Q}_1\geq 0 \quad\implies\quad \varrho(\bm{A}^{-1}\bm{Q}_2)\geq\varrho(\bm{A}^{-1}\bm{Q}_1)

e per il teorema Teorema C.2 punto 5 segue

\varrho(\bm{P}_1^{-1}\bm{Q}_1)= \dfrac{\varrho(\bm{A}^{-1}\bm{Q}_1)}{1+\varrho(\bm{A}^{-1}\bm{Q}_1)}\leq \dfrac{\varrho(\bm{A}^{-1}\bm{Q}_2)}{1+\varrho(\bm{A}^{-1}\bm{Q}_2)} =\varrho(\bm{P}_2^{-1}\bm{Q}_2)

in modo analogo si dimostrano le altre disuguaglianze.

Nel teorema Teorema C.3 il confronto dei raggi spettrali delle matrici di iterazione non è molto agevole perché ci sono di mezzo dei prodotti di matrici. Saranno quindi utili dei teoremi che confrontano direttamente le matrici \bm{P} e \bm{Q}.

C.8 Raggio spettrale e splitting debolmente non negativi

Teorema C.4 Siano \bm{A}=\bm{P}_1-\bm{Q}_1=\bm{P}_2-\bm{Q}_2 due splitting debolmente non negativi. Allora se \bm{A}^{-1}\geq 0, \bm{Q}_2\geq\bm{Q}_1 segue

\varrho(\bm{P}_1^{-1}\bm{Q}_1)\leq\varrho(\bm{P}_2^{-1}\bm{Q}_2)<1

C.9 Splitting non negativi e convergenza

Teorema C.5 Siano \bm{A}=\bm{P}_1 -\bm{Q}_1 =\bm{P}_2 -\bm{Q}_2 due splitting non negativi del tipo \bm{P}_1^{-1}\bm{Q}_1 , \bm{P}_2^{-1}\bm{Q}_2 \geq 0 con \bm{P}_1^{-1}\geq \bm{P}_2^{-1}. Se \bm{A}^{-1}>0 oppure \bm{A}^{-1}\geq 0 con \bm{P}_1^{-1}\bm{Q}_1 e \bm{P}_2^{-1}\bm{Q}_2 irriducibili allora

\sigma(\bm{P}_1^{-1}\bm{Q}_1 ) \leq \sigma(\bm{P}_2^{-1}\bm{Q}_2 )<1

se inoltre \bm{P}_1^{-1} > \bm{P}_2^{-1}

\sigma(\bm{P}_1^{-1}\bm{Q}_1 ) < \sigma(\bm{P}_2^{-1}\bm{Q}_2 )<1

Dimostrazione. Basta osservare che

\bm{A}^{-1} = \bm{P}_1^{-1} + \bm{P}_1^{-1} \bm{Q}_1 \bm{A}^{-1} = \bm{P}_2^{-1}+\bm{A}^{-1}\bm{Q}_2 \bm{P}_2^{-1}

e quindi

\bm{P}_1^{-1}\bm{Q}_1 \bm{A}^{-1} -\bm{A}^{-1}\bm{Q}_2 \bm{P}_2^{-1} = \bm{P}_2^{-1}-\bm{P}_1^{-1} \leq 0

Siano \bm{x}_1 , \bm{x}_2 \geq 0 i vettori di Frobenius² delle matrici \bm{P}_1^{-1}\bm{Q}_1, \bm{Q}_2 \bm{P}_2^{-1} rispettivamente sinistro e destro allora

\bm{x}_1^T \bm{P}_1^{-1}\bm{Q}_1 \bm{A}^{-1}\bm{x}_2 \leq \bm{x}_1^T\bm{A}^{-1}\bm{Q}_2 \bm{P}![2,-1]\bm{x}_2 \quad\implies \\ \sigma(\bm{P}![1,-1]\bm{Q}_1 )\bm{x}_1^T\bm{A}^{-1}\bm{x}_2 \leq \sigma(\bm{Q}_2 \bm{P}_2^{-1})\bm{x}_1^T\bm{A}^{-1}\bm{x}_2

Pertanto se \bm{A}^{-1}>0 segue che \bm{x}_1^T\bm{A}^{-1}\bm{x}_2 >0. Se \bm{A}^{-1} \geq 0 con \bm{P}_1^{-1}\bm{Q}_1 e \bm{Q}_2 \bm{P}_2^{-1} irriducibili si ha \bm{x}_1 , \bm{x}_2 >0 e quindi \bm{x}_1^T\bm{A}^{-1}\bm{x}_2 >0. Osserviamo che se la disuguaglianza è soddisfatta in senso stretto allora varrà anche sui raggi spettrali.

C.10 Confronto della velocità di convergenza fra alcuni metodi iterativi

Applichiamo ora i teoremi fin qui dimostrati allo studio della convergenza dei metodi iterativi. Dato il seguente sistema lineare

\bm{A}\bm{x}=\bm{b}

decomponiamo \bm{A} come \bm{A}=\bm{D}-\bm{L}-\bm{U}, dove \bm{D} è una matrice diagonale non singolare, \bm{L} è triangolare inferiormente ed \bm{U} è triangolare superiormente. Introduciamo altre due matrici: \mathcal{L} triangolare inferiormente e \mathcal{U} triangolare superiormente. Allora possiamo definire la fattorizzazione \bm{A}=\bm{P}-\bm{Q} dove:

\bm{P}=\left[ \bm{I}-(\bm{L}+\mathcal{L})\bm{K}^{-1} \right] \bm{K} \left[ \bm{I}-\bm{K}^{-1} (\bm{U}+\mathcal{U}) \right]

con \bm{K} una matrice diagonale non singolare definita in maniera implicita dalla seguente relazione \bm{K} = \bm{D} - \textrm{diag}\left\{(\bm{L}+\mathcal{L})\bm{K}^{-1}(\bm{U}+\mathcal{U})\right\} \tag{C.2} dove con diag(\bm{A}) si indica la matrice diagonale ottenuta ponendo a zero gli elementi non diagonali di \bm{A}. La C.2 può essere riscritta come

\begin{aligned} \bm{P} & = [\bm{I}-(\bm{L}+\mathcal{L})\bm{K}^{1}]\bm{K}[\bm{I}-\bm{K}^{-1}(\bm{U}+\mathcal{U})]\\ &= \bm{K}-(\bm{L}+\mathcal{L})-(\bm{U}+\mathcal{U})+(\bm{L}+\mathcal{L})\bm{K}^{-1}(\bm{U}+\mathcal{U})\\ &=\bm{D}-\bm{L}-\bm{U}+\bm{K}-\bm{D}-\mathcal{L}-\mathcal{U}+(\bm{L}+\mathcal{L})\bm{K}^{-1}(\bm{U}+\mathcal{U})\\ &=\bm{A}-\mathcal{L}-\mathcal{U}-\textrm{diag}\left\{ (\bm{L}+\mathcal{L})\bm{K}^{-1}\bm{U}+\mathcal{U})\right\}+(\bm{L}+\mathcal{L})\bm{K}^{-1}(\bm{U}+\mathcal{U})\\ &= \bm{A}-\mathcal{L}-\mathcal{U}+\textrm{offdiag}\left\{ (\bm{L}+\mathcal{L})\bm{K}^{-1}(\bm{U}+\mathcal{U})\right\} \end{aligned} \tag{C.3}

dove \textrm{offdiag}\left\{\bm{A}\right\}=\bm{A}-\textrm{diag}\left\{\bm{A}\right\}. Dalla C.3 segue

\bm{Q}=\textrm{offdiag}\left\{(\bm{L}+\mathcal{L})\bm{K}^{-1}(\bm{U}+\mathcal{U})\right\}-\mathcal{L}-\mathcal{U} \tag{C.4}

Con queste matrici il metodo iterativo diventa

\bm{x}_{n+1} = [\bm{I}-\bm{K}^{-1}(\bm{U}+\mathcal{U})]^{-1}\bm{K}^{-1} [\bm{I}-(\bm{L}+\mathcal{L})\bm{K}^{-1}](\bm{Q}\bm{x}![n]+\bm{b}) \tag{C.5}

che può essere decomposta nei due passi

\begin{aligned} \bm{x}![n+{1/2}] &= \bm{K}^{-1} \left[\bm{I} -(\bm{L}+\mathcal{L})\bm{K}^{-1}\right] (\bm{Q}\bm{x}![n]+\bm{b}) \\ \bm{x}![n+1] &= \left[\bm{I}-\bm{K}^{-1}(\bm{U}+\mathcal{U})\right]^{-1} \bm{x}![n+{1/2}] \end{aligned} \tag{C.6}

che sono facili da realizzare, poiché le matrici da invertire sono triangolari. Questo metodo, detto AGA, conduce, in base alla scelta delle matrici, alla costruzione di metodi iterativi classici, come i metodi di Jacobi³, Gauss⁴-Seidel⁵ ed EWA (si veda [1]).

Tabella C.1: Confronto metodi iterativi

	Jacobi	Gauss-Seidel	EWA
\bm{K}	\bm{D}	\bm{D}	\bm{D}_{\bm{B}} - \textrm{diag}\left\{\bm{L}\bm{D}_{\bm{B}}^{-1}\bm{U}\right\}
\bm{L}	-\bm{L}	-\bm{L}	\bm{0}
\bm{U}	-\bm{U}	\bm{0}	\bm{0}
\bm{P}	\bm{D}	\bm{D}-\bm{L}	(\bm{I}-\bm{L}\bm{K}_{\bm{B}}^{-1})\bm{K}_{\bm{B}}(\bm{I}-\bm{K}_{\bm{B}}^{-1}\bm{U})
\bm{Q}	\bm{L}+\bm{U}	\bm{L}	\textrm{offdiag}\left\{\bm{L}\bm{D}_{\bm{B}}^{-1}\bm{U}\right\}
\bm{P}^{-1}	\bm{D}^{-1}	(\bm{D}-\bm{L})^{-1}	(\bm{I}-\bm{K}_{\bm{B}}^{-1}\bm{U})^{-1}\bm{K}_{\bm{B}}^{-1}(\bm{I}-\bm{L}\bm{K}_{\bm{B}}^{-1})^{-1}
\bm{P}^{-1}\bm{Q}	\bm{D}^{-1}(\bm{L}+\bm{U})	(\bm{D}-\bm{L})^{-1}\bm{U}	(\bm{I}-\bm{K}_{\bm{B}}^{-1}\bm{U})^{-1}\bm{K}_{\bm{B}}^{-1}(\bm{I}-\bm{L}\bm{K}_{\bm{B}}^{-1})^{-1} \textrm{offdiag}\left\{\bm{L}\bm{D}_{\bm{B}}^{-1}\bm{U}\right\}

Specializzazione nel caso a due colori

Sia \bm{A} una matrice a due colori, cioè della forma

\bm{A} = \left(\begin{array}{c|c} \bm{D}_1 & -\bm{U} \\\hline -\bm{L} & \bm{D}_2 \end{array}\right) \tag{C.7}

dove \bm{D}_1 e \bm{D}_2 sono matrici diagonali. La relazione C.3 diventa

\begin{aligned} \left(\begin{array}{c|c} \bm{K}_1 & \bm{0} \\\hline \bm{0} & \bm{K}_2 \end{array}\right) &= \left(\begin{array}{c|c} \bm{D}_1 & \bm{0} \\\hline \bm{0} & \bm{D}_2 \end{array}\right) - \textrm{diag}\left\{ \left(\begin{array}{c|c} \bm{0} & \bm{0} \\\hline \bm{L}+\mathcal{L} & \bm{0} \end{array}\right) \times \left(\begin{array}{c|c} \bm{K}_1^{-1} & \bm{0} \\\hline \bm{0} & \bm{K}_2^{-1} \end{array}\right) \times \left(\begin{array}{c|c} \bm{0} & \bm{U}+\mathcal{U} \\\hline \bm{0} & \bm{0} \end{array}\right) \right\} \\ &= \left(\begin{array}{c|c} \bm{D}_1 & \bm{0} \\\hline \bm{0} & \bm{D}_2 \end{array}\right) - \textrm{diag}\left\{ \left(\begin{array}{c|c} \bm{0} & \bm{0} \\\hline \bm{0} & (\bm{L}+\mathcal{L}\bm{K}_1^{-1}(\bm{U}+\mathcal{U}) \end{array}\right)\right\} \\ &= \left(\begin{array}{c|c} \bm{D}_1 & \bm{0} \\\hline \bm{0} & \bm{D}_2 -\textrm{diag}\left\{(\bm{L}+\mathcal{L})\bm{K}_1^{-1}(\bm{U}+\mathcal{U})\right\} \end{array}\right) \end{aligned} \tag{C.8}

quindi la matrice diagonale \bm{K} è facilmente calcolabile, inoltre la C.2 diventa

\begin{aligned} \bm{P} &=\left(\begin{array}{c|c} \bm{I}_1 & \bm{0} \\\hline -(\bm{L}+\mathcal{L})\bm{D}_1^{-1} & \bm{I}_2 \end{array}\right)\times \left(\begin{array}{c|c} \bm{D}_1 & \bm{0} \\\hline \bm{0} & \bm{K}_2 \end{array}\right)\times \left(\begin{array}{c|c} \bm{I}_1 & -\bm{D}_1^{-1}(\bm{U}+\mathcal{U}) \\\hline \bm{0} & \bm{I}_2 \end{array}\right) \\ &= \left(\begin{array}{c|c} \bm{D}_1 & -(\bm{U}+\mathcal{U}) \\\hline -(\bm{L}+\mathcal{L}) & \bm{D}_2 -\textrm{diag}\left\{(\bm{L}+\mathcal{L})\bm{D}_1^{-1}(\bm{U}+\mathcal{U})\right\}+ (\bm{L}+\mathcal{L})\bm{D}_1^{-1}(\bm{U}+\mathcal{U}) \end{array}\right) \\ &= \left(\begin{array}{c|c} \bm{D}_1 & -(\bm{U}+\mathcal{U}) \\\hline -(\bm{L}+\mathcal{L}) & \bm{D}_2 +\textrm{offdiag}\left\{(\bm{L}+\mathcal{L})\bm{D}_1^{-1}(\bm{U}+\mathcal{U})\right\} \end{array}\right) \end{aligned} \tag{C.9}

per cui

\bm{Q}= \left(\begin{array}{c|c} \bm{0} & -\bm{U} \\\hline -\bm{L} & \textrm{offdiag}\left\{(\bm{L}+\mathcal{L})\bm{D}_1^{-1}(\bm{U}+\mathcal{U})\right\} \end{array}\right) \tag{C.10}

se \bm{K} è non singolare allora possiamo calcolare \bm{P}^{-1} come segue

\bm{P}^{-1} = \left(\begin{array}{c|c} \bm{I}_1 & \bm{D}_1^{-1}(\bm{U}+\mathcal{U}) \\\hline \bm{0} & \bm{I}[2] \end{array}\right)\times \left(\begin{array}{c|c} \bm{D}_1^{-1} & \bm{0} \\\hline \bm{0} & \left(\bm{D}_2 -\textrm{diag}\left\{(\bm{L}+\mathcal{L})\bm{D}_1^{-1}(\bm{U}+\mathcal{U})\right\}\right)^{-1} \end{array}\right)\times \left(\begin{array}{c|c} \bm{I}_1 & \bm{0} \\\hline (\bm{L}+\mathcal{L})\bm{D}_1^{-1} & \bm{I}_2 \end{array}\right)

osserviamo che dalla condizione \bm{Q}\geq \bm{0} segue che devono essere \bm{L}, \bm{U}\leq \bm{0}. Ci chiediamo ora sotto quali condizioni la matrice diagonale \bm{K} è non singolare.

M-matrice e elementi diagonali

Teorema C.6 Sia \bm{A}=\left(\begin{array}{c|c} \bm{D}_1 & -\bm{U} \\\hline -\bm{L} & \bm{D}_2 \end{array}\right) \tag{C.11}

una M-matrice a due colori, allora se -\bm{L}\leq \mathcal{L}\leq \bm{0}, -\bm{U}\leq \mathcal{U}\leq \bm{0}, segue che la matrice

\bm{K}_2 = \bm{D}_2 - \textrm{diag}\left\{(\bm{L}+\mathcal{L})\bm{D}_1^{-1}(\bm{U}+\mathcal{U})\right\} \tag{C.12}

è non singolare con elementi diagonali strettamente positivi.

Dimostrazione. Osserviamo che la matrice

\begin{aligned} \bm{B} &= \left(\begin{array}{c|c} \bm{D}_1 & \bm{0} \\\hline \bm{0} & \bm{D}_2 -(\bm{L}+\mathcal{L})\bm{D}_1^{-1}(\bm{U}+\mathcal{U}) \end{array}\right) \\ &= \left(\begin{array}{c|c} \bm{I}_1 & \bm{0} \\\hline (\bm{L}+\mathcal{L})\bm{D}_1^{-1} & \bm{I}_2 \end{array}\right) \left(\begin{array}{c|c} \bm{D}_1 & -(\bm{U}+\mathcal{U}) \\\hline -(\bm{L}+\mathcal{L}) & \bm{D}_2 \end{array}\right) \left(\begin{array}{c|c} \bm{I}_1 & \bm{D}_1^{-1}(\bm{U}+\mathcal{U}) \\\hline \bm{0} & \bm{I}_2 \end{array}\right) \end{aligned} \tag{C.13}

contiene la matrice \bm{K}_2 = \bm{D}_2 - \textrm{diag}\left\{(\bm{L}+\mathcal{L})\bm{D}_1^{-1}(\bm{U}+\mathcal{U})\right\}. Se proviamo che la parte diagonale della matrice \bm{B} strettamente positiva abbiamo dimostrato il teorema. Poiché \bm{A} è una M-matrice, dal lemma Lemma 25.3 segue che

\bm{A} = \rho \bm{I} - \bm{B} \tag{C.14}

dove

\rho = \left|\left|\textrm{diag}\left\{\bm{A}\right\}\right|\right|_\infty,\qquad \bm{B} = \rho \bm{I} - \left(\begin{array}{c|c} \bm{D}_1 & -\bm{U} \\\hline -\bm{L} & \bm{D}_2 \end{array}\right) = \left(\begin{array}{c|c} \rho\bm{I}_1 -\bm{D}_1 & \bm{U} \\\hline \bm{L} & \rho\bm{I}_2 -\bm{D}_2 \end{array}\right)\geq \bm{0} \tag{C.15}

ed ancora \rho>\varrho(\bm{B}). Definendo

\bm{C}=\left(\begin{array}{c|c} \bm{D}_1 & -\bm{U}-\mathcal{U} \\\hline -\bm{L}-\mathcal{L} & \bm{D}_2 \end{array}\right) \tag{C.16}

osserviamo che la matrice \bm{C} si può scrivere come

\begin{aligned} \bm{C} &= \left(\begin{array}{c|c} \bm{D}_1 & -\bm{U}-\mathcal{U} \\\hline -\bm{L}-\mathcal{L} & \bm{D}_2 \end{array}\right)\\ &= \rho\bm{I} -\left\{ \rho\bm{I} - \left(\begin{array}{c|c} \bm{D}_1 & -\bm{U}-\mathcal{U} \\\hline -\bm{L}-\mathcal{L} & \bm{D}_2 \end{array}\right) \right\} \\ &= \rho\bm{I} -\bar{\bm{B}} \end{aligned} \tag{C.17}

se vale la condizione -\bm{L}\leq \mathcal{L}\leq \bm{0}, -\bm{U}\leq \mathcal{U}\leq \bm{0}, allora abbiamo

\bm{0} \leq \bar{\bm{B}} = \left(\begin{array}{c|c} \rho\bm{I}-\bm{D}_1 & \bm{U}+\mathcal{U} \\\hline \bm{L}+\mathcal{L} & \rho\bm{I}-\bm{D}_2 \end{array}\right)\leq \left(\begin{array}{c|c} \rho\bm{I}-\bm{D}_1 & \bm{U} \\\hline \bm{L} & \rho\bm{I}-\bm{D}_2 \end{array}\right) = \bm{B} \tag{C.18}

e applicando il lemma Lemma C.2 otteniamo

\varsigma(\bar{\bm{B}})\leq \varsigma(\bm{B}) < \rho \tag{C.19}

quindi, per il lemma Lemma 25.3, \bm{C} è una M-matrice. Osserviamo che la matrice \bm{D}_2 -(\bm{L}+\mathcal{L})\bm{D}_1^{-1}(\bm{U}+\mathcal{U}) ha elementi non diagonali non positivi. Sia

\bm{C}^{-1} = \left(\begin{array}{c|c} \bm{C}_{1,1} & \bm{C}_{1,2} \\\hline \bm{C}_{2,1} & \bm{C}_{2,2} \end{array}\right) \geq \bm{0} \tag{C.20}

allora dalla C.13 segue

\begin{aligned} \bm{B}^{-1} &= \left(\begin{array}{c|c} \bm{D}_1^{-1} & \bm{0} \\\hline \bm{0} & \left( \bm{D}_2 -(\bm{L}+\mathcal{L})\bm{D}_1^{-1}(\bm{U}+\mathcal{U})\right)^{-1} \end{array}\right) \\ &= \left(\begin{array}{c|c} \bm{I}_1 & -\bm{D}_1^{-1}(\bm{U}+\mathcal{U}) \\\hline \bm{0} & \bm{I}_2 \end{array}\right) \left(\begin{array}{c|c} \bm{C}_{1,1} & \bm{C}_{1,2} \\\hline \bm{C}_{2,1} & \bm{C}_{2,2} \end{array}\right) \left(\begin{array}{c|c} \bm{I}_1 & \bm{0} \\\hline -(\bm{L}+\mathcal{L})\bm{D}_1^{-1} & \bm{I}_2 \end{array}\right)\\ &= \left(\begin{array}{c|c} \bm{C}_{1,1}-\bm{C}_{1,2}(\bm{L}+\mathcal{L})\bm{D}_1^{-1}-\bm{D}_1^{-1}(\bm{U}+\mathcal{U})\bm{C}_{1,2}+ \bm{D}_1^{-1}(\bm{U}+\mathcal{U})\bm{C}_{2,2}(\bm{L}+\mathcal{L})\bm{D}_1^{-1} & \bm{C}_{2,2}-\bm{D}_1^{-1}(\bm{U}+\mathcal{U})\bm{C}_{1,2} \\\hline \bm{C}_{2,1}-\bm{C}_{2,2}(\bm{L}+\mathcal{L})\bm{D}_1^{-1} & \bm{C}_{2,2} \end{array}\right) \end{aligned} \tag{C.21}

e di conseguenza \bm{D}_2 -(\bm{L}+\mathcal{L})\bm{D}_1^{-1}(\bm{U}+\mathcal{U})=\bm{C}_{2,2}\geq \bm{0}, quindi \bm{D}_2 -(\bm{L}+\mathcal{L})\bm{D}_1^{-1}(\bm{U}+\mathcal{U}) è una M-matrice e per il lemma Lemma 25.2 ha elementi diagonali strettamente positivi.

Osserviamo che le matrici \bm{Q} per i metodi di Jacobi, Gauss-Seidel e EWA diventano

\begin{aligned} \bm{Q}_J &= \left(\begin{array}{c|c} \bm{0} & \bm{U} \\\hline \bm{U} & \bm{0} \end{array}\right),\\ \bm{Q}_{GS} &= \left(\begin{array}{c|c} \bm{0} & \bm{0} \\\hline \bm{L} & \bm{0} \end{array}\right),\\ \bm{Q}_{EWA} &= \left(\begin{array}{c|c} \bm{0} & \bm{0} \\\hline \bm{0} & \textrm{offdiag}\left\{\bm{L}\bm{D}_1^{-1}\bm{U}\right\} \end{array}\right) \end{aligned} \tag{C.22}

è immediato verificare che \bm{Q}_J\geq \bm{Q}_{GS} e quindi applicando il teorema Teorema C.3 nel caso \bm{A} sia una M-matrice si verifica il fatto noto che

\varrho(\bm{P}_{GS}^{-1}\bm{Q}_{GS})\leq\varrho(\bm{P}_{J}^{-1}\bm{Q}_J) \tag{C.23}

purtroppo la matrice \bm{Q}_{EWA} non è confrontabile con le matrici \bm{Q}_J e \bm{Q}_{GS}. Possiamo però applicare il teorema Teorema C.4 sulle matrici

\begin{aligned} \bm{P}_{J}^{-1} &= \left(\begin{array}{c|c} \bm{D}_1^{-1} & \bm{0} \\\hline \bm{0} & \bm{D}_2^{-1} \end{array}\right), \\ \bm{P}_{GS}^{-1} &= \left(\begin{array}{c|c} \bm{D}_1^{-1} & \bm{D}_1^{-1}\bm{U}\bm{D}_2^{-1} \\\hline \bm{0} & \bm{D}_2^{-1} \end{array}\right), \\ \bm{P}_{EWA}^{-1} &= \left(\begin{array}{c|c} \bm{D}_1^{-1}+\bm{D}_1^{-1}\bm{U}\bm{K}_{2,EWA}^{-1}\bm{L}\bm{D}_1^{-1} & \bm{D}_1^{-1}\bm{U}\bm{K}_{2,EWA}^{-1} \\\hline \bm{K}_{2,EWA}^{-1}\bm{L}\bm{D}_1^{-1} & \bm{K}_{2,EWA}^{-1} \end{array}\right). \end{aligned} \tag{C.24} infatti

\bm{K}_{2,EWA}^{-1} = \bm{D}_2 -\textrm{diag}\left\{\bm{L}\bm{D}_1^{-1}\bm{U}\right\}\leq \bm{D}_2 \tag{C.25}

e di conseguenza \bm{K}_{2,EWA}^{-1}\geq \bm{D}_2^{-1} e ancora

\bm{P}_{EWA}^{-1}\geq \bm{P}_{GS}^{-1} \geq \bm{P}_{J}^{-1}, \quad\implies\quad \varrho(\bm{P}_{EWA}^{-1}\bm{Q}_{EWA}) \leq \varrho(\bm{P}_{GS}^{-1}\bm{Q}_{GS}) \leq \varrho(\bm{P}_{J}^{-1}\bm{Q}_{J}) \tag{C.26}

AGA

Teorema C.7 Nel caso \bm{L}\leq \mathcal{L}\leq \bm{0}, \bm{U}\leq \mathcal{U}\leq \bm{0}, per un qualunque metodo AGA abbiamo:

\varrho(\bm{P}_{EWA}^{-1}\bm{Q}_{EWA})\leq \varrho(\bm{P}_{AGA}^{-1}\bm{Q}_{AGA})

Dimostrazione. Osserviamo che

\bm{P}_{AGA}^{-1} = \left(\begin{array}{c|c} \bm{D}_1^{-1}+\bm{D}_1^{-1}(\bm{U}+\mathcal{U})\bm{K}_{2,AGA}^{-1} (\bm{L}+\mathcal{L})\bm{D}_1^{-1} & \bm{D}_1^{-1}(\bm{U}+\mathcal{U})\bm{K}_{2,AGA}^{-1} \\\hline \bm{K}_{2,AGA}^{-1}(\bm{L}+\mathcal{L})\bm{D}_1^{-1} & \bm{K}_{2,AGA}^{-1} \end{array}\right) \tag{C.27}

e

\begin{aligned} \bm{K}_{2,AGA} &= \bm{D}_2 -\textrm{diag}\left\{(\bm{L}+\mathcal{L})\bm{D}_1^{-1}(\bm{U}+\mathcal{U})\right\} \\ &= \bm{D}_2 -\textrm{diag}\left\{\bm{L}\bm{D}_1^{-1}\bm{U}\right\} -\textrm{diag}\left\{\mathcal{L}\bm{D}_1^{-1}(\bm{U}+\mathcal{U})\right\} -\textrm{diag}\left\{(\bm{L}+\mathcal{L})\bm{D}_1^{-1}\mathcal{U}\right\} \\ &\geq \bm{D}_2 -\textrm{diag}\left\{\bm{L}\bm{D}_1^{-1}\bm{U}\right\} = \bm{K}_{2,EWA} \end{aligned}

di conseguenza \bm{K}_{2,EWA}^{-1}\geq\bm{K}_{2,AGA}^{-1} in questo particolare caso. Vale inoltre

\bm{P}_{EWA}^{-1} \geq \bm{P}_{AGA}^{-1}

e per il teorema Teorema C.3

\varrho(\bm{P}_{EWA}^{-1}\bm{Q}_{EWA}) \leq \varrho(\bm{P}_{AGA}^{-1}\bm{Q}_{AGA})

NotaOsservazione

Togliendo la condizione sufficiente -\bm{L}\leq \mathcal{L}\leq \bm{0}, -\bm{U}\leq \mathcal{U}\leq \bm{0} otteniamo che in generale i metodi AGA (di cui EWA caso particolare) possono avere convergenza più elevata del metodo EWA. Per informazioni più dettagliate è utile leggere [1] e le referenze ivi contenute.

Confronto raggi spettrali

Teorema C.8 Sia \bm{B}\in L(\mathbb{R}^n) e \bm{C}\in L(\mathbb{C}^n). Allora se \left\lvert\bm{C}\right\rvert \leq \bm{B} allora \varrho(\bm{C})\leq \varrho(\bm{B}).

Dimostrazione. Sia \sigma=\varrho(\bm{B}) ed \epsilon >0 arbitrario, se poniamo

\bm{B}_1 = ( \sigma+\epsilon )^{-1} \bm{B}, \qquad \bm{C}_1 = ( \sigma+\epsilon )^{-1} \bm{C},

ovviamente \varrho(\bm{B}_1 ) < 1 ed,

\left\lvert\bm{C}_1 \right\rvert^k \leq \left\lvert\bm{B}_1 \right\rvert^k \qquad k=1,2,\ldots,

poiché \lim_{k\mapsto\infty} \bm{B}_1^k = 0 allora \lim_{k\mapsto\infty} \left\lvert\bm{C}_1^k\right\rvert = 0 e di conseguenza \ \varrho(\bm{C}_1 ) < 1 e \varrho(\bm{C}) < \sigma+\epsilon ed essendo \epsilon arbitrario \varrho(\bm{C}) \leq \sigma.

M-matrice caratterizzazione

Teorema C.9 Sia \bm{A}_1 \in \mathcal{L}(\mathbb{R}^n,\mathbb{R}^{n}) una M-matrice. Posto \bm{A}_1 = \bm{D}_1 -\bm{B}_1 con \bm{D}_1 parte diagonale di \bm{A}_1, se \bm{D}_2 \in \mathcal{L}(\mathbb{R}^n,\mathbb{R}^{n}) è diagonale e \bm{D}_2 \geq 0, \bm{B}_2 \geq \bm{0}, \bm{B}_2\leq \bm{B}_1 allora,

\bm{A}=\bm{D}_1 +\bm{D}_2 -(\bm{B}_1 -\bm{B}_2 ),

è una M-matrice ed \bm{A}^{-1} \leq \bm{A}_1^{-1}.

Dimostrazione. Sia

\begin{aligned} \bm{D} & = \bm{D}_1 +\bm{D}_2 ,\qquad & \bm{B} &= \bm{B}_1 -\bm{B}_2 , \\ \bm{H} & = \bm{D}^{-1}\bm{B}, & \bm{H}_1 &= \bm{D}_1^{-1}\bm{B}_1 , \end{aligned}

allora

\bm{D} \geq \bm{D}_1 \quad\implies\quad\bm{D}^{-1} \leq \bm{D}_1^{-1}

e inoltre,

0 \leq \bm{B} \leq \bm{B}_1 \; ,\; 0 \leq \bm{H} \leq \bm{H}_1 ,

dal teorema Teorema C.8 si ha \varrho(\bm{H}) \leq \varrho(\bm{H}_1 )<1 ed allora il teorema Teorema 25.1 assicura che \bm{A} è una M-matrice. Poiché \bm{A} \geq \bm{A}_1 allora moltiplicando a destra e a sinistra per \bm{A}^{-1} ed \bm{A}_1^{-1} (si può perché sono entrambe positive e invertibili).

\begin{aligned} \bm{A}^{-1}\bm{A}\bm{A}_1^{-1} & \geq \bm{A}^{-1}\bm{A}_1^{-1}\bm{A}_1^{-1}, \\ \bm{A}_1^{-1} & \geq \bm{A}^{-1}, \end{aligned}

Corollario C.1 Sia \bm{A}\in \mathcal{L}(\mathbb{R}^n,\mathbb{R}^{n}) una matrice di Stieltjes. Allora \bm{A} è definita positiva.

Dimostrazione. Sia \lambda autovalore di \bm{A} con \lambda \leq 0 allora se poniamo \bm{B}_2 =0 e \bm{D}_2 = -\lambda \bm{I} avremo che \bm{A}-\lambda\bm{I} è una M-matrice perché contraddice la singolarità di \bm{A}-\lambda \bm{I}.

Mappa isotona

Definizione C.3 Una mappa F:D\subset\mathbb{R}^n \mapsto \mathbb{R}^n è detta isotona (antitona) su D_o \subset D se \bm{F}(\bm{x}) \leq \bm{F}(\bm{y})(\bm{F}(\bm{x}) \geq \bm{F}(\bm{y})) quando \bm{x}\leq \bm{y}\ \forall\,\bm{x},\bm{y} \in D_o.

[1]

Z. I. Woźnicki. 1994. Nonnegative splitting theory. Japan Journal of Industrial and Applied Mathematics 11, 2 (1994), 289–342. https://doi.org/10.1007/BF03167226

---

1. Israel Moiseevič Gel’fand (1913-2009)

2. Ferdinand Georg Frobenius (1849-1917)

3. Carl Gustav Jacob Jacobi (1804-1851)

4. Carl Friedrich Gauss (1777-1855)

5. Philipp Ludwig von Seidel (1821-1896)