\documentclass[10pt,a4paper]{article}
\usepackage{amssymb} % for \mathbb (also package 'amsfonts' is ok)
\usepackage[dvips]{graphicx}
% commands for influencing style: ...
\input{mydef}
\begin{document}

Esercizi ($\&$ teoria): si svolgono dall'ultimo al primo (SMC-STM 2009)

\vskip0.2cm

$\square$ Siano
$$
     A = \ba{ccc}
            0 & 1 & 2 \\
            -2 & 3 & 5 \\
            1 & -1 & 1 \ea,\ \
        \b = \ba{c}
               3 \\
               6 \\
               1 \ea.
$$
\begin{itemize}
\item[i]
Risolvere il sistema lineare $A\x=\b$ con il metodo di Gauss
\item[ii]
Trovare matrici $\Pi$ di permutazione, $D$ diagonale, $L$ e
$U^T$ triangolari inferiori con $L_{ii}=U_{ii}=1$, $i=1,2,3$,
tali che $A=\Pi L U$
\item[iii]
Annullare la seconda e la terza componente del vettore $\b$
usando il metodo di Givens
\item[iv]
Esistono le fattorizzazioni di Cholesky delle matrici $M=A+A^T$
e $N=AA^T$?
\item[v]
Dire se $-4$ pu\`o essere autovalore di $A$
(non calcolare il polinomio caratteristico di $A$)
\item[vi]
Studiare la convergenza del metodo di Gauss-Seidel nella risoluzione
di $A\x=\b$
\end{itemize}

\vskip0.2cm

$\ldots$ \qquad $\ldots$ \qquad $\ldots$

\vskip0.4cm

? Maggio 2009

\vskip0.2cm

{\it Condizionamento di un sistema lineare vs stabilit\`a
dell'algoritmo per la sua risoluzione} (seconda parte)

\vskip0.2cm

Esempio. Gauss al sistema
$$
A(\x+d\x) = \ba{cc}
               .3\cdot10^{-3}  &  1  \\
                      1    &  0  \ea
            \ba{c}
               x_1+dx_1  \\
               x_2+dx_2  \ea
          = \ba{c}
               1 \\
               1 \ea = \b+d\b.
$$
Anzich\'e
$$
         E =  \ba{cc}
                  1   &  0 \\
             -1/.3\cdot 10^{-3} &  1 \ea
$$
il calcolatore definisce
$$
``E" = \ba{cc}
         1     &    0  \\
    -.333\cdot 10^4 &    1  \ea.
$$
Poi effettua le moltiplicazioni macchina
$$
``E"A = \ba{cc}
       .3\cdot 10^{-3}  &    1  \\
         0         &   -.333\cdot 10^4 \ea,\ \
``E"(\b+d\b) =  \ba{c}
                   1   \\
               -.333\cdot 10^4 \ea
$$
($-.333\cdot 10^4``+"1 = -.333\cdot 10^4$).
Quindi $``\x+d\x"=$ (cio' che la macchina ha effettivamente
ottenuto calcolando $\x+d\x$) $=\ba{c} 0 \\ 1 \ea$ ed

errore algoritmico $= \|``\x+d\x"-(\x+d\x)\|/\|\x+d\x\| = 1/1 =1$.
Nota: \`e grande rispetto a $u=0.5\cdot 10^{-2}$
($\x+d\x = \ba{c} 1 \\ 1 -.3\cdot 10^{-3} \ea$ e si \`e
usata la norma infinito).

In effetti gli elementi di
$$
 ``L" = \ba{cc}
           1   &   0  \\
     .333\cdot 10^4 &   1  \ea,\
 ``U" = \ba{cc}
         .3\cdot 10^{-3} & 1          \\
         0          & -.333\cdot 10^4 \ea
$$
sono in modulo molto pi\`u grandi di quelli di $|A|$.

Conclusione: il problema $A\x=\b$ \`e ben condizionato,
ma l'algoritmo di Gauss per la sua risoluzione \`e instabile.

\vskip0.1cm

Modificando Gauss \`e possibile definire un algoritmo stabile per la
risoluzione di $A\x=\b$:

Gauss modificato al sistema
$$
A(\x+d\x) = \ba{cc}
               .3\cdot 10^{-3} & 1 \\
                    1     & 0 \ea
               \ba{c}
                  x_1+dx_1 \\
                  x_2+dx_2 \ea
          = \ba{c}
                 1 \\
                 1 \ea = \b+d\b.
$$
$$
P = \ba{cc}
        0 & 1 \\
        1 & 0 \ea,\
PA = \ba{cc}
            1  &  0  \\
     .3\cdot 10^{-3}&  1  \ea,\
P(\b+d\b) = \ba{c}
                1 \\
                1 \ea,
$$
$$
E = \ba{cc}
         1     & 0 \\
   -.3\cdot 10^{-3} & 1 \ea,\
EPA = \ba{cc}
          1 & 0 \\
          0 & 1 \ea,\
EP(\b+d\b) = \ba{c}
                 1 \\
                 1 \ea
$$
($-.3\cdot 10^{-3}``+"1 = 1$).
Quindi $``\x+d\x" = \ba{c} 1 \\ 1 \ea$ ed

errore algoritmo
$= \|``\x+d\x"-(\x+d\x)\|/\|\x+d\x\| = .3\cdot 10^{-3}/1 = .3\cdot 10^{-3}$.
Nota: \`e pi\`u piccolo di $u=0.5\cdot 10^{-2}$.

In effetti gli elementi di
$$
   ``L" = \ba{cc}
             1 & 0 \\
     .3\cdot 10^{-3}& 1 \ea,\ \
   ``U" = \ba{cc}
             1 & 0 \\
             0 & 1 \ea
$$
sono dello stesso ordine di grandezza di quelli di $|A|$.

Conclusione: l'algoritmo di Gauss modificato per la risoluzione
di $A\x=\b$ \`e stabile.

\vskip0.2cm

18 Maggio 2009, 9 Maggio 2009, 28 Aprile 2009, 21 Aprile 2009

18 Maggio 2009

\vskip0.2cm

{\it Condizionamento di un sistema lineare vs stabilit\`a
dell'algoritmo per la sua risoluzione} (prima parte)

\vskip0.2cm

``Risultato 1'' (senza dim)
sul condizionamento di un sistema lineare $A\x=\b$:

Siano $\x$ e $\x+d\x$ tali che $A\x=\b$ e $(A+dA)(\x+d\x)=\b+d\b$
dove $dA$ e $d\b$ sono perturbazioni, rispettivamente, della matrice
A e del vettore $b$. Allora
$$
\f{\|d\x\|}{\|\x\|} \leq \mu(A) \f{\|dA\|/\|A\|+\|d\b|/\|\b\|}
                                {1-\mu(A)\|dA\|/\|A\|}
$$
dove $\mu(A)=\|A\|\|A^{-1}\|$ e la norma matriciale \`e quella
indotta dalla norma vettoriale utilizzata.

[Nota: per $dA=0$ ritroviamo il risultato visto in precedenza,
relativo a perturbazioni sul solo vettore dei termini noti:
$A\x=\b$ $\&$ $A(\x+d\x)=\b+d\b$ $\then$
$\|d\x\|/\|\x\| \leq \mu(A) \|d\b\|/\|\b\|$.]

Questo risultato \`e ovviamente utile per valutare l'errore inerente
sulla soluzione di un sistema lineare:
$\mu(A)$ grande $\then$ errore inerente pu\`o essere molto pi\`u
grande dell'errore inerente sui dati;
$\mu(A)$ piccolo $\then$ errore inerente deve essere dello
stesso ordine dell'errore inerente sui dati.

\vskip0.1cm

Esempio. Il sistema
$$
A\x = \ba{cc}
        .3\cdot 10^{-3} & 1 \\
         1         & 0 \ea
        \ba{c}
            x_1 \\
            x_2 \ea
    = \ba{c}
         1+.3\cdot 10^{-3} \\
          1           \ea  = \b
$$
in $F(10,3,\ldots)$ diventa
$$
A(\x+d\x) = \ba{cc}
        .3\cdot 10^{-3} & 1 \\
         1         & 0 \ea
             \ba{c}
               x_1+dx_1 \\
               x_2+dx_2 \ea
          = \ba{c}
               1 \\
               1 \ea = \b+d\b
$$
($1+.3\cdot 10^{-3}=.10003\cdot 10^1$, $1``+".3\cdot 10^{-3}=.1\cdot 10^1$)
quindi, per il ``Risultato 1'' con $dA=0$,
utilizzando la norma infinito, si ottiene la limitazione
$$
  \f{\|d\x\|}{\|\x\|} \leq (1+e)^2 \f{\|d\b\|}{\|\b\|},\
                \f{\|d\b\|}{\|\b\|} =\f{.3\cdot 10^{-3}}{1+.3\cdot 10^{-3}}.
$$
Essendo $e=.3\cdot 10^{-3}$, il numero $\mu_{\infty}(A)=(1+e)^2$ \`e
poco pi\`u grande di $1$
$\then$ l'errore inerente sulla soluzione \`e dello stesso ordine di
grandezza dell'errore inerente sul vettore dei termini noti $\then$
il problema $A\x=\b$ \`e ben condizionato.

\vskip0.2cm

Vediamo ora come il ``Risultato 1'' pu\`o essere utile anche per
valutare l'errore commesso nelle successive operazioni richieste dal
metodo di Gauss (errore dovuto ai necessari arrotondamenti operati
dalla macchina durante i calcoli) per la risoluzione di $A\x=\b$.

Premessa:
``Risultato 2'' (senza dim)
sul metodo di Gauss :

Dati $A$ $n\times n$ non singolare, $\b$ $n\times 1$, con $a_{ij}$
e $b_i$ numeri macchina, posto $\x =$ soluzione esatta di $A\x=\b$,
$``\x" =$ soluzione effettivamente calcolata con Gauss tramite i passi:

a) scrittura di $``L", ``U"$ (i fattori della decomposizione LU di $A$
effettivamente calcolati) e di $``\c"$ (la soluzione di $``L"\c=\b$
effettivamente calcolata);

b) scrittura di $``\x"$ (la soluzione di $``U"\x=``\c"$ effettivamente
calcolata),

SI HA CHE $``\x"$ \`e la soluzione esatta di un sistema
ottenuto da $A\x=\b$ perturbando $A$ di $DA$, cio\`e vale
l'identit\`a
$$
    (A+DA)``\x"=\b,\ \
         |DA| \leq 4nu(|A|+|``L"||``U"|) + O(u^2)
$$
($|M|=$ matrice i cui elementi sono i moduli degli elementi di $M$).

\vskip0.1cm

Il ``Risultato 2'' permette di valutare l'errore dell'algoritmo di
Gauss sfruttando la maggiorazione del ``Risultato 1'':
$$
   \f{\|``\x"-\x\|}{\|\x\|} \leq
            \mu(A) \f{\|DA\|/\|A\|}{1-\mu(A)\|DA\|/\|A\|}
$$
(usa Ris.1 per $dA=DA$, $d\b=\vn$, $\x+d\x=``\x"$).
Quest'ultima disuguaglianza e la maggiorazione data per $|DA|$
ci dicono che $\|``\x"-\x\|/\|\x\|$ pu\`o essere grande quando
$|``L"|$ e $|``U"|$ sono grandi rispetto a $|A|$; $\|``\x"-\x\|/\|\x\|$
\`e invece piccolo se $|``L"|$ e
$|``U"|$ sono dello stesso ordine di grandezza di $|A|$.

\vskip0.2cm
\hrule
\vskip0.2cm

Per risolvere $A\x=\b$ (sempre nel caso $\det(S_k)\neq 0$,
$k=1,\ldots, n$) si pu\`o usare anche l'algoritmo:

\begin{itemize}
\item[(1)] calcolare $L$ ed $U$ tali che $A=LU$,
\item[(2)] risolvere il sistema $L\c=\b$ (con il m. di sostituzione
in avanti),
\item[(3)] risolvere il sistema $U\x=\c$ (con il m. di sostituzione
all'indietro).
\end{itemize}

NOTA: applicare le $E_i$ oltre che ad $A$ anche a $\b$ ( cio\`e
calcolare $E_{n-1}\cdots E_2E_1[A\,|\,\b]$), come si fa nel metodo
di Gauss, \`e equivalente ad eseguire i passi (1) e (2) del presente
algoritmo contemporaneamente, infatti
$E_{n-1}\cdots E_2E_1\b=L^{-1}\b$.

\vskip0.2cm

9 Maggio 2009

\vskip0.2cm

$\square$ Risolvere con il metodo di Gauss il sistema lineare
$$
   \ba{ccc}
     -2 & 4 & -1 \\
     4  &-9 & 0  \\
     -4 & 5 &-5  \ea
    \ba{c}
        x_1 \\
        x_2 \\
        x_3 \ea = \ba{c}
                     12 \\
                     -32 \\
                      3 \ea .
$$

\vskip0.2cm

$\square$ Calcolare le decomposizioni LU delle matrici
$$
A = \ba{cc}
      -2 & 4 \\
       4 & -8 \ea, \
A = \ba{ccc}
        6 & 3 & 3 \\
        3 & 3 & 3 \\
        3 & 3 & 3 \ea,\
A = \ba{cc}
        1  & 1/2 \\
       1/2 & 1/3 \ea,\
A = \ba{ccc}
       1  &  1/2 & 1/3 \\
      1/2 &  1/3 & 1/4 \\
      1/3 &  1/4 & 1/5 \ea
$$
Nota: Le prime due matrici sono singolari, ad esempio nella prima
matrice la seconda colonna \`e $-2$ volte la prima colonna, quindi
\`e ``linearmente dipendente'' dalla prima. Ne segue che per tali
matrici $u_{nn}=0$.

\vskip0.2cm

{\it Metodo di Gauss: decomposizione LU, risoluzione sistemi lineari}

\vskip0.2cm
$$
A = \ba{cccc}
      a_{11} & a_{12} & \cdots & a_{1n} \\
      a_{21} & a_{22} & \cdots & a_{2n} \\
         .   &   .    &        &  .     \\
      a_{n1} & a_{n2} & \cdots & a_{nn} \ea
$$
IPOTESI: $a_{11}\neq 0$
$$                     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
E_1 = \ba{ccccc}
              1    &   0  & \cdots &  &   0 \\
      -a_{21}/a_{11} & 1  & . &      &  .  \\
              .      & 0  & .  & .   &.   \\
              .      & .  & .  & .   & 0 \\
      -a_{n1}/a_{11} & 0  & \cdots & 0 &  1 \ea,\
E_1A =  \ba{cccc}
        a_{11} & a_{12} &  \cdots & a_{1n} \\
         0     & a_{22}^2 & \cdots & a_{2n}^2 \\
         .     &  .      &         &    .   \\
         0     & a_{n2}^2 & \cdots &  a_{nn}^2 \ea =:A^{2},
$$

$a_{ij}^2 = a_{ij} - (a_{i1}/a_{11}) a_{1j}$,  $2\leq i,j\leq n$,

$a_{i1}^2 = 0$, $2\leq i\leq n$,

$a_{ij}^2 = a_{ij}$ altrimenti (per i rimanenti $i$ e $j$).

\noindent NOTA:
$$
      \ba{cc}
           1      & 0 \\
   -a_{21}/a_{11} & 1 \ea
           \ba{cc}
             a_{11} & a_{12} \\
             a_{21} & a_{22} \ea
       = \ba{cc}
           a_{11} &   a_{12} \\
             0    & a_{22}^2 \ea,
$$
quindi, passando ai determinanti,
$$
        a_{22}^2 = \f{1}{a_{11}} \det \ba{cc}
                                   a_{11} & a_{12} \\
                                   a_{21} & a_{22} \ea.
$$
IPOTESI: $a_{22}^2 \neq 0$ (ovvero $\det\ba{cc}
                                    a_{11} & a_{12} \\
                                    a_{21} & a_{22} \ea \neq 0$)
$$
E_2 = \ba{ccccc}
       1     &    0    &       0  & \cdots &   0 \\
      0       &  1      &     0   &  \cdots  & 0 \\
      0 & -a_{32}^2/a_{22}^2 & 1 &     . &  . \\
      .    &     .   &           . & .  & 0 \\
      0 & -a_{n2}^2/a_{22}^2 & 0 & \cdots 0  & 1 \ea
$$
$$
E_2E_1A =  \ba{ccccc}
          a_{11} & a_{12}  &  a_{13} & \cdots & a_{1n}   \\
            0    & a_{22}^2 & a_{23}^2 & \cdots & a_{2n}^2 \\
            0    &  0  &      a_{33}^3 & \cdots & a_{3n}^3 \\
            .    &  .  &      .   &    &          .  \\
            0    & 0   &    a_{n3}^3 & \cdots & a_{nn}^3   \ea =: A^{3},
$$

$a_{ij}^3 = a_{ij}^2 - (a_{i2}^2/a_{22}^2) a_{2j}^2$,
 $3\leq i,j\leq n$,

$a_{i2}^2 = 0$, $3\leq i\leq n$,

$a_{ij}^3 = a_{ij}^2$ altrimenti (per i rimanenti $i$ e $j$).

\noindent NOTA:
$$
    \ba{ccc}
        1 & 0  & 0 \\
        0 & 1  & 0 \\
        0 &-a_{32}^2/a_{22}^2 & 1 \ea
        \ba{ccc}
           1 & 0 & 0 \\
           -a_{21}/a_{11} & 1 & 0 \\
           -a_{31}/a_{11} & 0 & 1 \ea
           \ba{ccc}
             a_{11} & a_{12} & a_{13} \\
             a_{21} & a_{22} & a_{23} \\
             a_{31} & a_{32} & a_{33} \ea
       = \ba{ccc}
            a_{11} & a_{12}   & a_{13} \\
               0   & a_{22}^2 &  a_{23}^2 \\
               0   &    0     & a_{33}^3 \ea,
$$
quindi, passando ai determinanti,
$$
      a_{33}^3 = \f{1}{a_{11}a_{22}^2}
                       \det \ba{ccc}
                               a_{11} & a_{12} & a_{13} \\
                               a_{21} & a_{22} & a_{23} \\
                               a_{31} & a_{32} & a_{33} \ea.
$$
$\ldots$

IPOTESI: $a_{n-1,n-1}^{n-1} \neq 0$
(ovvero $\det\ba{ccc}
                a_{11} & \cdots & a_{1n-1} \\
                     . &        &  .       \\
              a_{n-11} & \cdots & a_{n-1n-1} \ea \neq 0$)
$$
E_{n-1} = \ba{ccccc}
          1  & 0  &     \cdots &   .   &             0  \\
          0  & .  &      .     &    .  &        . \\
          .  &  . &         .   &   1   &         0  \\
          0  & \cdots & 0 & -a_{nn-1}^{n-1}/a_{n-1n-1}^{n-1} & 1 \ea
$$
$$
E_{n-1}\cdots E_2E_1A = \ba{cccc}
                    a_{11} & a_{12} &        &   a_{1n} \\
                           & a_{22}^2 &      &  a_{2n}^2   \\
                             &       . &        & .  \\
                           &       &       & a_{nn}^n \ea =: A^{n},
$$

$a_{nn}^n = a_{nn}^{n-1}-(a_{nn-1}^{n-1}/a_{n-1n-1}^{n-1})
             a_{n-1n}^{n-1}$,

$a_{nn-1}^n = 0$,

$a_{ij}^n = a_{ij}^{n-1}$ altrimenti (per i rimanenti $i$ e $j$).

\noindent NOTA: si osserva che
$$
   a_{nn}^n = \f{1}{a_{11}a_{22}^2...a_{n-1n-1}^{n-1}} \det(A).
$$
Sia $A$ $n\times n$ e
$$
       S_k = \ba{ccc}
                a_{11} & \cdots & a_{1k} \\
                   .   &        & .      \\
                a_{k1} & \cdots & a_{kk} \ea,\ \ k=1,\ldots,n.
$$
Teorema. Se $\det(S_k) \neq 0$ per $k=1\ldots n-1$ allora
\begin{itemize}
\item[(1)]
esistono matrici $E_1, E_2,\ldots, E_{n-1}$ ``elementari di Gauss''
tali che $E_{n-1}\cdots E_2E_1A=A^{(n)}=(a_{ij}^n)_{i,j=1}^n$
\`e triangolare superiore
\item[(2)]
$\det(A)=0$ se e solo se $a_{nn}^n = 0$
\item[(3)]
esiste $L$ $n\times n$ triangolare inferiore, $L_{ii}=1$, ed $U$
triangolare superiore tali che $A=LU$: $U=A^{(n)}$ e
$$
L = E_1^{-1}E_2^{-1}\cdots E_{n-1}^{-1}
= \ba{ccccc}
    1     &     0     &         \cdots &     .     &          0 \\
 a_{21}/a_{11} &    1  &             &          .   &          .  \\
       .    &   a_{32}^2/a_{22}^2 &       .   &            &    . \\
       .        &   .             &               &   1    &  0   \\
 a_{n1}/a_{11} & a_{n2}^2/a_{22}^2 & . &
       a_{nn-1}^{n-1}/a_{n-1n-1}^{n-1} & 1  \ea
$$
\item[(4)]
(metodo di Gauss (a))
considerato il sistema lineare $A\x=\b$, $\b$ $n\times 1$
generico, si pu\`o introdurre un sistema lineare triangolare
superiore $U\x=\c$ equivalente ad $A\x=\b$ col seguente algoritmo:
$$
  \bi{l}
[A\ |\ \b]  \\
E_1[A\ |\ \b] = [E_1A\ |\ E_1\b]  \\
E_2E_1[A\ |\ \b] = [E_2E_1A\ |\ E_2E_1\b]  \\
\ldots   \\
E_{n-1}\cdots E_2E_1[A\ |\ \b] =
          [E_{n-1}\cdots E_2E_1A\ |\ E_{n-1}\cdots E_2E_1\b], \\
U = E_{n-1}\cdots E_2E_1A,\ \  \c = E_{n-1}\cdots E_2E_1\b  \ei
$$
ovvero:
$$
\bi{l}
\hbox{per }\ k=1\ldots n-1\ \ \{   \\
a_{ij}^{k+1} = a_{ij}^k - (a_{ik}^k/a_{kk}^k) a_{kj}^k,\ \
              k+1\leq i,j\leq n,   \\
a_{ik}^{k+1} = 0, \ \  k+1\leq i\leq n,  \\
a_{ij}^{k+1} = a_{ij}^k,\ \ \hbox{altrimenti (per i rimanenti i,j)}, \\
b_i^{k+1} = b_i^k - (a_{ik}^k/a_{kk}^k) b_k^k,\ \  k+1\leq i\leq n, \\
b_i^{k+1}= b_i^k,\ \ \hbox{altrimenti }\  (i<=k); \ \} \\
U=A^{n}=(a_{ij}^n)_{i,j=1\ldots n}, \\
\c=\b^n\ .  \ei
$$
Il costo di questo algoritmo \`e $n^3/3 +O(n^2)$
operazioni moltiplicative.
Pi\`u precisamente,
per $k$ generico occorre eseguire:
$n-k$ divisioni per calcolare i rapporti
$l_{ik}=a_{ik}^k/a_{kk}^k$, cio\`e
gli elementi della matrice $L$,
le $(n-k)^2$ moltiplicazioni $l_{ik}a_{kj}^k$
e le $n-k$ moltiplicazioni $l_{ik}b_k^k$.
Quindi $L$ ed $U$ possono essere calcolate con
$\sum_{k=1\ldots n-1} (n-k) = n(n-1)/2$ divisioni e
$\sum_{k=1\ldots n-1} (n-k)^2 = n(n-1)(2n-1)/6$ moltiplicazioni.
Per calcolare anche $\c$ occorre eseguire altre
$\sum_{k=1\ldots n-1} (n-k) = n(n-1)/2$ moltiplicazioni
\item[(5)]
(metodo di Gauss (b))
se $A$ \`e inoltre non singolare i sistemi $A\x=\b$ e
$U\x=\c$ oltre ad essere equivalenti ammettono una unica soluzione
$\x=A^{-1}\b=U^{-1}\c$, calcolabile, con altre $n(n-1)/2$
moltiplicazioni
e $n$ divisioni, applicando il metodo di sostituzione all'indietro al
sistema $U\x=\c$
\end{itemize}

$\square$ Se $A$ $n\times n$ \`e definita positiva allora $\det(S_k)>0$,
$k=1\ldots n$, quindi esiste la decomposizione LU di $A$ ed ogni sistema
$A\x=\b$, $\b$ $n\times 1$, pu\`o essere
risolto usando il metodo di Gauss

\vskip0.2cm

$\square$ Un esercizio dell'esonero

$A,B$ $n\times n$.
Se $\E$ \`e autovalore di $AB$ allora \`e autovalore di $BA$.

Infatti $\E$ autovalore di $AB$ $\then$ esiste $\v\neq\vn$ tale che
$AB\v=\E\v$ $\then$
$B(AB\v)=B(\E\v)$ $\then$ $(BA)B\v=\E B\v$, ovvero $\E$ \`e autovalore
di $BA$ con corrispondente autovettore $B\v$.
Quindi $AB$ e $BA$ hanno gli stessi autovalori e gli autovettori di
$BA$ si ottengono moltiplicando quelli di $AB$ per $B$

$A$ $n\times n$ invertibile $\then$ $\mu_2(A^*A)=\mu_2(A)^2$.

Infatti,
$$
    \bi{rcl}
\mu_2(A^*A) & = & \|A^*A\|_2\|(A^*A)^{-1}\|_2
          = \rho(A^*A) \rho((A^*A)^{-1}) \\
         & = & \rho(A^*A) \rho(A^{-1}(A^*)^{-1})
          = \rho(A^*A) \rho((A^*)^{-1}A^{-1}) \\
        &  = & \rho(A^*A) \rho((A^{-1})^*A^{-1})
          = \|A\|^2 \|A^{-1}\|^2
          = \mu_2(A)^2 \ei
$$
( risultati utilizzati: $A^*A$ \`e hermitiana;
$M$ hermitiana $\then$ $M^{-1}$ hermitiana;
$MN$ ed $NM$ hanno gli stessi autovalori, quindi
$\rho(MN)=\rho(NM)$; ($M^*)^{-1}=(M^{-1})^*$)

\vskip0.2cm

28 Aprile 2009

\vskip0.2cm

$\square$ Usando il Teorema di Schur scrivere un algoritmo
alternativo per la risoluzione di $A\x=\b$, $A$ $n\times n$,
$\b$ $n\times 1$. Si suppone $\det(A)=$ determinante di $A$
diverso da zero. Qual'\`e l'inconveniente di tale algoritmo?

\vskip0.1cm

{\it Risoluzione}. Algoritmo:
\begin{itemize}
\item[(1)]
calcolare una matrice unitaria $S$ tale che
$S^{-1}AS=:U$ \`e triangolare superiore (essa esiste per il Teorema di Schur),
\item[(2)]
risolvere i due sistemi lineari: $U\y=S^*\b$, $S^*\x=\y$.
\end{itemize}

Inconveniente: l'operazione di cui al punto (1) non \`e banale e comunque non pu\`o essere effettuata (in generale) con un numero finito di operazioni aritmetiche. Sappiamo invece che, usando Gauss o una delle sue varianti, o Givens, o Householder, \`e possibile introdurre un sistema lineare triangolare $U\x=\c$ equivalente ad $A\x=\b$ facendo $tot<+\infty$ o.a.. La $U$ ottenuta con tali algoritmi non ha gli autovalori di $A$, ma che importa !

\vskip0.2cm

{\it Risolvere sistemi lineari con matrice dei coefficienti
triangolare superiore}

\vskip0.2cm

$U$ $n\times n$ triangolare superiore non singolare, ovvero
$[U]_{ii} \neq 0$, per ogni $i$, e $\c$ vettore $n\times 1$:
$U\x=\c$ iff
$$
     \bi{rcl}
u_{11}x_1 + u_{12}x_2 +\ldots+ u_{1n}x_n & = & c_1 \\
            u_{22}x_2 +\ldots+ u_{2n}x_n & = & c_2 \\
                                         &\vdots&     \\
                 u_{n-1,n-1}x_{n-1} + u_{n-1,n}x_n & = & c_{n-1} \\
                                    u_{nn}x_n & = &c_n  \ei
$$
iff
$$
    \bi{l}
x_n = c_n / u_{nn} \\
x_{n-1} = ( c_{n-1} - u_{n-1,n}x_n ) / u_{n-1,n-1}  \\
  \vdots      \\
x_2 = ( c_2 - u_{23}x_3 ... - u_{2n}x_n ) / u_{22} \\
x_1 = ( c_1 - u_{12}x_2 .... - u_{1n}x_n ) / u_{11} \ei
$$
iff per $i=n,\ldots, 1$:
$x_i = (c_i - \sum_{j=i+1,\ldots, n} u_{ij} x_j ) / u_{ii}$.
Costo $= n(n+1)/2$ moltiplicazioni-divisioni.

\vskip0.2cm

{\it Risolvere sistemi lineari con matrice dei coefficienti generica,
triangolarizzazione di una matrice}

\vskip0.2cm

$A$ matrice $n\times n$ non singolare, $\b$ vettore $n\times 1$.
$E_k$, $k=1,\ldots, n-1$, matrici $n\times n$ non singolari tali che
$$
   \bi{l}
A \x = \b \hbox{ iff}   \\
E_1 A \x = E_1 \b,\ \ E_1A = \ba{cccc}
                         * & * & \cdots & * \\
                         0 & * & \cdots & * \\
                         . & . &        & . \\
                         0 & * & \cdots & * \ea    \hbox{ iff} \\
E_2 E_1 A \x = E_2 E_1 \b,\ \ E_2E_1A = \ba{ccccc}
                                    * & * & * & \cdots & * \\
                                    0 & * & * & \cdots & * \\
                                    . & 0 & * & \cdots & * \\
                                    . & . & . &        & . \\
                                    0 & 0 & * & \cdots & * \ea
                          \hbox{ iff}  \ei
$$
$\ldots$  iff
$E_{n-1}\cdots E_2 E_1 A \x = E_{n-1}\cdots E_2 E_1 \b$, ovvero
$U \x = \c$, con
$$
U = E_{n-1}\cdots E_2E_1A = \ba{ccccc}
                        * & * & * & \cdots & * \\
                        0 & * & * & \cdots & * \\
                        . & 0 & * & \cdots & * \\
                        . & . & . &  .     & . \\
                        0 & . & . &  0     & * \ea,\ \
         \c = E_{n-1}\cdots E_2 E_1 \b.
$$

\vskip0.2cm

{\it Definizione di $E_k$ (passo $k$ della triangolarizzazione)}

\vskip0.2cm

Per $k=1,\ldots, n-1$:
Al termine del passo $k-1$ \`e stata prodotta la matrice
$$
E_{k-1}\cdots E_2E_1A = \ba{cc}
                            T & V \\
                            0 & W \ea,
$$
$T$ $k-1\times k-1$ triangolare superiore, $W$ $n-k+1\times n-k+1$
(per $k=1$ si ha $A=W$).

Si vogliono annullare gli elementi $(k+1,k),\ldots,(n,k)$ di tale
matrice, ovvero il secondo, $\ldots$, l'ultimo elemento della prima
colonna di $W$:
$$
    \bi{l}
E_k = \ba{cc}
         I & 0 \\
         0 & F \ea,\ I\ k-1\times k-1,\ \ F\ n-k+1\times n-k+1,   \\
E_k(E_{k-1}\cdots E_2E_1A) = \ba{cc}
                                I & 0 \\
                                0 & F \ea
                             \ba{cc}
                                T & V \\
                                0 & W \ea
                           = \ba{cc}
                                T & V \\
                                0 & FW \ea
                           = \ba{cc}
                                T & V \\
                                0 & [F\w\ FY] \ea \ei
$$
dove $W = [\w\ Y]$. Se $\w$, la prima colonna di $W$,
\`e gia' della forma $[*\ 0\ \cdots\ 0]^T$
allora porre $F=I$, altrimenti scegliere $F$ come in Gauss semplice,
Gauss con pivot parziale, Givens, Householder per ottenere
$F\w = [*\ 0\ \cdots\ 0]^T$.

\vskip0.2cm

Costo $= \sum_{k=1\ldots n-1} [$costo del prodotto matrice-matrice
$FY$, $F$ $n-k+1\times n-k+1$, $Y$ $n-k+1\times n-k$].
Ad esempio, in Gauss costo($FY)=(n-k)^2$ moltiplicazioni $\then$
costo di Gauss $= n^3/3 + O(n^2)$.

\vskip0.2cm

{\it Un esempio di triangolarizzazione}

\vskip0.2cm

$$
A = \ba{cccc}
     1 & 0 & 0 & 1 \\
    -1 & 1 & 0 & 1 \\
    -1 &-1 & 1 & 1 \\
    -1 &-1 &-1 & 1 \ea,
$$
$$
E_1 = \ba{cccc}
        1 & 0 & 0 & 0 \\
        1 & 1 & 0 & 0 \\
        1 & 0 & 1 & 0 \\
        1 & 0 & 0 & 1 \ea,\
E_1A = \ba{cccc}
        1 & 0 & 0 & 1 \\
        0 & 1 & 0 & 2 \\
        0 &-1 & 1 & 2 \\
        0 &-1 & -1& 2 \ea\ (F=E_1,\ W=A),
$$
$$
E_2 = \ba{cccc}
        1 & 0 & 0 & 0 \\
        0 & 1 & 0 & 0 \\
        0 & 1 & 1 & 0 \\
        0 & 1 & 0 & 1 \ea,\
E_2E_1A = \ba{cccc}
            1 & 0 & 0 & 1 \\
            0 & 1 & 0 & 2 \\
            0 & 0 & 1 & 4 \\
            0 & 0 & -1 & 4 \ea\
(F = \ba{ccc}
       1 & 0 & 0 \\
       1 & 1 & 0 \\
       1 & 0 & 1 \ea,\
 W = \ba{ccc}
       1 & 0 & 2 \\
      -1 & 1 & 2 \\
      -1 & -1 & 2 \ea),
$$
$$
E_3 = \ba{cccc}
        1 & 0 & 0 & 0 \\
        0 & 1 & 0 & 0 \\
        0 & 0 & 1 & 0 \\
        0 & 0 & 1 & 1 \ea,\
E_3E_2E_1A = \ba{cccc}
               1 & 0 & 0 & 1 \\
               0 & 1 & 0 & 2 \\
               0 & 0 & 1 & 4 \\
               0 & 0 & 0 & 8 \ea =:U\ \
(F=\ba{cc}
     1 & 0 \\
     1 & 1 \ea,\ W = \ba{cc}
                       1 & 4 \\
                       -1 & 4 \ea).
$$
In questo esempio di triangolarizzazione di una matrice
si osserva che Gauss con pivot parziale coincide con
Gauss semplice e che $\max|(FW)_{ij}| = 2 \max|(W)_{ij}|$, cio\`e
la disuguaglianza ottenuta prima \`e ottimale.
Nota: $\|A\|_F = \R{13} < \|U\|_F = \R{88}$.

Applicando Givens, per triangolarizzare $A$, si ottiene
$$
E_3 E_2 E_1 A = U = \ba{cccc}
                    2   &  1/2  &   0  &  -1     \\
                    0   & \R{11}/2 &  0  &  -1/\R{11} \\
                    0   &   0   & \R{2} &  0  \\
                    0   &  0    &  0    & \R{2}/\R{11}  \ea.
$$
(vedi pi\`u avanti). Nota: $\|A\|_2 = \|U\|_2 \leq \|A\|_F = \|U\|_F = \R{13}$.

Vedremo che per triangolarizzare una matrice $A$ $n\times n$
occorre calcolare dei prodotti del tipo $FW$ con $F$,$W$ matrici $j\times j$,
$j=n,\ldots,2$. La prima riga di $FW$ coincide con
$[u_{n-j+1,n-j+1} \ldots u_{n-j+1,n}]$ essendo $U$ $n\times n$
la matrice triangolare finale. Gli elementi della prima colonna di $FW$ se si eccettua il primo sono tutti nulli. Inoltre l'elemento $(2,2)$
dell'ultima $FW$ coincide con $u_{nn}$.

In Givens e Householder
$F$ \`e unitaria, quindi $\|FW\|_2=\|W\|_2$, ovvero gli elementi
di $FW$ e $W$ hanno lo stesso ordine di grandezza.

In Gauss $F=GP$,
$$
G = \ba{cccc}
        1 &  0 & \cdots   & 0 \\
   m_{21} &  1 &          &   \\
   \vdots &    &          & 0 \\
   m_{j1} &  0 & \ldots 0 & 1 \ea,\ \ P\  j\times j\  \hbox{di permutazione}
$$
$\then$  $\|FW\|_2 \leq \|F\|_2\|W\|_2$, dove
$$
   \bi{rcl}
\|F\|_2 & = & \|G\|_2 = \max_{\x\,j\times1\,\|\x\|_2=1} \|G\x\|_2 \\
        & \geq & \|G\e_1\|_2 = \R{1+m_{21}^2+\ldots+m_{j1}^2} > 1\ \
  \hbox{se}\ \ G\neq I,  \ei
$$
ovvero gli elementi di $FW$ possono essere in media pi\`u grandi
di quelli di $W$.

Nota: poich\'e
$m_{k1}=-(P\w)_k/(P\w)_1$, $k=2,\ldots,j$, dove $\w$ \`e
il vettore che vogliamo trasformare in
$$
  F\w = \ba{c}
           *  \\
           0  \\
          \vdots \\          .
           0  \ea
$$
($\w$=prima colonna di $W$),
il numero $\R{1+m_{21}^2+\ldots+m_{j1}^2}$ \`e minimo quando $P$ \`e
scelta in modo che $|(P\w)_1|=\max_k |(P\w)_k|$, ovvero in Gauss con
pivot parziale. In Gauss con pivot parziale si ha inoltre:
$\max|(FW)_{ij}| \leq 2 \max|(W)_{ij}|$
(provare a dimostrare questa disuguaglianza)
da cui segue il risultato $\max|u_{ij}|\leq 2^{n-1}\max|a_{ij}|$,
cio\`e gli elementi di U non possono essere pi\`u di $2^{n-1}$ volte
pi\`u grandi di quelli di $A$.

\vskip0.2cm
\hrule
$$
    \ba{cccc}
1/\R{2} & -1/\R{2} &  &  \\
1/\R{2} &  1/\R{2} &  &  \\
      &        & 1&  \\
      &        &  & 1\ea
    \ba{cccc}
       1 & 0 & 0 & 1 \\
      -1 & 1 & 0 & 1 \\
      -1 &-1 & 1 & 1 \\
      -1 &-1 &-1 & 1 \ea
  = \ba{cccc}
     \R{2} & -1/\R{2} & 0 & 0   \\
       0 &  1/\R{2} & 0 & \R{2} \\
      -1 &   -1   & 1 & 1   \\
      -1 &   -1   &-1 & 1   \ea,
$$
$$
\bi{c}
   \ba{cccc}
     \R{2}/\R{3} & 0   & -1/\R{3}  &    \\
       0     & 1   &   0     &    \\
     1/\R{3}   & 0   & \R{2}/\R{3} &    \\
             &     &         &  1 \ea
 \ba{cccc}
     \R{2} & -1/\R{2} & 0 & 0   \\
       0 &  1/\R{2} & 0 & \R{2} \\
      -1 &   -1   & 1 & 1   \\
      -1 &   -1   &-1 & 1   \ea   \\
   = \ba{cccc}
      \R{3} & 0      & -1/\R{3}  & -1/\R{3}   \\
       0  & 1/\R{2}  &  0      &  \R{2}     \\
       0  &-\R{3}/\R{2}&  \R{2}/\R{3}&  \R{2}/\R{3} \\
      -1  & -1     & -1      & 1        \ea,   \ei
$$
$$
    \bi{c}
   \ba{cccc}
     \R{3}/2 & 0 & 0 & -1/2 \\
       0   & 1 & 0 &   0  \\
       0   & 0 & 1 &   0  \\
      1/2  & 0 & 0 & \R{3}/2\ea
   \ba{cccc}
      \R{3} & 0      & -1/\R{3}  & -1/\R{3}   \\
       0  & 1/\R{2}  &  0      &  \R{2}     \\
       0  &-\R{3}/\R{2}&  \R{2}/\R{3}&  \R{2}/\R{3} \\
      -1  & -1     & -1      & 1        \ea            \\
   = \ba{cccc}
       2 & 1/2    &   0     &    -1   \\
       0 & 1/\R{2}  &   0     &   \R{2}   \\
       0 & -\R{3}/\R{2}& \R{2}/\R{3} & \R{2}/\R{3} \\
       0 &-\R{3}/2  & -2/\R{3}  & 1/\R{3}   \ea,         \ei
$$
$$
   \bi{c}
    \ba{cccc}
      1  & 0     &    0    & 0  \\
      0  & 1/2   & -\R{3}/2  & 0  \\
      0  & \R{3}/2 & 1/2     & 0  \\
      0  & 0     &  0      & 1  \ea
   \ba{cccc}
       2 & 1/2    &   0     &    -1   \\
       0 & 1/\R{2}  &   0     &   \R{2}   \\
       0 & -\R{3}/\R{2}& \R{2}/\R{3} & \R{2}/\R{3} \\
       0 &-\R{3}/2  & -2/\R{3}  & 1/\R{3}   \ea        \\
   = \ba{cccc}
       2 & 1/2   &    0        &   -1     \\
       0 & \R{2}   & -\R{2}/2      &    0     \\
       0 &  0    & (\R{2}/\R{3})/2 & 2\R{2}/\R{3} \\
       0 &-\R{3}/2 & -2/\R{3}      & 1/\R{3}    \ea,    \ei
$$
$$
  \bi{c}
    \ba{cccc}
        1 &     0         & 0  &   0       \\
        0 & 2\R{2}/\sqrt{11}& 0  &-\R{3}/\sqrt{11} \\
        0 &     0         & 1  &  0             \\
        0 & \R{3}/\sqrt{11} & 0  & 2\R{2}/\sqrt{11} \ea
    \ba{cccc}
       2 & 1/2   &    0        &   -1     \\
       0 & \R{2}   & -\R{2}/2      &    0     \\
       0 &  0    & (\R{2}/\R{3})/2 & 2\R{2}/\R{3} \\
       0 &-\R{3}/2 & -2/\R{3}      & 1/\R{3}    \ea      \\
    = \ba{cccc}
      2 & 1/2         &   0                &  -1            \\
      0 & \sqrt{11}/2 &   0                & -1/\sqrt{11}   \\
      0 & 0           & (\R{2}/\R{3})/2        & 2\R{2}/\R{3}       \\
      0 & 0           & -(\sqrt{22}/\R{3})/2 & 2\R{2}/\sqrt{33} \ea,  \ei
$$
$$
  \bi{c}
   \ba{cccc}
     1 & 0 &  0                & 0                  \\
     0 & 1 &  0                & 0                  \\
     0 & 0 & (1/\R{3})/2         & -(\sqrt{11}/\R{3})/2 \\
     0 & 0 & (\sqrt{11}/\R{3})/2 & (1/\R{3})/2          \ea
  \ba{cccc}
      2 & 1/2         &   0                &  -1            \\
      0 & \sqrt{11}/2 &   0                & -1/\sqrt{11}   \\
      0 & 0           & (\R{2}/\R{3})/2        & 2\R{2}/\R{3}       \\
      0 & 0           & -(\sqrt{22}/\R{3})/2 & 2\R{2}/\sqrt{33} \ea    \\
   = \ba{cccc}
       2  & 1/2         &  0  &  -1            \\
       0  & \sqrt{11}/2 &  0  & -1/\sqrt{11}   \\
       0  &  0          & \R{2} &   0            \\
       0  &  0          &  0  & 4\R{2}/\sqrt{11} \ea.   \ei
$$

\vskip0.2cm
\hrule
\vskip0.2cm

$\square$ Mostrare che $\|\y\w^*\|_2 = \|\y\w^*\|_F = \|\y\|_2\|\w\|_2$,
$\y,\w$ vettori $n\times 1$,
ricordando che $\|M\|_2=\sqrt{\rho(M^*M)}$ e $\|M\|_F=\sqrt{\tr(M^*M)}$
($\tr(A)=$ traccia di $A$ $= \sum_i a_{ii}$)

\vskip0.1cm

{\it Risoluzione}.
$$
   \|\x\y^*\|_F^2 = \tr(\y\x^*\x\y^*) = \x^*\x [\tr(\y\y^*)]
      = \x^*\x [\y^*\y] = \|\x\|_2^2 \|\y\|_2^2,
$$
$$
  \|\x\y^*\|_2^2 = \rho(\y\x^*\x\y^*) = \x^*\x [\rho(\y\y^*)]
   = \x^*\x [\y^*\y]=\|\x\|_2^2 \|\y\|_2^2
$$
Nota: a entrambi i risultati si puo arrivare usando solo le definizioni di $\|\cdot\|_F$ e $\|\cdot\|_2$ e la disuguaglianza di Schwartz:
$$
\|\y\w^*\|_2 = \max_{\x\ n\times 1\ \|\x\|_2=1} \|\y\w^*\x\|_2
         = \max_{\x\ n\times 1\ \|\x\|_2=1} |\w^*\x|\|\y\|_2
         = \|\y\|_2 \max_{\x\ n\times 1\ \|\x\|_2=1} |\w^*\x|.
$$
Studiamo l'argomento del max: se $\x=\w/\|\w\|_2$, allora
$|\w^*\x|=\|\w\|_2$;
per ogni $\x$, invece, $\|\w^*\x\| \leq \|\w\|_2\|\x\|_2 = \|\w\|_2$.
Ne segue che
$\max_{\x\ n\times 1\ \|\x\|_2=1} |\w^*\x| = \|\w\|_2$.

\vskip0.2cm

{\it Esercizi, II Teorema di Gershgorin, matrici normali e
Teorema di Schur}

\vskip0.2cm

$\square$ $A$,$B$ matrici $n\times n$ non singolari.
\begin{itemize}
\item[a] $\mu(AB)\leq \mu(A)\mu(B)$, $\mu(M)=\|M\|\|M^{-1}\|$
\item[b] $AB$ e $BA$ hanno gli stessi autovalori
(sugg.: dimostrare che $AB$ e $BA$ sono simili)
\item[c] $\mu_2(B^*B)\leq \mu_2(B)^2$
(sugg.: usare a) e b))
\end{itemize}

\vskip0.2cm

$\square$
$$
A=\ba{cccc}
   1 & 1 & 0 & 1 \\
   1 & 1 & 0 & 1 \\
   1 & 1 & a & 1 \\
   1 & 1 & 0 & 1 \ea,\ a\in\CC.
$$
\begin{itemize}
\item[a] Trovare $P$ $4\times 4$ di permutazione tale che
$$
PAP^T = \ba{cccc}
           * & * & * & * \\
           0 & * & * & * \\
           0 & * & * & * \\
           0 & * & * & * \ea
$$
(Nota: righe di $PA =$ permutazione delle righe di $A$;
colonne di $PAP^T =$ permutazione delle colonne di $PA$ con la stessa
legge)
\item[b] per quali valori di $a$ la matrice $A$ ha un autovalore
uguale a $\rho(A)$ ?
\end{itemize}

\vskip0.2cm

$\square$ Dati $\y,\w,\z$ vettori $n\times 1$ dimostrare che il prodotto
matrice vettore $(\y\w^*)\z$ si pu\`o calcolare con $2n$
moltiplicazioni

\vskip0.2cm

$\square$ Mostrare che in generale non \`e vera l'identit\`a $AB=BA$, $A,B$
$n\times n$

\vskip0.2cm

$\square$ Per $A$ $n\times n$ la misura
$\|A\|_F = \sqrt{\sum_{i,j=1,\ldots,n}|a_{ij}|^2}$ \`e una
norma matriciale che non \`e indotta da nessuna norma vettoriale.
Mostrare che $\|A\|_2\leq\|A\|_F$.

\vskip0.2cm

$\square$ Localizzare nel modo migliore possibile gli autovalori di
$$
   A = \ba{ccc}
           10 & 2 &  3 \\
           -1 & 2 & -1 \\
            0 & 1 &  3 \ea.
$$
Nota1: $A$ ha elementi reali $\then$ il polinomio caratteristico di
$A$ ha coefficienti reali $\then$ se $\E$ \`e autovalore di $A$
anche $\o{\E}$ \`e autovalore di $A$.
Nota2: $A$ e $A^T$ hanno gli stessi autovalori

\vskip0.2cm

$\square$ II Teorema di Gershgorin:
Se $m$ cerchi di Gershgorin di $A$ $n\times n$ sono disgiunti dai
rimanenti $n-m$, allora $m$ autovalori sono nell'unione di quegli $m$ cerchi e $n-m$ nell'unione di quegli altri

\vskip0.2cm

$\square$ La matrice
$$
  A = \ba{cc}
        3 & 2 \\
        1 & 2 \ea
$$
\`e diagonalizzabile con una trasformazione unitaria?

\vskip0.2cm

$\square$ $A$ $n\times n$ si dice ``normale'' se $AA^*=A^*A$, ovvero se commuta
con la sua trasposta coniugata.
\begin{itemize}
\item[(1)]
Se $A$ \`e normale e triangolare allora $A$ \`e diagonale.
(sugg.:
fare il caso $n=2$. Per $n$ generico far vedere che
$A$ $n\times n$ triangolare $\then$
$$
   A = \ba{cc}
        a_{11} & \w^T \\
          \vn  & B   \ea
$$
con $B$ $n-1\times n-1$ triangolare,
e che, se $A$ \`e anche normale allora il vettore $\w$ deve essere
nullo e la matrice $B$ deve essere normale.
\item[(2)]
Sia $A=QTQ^*$ con $Q$ unitaria, $T$ triangolare. Allora
$A$ \`e normale se e solo se $T$ \`e normale.
{\it Teorema di Schur}: Data $A$ $n\times n$ esiste $Q$ unitaria
tale che $A=QTQ^*$ con $T$ triangolare, ovvero ogni matrice si pu\`o
trasformare in triangolare con una trasformazione per similitudine
unitaria. Dimostrazione: omessa.
\item[(3)]
$A$ $n\times n$ si pu\`o diagonalizzare con una trasformazione per
similitudine unitaria se e solo se \`e normale
(sugg. usare il teorema di Schur e i risultati (1) e (2))
\end{itemize}

\vskip0.2cm

$\square$
$$
  A = \ba{cccc}
      9 & 1 & -2 & 1 \\
      0 & 8 &  1 & 1 \\
     -1 & 0 &  7 & 0 \\
      1 & 0 &  0 & 1 \ea, \ \
   B = \ba{cccc}
       -9 & 1 &-2 & 0 \\
        1 & 8 & 0 & 1 \\
       -2 & 0 & 7 & 0 \\
        0 & 1 & 0 & 2 \ea
$$
\begin{itemize}
\item[i] osservare che $A$ ha almeno due autovalori reali
\item[ii] trovare un limite superiore di $\mu_2(B)$
\end{itemize}

\vskip0.2cm

$\square$ Sia $p$ un numero naturale.
Se $A^p=0$, allora gli autovalori $\E$ di $A$ sono tutti nulli.
Se $A^p=I$, allora gli autovalori $\E$ di $A$ devono risolvere l'equazione algebrica $z^p-1=0$

\vskip0.2cm

21 Aprile 2009

\vskip0.2cm

{\it Come annullare tutti gli elementi di un vettore eccetto il primo}

$\square$ Dato $\w$ vettore $j\times 1$ trovare $F$ matrice $j\times j$
tale che $(F\w)_k=0$, $k=2,\ldots,j$,
cio\`e:
$$
\w= \ba{c}
   w_1 \\
   w_2 \\
 \vdots\\
   w_j \ea \quad \to \quad F\w = \ba{c}
                                   * \\
                                   0 \\
                               \vdots\\
                                   0 \ea.
$$
Vediamo quattro matrici $F$ con questa propriet\`a:
\begin{itemize}
\item[(1)]
Metodo di Gauss:
$F=GP$ dove $P$ di permutazione tale che $(P\w)_1 \neq 0$ e
$$
 G =  \ba{ccccc}
      1            &  0     &       & \cdots &  0     \\
    -(P\w)_2/(P\w)_1 &  1     &  0    & \cdots &  0     \\
           .       &  0     &\ddots &        & \vdots \\
      \vdots       & \vdots &       &        &  0     \\
    -(P\w)_j/(P\w)_1 &  0     &\cdots &   0    &  1     \ea
$$
\item[(2)]
Metodo di Gauss con pivot parziale:
come (1), ma si richiede $|(P\w)_1|=\max_{k=1,\ldots,j} |(P\w)_k|$.
Con questa scelta di $P$ gli elementi della matrice $G$ hanno tutti
modulo minore o uguale a $1$ $\then$
se $\z$ \`e un vettore affetto da errore questo errore
non \`e amplificato nel calcolo di $G\z$ $\then$
pi\`u stabile (meno accumulazione degli errori di
arrotondamento) di Gauss
\item[(3)]
Metodo di Givens ($F$ unitaria):
$F=Q_j\cdots Q_3Q_2$, $Q_k$ matrice $j\times j$ di Givens.

$a=w_1/\sqrt{w_1^2+w_2^2}$, $b=w_2/\sqrt{w_1^2+w_2^2}$,
$$
  Q_2\w = \ba{ccccc}
           a & b &   &       &   \\
          -b & a &   &       &   \\
             &   & 1 &       &   \\
             &   &   &\ddots &   \\
             &   &   &       & 1 \ea
                \ba{c}
                   w_1   \\
                   w_2   \\
                  \vdots \\
                   w_j   \ea
         = \ba{c}
             \sqrt{w_1^2+w_2^2} \\
               0    \\
               w_3  \\
             \vdots \\
               w_j  \ea
$$
$a=\sqrt{w_1^2+w_2^2}/\sqrt{w_1^2+w_2^2+w_3^2}$,
$b=w_3/\sqrt{w_1^2+w_2^2+w_3^2}$,
$$
Q_3Q_2w =  \ba{cccccc}
             a & 0 & b &   &        &    \\
             0 & 1 & 0 &   &        &    \\
            -b & 0 & a &   &        &    \\
               &   &   & 1 &        &    \\
               &   &   &   & \ddots &    \\
               &   &   &   &        &  1 \ea
          \ba{c}
             \sqrt{w_1^2+w_2^2} \\
              0                 \\
              w_3               \\
             \vdots             \\
              w_j               \ea
       = \ba{c}
           \sqrt{w_1^2+w_2^2+w_3^2} \\
              0                     \\
              0                     \\
              w_4                   \\
             \vdots                 \\
              w_j                   \ea
$$
e cosi' via...

\item[(4)] Metodo di Householder ($F$ unitaria):
$F =$ matrice di Householder $= I-(2/\u^*\u)\u\u^*$, $\u$ vettore
$j\times 1$ opportuno
\end{itemize}
\vskip0.2cm

$\square$ Utilizzando i metodi (1),(2),(3) trasformare i vettori
$$
\w = \ba{c}
         0            \\
       1/\sqrt{3}     \\
    \sqrt{2}/\sqrt{3} \ea,\ \
\w = \ba{c}
       1/\sqrt{2}    \\
       1/2     \\
       1/2 \ea
$$
in un vettore del tipo
$$
F\w = \ba{c}
          * \\
          0 \\
          0 \ea
$$

\vskip0.2cm

{\it Numero di condizionamento di una matrice}

\vskip0.2cm

$\square$ Mostrare che le seguenti due matrici
$$
          \ba{cc}
             1 & 1/2 \\
            1/2 & 1/3 \ea, \ \
\ba{ccc}
   1  &  1/2 & 1/3 \\
  1/2 & 1/3  & 1/4 \\
  1/3 & 1/4  & 1/5 \ea
$$
sono definite positive.
Calcolare il loro numero di condizionamento

\vskip0.2cm

$\square$ Usando l'identit\`a $1/(i+j-1) = \int_0^1 x^{i+j-2}dx$,
mostrare che la matrice ``di Hilbert''
$$
A = \ba{cccc}
     1 &  1/2 & \cdots & 1/n \\
   1/2 &  1/3 & \cdots & 1/(n+1) \\
       &      &        &         \\
   1/n & 1/(n+1) & \cdots & 1/(2n-1) \ea
   = ( 1/(i+j-1) )_{i,j=1\ldots n}
$$
\`e definita positiva.
La matrice di Hilbert ha un numero di condizionamento che
cresce molto rapidamente con n

\vskip0.2cm

$\square$ Per $A$ $n\times n$ non singolare sia $\mu(A)=\|A\|\|A^{-1}\|$ il
``numero di condizionamento'' di $A$.
Dal risultato:
$A\x=\b$ $\&$ $A(\x+d\x)=\b+d\b$ $\then$
$\|d\x\| / \|\x\| \leq \mu(A)\|d\b\|/\|\b\|$
(valido se la norma matriciale \`e indotta da quella vettoriale),
segue che $\mu(A)$ misura la sensibilit\`a della soluzione di un
sistema lineare a una eventuale perturbazione del vettore dei
termini noti.
Ad esempio la soluzione del sistema
$$
  A\x =  \ba{cc}
      1 & 900 \\
      0 & 1   \ea
    \ba{c}
       x_1 \\
       x_2 \ea
  = \ba{c}
       b_1 \\
       b_2 \ea
$$
\`e molto sensibile a variazioni di $b_1,b_2$ perch\'e
$\mu(A) \approx 10^6$ e, quindi, una perturbazione su $\b$ pu\`o
causare una grande perturbazione su $\x$

\vskip0.2cm

$\square$ Valgono le seguenti affermazioni:
\begin{itemize}
\item[(1)] $\mu(A)\geq \max|\E_i|/\min|\E_i|\geq 1$, $\E_i$ autovalori di $A$
\item[(2)] Se $A$ \`e hermitiana e $\|\cdot\|$ \`e la norma spettrale
(cio\`e la norma matriciale indotta dalla norma vettoriale euclidea),
allora $\mu(A)=\max|\E_i|/\min|\E_i|$
\item[(3)] Se $A$ \`e definita positiva e $\|\cdot\|$ \`e la norma spettrale,
allora $\mu(A)=\max \E_i/\min \E_i$
\end{itemize}

\vskip0.2cm

$\square$ Scrivere una limitazione superiore per $\mu(A)$ essendo $A$ la matrice
tridiagonale
$$
A = \ba{ccccc}
     2+h^2p_1 & -1       &       &       &          \\
      -1      & 2+h^2p_2 & -1    &       &          \\
              & -1       & \ddots& \ddots&          \\
              &          & \ddots& \ddots& -1       \\
              &          &       & -1    & 2+h^2p_n \ea ,
$$
con $p_i$ reali positivi per ogni $i$

\vskip0.2cm

$\square$ Il numero di condizionamento delle matrici
$$
   \ba{cc}
       1   & 0 \\
    m_{21} & 1 \ea, \ |m_{21}|\leq 1,\
   \ba{ccc}
     1  &   0 &   0 \\
m_{21}  &   1 &   0 \\
m_{31}  &   0 &   1 \ea,\  |m_{i1}|\leq 1,
$$
\`e maggiore di $1$.

\vskip0.2cm

$\square$ Il numero di condizionamento di ogni matrice unitaria, misurato con
la norma spettrale, \`e uguale a $1$

\vskip0.2cm

{\it Norme matriciali}

\vskip0.2cm

$\square$ Data $\|\cdot\|$ norma vettoriale, per $A$ $n\times n$ si pu\`o
usare come misura di $A$ il numero
$\|A\| = \sup_{\z\ n\times 1\neq\vn} (\|A\z\|/\|\z\|)$.
Questo numero soddisfa le seguenti propriet\`a:
\begin{itemize}
\item[(1)] $\|A\|\geq 0$
\item[(2)] $\|A\|=0$ iff $A=0$
\item[(3)] $\|aA\|=|a|\|A\|$
\item[(4)] $\|A+B\|\leq\|A\|+\|B\|$
\item[(5)] $\|AB\|\leq\|A\|\|B\|$
\end{itemize}
($A,B$ $n\times n$, $a$ $1\times 1$)

Ogni numero che soddisfa tali propriet\`a \`e detto ``norma matriciale''

\vskip0.2cm

$\square$ Dimostrare che $\rho(A)=\max|\E_i|$, $\E_i$ autovalori di $A$
$n\times n$, non \`e una norma matriciale

\vskip0.2cm

$\square$ Per le norme matriciali ``indotte'' dalle norme vettoriali
$\|\cdot\|_2$, $\|\cdot\|_1$, $\|\cdot\|_{\infty}$, si dimostra che
$\|A\|_2 = \sqrt{\rho(A^*A)}$,
$\|A\|_1 = \max_j \sum_i |a_{ij}|$,
$\|A\|_{\infty} = \max_i \sum_j |a_{ij}|$.
Se $\|\cdot\|$ \`e una norma matriciale indotta da una norma vettoriale
ed $I$ \`e la matrice identica allora $\|I\|=1$.
Esempi di norme matriciali che non sono indotte da norme vettoriali
sono:
$\|A\|_F = \sqrt{\sum_{i,j} |a_{ij}|^2} = \sqrt{ \tr(A^*A) }$
``norma di Frobenius''
e $\|A\| = n \max_{i,j} |a_{ij}|$,
infatti se si misura la matrice identica con tali norme si ottengono
numeri maggiori di $1$.
Le norme matriciali, come quelle vettoriali, sono equivalenti tra loro.

\vskip0.2cm

$\square$ La maggiorazione per il raggio spettrale (di una matrice) ottenuta in
precedenza si pu\`o riscrivere come segue:
$\rho(A)\leq \min\{\|A\|_1,\|A\|_{\infty}\}$.
Tale risultato si pu\`o generalizzare:
per ogni norma matriciale $\|\cdot\|$ indotta da una norma vettoriale
si ha $\rho(A)\leq\|A\|$.
In realt\`a la limitazione  $\rho(A)\leq\|A\|$ \`e vera per ogni norma matriciale $\|\cdot\|$.
Quindi, ogni cerchio del piano complesso del tipo
$\{z\in\CC:\ |z|\leq\|A\|\}$
(di centro $(0,0)$ e raggio $\|A\|$) con $\|\cdot\|$ norma matriciale
qualsiasi deve contenere tutti gli autovalori di $A$

\vskip0.2cm

$\square$ Dimostrare che per $A$ $n\times n$ il numero
$\max_{i,j} |a_{i,j}|$ \`e una misura di $A$ che
non \`e una norma matriciale

\vskip0.2cm

$\square$ Sia $A$ $n\times n$ generica e $Q$ $n\times n$ unitaria.
Allora
\begin{itemize}
\item[(1)] $\|Q\|_2=1$
\item[(2)] $\|QA\|_2=\|AQ\|_2=\|A\|_2$
\item[(3)] $\|Q\|_F=\sqrt{n}$
\item[(4)] $\|QA\|_F=\|AQ\|_F=\|A\|_F$
\item[(5)] $\|A\|_{2,F}=\|A^H\|_{2,F}$
\item[(6)] $(\|A\|_2)^2 \leq \|A\|_1\|A\|_{\infty}$
\item[(7)] esiste $A$ $n\times n$ tale che $\|A\|_2>\|A\|_{\infty}$
\end{itemize}

{\it Risoluzione}.
(5)
$\|A\|_2^2=\rho(A^*A)\leq\|A^*A\|_2\leq\|A^*\|_2\|A\|_2$ $\then$
$\|A\|_2\leq\|A^*\|_2$. Si dimostra allo stesso modo che $\|A^*\|_2\leq\|A\|_2$.

\vskip0.1cm

(6)
$\|A\|_2^2=\rho(A^*A)\leq\|A^*A\|_1\leq\|A^*\|_1\|A\|_1=\|A\|_{\infty}\|A\|_1$.

\vskip0.1cm

(7) Sia
$$
A=\ba{cc} 1 & 10 \\ 1 & 10 \ea
$$
Allora $\|A\|_{\infty}=11$, $\|A\|_1=20$,
$\|A\|_2\geq\f{\|A\e_2\|_2}{\|\e_2\|_2}=10\R{2}$ $\then$
$\|A\|_2>\|A\|_{\infty}$.

Un altro esempio. Sia $A=\al\e\e^T+\be\e\e_j^T$, $\e^T=[1\ 1 \cdots 1]$, $\al\geq 0$, $\be>0$ $\then$
$\|A\|_{\infty}=n\al+\be$, $\|A\|_1=n(\al+\be)$,
$\|A\|_2\geq\f{\|A\e_j\|_2}{\|\e_j\|_2}=\R{n}(\al+\be)$. Quindi, se
$\be>\R{n}\al$ allora $\|A\|_2>\|A\|_{\infty}$.

Nota: per (6), ogni volta che $\|A\|_2>\|A\|_{\infty}$ deve essere necessariamente verificata la disuguaglianza $\|A\|_2<\|A\|_1$.

\vskip0.3cm

$\square$ Calcolare il numero
$\mu_1(A)=\|A\|_1 \|A^{-1}\|_1$
per
$$
  A = \ba{cc}
        1 & 900 \\
        0 &  1  \ea
$$

\vskip0.2cm

7 Aprile 2009, 4 Aprile 2009, 22 Marzo 2009, 15 Marzo 2009,
7 Marzo 2009

\vskip0.2cm

7 aprile era perFra

\vskip0.2cm

4 Aprile 2009

\vskip0.2cm

$\square$ Sia $A=\u\v^*$, con $\u,\v$ vettori $n\times 1$.
Dimostrare:
\begin{itemize}
\item[(1)] $\sqrt{\rho(A^*A)}=\|\u\|_2\|\v\|_2$
\item[(2)] $\max_i \sum_j |a_{ij}| = \|\u\|_{\infty}\|\v\|_1$
\item[(3)] $\max_j \sum_i |a_{ij}| = \|\u\|_1\|\v\|_{\infty}$
\item[(4)] $\rho(A)=|\v^*\u| \leq
           \min\{\|\u\|_2\|\v\|_2,
                 \|\u\|_1\|\v\|_{\infty},\|\u\|_{\infty}\|\v\|_1\}$
\item[(5)] Esistono $\u,\v$ per cui
$|\v^*\u|\leq\|\u\|_1\|\v\|_{\infty}<\|\u\|_2\|\v\|_2$
\end{itemize}

\vskip0.2cm

$\square$ Usando il I teorema di Gershgorin osservare che esiste
un intervallo positivo della retta reale che contiene i due
autovalori di
$$
A = \ba{cc}
      1 & -1/2 \\
   -1/2 &  1   \ea
$$
(non calcolare gli autovalori).
Essendo $A$ anche hermitiana ne segue che $A$ \`e definita positiva.

\vskip0.2cm

$\square$ E' possibile stabilire usando il I teorema di Gershgorin se
$$
A = \ba{cc}
       1 & 1/2 \\
     1/2 & 1/3 \ea
$$
\`e definita positiva?
Dimostrare che A \`e definita positiva.

\vskip0.2cm

$\square$ Data
$$
A = \ba{cccc}
     1 & 1/4 &  2 &  1   \\
    1/2&   2 &   0&  1-\sqrt{2} \\
     0 &  1/2&  -3&   0  \\
   -\ui/2&  1/2&   1&  1+\ui \ea
$$
disegnare i seguenti insiemi, tutti contenenti gli autovalori di $A$:
\begin{itemize}
\item[(1)] $\{ z:\ |z|\leq\min\{\max_i \sum_j |a_{ij}|,
                          \max_j \sum_i |a_{ij}|\} \}$
\item[(2)] $U_{i=1\ldots n} K_i$, $K_i$ cerchi di Gershgorin di $A$
\item[(3)] $U_{i=1\ldots n} H_i$, $H_i$ cerchi di Gershgorin di $A^T$
\item[(4)] $(U_{i=1\ldots n} K_i)\ \bigcap\ (U_{i=1\ldots n} H_i)$
\end{itemize}
Si pu\`o stabilire se $A$ \`e non singolare senza calcolare il suo
determinante?

\vskip0.2cm

$\square$ I T. di Gershgorin:
Sia $A$ $n\times n$ generica. Gli autovalori di $A$ sono nell'insieme
$U_{i=1\ldots n} K_i$,
$K_i = \{z:\ |z-a_{ii}| \leq \sum_{j,j \neq i} |a_{ij}|\}$

\vskip0.2cm

$\square$ Rafforzare il I T.di Gershgorin usando l'osservazione che
$A$ e $A^T$ hanno gli stessi autovalori.

\vskip0.2cm

$\square$ Localizzare gli autovalori della matrice
$$
A = \ba{ccc}
     1 & 2   & 3 \\
    -1 & 1/2 & 1 \\
     4 & 2   & 1 \ea
$$

\vskip0.2cm

$\square$ Dimostrare, senza calcolare gli autovalori, che la matrice
$$
A = \ba{cc}
      3 & 2 \\
      1 & 2 \ea
$$
ha autovalori reali

\vskip0.2cm

$\square$ Sia $Q$ unitaria $n\times n$. Dimostrare l'identit\`a
$\|Q\x\|_2=\|\x\|_2$, ovvero
applicando una matrice unitaria a un vettore la misura in norma
euclidea del vettore non cambia.

\vskip0.2cm

$\square$ Sia $\w$ $n\times 1$.
Se $F$ $n\times n$ unitaria \`e tale che
$$
Fw = \ba{c} a \\ 0 \\ \vdots \\ 0 \ea,
$$
cio\`e $(F\w)_i=0$, $i=2\ldots n$, allora $|a|=\|w\|_2$.

\vskip0.2cm

$\square$ Dare una maggiorazione per $\rho(A)$ essendo
$$
A = \ba{ccc}
      1 & 2   & 3 \\
     -1 & 1/2 & 1 \\
      4 & 2   & 1 \ea
$$

\vskip0.2cm

$\square$ Scrivere l'inversa della matrice $A$ $n\times n$
$$
a_{i,i}=1,\  i=1\ldots n,\
a_{i,i+1}=-1,\  i=1\ldots n-1,\
a_{n,1}=a,\
a_{i,j}=0\ \hbox{altrimenti}.
$$

\vskip0.2cm

$\square$ Sia $A=A^*$ $n\times n$. Allora le seguenti affermazioni
sono equivalenti:
\begin{itemize}
\item[(1)] $\z^*A\z>0$ per ogni vettore $\z$ non nullo
\item[(2)] gli autovalori di $A$ sono positivi
\item[(3)] le sottomatrici di $A$
$$
\ba{ccc}
a_{11} & \cdots & a_{1k} \\
\vdots &        & \vdots \\
a_{k1} & \cdots & a_{kk} \ea
$$
hanno determinante positivo per $k=1,\ldots,n$.
\end{itemize}
($A$ tale che $A=A^*$ e vale (1) si dice definita positiva).

Vedremo che in certi casi \`e possibile
dire che gli autovalori sono positivi senza calcolarli e questo, per
la (2), \`e sufficiente per stabilire che $A$ \`e definita positiva

\vskip0.2cm

$\square$ (PER ME) Sia $A$ la matrice $2\times 2$
$$
A = \ba{cc}
     c  &   a \\
   \o{a}&  b   \ea,
$$
$a$ numero complesso, $b,c$ reali.
Si osserva che $A$ \`e hermitiana.

1) Condizione necessaria affinch\'e $A$ sia definita positiva \`e
che $b$ e $c$ siano positivi.

2) Condizione necessaria e sufficiente affinch\'e $A$
sia definita positiva \`e che $c>0$, $b/c>0$, $\sqrt{b/c}-|a/c|>0$
ovvero che $c>0$ $\&$ $bc-|a|^2>0$.

Suggerimento: applicare il risultato ottenuto nell'esercizio precedente

\vskip0.1cm

{\it Risoluzione}
$$
   A = \ba{cc}
         c   & a \\
       \o{a} & b \ea,\ b,c\in\RR,\ \
   A = c \ba{cc}
           1  &  a/c \\
      \o{a/c} &  b/c \ea
$$
definita positiva iff
$$
   c>0\ \ \& \ \ \ba{cc}
                    1  &  a/c \\
              \o{a/c}  &  b/c \ea \ \ \pd
$$
iff $c>0$, $b/c>0$, $\sqrt{b/c}-|a/c|>0$
iff $c>0$ $\&$ $bc-|a|^2>0$

\vskip0.2cm

$\square$ (PER ME) Sia $A$ la matrice $2\times 2$
$$
A = \ba{cc}
     1   &   a \\
   \o{a} &   b \ea,
$$
$a$ numero complesso, $b$ reale.
Si osserva che $A$ \`e hermitiana

1) Condizione necessaria affinch\'e $A$ sia definita positiva \`e
che $b$  sia positivo.

2) Condizione necessaria e sufficiente affinch\'e $A$ sia definita
positiva \`e che $b$ sia positivo $\&$ $\sqrt{b}-|a|>0$ o,
equivalentemente,
che $b-|a|^2$ sia positivo.

Trovare una formula per $\z^*A\z$ che consenta di dedurre tale
affermazione senza calcolare esplicitamente gli autovalori.

\vskip0.1cm

{\it Risoluzione}

$a$, $b$ numeri complessi $\then$
$$
  \z^*A\z = |z_1|^2 + b|z_2|^2 + z_1\o{z_2}\o{a} + \o{z_1}z_2a.
$$
b reale positivo $\then$
$$
  \z^*A\z = (1-\f{|a|}{\sqrt{b}})(|z_1|^2+b|z_2|^2)
    + \f{|a|}{\sqrt{b}} |z_1+\sqrt{b}\exp{\ui\arg(a)}z_2|^2.
$$
Ne segue che $A$ \`e definita positiva se e solo se $b>0$ $\&$
$\sqrt{b}-|a|>0$ se e solo se $b-|a|^2>0$

\vskip0.2cm

$\square$ La matrice
$$
A = \ba{cc}
       1  &  a \\
   \o{a}  &  1 \ea,
$$
$a$ numero complesso,
\`e definita positiva se e solo se $1-|a|>0$ (o, equivalentemente,
se e solo se $1-|a|^2>0$).
Trovare una formula per $\z^*A\z$ che consenta di dedurre (senza
calcolare esplicitamente gli autovalori) tale affermazione.
Suggerimento: studiare i casi $a$ reale negativo (vedi $a=-1/2$
del precedente esercizio), poi $a$ reale positivo e infine
$a$ generico.

\vskip0.1cm

{\it Risoluzione}
$$
   \z^*A\z = |z_1|^2+|z_2|^2+z_1\o{z_2}\o{a}+z_2\o{z_1}a.
$$
\begin{itemize}
\item[]
$a$ reale positivo: $\z^*A\z = (1-a)(|z_1|^2+|z_2|^2)+a|z_1+z_2|^2$,
\item[]
$a$ reale negativo: $\z^*A\z = (1+a)(|z_1|^2+|z_2|^2)-a|z_1-z_2|^2$,
\item[]
$a$ generico:       $\z^*A\z = (1-|a|)(|z_1|^2+|z_2|^2)
                          +|a||z_1+\exp{\ui\arg(a)}z_2|^2$.
\end{itemize}
Ne segue che $A$ \`e definita positiva se e solo se $1-|a|>0$.

\vskip0.2cm

$\square$ Dimostrare, senza calcolare gli autovalori, che la matrice
$$
A = \ba{cc}
      1 &  -1/2 \\
   -1/2 &  1    \ea
$$
\`e definita positiva.

{\it Risoluzione}:
1) $A$ \`e reale simmetrica, quindi \`e hermitiana.
2) Inoltre,
$$
\bi{rcl}
\z^*A\z & = & [\o{z_1}\ \o{z_2}]
              \ba{cc}
                  1 &  -1/2 \\
               -1/2 &   1 \ea \ba{c} z_1 \\ z_2 \ea
      = [\o{z_1}-1/2\o{z_2}\  -1/2\o{z_1}+\o{z_2}]\ba{c}
                                                     z_1 \\
                                                     z_2 \ea  \\
      & = & |z_1|^2-1/2z_1\o{z_2}-1/2\o{z_1}z_2+|z_2|^2
      = 1/2(|z_1|^2+|z_2|^2) + 1/2(z_1-z_2)(\o{z_1}-\o{z_2}) \\
     & = & 1/2(|z_1|^2+|z_2|^2) + 1/2|z_1-z_2|^2
      >= 1/2(|z_1|^2+|z_2|^2).  \ei
$$
Ne segue che $\z^*A\z>0$ per ogni vettore $\z=[z_1\ z_2]^T$
non nullo.

\vskip0.2cm

{\it Norme vettoriali}:

\vskip0.2cm

$\square$ $a$ scalare ($1\times 1$), $|a|=$ modulo di $a$
                    $=$ misura della distanza tra i punti
                     $(0,0)$ e $(\Re(a),\Im(a))$
                    $=\sqrt{\Re(a)^2+\Im(a)^2}$.

$\square$ $\z$ $n\times 1$,
$\|\z\|=\|\z\|_2=(\sum_i |z_i|^2)^{1/2}=$ misura
``euclidea'' di $\z$.
Propriet\`a:

\begin{itemize}
\item[(1)] $\|\z\|\geq 0$ per ogni $\z$
\item[(2)] $\|\z\|=0$ iff $\z=\vn$
\item[(3)] $\|a\z\|=|a|\|\z\|$, per ogni $a$ scalare e $\z$
\item[(4)] $\|\z+\w\|\leq\|\z\|+\|\w\|$, per ogni $\z,\w$
\end{itemize}

Ogni misura che soddisfa tali propriet\`a \`e detta
``norma vettoriale''.

Ad esempio sono norme vettoriali anche
$\|\z\|=\|\z\|_1=\sum_i |z_i|$ e
$\|\z\|=\|\z\|_{\infty}=\max_i |z_i|$
(verificarlo).

Per ogni $\z$ $n\times 1$ non nullo il vettore $\y=\z/\|\z\|$
ha norma uguale a $1$, infatti,
per la terza propriet\`a delle norme vettoriali,
$\|\z/\|\z\|\|=(1/\|\z\|)\|\z\|=1$.

Esempi:
$$
     \z = \ba{c}
            1/2 \\
            1/2 \ea\ \then\ \|\z\|_2=\f{1}{\sqrt{2}},\ \|\z\|_1=1,
          \ \|\z\|_{\infty}=1/2
$$
$$
    \then\ \y=\z/\|\z\|_2 = \ba{c} \sqrt{2}/2 \\ \sqrt{2}/2 \ea,\
       \y=\z/\|\z\|_1 = \ba{c} 1/2 \\ 1/2 \ea,\
     \y=\z/\|\z\|_{\infty} = \ba{c} 1 \\ 1 \ea.
$$
E' semplice far vedere che, per ogni vettore $\z$ $n\times 1$,
$(1/n)\|\z\|_1\leq\|\z\|_{\infty}\leq\|\z\|_1$.

Pi\`u in generale comunque prese due norme vettoriali
$\|\cdot\|_a$ e $\|\cdot\|_b$
queste sono equivalenti, cio\`e esistono $c_1$ e $c_2$ costanti
positive per cui $c_1\|\z\|_b\leq\|\z\|_a\leq c_2\|\z\|_b$
per ogni $\z$.
Ne segue che, se un vettore ha misura grande (piccola) in una
norma allora ha misura grande (piccola) in ogni altra norma.
Inoltre, se per una certa norma $\|\cdot\|_b$ si ha che
$\|\z_k-\z\|_b\to 0$
(per $k$ che tende a infinito) allora sar\`a anche vero che
$\|\z_k-\z\|\to 0$ in ogni norma vettoriale $\|\cdot\|$.

\vskip0.2cm

{\it Due limitazioni superiori per il raggio spettrale}:

\vskip0.2cm

$\square$
$$
A\ n\times n\ \ \then
\rho(A) \leq \max_i \sum_j |a_{ij}|,\ \
\rho(A)\leq \max_j \sum_i |a_{ij}|
$$
Dim: $A\v=\E\v$ $\then$ $\sum_j a_{ij}v_j=\E v_i$ per ogni $i$
$\then$
$|\E||v_i| \leq \sum_j |a_{ij}||v_j|
\leq \|\v\|_{\infty} \sum_j |a_{ij}|$ per ogni $i$
$\then$ esiste $k$ tale che $|\E|\leq \sum_j |a_{kj}|
\leq\max_i \sum_j |a_{ij}|$.
La seconda disuguaglianza si ottiene applicando la prima ad $A^T$ ed
osservando che $\rho(A)=\rho(A^T)$ (gli autovalori di $A^T$
coincidono con quelli di $A$).

\vskip0.2cm

{\it Teoria(metododellepotenze)}
[per il calcolo dell'autovalore in modulo dominante di una matrice e
del corrispondente autovettore]:

\vskip0.2cm

$A$ $n\times n$ diagonalizzabile, ovvero $A\v_i=\E_i\v_i$,
$i=1,\ldots,n$, con $\v_1,\ldots,\v_n$
linearmente indipendenti.
$|\E_1|>|\E_j|$ per ogni $j \neq 1$, ovvero c'\`e un solo autovalore
il cui modulo \`e uguale al raggio spettrale di $A$ e tale autovalore
\`e semplice
(cio\`e \`e radice semplice del polinomio caratteristico di $A$).
$\x$ $n\times 1$ tale che $a_1$ in $\x=a_1\v_1+a_2\v_2+\ldots+a_n\v_n$
\`e diverso da zero.
In queste ipotesi si ha, per $k$ che tende a infinito,
\begin{itemize}
\item
 $(1/\E_1^k)A^k\x \to a_1\v_1$, quindi
  $(\exp{-\ui a})^k A^k\x/\|A^k\x\| \to a_1\v_1/\|a_1\v_1\|$
dove $a$ \`e l'argomento di $\E_1$ ($\E_1=|\E_1|\exp{\ui a}$).
\item
 per ogni $\v$, $\v^T\v_1 \neq 0$, $\v^TA^{k+1}\x/\v^TA^k\x \to \E_1$
(nota: $\v^T\v_1 \neq 0$ $\then$ $\v^TA^k\x \neq 0$ per $k$ grande).
\end{itemize}

Ne segue che le successioni $\{\z_k\},\{\y_k\}$ generate
dall'algoritmo:
$$
  \bi{l}
    \y_{-1}=\x    \\
    \hbox{Per}\ k=0,1\ldots  \\
     \z_k=\y_{k-1}/\|\y_{k-1}\|,\ \y_k=A\z_k\
       (\hbox{NOTA}:\ \z_k=A^k\x/\|A^k\x\|)  \ei
$$
soddisfano le propriet\`a:
\begin{itemize}
\item[(1)]
 $(\exp{-\ui a})^k \z_k \to a_1\v_1/\|a_1\v_1\|$
\item[(2)]
 $\v^T\y_k/\v^T\z_k \to \E_1$
($\v^T\v_1 \neq 0$ $\then$ $\v^T\z_k \neq 0$ per $k$ grande)
\end{itemize}

Dim della NOTA. Per induzione:
$$
     \z_0=\f{\y_{-1}}{\|\y_{-1}\|}=\f{\x}{\|\x\|},\ \ ok!
$$
$$
    \z_{k+1} = \f{\y_k}{\|\y_k\|} = \f{A\z_k}{\|A\z_k\|}
             = \f{AA^k\x}{\|AA^k\x\|}
             = \f{A^{k+1}\x}{\|A^{k+1}\x\|},\ \ ok!
$$
Dim di (1) e (2). Usare la NOTA. Ad esempio, per (2):
$$
    \f{\v^T\y_k}{\v^T\z_k} = \f{\v^TA\z_k}{\v^T\z_k}
          = \f{\v^TA^{k+1}\x/\|A^k\x\|}
              {\v^TA^k\x/\|A^k\x\|}
          = \f{\v^TA^{k+1}\x}{\v^TA^k\x}.
$$

\vskip0.2cm

Esercizi:

\vskip0.2cm

$\square$ Sia $A$ la matrice
$$
   \ba{cc}
     1 &  -1/2  \\
  -1/2 &    1   \ea.
$$
Scrivere un algoritmo per il calcolo dell'autovalore di
modulo massimo e del corrispondente autovettore (usare il metodo
delle potenze con $\|\z\|=\sum_i |z_i|$)

{\it Risoluzione}:
$A$ \`e diagonalizzabile e $|\E_1|>|\E_2|$:
$A=VDV^{-1}$,
$$
   D = \ba{cc}
         1/2 & 0 \\
         0 & 3/2 \ea,
    V = \f{1}{\sqrt{2}} \ba{cc}
                           1 & 1 \\
                           1 & -1 \ea
$$
(Nota: $V=V^*=V^{-1}$). In altri termini
$A\v_1=\E_1\v_1$, $A\v_2=\E_2\v_2$,
$\v_1=\ba{c} 1 \\ -1 \ea$, $\E_1=3/2$, $\v_2=\ba{c} 1\\ 1 \ea$,
$\E_2=1/2$
e $\v_1,\v_2$ sono linearmente indipendenti.
Sia $\x$ il vettore $\ba{c} 1 \\ 0 \ea$.
$a_1$ in $\x=a_1\v_1+a_2\v_2$ \`e diverso da zero, infatti
$$
    \ba{c}
        1 \\
        0 \ea = \um \ba{c} 1 \\ 1 \ea
                + \um \ba{c} 1 \\ -1 \ea.
$$
Quindi, se $\y_{-1}=\x$ e per $k=0,1,\ldots$ si definisce
la coppia di vettori
$\z_k=\y_{k-1}/\|\y_{k-1}\|$, $\y_k=A\z_k$
(nota: $\z_k=A^k\x/\|A^k\x\|$)
allora, per $k$ che tende a infinito,
$$
    \z_k \to a_1\v_1/\|a_1\v_1\| = \ba{c} 1/2 \\ -1/2 \ea,
   \v^T\y_k/\v^T\z_k \to \E_1=3/2 \ \ \fa\,\v,\, \v^T\v_1 \neq 0
$$
(nota: $\v^T\v_1 \neq 0$ $\then$ $\v^T\z_k \neq 0$ per $k$ grande).

\vskip0.2cm

$\square$ Eseguiamo i primi passi con
$\v=\ba{c}1\\0\ea$ ($\v=\ba{c}1\\1\ea$
non ok perch\'e $\v^T\v_1=0$)
$$
   \bi{l}
\z_0 = \ba{c}1\\0\ea,\ \y_0 = \ba{c}1\\-1/2\ea,\
\v^T\y_0/\v^T\z_0=1 \\
\z_1 = \ba{c}2/3\\-1/3\ea,\ \y_1 = \ba{c}5/6\\-4/6\ea,\
\v^T\y_1/\v^T\z_1=5/4 \\
\z_2 = \ba{c}5/9\\-4/9\ea,\ \y_2 = \ba{c}14/18\\-13/18\ea,\
\v^T\y_2/\v^T\z_2=14/10 \ei
$$
$\ldots$

\vskip0.2cm

$\square$ Ripetere l'esercizio precedente per le matrici
$$
   \ba{cc}
       1 & -1/2 \\
      -4 & 1    \ea,\ \ \ba{cc}
                           1 & 1 \\
                           4 & -2 \ea.
$$

\vskip0.2cm

$\square$ Sia $A$ $n\times n$ definita positiva e
$\E_j$, $j=1,\ldots,n$, i suoi autovalori.
Nell'ipotesi $\E_1>\E_2\geq \ldots\geq\E_{n-1}>\E_n$ proporre un
algoritmo per il
calcolo del numero $\max \E_j/\min \E_j$

\vskip0.2cm

$\square$ Sia $A$ $n\times n$ hermitiana invertibile e $\E_j$,
$j=1,\ldots,n$, i suoi autovalori.
Proporre un algoritmo per il calcolo del numero
$\max|\E_j|/\min|\E_j|$

\vskip0.2cm

$\square$ (PER ME) Sia $A$ $n\times n$ hermitiana e
$\E_1,\E_2,\ldots,\E_n$ i suoi autovalori
dove $\E_1$ si suppone diverso da $0$.
Sia $\y_1$ $n\times 1$ non nullo tale che $A\y_1=\E_1\y_1$ e
$W=A-(\E_1/\y_1^*\y_1)\y_1\y_1^*$.
Allora $W$ \`e hermitiana e i suoi autovalori sono
$0,\E_2,\ldots,\E_n$.
Dedurre da questo risultato un algoritmo per il calcolo di tutti
gli autovalori di $A$

\vskip0.2cm

$\square$ (PER ME) Sia $A$ $n\times n$ e $\E_1,\E_2,\ldots,\E_n$
i suoi autovalori dove $\E_1$ si
suppone diverso da $0$.
Sia $\y_1$ $n\times 1$ non nullo tale che $A\y_1=\E_1\y_1$ e
$W=A-(\E_1/\w^*\y_1)\y_1\w^*$ con $\w$ $n\times 1$
tale che $\w^*\y_1 \neq 0$.
Allora gli autovalori di $W$ sono, per ogni scelta di $\w$,
$0,\E_2,\ldots,\E_n$.

ESEMPIO. Se $\w^*=\e_i^TA=$ riga $i$ di $A$ con $i$ tale che
$(\y_1)_i \neq 0$,
allora $\w^*\y_1=\E_1(\y_1)_i \neq 0$, quindi gli autovalori di
$W=A-(1/(\y_1)_i)\y_1\e_i^TA$
sono $0,\E_2,\ldots,\E_n$.
Notare che per tale scelta di $\w$, la riga $i$ di $W$ \`e nulla,
cio\`e
$$
 W = \ba{ccc}
      W_{11} & W_{12} & W_{13} \\
      0 .. 0 &  0     & 0 .. 0 \\
      W_{31} & W_{32} & W_{33} \ea
$$
con $W_{11}$ $i-1\times i-1$, $W_{12}$ $i-1\times 1$, $W_{32}$
$n-i\times 1$, $W_{33}$ $n-i\times n-i$.
Ne segue che $\E_2,\ldots,\E_n$ sono gli autovalori della
matrice $n-1\times n-1$
$$
\ba{cc}
W_{11} & W_{13} \\
W_{31} & W_{33} \ea.
$$
FINE ESEMPIO

Si verifica inoltre che $W\y_1=0$, cio\`e $\y_1$
(autovettore di $A$ relativo a $\E_1$)
\`e autovettore di $W$ relativo a $0$.
Se poi $\y_i$ son tali che $A\y_i=\E_i\y_i$, $i=2,\ldots,n$, allora
per gli $i$ tali che $\E_i \neq 0,\E_1$, posto
$\w_i=\y_i-(\E_1/\E_i)(\w^*\y_i/\w^*\y_1)\y_1$
si ha $W\w_i=\E_i\w_i$.
Per\`o, se $A$ \`e singolare ci sono valori di $i$ in $2,\ldots,n$
per cui $\E_i=0$.
In questo caso $A\y_i=\vn$ $\then$ $W\w_i=\vn$ con $\w_i=$ ? $\ldots$
Inoltre, $\E_1$ pu\`o essere radice multipla del polinomio
caratteristico
di $A$, cio\`e ci possono essere valori di $i$ in $2,\ldots,n$
tali che $\E_i=\E_1$.
In questo caso $A\y_i=\E_1\y_i$ $i \neq 1$ $\then$
$W\w_i=\E_1\w_i$ con $\w_i=$ ? $\ldots$

\vskip0.2cm

{\it Teoria(matrici stocastiche)}:

\vskip0.2cm

Se $A$ $n\times n$ \`e stocastica per colonne, cio\`e se
$a_{ij}\geq 0$ per ogni $i,j$ e
$\sum_i a_{ij} = 1$ per ogni $j$, allora:


\begin{itemize}
\item[(1)] $1$ \`e autovalore di $A$, cio\`e esiste $\z$ non nullo
    tale che $A\z=\z$
(ma \`e banale calcolarlo solo se $A$ \`e anche stocastica
per righe)
\item[(2)] $\rho(A)=1$, cio\`e $1\geq|\E|$ per ogni autovalore $\E$ di $A$
\item[(3)] per ogni vettore $\x$ $n\times 1$ con tutte le componenti
   non negative e di somma uguale a $1$ si ha che $A\x\geq \vn$
   $\&$ $\sum_i (A\x)_i = 1$
\item[(4)] Teoria(metododellepotenzematricistocastiche):
   \begin{itemize}
    \item[] se $A$, inoltre, \`e diagonalizzabile,
    \item[] se $\E_1=1>|\E_j|$ per ogni $j \neq 1$,
    \item[] se $\x$ \`e tale che $a_1$ in
            $\x=a_1\v_1+\ldots+a_n\v_n$ \`e diverso da $0$,
    \item[] se $\|\cdot\|$ \`e la norma $\|\z\|=\sum_i |z_i|$, e
    \item[] se il vettore iniziale $\x$ \`e scelto tale che
           $x_i\geq 0$ $\&$ $\sum_i x_i=\|\x\|=1$,
   \end{itemize}
   ALLORA
la successione $\{\z_k\}$ generata dall'algoritmo:
$$
   \z_0=\x, \quad \z_{k+1}=A\z_k,\ k=0,1\ldots
$$
soddisfa le propriet\`a:
   \begin{itemize}
     \item[-] $\z_k=A^k\x\geq 0$ e $\|\z_k\|=1$ per ogni
        $k=0,1,\ldots$ e, per $k$ che tende
        a infinito, $\z_k \to a_1\v_1/\|a_1\v_1\|=\z$, $A\z=\z$,
        $\z\geq\vn$, $\|\z\|=1$,
     \item[-] $\e^T\z_{k+1}/\e^T\z_k=1/1 \to 1$
     ($\e^T=[1\ 1\ \ldots\ 1]$).
    \end{itemize}
\end{itemize}

\vskip0.2cm

Esercizi:

\vskip0.2cm

$\square$ Sia
$$
 A = \ba{ccc}
       1/2 & 0 & 1/3 \\
         0 & 1/2 &  2/3 \\
        1/2 & 1/2 & 0 \ea.
$$
Osservare che per $\z_0=\x=[ 1/3\ 1/3\ 1/3]^T$ si ottiene
$$
  \z_1=A\z_0=\ba{c}
                5/18 \\
                7/18 \\
                1/3  \ea,\ \ \z_2=A\z_1 = \ba{c}
                                             3/12 \\
                                             5/12 \\
                                             4/12 \ea,\ \ldots
$$
quindi, effettivamente $\z_k$ sta convergendo al vettore
$\z$ tale che $A\z=\z$, cio\`e $\z = [2/9\ 4/9\ 3/9]^T$.

Verificare che tutte le ipotesi della teoria sulla convergenza
sono soddisfatte
(gli autovalori di $A$ sono: $1,1/2,-1/2$ $\ldots$)

\vskip0.2cm

$\square$ Ripetere l'esercizio precedente per
$$
A = \ba{ccc}
    1/6 & 1/2 & 1/3 \\
    1/6 & 1/4 & 1/3 \\
    2/3 & 1/4 & 1/3 \ea
$$

\vskip0.2cm

{\it Teoria(Google)}

\vskip0.2cm

[In un modello per la ricerca di documenti nel web \`e determinante
una corretta valutazione delle importanze delle sue pagine. Per
eseguirla \`e sufficiente calcolare l'autovettore relativo
all'autovalore dominante di una matrice, solo che questa matrice \`e
$n\times n$ con $n=$ numero delle pagine del web($\ldots$)]:

\vskip0.2cm

\begin{itemize}
\item $G=\{1,2,\ldots,n\}$ le pagine del web
\item $p_i=$ importanza della pagina $i$
\item $\deg(j)=$ numero delle pagine puntate da $j$
\end{itemize}

$p_i=\sum_{j:j\to i}  p_j/\deg(j)$
($p_i$ \`e proporzionale alle importanze delle pagine che la puntano
e inversamente proporzionale al numero delle pagine puntate da queste).

$a_{ij}=1/\deg(j)$ se $j\to i$, $a_{ij}=0$ altrimenti $\then$
$p_i=\sum_{j=1\ldots n} a_{ij}p_j$,
cio\`e, in forma vettoriale,
$\p=A\p$.
Quindi, per determinare il vettore $\p=[p_1\ p_2\ldots p_n]^T$
delle importanze delle pagine web \`e sufficiente trovare
l'autovettore di $A$ relativo all'autovalore $1$.

Se $A$ fosse stocastica per colonne e soddisfacesse le ipotesi in
Teoria(metododellepotenzematricistocastiche), $\p$ si potrebbe
calcolare con il metodo delle potenze.
Questo in generale non \`e vero (ad esempio, \`e semplice vedere che
$\sum_i a_{ij}= 1$ se $\deg(j)>0$ e $\sum_i a_{ij}=0$ altrimenti,
cio\`e se vi
sono pagine $j$ che non puntano a nulla $A$ non \`e nemmeno stocastica
per colonne). Quindi $A$ va sostituita con una matrice $A'$ che
soddisfa le
propriet\`a dette, con il metodo delle potenze si calcola $\p'$
tale che
$\p'=A'\p'$ e si usa $\p'$ come vettore delle importanze ($\ldots$)

\vskip0.2cm

22 Marzo 2009

\vskip0.2cm

$\square$ $\e_1$ vettore $n\times 1$ con elementi tutti nulli
eccetto il primo che \`e uguale a $1$,
$\y$ vettore $n\times 1$ con prima componente nulla.
Allora $(I+\y\e_1^T)^{-1} = I-\y\e_1^T$

\vskip0.2cm

$\square$ Scrivere l'inversa delle matrici
$$
\ba{ccccc}
   1 & 0 & 0 & 0 & 0 \\
 1/3 & 1 & 0 & 0 & 0 \\
   1 & 0 & 1 & 0 & 0 \\
  -2 & 0 & 0 & 1 & 0 \\
 1/2 & 0 & 0 & 0 & 1 \ea,\ \
    \ba{ccc}
       3 & 0 & 0 \\
       1 & 3 & 0 \\
     1/2 & 0 & 3 \ea
$$

\vskip0.2cm

$\square$ Il prodotto di due matrici $T$, $U$ triangolari superiori
(inferiori) \`e triangolare superiore (inferiore).
Una matrice $T$ triangolare \`e invertibile se e solo se
i suoi elementi diagonali sono tutti non nulli.
L'inversa di una matrice $T$ triangolare superiore (inferiore)
invertibile
\`e triangolare superiore (inferiore). Inoltre gli elementi
diagonali di $T^{-1}$ sono gli inversi degli elementi diagonali
di $T$. ($T$, $U$ matrici $n\times n$)

\vskip0.2cm

$\square$ Trovare i valori di $a$ numero complesso per cui
la matrice $A$ $2\times 2$
$$
\ba{cc}
  a & a \\
  a & -a \ea
$$
\`e unitaria

\vskip0.2cm

$\square$ $A$ hermitiana iff esiste $Q$ tale che $Q^{-1}AQ=D$,
$Q^*=Q^{-1}$, $D$ diagonale reale (dimostrare almeno una delle
due implicazioni)

\vskip0.2cm

$\square$ Dimostrare che le matrici $A$
$$
   \ba{cc}
     2 & -1 \\
    -1 & 2  \ea,\
   \ba{cc}
      2 & -1 \\
     -3 & 2  \ea,\
   \ba{cc}
      2  & \ui+4 \\
   \ui+4 &  7    \ea,\
   \ba{cc}
      0 & 1 \\
     -1 & 0 \ea,\
   \ba{ccc}
     1/2 & 0   & 1/3 \\
      0  & 1/2 & 2/3 \\
     1/2 & 1/2 & 0 \ea
$$
sono diagonalizzabili, cio\`e esiste
$S$ non singolare tale che $S^{-1}AS=D$, $D$ diagonale.
Dire quali tra di esse \`e diagonalizzabile tramite trasformazione
unitaria, cio\`e esiste $S$, $S^H=S^{-1}$, per cui $S^{-1}AS=D$,
con $D$ diagonale.
Dire quali di esse hanno autovalori tutti reali.

\vskip0.2cm

$\square$ Mostrare che le matrici
$$
A = \ba{cc}
      0 & 1 \\
      0 & 0 \ea,\ \
   B = \ba{ccc}
         0 & 1 & 0 \\
         0 & 0 & 1 \\
         0 & 0 & 0 \ea
$$
non sono diagonalizzabili. Calcolare $A^k$, $B^k$, $k=1,2,\ldots$
Dimostrare che ogni matrice $A$ $n\times n$ hermitiana che abbia
tutti gli autovalori nulli deve essere la matrice nulla.

\vskip0.2cm

$\square$ Descrivere i seguenti insiemi di numeri complessi $z$:
$\I_1=\{z:\ |z-1|=1\}$,
$\I_2=\{z:\ |z+1|=3\}$,
$\I_3=\{z:\ |z-1|>1\}$,
$\I_4=\{z:\ |z+1|<3\}$,
$\I_3 \bigcup \I_4$,
$\I_3 \bigcap \I_4$,
$\I_1 \bigcap \I_2$,
$\I_2 \bigcup \I_4$,
$\partial \I_4$,
$\o{\I_4}$.

\vskip0.2cm

$\square$ Se $A=I+\y\w^*$ \`e unitaria allora $\w=a\y$
con $a$ complesso

\vskip0.2cm

$\square$ I valori di $b$ numero complesso per cui la matrice
$A=I+b\y\y^*$ \`e unitaria sono $b=-2\cos(a)\exp{\ui a}/\y^*\y$,
$a$ reale. Per $a=0$ (oppure $a=\pi$) si ottengono, in particolare,
le matrici di Householder

\vskip0.2cm

$\square$ Usando la formula $(I+\y\w^*)^{-1}=I-(1/(\w^*\y+1))\y\w^*$,
trovare una formula per $(A+\y\w^*)^{-1}$, $A$ $n\times n$
non singolare (Sherman-Morrison).
Suggerimento: $(A+\y\w^*)^{-1}=( A(I+A^{-1}\y\w^*) )^{-1}$

\vskip0.2cm

$\square$ Se $S^{-1}MS=\diag(a,b,0\ldots 0)$, $S^*=S^{-1}$,
allora esistono $\y$, $\w$ tali che
$M=\y\y^*+\w\w^*$.

\vskip0.2cm

$\square$ (PER ME) $A\x=\b$, $A$ hermitiana con autovalori qualsiasi,
Sistema equivalente: $R\x=\c$, $R$ hermitiana
con autovalori tutti uguali a $1$ eccetto due, $1+a$ e $1+b$ $\then$
$R-I$ hermitiana con autovalori tutti nulli eccetto due, $a$ e $b$
$\then$ $R-I=\y\y^*+\w\w^*$ $\ldots$

\vskip0.2cm

$\square$ Siano $\y$, $\w$ vettori indipendenti.
$$
   (\y\y^*+\w\w^*)(a\y+b\w)=c(a\y+b\w),
$$
con $a$, $b$ non entrambi
nulli, se e solo se
$$
  \bi{l}
  a(\y^*\y-c)+b(\y^*\w)=0,  \\
  a(\w^*\y)+b(\w^*\w-c)=0,  \ei
$$
con $a,b$ non entrambi nulli, se e solo se
il determinante della matrice $2\times 2$
$$
   \ba{cc}
    \y^*\y-c & \y^*\w \\
     \w^*\y  &  \w^*\w-c \ea                       \eqno(eq(c))
$$
\`e zero.
In altre parole, i due autovalori significativi di $\y\y^*+\w\w^*$
(cio\`e quelli non nulli) sono i due autovalori della matrice
$$
  \ba{cc}
    \y^*\y & \y^*\w \\
    \w^*\y & \w^*\w \ea
$$
e cio\`e $c_{\pm}=\um(\y^*\y+\w^*\w \pm\R{(\y^*\y-\w^*\w)^2+4|\y^*\w|^2})$.
Poich\'e $\y$ e $\w$ sono indipendenti, si ha $|\y^*\w|<\|\y\|\|\w\|$ (Nota: $(\y^*\y)(\w^*\w)=|\y^*\w|^2$ iff $\w=a\y$,infatti
$\y^*[\w-(\y^*\w/\y^*\y)\y]=0$, $\w^*[\ldots]=0$ $\then$ $[\ldots]=\vn$). Ne segue che $0<c_-\leq c_+$.

Agli autovalori $c_+$ e $c_-$ corrispondono,
rispettivamente, gli
autovettori $\v_+=a_+\y+b_+\w$ e $\v_-=a_-\y+b_-\w$ con $a_{\pm},b_{\pm}$
soluzioni di $eq(c_{\pm})$.

\vskip0.1cm

$(\y\y^*+\w\w^*)\z=0\y+0\w=0$ se $\y^*\z=\w^*\z=0$.
Quindi $0$ \`e autovalore di $\y\y^*+\w\w^*$ e
i corrispondenti autovettori sono i $\z\neq\vn$ per cui
$\y^*\z=\w^*\z=0$. Calcoliamoli.
Poich\'e
$\y$ e $\w$ sono indipendenti, esiste $i<j$ tale che
$y_iw_j-y_jw_i \neq 0$. Quindi gli autovettori corrispondenti
all'autovalore $0$ sono i $\z\neq\vn$ tali che
$$
    \ba{c}
      z_i \\
      z_j \ea
   =  \ba{cc}
         \o{y_i} & \o{y_j} \\
         \o{w_i} & \o{w_j} \ea ^{-1}
       \ba{c}
       -\sum_{k \neq i,j} \o{y_k}z_k \\
       -\sum_{k \neq i,j} \o{w_k}z_k \ea.
$$
Tra di essi se ne possono trovare $n-2$ linearmente indipendenti, $\v_1$,
$\ldots$, $\v_{n-2}$. Riassumendo
$$
   \bi{l}
  (\y\y^*+\w\w^*)[\v_+|\v_-|\v_1|\ \ldots\ |\v_{n-2}]    \\  \qquad\qquad
      = [\v_+|\v_-|\v_1|\ \ldots\ |\v_{n-2}]\diag(c_+,c_-,0,\ldots,0) \ei
$$
(Nota: $\y^*\w=0$ $\then$ $(\y\y^*+\w\w^*)\w=(\w^*\w)\w$ e
$(\y\y^*+\w\w^*)\y=(\y^*\y)\y$.)

\vskip0.2cm

$\square$ (PER ME) Siano $\y,\w,\z$ vettori indipendenti.
$$
 (\y\y^*+\w\w^*+\z\z^*)(a\y+b\w+c\z)=d(a\y+b\w+c\z),
$$
con $a,b,c$ non tutti nulli,
se e solo se
$$
  \bi{l}
   a(\y^*\y-d)+b(\y^*\w)+c(\y^*\z)=0 \\
   a(\w^*\y)+b(\w^*\w-d)+c(\w^*\z)=0 \\
   a(\z^*\y)+b(\z^*\w)+c(\z^*\z-d)=0,\ei
$$
con $a,b,c$ non tutti nulli,
se e solo se il determinante della matrice $3\times 3$
$$
  \ba{ccc}
    \y^*\y-d & \y^*\w & \y^*\z \\
    \w^*\y   & \w^*\w-d & \w^*\z \\
    \z^*\y   & \z^*\w   & \z^*\z-d  \ea
$$
\`e zero.
In altre parole, i tre autovalori significativi di
$\y\y^*+\w\w^*+\z\z^*$
(cio\`e quelli non nulli) sono i tre autovalori della matrice
$$
   \ba{ccc}
    \y^*\y & \y^*\w & \y^*\z  \\
    \w^*\y & \w^*\w & \w^*\z  \\
    \z^*\y & \z^*\w & \z^*\z  \ea
$$
(Nota: quest'ultima matrice ha $0$ come autovalore
se e solo se $\ldots$ $\y,\w,\z$ linearmente dipendenti ?)

\vskip0.2cm

$\square$ (PER ME) Siano $\y,\w$ vettori indipendenti e $\u,\v$ vettori
indipendenti.

$(\y\u^*+\w\v^*)(a\y+b\w)=c(a\y+b\w)$, con $a,b$ non entrambi nulli,
se e solo se
$$
  \bi{l}
      a(\u^*\y-c)+b(\u^*\w)=0,  \\
      a(\v^*\y)+b(\v^*\w-c)=0,  \ei
$$
con $a,b$ non entrambi nulli,
se e solo se il determinante della matrice $2\times 2$
$$
   \ba{cc}
     \u^*\y-c & \u^*\w \\
       \v^*\y & \v^*\w-c \ea
$$
\`e zero.
In altre parole, i due autovalori significativi di $\y\u^*+\w\v^*$
(cio\`e quelli non nulli) sono i due autovalori della matrice
$$
 \ba{cc}
   \u^*\y & \u^*\w \\
   \v^*\y & \v^*\w \ea
$$
(Nota: quest'ultima matrice ha $0$ come autovalore se e solo se
$(\u^*\y)(\v^*\w)=(\u^*\w)(\v^*\y)$ $\then$
$\v^*(\w-\f{\u^*\w}{\u^*\y}\y)=\vn$,
$\u^*(\w-\f{\u^*\w}{\u^*\y}\y)=\vn$ $\then$ piano $\u,\v$ ortogonale a
piano $\y,\w$ $\ldots$ $0$ autovalore $\then$ $\y\u^*+\w\v^*$ ha rango $1$
? Nota sul viceversa: $\y$ e $\w$ ($\u$ e $\v$) dipendenti $\then$ $0$
\`e autovalore.)

\vskip0.2cm

$\square$ 
$\y\u^*+\w\v^*$ \`e uguale a $\x\z^*$ se e solo se $\w$ e $\y$ (o $\v$ e $\u$) sono linearmente dipendenti. E' vera tale affermazione ?

\vskip0.2cm

15 Marzo 2009

\vskip0.2cm

$\square$ $A$ $n\times n$ di dice ``definita positiva''
se soddisfa le due propriet\`a:

\begin{itemize}
\item[(1)] $A=A^*$ ($A$ \`e hermitiana)
\item[(2)] $\z^*A\z>0$, per ogni vettore $n\times 1$ $\z$ non nullo
\end{itemize}

(Nota: (1) $\then$ $\o{\z^*A\z}=\z^*A\z$, cio\`e $\z^*A\z$ reale
$\then$  ha senso richiedere una condizione sul segno di
$\z^*A\z$)

\vskip0.2cm

$\square$ Trovare una condizione su $B$ $n\times n$ per cui
$A=B^*B$ (oppure $A=BB^*$) sia definita positiva

\vskip0.2cm

$\square$ Se $A$ soddisfa (1)
allora valgono le seguenti due implicazioni:

(2) $\then$ autovalori di $A$ positivi
(Dim: $\E=\v^*A\v/\v^*\v$, con $\v$ autovettore relativo
all'autovalore $\E$ di $A$),

autovalori di $A$ positivi $\then$ (2)
(Dim: omessa).

In altre parole, se $A$ \`e hermitiana, per verificare se $A$
soddisfa la condizione (2) \`e necessario e sufficiente verificare
che il segno degli autovalori di $A$ sia positivo

\vskip0.2cm

$\square$ Dimostrare che $A=I+\y\y^*$ \`e definita positiva
ed osservare che $A^{-1}=I-(1/(\y^*\y+1))\y\y^*$.
Sotto quali condizioni su $b$ reale la matrice $A=I+b\y\y^*$
\`e definita positiva?
Scrivere l'inversa della matrice $3I+\y\y^*$.
Risolvere il sistema
$$
  \ba{cccc}
    4  & -1   & -\ui  & 2 \\
   -1  & 4    & \ui   & -2 \\
   \ui & -\ui & 4     & 2\ui \\
    2  & -2   & -2\ui & 7 \ea \ba{c} x_1 \\ x_2 \\ x_3 \\ x_4 \ea
 =  \ba{c} 1 \\ 1 \\ 1 \\ 1 \ea
$$

\vskip0.2cm

$\square$ Dimostrare che $A=I+\y\w^*$ \`e non singolare
se $\w^*\y \neq -1$ ed osservare che
$A^{-1}=I-(1/(\w^*\y+1))\y\w^*$.
Sotto quali condizioni su $b$ reale la matrice $A=I+b\y\w^*$
\`e definita positiva?
Scrivere, quando esiste, l'inversa della matrice $3I+\y\w^*$.
Risolvere il sistema
$$
   \ba{cccc}
       4 & -2    & 1     & -1  \\
      -1 &  5    & -1    &  1  \\
     \ui & -2\ui & \ui+3 &  -ui  \\
       2 & -4    & 2     & 1 \ea
   \ba{c} x_1 \\ x_2 \\ x_3 \\ x_4 \ea
   = \ba{c} 1 \\ 1 \\ 1 \\ 1 \ea
$$

\vskip0.2cm

$\square$ Siano $M$ $n\times n$ hermitiana e $b$ reale.
Mostrare che esistono sempre
valori di $a$ reale per cui $A=aI+bM$ \`e definita positiva

\vskip0.2cm

$\square$ Calcolare autovalori, determinante e inversa della matrice
$A$ $n\times n$, con $a_{ii}=2$, per ogni $i$, e $a_{ij}=1$ se $i$
\`e diverso da $j$.

\vskip0.2cm

$\square$ $Q$ $n\times n$ si dice unitaria se $Q^*=Q^{-1}$
(ovvero, se per calcolarne l'inversa basta farne la trasposta
coniugata) o, equivalentemente, se $Q^*Q=I$

\vskip0.2cm

$\square$ Se $Q$ \`e unitaria allora gli autovalori di $Q$ hanno
modulo $1$

\vskip0.2cm

$\square$ Gli autovalori della ``matrice di Givens''
$$
   A = \ba{cc}
          a & b \\
         -b & a \ea,\ a,b\in\RR,\ a^2+b^2=1
$$
sono $a-\ui b$ e $a+\ui b$.
Le matrici di Givens hanno determinante 1

\vskip0.2cm

$\square$ La matrice $A=I+b\y\y^*$, $b$ reale, \`e unitaria
se $b=-2/\y^*\y$. In tal caso i suoi autovalori sono $1$ ($n-1$
volte) e $-1$. Le ``matrici di Householder'' $A=I-(2/\y^*\y)\y\y^*$
hanno determinante $-1$.

\vskip0.2cm

$\square$ $Q$ $n\times n$ si dice ``matrice di permutazione'' se
$Q=[\e_{i_1}\, \e_{i_2}\, \ldots\, \e_{i_n}]$ dove
$\{i_1,i_2,\ldots,i_n\}$ \`e una permutazione di $\{1,2,\ldots,n\}$
e $\e_j$ \`e il vettore con componenti tutte nulle eccetto la
$j$-esima che \`e uguale a $1$.
Osservare che le matrici di permutazione sono matrici unitarie
(cio\`e $Q^*Q=I$) e che il loro determinante deve essere uguale a $1$
oppure a $-1$

\vskip0.2cm

Esercizi di base

\begin{itemize}
\item[-] Se $A$ $m\times n$, $B$ $n\times k$ allora $(AB)^*=B^*A^*$
\item[-] Se $A, B$ sono matrici $n\times n$ allora
         $(AB)^{-1}=B^{-1}A^{-1}$
\item[-] $a$ numero complesso, $A$ matrice $n\times n$ $\then$
         $(aA)^{-1}=a^{-1}A^{-1}$
\item[-] se $\E$ \`e autovalore di $M$ $n\times n$ allora
         $a_0+a_1\E+\ldots+a_k\E^k$ \`e autovalore di
         $A=a_0I+a_1M+\ldots+a_kM^k$ ($a_j$ numeri complessi)
\item[-] $\det(A)=\det(A^T)$, $\det(\o{A})=\o{\det(A)}$,
       $\det(A^*)=\o{\det(A)}$
\item[-] se $\E$ \`e autovalore di $A$ allora $\E$ \`e autovalore
         di $A^T$
\item[-] se $\E$ \`e autovalore di $A$ allora $\o{\E}$ \`e
   autovalore di $\o{A}$ e, quindi, di $A^*$
\end{itemize}

7 Marzo 2009

\vskip0.2cm

$\square$ Dato $\y$, vettore colonna $n\times 1$,
trasposto di $\y$: $\y^T=[y_1\ y_2\ \ldots\ y_n]$,
trasposto coniugato di $\y$:
$\y^*=[\o{y_1}\ \o{y_2}\ \ldots\ \o{y_n}]$

\vskip0.1cm

($\o{y_1}=\o{\Re(y_1)+i\Im(y_1)}=\Re(y_1)-i\Im(y_1)$, $\ldots$)

\vskip0.2cm

$\square$ Sia $\rho(*)$ il raggio spettrale di $*$.
Siano $A$, $B$ matrici $n\times n$, $a$ scalare.
Quali delle seguenti propriet\`a sono vere?
\begin{itemize}
\item[(1)] $\rho(A) \geq 0$
\item[(2)] $\rho(A)=0$ iff $A=0$
\item[(3)] $\rho(aA)=|a|\rho(A)$
\item[(4)] $\rho(A+B) \leq \rho(A)+\rho(B)$
\item[(5)] $\rho(AB) \leq \rho(A)\rho(B)$
\end{itemize}

\vskip0.1cm

{\it Risoluzione}

Lapropriet\`a (4) \`e falsa, infatti
$$
A = \ba{cc}
      a & b \\
      0 & 0 \ea,\
B = \ba{cc}
      0 & 0 \\
     -b & a \ea,\ a,b\in\RR,\ a^2+b^2=1, \quad
         \rho(A+B)=1,\ \rho(A)+\rho(B)=2|a|
$$
($A+B$ is real unitary). Thus, if $|a|<1/2$ then
$\rho(A+B)>\rho(A)+\rho(B)$.

In the complex field:
$$
A = \ba{cc}
      a & b \\
      0 & 0 \ea,\
B = \ba{cc}
      0     & 0     \\
     -\o{b} & \o{a} \ea,\ a,b\in\CC,\ |a|^2+|b|^2=1, \quad
         \rho(A+B)=1,\ \rho(A)+\rho(B)=2|a|
$$
($A+B$ is unitary). Thus, if $|a|<1/2$ then
$\rho(A+B)>\rho(A)+\rho(B)$.

\vskip0.1cm

La propriet\`a (5) \`e falsa, infatti
$$
A = \ba{cc}
      1 & 0 \\
      0 & 0 \ea, \
B = \ba{cc}
      0 & 0 \\
      0 & 1 \ea, \quad \rho(AB)=0<\rho(A)\rho(B) = 1\cdot 1 = 1,
$$
$$
A = \ba{cc}
      1 & 1 \\
      1 & 1 \ea, \
B = \ba{cc}
      1 & 1 \\
      1 & 1 \ea, \quad \rho(AB)=\rho(2A)=2\rho(A)
            =2\cdot 2=4=\rho(A)\rho(B),
$$
$$
A = \ba{cc}
      1 & 1 \\
      0 & 0 \ea,\
B = \ba{cc}
      1 & 0 \\
      1 & 0 \ea, \quad \rho(AB)=2>\rho(A)\rho(B)=1\cdot 1=1.
$$



\vskip0.2cm

$\square$ Discutere se, per ogni $A$, $B$ $n\times n$,
(1) $AB=BA$
(2) autovalori di $AB$ coincidono con quelli di $BA$, quindi
$\rho(AB)=\rho(BA)$

\vskip0.2cm

$\square$ Supponendo $\y$, $\w$ indipendenti, scrivere l'insieme
dei $\z$ per cui
$\y^*\z=0$ $\&$ $\w^*\z=0$

\vskip0.2cm

$\square$ Discutere l'affermazione: $|\y^*\w|=\|\y\| \|\w\|$
iff $\w=a\y$

\vskip0.2cm

$\square$ Siano $\y$, $\w$ vettori $n\times 1$ indipendenti.
Calcolare esplicitamente
\begin{itemize}
\item[(1)] determinante, traccia, autovalori e autovettori di $\y\y^*$
\item[(2)] {\it idem} di $\y\w^*$
\item[(3)] {\it idem} di $\y\y^*+\w\w^*$
\item[(4)] {\it idem} di $I+\y\w^*$
\item[(5)] inversa di $A=I+\y\w^*$ (cercarla del tipo $I+a\y\w^*$)
\end{itemize}

\vskip0.1cm

{\it Risoluzione}

(1): $(\y\y^*)\y=\y(\y^*\y)=(\y^*\y)\y$ $\then$ $\y^*\y$ \`e autovalore
di $\y\y^*$ con corrispondente autovettore $\y$.

$(\y\y^*)\z=0\y=\vn$ se $\y^*\z=0$. Quindi $0$ \`e autovalore di
$\y\y^*$ e i corrispondenti autovettori sono i $\z\neq\vn$ per cui
$\y^*\z=0$. Calcoliamoli. Poich\'e
$\y\neq\vn$, esiste $i$ t.c. $y_i \neq 0$. Quindi gli autovettori
corrispondenti all'autovalore $0$ sono i $\z\neq\vn$ tali che
$z_i=(-\sum_{k \neq i} \o{y_k}z_k)/\o{y_i}$. Tra di essi se ne possono trovare $n-1$ linearmente indipendenti, $\v_1$, $\ldots$, $\v_{n-1}$. Riassumendo
$$
     \y\y^*[\y|\v_1|\ldots|\v_{n-1}]
            = [\y|\v_1|\ldots|\v_{n-1}]\diag(\y^*\y,0,\ldots,0).
$$
In particolare si ha: $\rho(\y\y^*)=\y^*\y$

\vskip0.1cm

(2): $(\y\w^*)\y=\y(\w^*\y)=(\w^*\y)\y$ $\then$ $\w^*\y$ \`e
autovalore di $\y\w^*$
con corrispondente autovettore $\y$.
$\w^*\y$ in generale non \`e reale.

$(\y\w^*)\z=0\y=0$ se $\w^*\z=0$.
Quindi $0$ \`e autovalore di $\y\w^*$ e
i corrispondenti autovettori sono i $\z\neq\vn$ per cui $\w^*\z=0$. Calcoliamoli. Poich\'e
$\w\neq\vn$, esiste $i$ t.c. $w_i \neq 0$.  Quindi gli autovettori
corrispondenti all'autovalore $0$ sono i $\z\neq\vn$ tali che
$z_i=(-\sum_{k \neq i} \o{w_k}z_k)/\o{w_i}$. Tra di essi se ne possono trovare $n-1$ linearmente indipendenti, $\v_1$, $\ldots$, $\v_{n-1}$. Riassumendo
$$
  \y\w^*[\y|\v_1|\ldots|\v_{n-1}]
     = [\y|\v_1|\ldots|\v_{n-1}]\diag(\w^*\y,0,\ldots,0).
$$
In particolare si ha: $\rho(\y\w^*)=|\w^*\y|$

\vskip0.1cm

Nota: $\rho(\y\w^*) = |\w^*\y| \leq \|\y\w^*\|_2 = \|\y\|_2\|\w\|_2$,
mentre $\rho(\y\y^*)=\y^*\y=\|\y\y^*\|_2=\|\y\|_2^2$.

\vskip0.1cm

(3) (vedi pi\`u avanti).

\vskip0.2cm

$\square$ Studiare l'andamento del numero
$\rho(A)\rho(A^{-1})$, $A=I+\y\w^*$

\vskip0.2cm

$\square$ Scrivere le matrici
$$
     \ba{cc}
       2 & 1 \\
      1 & 1/2 \ea, \ \
    \ba{cccc}
        1 & -1 & 2\ui & -3    \\
        2 & -2 & 4\ui & -6    \\
        i & -i & -2   & -3\ui \\
        4 & -4 & 8\ui & -12   \ea
$$
nella forma $\y\y^*$ o $\y\w^*$, e calcolare il loro
raggio spettrale

\vskip0.2cm

$\square$ Calcolare $\rho(A)$ dove $A$ \`e la matrice $4\times 4$
$$
   \ba{cccc}
 1 & -2 & 5 & -1 \\
-2 & 4  & 10&  2 \\
 5 & 10 & 25& -5 \\
-1 & 2  & -5&  1 \ea
$$

\vskip0.2cm

$\square$ Calcolare gli autovalori $\E$ della matrice $2\times 2$
$$
    \ba{cc}
      a & b \\
     -b & a \ea,
$$
con $a,b$ reali. Determinare una CNES affinch\'e $|\E|=1$

\vskip0.1cm

{\it Risoluzione}

Gli autovalori sono $a-\ui|b|$ e $a+\ui|b|$, e il loro modulo \`e
$\sqrt{a^2+b^2}$. Quindi, $|\E|=1$ se e solo se $a^2+b^2=1$.

Gli autovalori di
$$
A = \ba{cc}
      a     & b     \\
     -\o{b} & \o{a} \ea,\ a,b\in\CC,
$$
sono $\Re(a) \pm \ui\sqrt{\Im(a)^2+|b|^2}$,
e il loro modulo vale $\sqrt{|a|^2+|b|^2}$. Quindi, $|\E|=1$ se e solo se $|a|^2+|b|^2=1$.

\vskip0.2cm

$\square$ Per $A$ $n\times n$ sia $A^*$ la matrice
$[A^*]_{ij}=\o{[A]_{ji}}$.
$A$ $n\times n$ si dice hermitiana, se $a_{ij}=\o{a_{ji}}$
$\fa\,i,j$ (ovvero se $A=A^*$).

\vskip0.2cm

$\square$ $\y\w^*$ \`e hermitiana se e solo se $\w=a\y$, $a$ reale

\vskip0.2cm

$\square$
$A$ $n\times n$ con elementi non negativi tale che
$\sum_j a_{ij}=1$ per ogni $i$ si dice stocastica per righe.
Se $A$ \`e stocastica per righe allora
\begin{itemize}
\item[(1)] $1$ \`e autovalore di $A$ con autovettore $[1\ 1\,\ldots\,1]^T$
\item[(2)] $\rho(A)=1$
\item[(3)] $A^k$ \`e stocastica per righe (per induzione su $k$)
\item[(4)] $\sum_{k=0}^r y_kA^k$ \`e stocastica per righe,
      se $y_k\geq 0$ per ogni $k$ e $\sum_k y_k=1$
\end{itemize}

\vskip0.2cm

Esercizi di base

- Ad autovalori distinti corrispondono autovettori indipendenti

- Gli autovalori di $aA$ si ottengono moltiplicando gli autovalori
di $A$ per $a$

- Gli autovalori di $A^k$ si ottengono facendo le potenze $k$
degli autovalori di $A$

- Gli autovalori di $A^{-1}$ si ottengono invertendo quelli di $A$

- Se $B=S^{-1}AS$ allora $A$ e $B$ hanno gli stessi autovalori

- Se $T$ \`e triangolare gli autovalori di $T$ sono i suoi
  elementi diagonali

- Se $S^{-1}AS=T$ con $T$ triangolare allora gli autovalori di
  $A$ sono gli elementi diagonali di $T$

- Se $S^{-1}AS=D$ con $D$ diagonale allora gli autovalori di $A$
  sono gli elementi diagonali di $D$ e i corrispondenti autovettori
  sono le colonne di $S$ (e $A$ si dice diagonalizzabile)

- Esiste sempre $S$, $S^*=S^{-1}$, per cui $S^{-1}AS=T$ con $T$
  triangolare.
  Esiste $S$, $S^*=S^{-1}$, per cui $S^{-1}AS=D$ se e solo se
  $AA^*=A^*A$ (ovvero $A$ \`e normale)

- $A=A^*$ $\then$ autovalori di $A$ reali

- Autovalori di $A$ reali $\&$ $A$ normale $\then$ $A=A^*$

\vskip0.2cm
\hrule
\vskip0.2cm

{\it Inizio}:

$\y$ vettore colonna $n\times 1$,

$\y^T=[y_1\ \ldots\ y_n]$ trasposto di $\y$,

$\y^*=[\o{y_1}\ \ldots\ \o{y_n}]$ trasposto coniugato di $\y$

Esempio
$$
   \y = \ba{c} 1 \\ 1-\ui \ea,\quad
\y^T=[1\ \ 1-\ui],\quad  \y^H=[1\ \ 1+i]
$$

$\y^*\y=\sum_i |y_i|^2$ \`e un numero reale non negativo
(che si indica anche $\|y\|_2^2$)

$\y\y^*$ \`e una matrice $n\times n$, ha determinante nullo
($\then$ ha almeno un autovalore uguale a zero), ha traccia
uguale a $\|y\|_2^2$, \`e un esempio di matrice hermitiana
(def di traccia e di matrice hermitiana)

matrici hermitiane hanno gli elementi diagonali reali

def di autovalori, autovettori, polinomio caratteristico,
$A$ $n\times n$ ha $n$ autovalori, gli autovalori di una matrice
triangolare sono i suoi elementi diagonali, autovettori di
autovalori distinti sono indipendenti, se $A$ \`e simile a $T$
triangolare allora gli autovalori di $A$ sono gli elementi
diagonali di $T$

def di raggio spettrale di $A$ $n\times n$:
$\rho(A)=\max_i |\E_i|$ dove $\E_i$, $i=1,\ldots,n$
sono gli autovalori di $A$.

es. $\y$ vettore $n\times 1$ $\then$ $\rho(\y\y^*)=\y^*\y$

es. trovare due matrici $2\times 2$ $A$, $B$ per cui
$\rho(AB)>\rho(A)\rho(B)$, $<$ , $=$

\end{document}
