Calcolo Numerico Raccolta Sistemi lineari

Calcolo Numerico

Prof. Michela Redivo Zaglia

Raccolta di esercizi sui SISTEMI DI EQUAZIONI LINEARI

Esercizio 1

Si scrivano due subroutine per implementare la risoluzione di un sistema triangolare superiore e di un sistema triangolare inferiore (gli algoritmi si trovano sul libro di testo, sezioni 4.17.1 e 4.17.2)
Si scrivano poi due programmi di utilizzo di tali subroutine, provandoli con i sistemi:

$\begin{displaymath} (U\vert{\mathbf{b}})= \left( \begin{array}{ccc\vert c} 2 &... ... \\ 4 & 3 & 0 & 18 \\ -2 & 5 & 2 & 6 \end{array} \right) \end{displaymath}$

entrambi con soluzione ${\mathbf{x}}=(3,2,1)^T$ .

Esercizio 2

Usando la doppia precisione, si scrivano due subroutine per implementare il Metodo di Gauss (una senza pivoting e l'altra con pivoting), come indicato nel libro di testo (sezioni 4.17.3 e 4.17.4).
Si scrivano poi i programmi ed, utilizzando anche la subroutine sviluppata nell'Esercizio 1 (risoluzione di un sistema triangolare superiore) li si provino sul sistema che ha la seguente matrice aumentata, e soluzione esatta ${\mathbf{x}}=(1,1,1)^T$ .

$\begin{displaymath} (A\vert{\mathbf{b}})= \left( \begin{array}{ccc\vert c} 1 ... ... & 6\\ 4 & 3 & -2 & 5\\ -2 & 5 & 2 & 5 \end{array} \right) \end{displaymath}$

Esercizio 3

Usando la doppia precisione, si scriva una subroutine per il calcolo della fattorizzazione LU di Crout (sezione 4.17.5 del libro di testo).
Si scriva poi un programma che calcoli le matrici L ed U di Gauss (senza pivoting) e quelle di Crout, provandolo con la matrice dell'Esercizio 2, e verificando che i prodotti restituiscano la matrice A.

Esercizio 4

Usando la doppia precisione, si scrivano due procedure per implementare la risoluzione di un sistema con i due metodi di Jacobi e di Gauss-Seidel (sezioni 4.17.6 e 4.17.7 del libro di testo)
Si scrivano poi due programmi di utilizzo di tali procedure e si provino sul sistema:

$\begin{displaymath} \left( \begin{array}{ccc} 2 & 1 & 0\\ 1 & 3 & 1 \\ 0 &... ...ht) = \left(\begin{array}{c} 3\\ 5\\ 3 \end{array} \right) \end{displaymath}$

Si prenda come vettore iniziale ${\mathbf{x}_0}=(0,0,0)^T$ e si determinino le iterazioni necessarie ad ottenere una tolleranza sulla norma euclidea del residuo di $10^{-8}$ . Si disegnino poi su di uno stesso grafico, per ogni iterazione i valori $\log_{10}\Vert{\mathbf{r}_k}\Vert _2$ per il metodo di Jacobi e per quello di Gauss Seidel.

Soluzione: Entrambi i metodi convergono qualsiasi sia la scelta iniziale di ${\mathbf{x}_0}$ , alla soluzione ${\mathbf{x}}=(1,1,1)^T$ . Perchè?
Posto ${\mathbf{x}_0}=(0,0,0)^T$ Jacobi converge in circa 34 iterazioni ( Soluzione Jacobi) e Gauss-Seidel ( Soluzione Gauss Seidel) in circa 16 iterazioni. Il disegno di $\log_{10}\Vert{\mathbf{r}_k}\Vert _2$ mostra la convergenza più rapida del metodo di Gauss Seidel.

Esercizio 5

Si consideri il sistema lineare che ha la seguente matrice aumentata (tali dati devono essere memorizzati su di un file di nome matrice.dat)

$\begin{displaymath} \left( \begin{array}{rrrr\vert r} \par 1& 0& 2& 1& 2\\ 4 &-... ...1 & 14\\ 8 &16& 6& 5& -3\\ 2 &3 &2 &1 &0 \end{array} \right) \end{displaymath}$
Utilizzando il metodo di Gauss senza pivoting, si calcolino le due matrici ed della fattorizzazione ed il vettore ${\mathbf{y}}$ e si scrivano tali dati su di un file di nome gauss.dat.

Soluzione: gauss.dat

Utilizzando la fattorizzazione di Gauss-Crout si calcolino le due matrici ed della fattorizzazione e si scrivano tali dati su di un file di nome crout.dat (l'ultima colonna della matrice aumentata non deve essere usata).

Soluzione: crout.dat

Esercizio 6

Si risolva l'esercizio 4.6 (pag.160 del testo).

Esercizio 7

Si risolva l'esercizio 4.7 (pag.160 del testo).

Esercizio 8

Si consideri il seguente sistema lineare $A{\mathbf{x}}={\mathbf{b}}$ la cui soluzione è ${\mathbf{x}}=(1.,1.,1.,1.,1.)^T$ (matrice e termine noto devono essere memorizzati e fatti leggere da un file di nome sistema.dat)

$\begin{displaymath}A = \left( \begin{array}{rrrrr} 10. & 2. & 3.& 4.& 5. \\ 2.... ...ray}{r} 24. \\ 154. \\ 207.\\ 413.\\ 600. \end{array} \right) \end{displaymath}$
Prendendo come vettore iniziale ${\mathbf{x_0}}=(0,0,0,0,0)^T$ , si applichi il metodo iterativo di Jacobi per determinare la soluzione con una tolleranza ${\tt toll}=1.0 \times 10^{-9}$ ed utilizzando il test di arresto sulla norma euclidea del vettore residuo ${\mathbf{r_k}}$ .
Si scrivano sul file jac.dat, su ogni riga, i valori
$k \mbox{~~~~~} \displaystyle +\log_{10}\Vert{\mathbf{r_k}}\Vert _2$
ottenuti con la successione di iterate. Alla fine del file si scrivano anche i seguenti dati:
Tolleranza
Tolleranza $\times \, \, \Vert{\mathbf{b}}\Vert _2$
Numero di iterazioni eseguite
Vettore soluzione ${\mathbf{x}}$
Norma residuo finale
Si ripeta la risoluzione con il metodo di Gauss-Seidel (con gli stessi parametri) e si produca un file di nome gs.dat avente la medesima struttura descritta in precedenza per il file jac.dat.
Si rappresentino su di una stessa figure (di nome jacgs.ps), considerando come ascisse gli indici delle iterate, le curve di Jacobi e di Gauss-Seidel, corrispondenti ai valori $\displaystyle +\log_{10}\Vert{\mathbf{r_k}}\Vert _2$ .

Soluzioni:

sistema.dat, jac.dat

gs.dat

e jacgs.ps

Esercizio 9

Si consideri il sistema lineare che ha la seguente matrice aumentata, e la cui soluzione esatta è ${\mathbf{x}}=(1,1,1)^T$

$\begin{displaymath} \left( \begin{array}{rrr\vert r} \par 2& 0& 1& 3\\ 0 &2 &0 &2 \\ -1 &0& 2& 1 \end{array} \right) \end{displaymath}$
Dopo aver memorizzato nel file mat2.dat la matrice A, il termine noto ${\mathbf{b}}$ ed il vettore ${\mathbf{x_0}}=(0,0,0)^T$ , si applichi tre volte il metodo di risoluzione iterativo SOR che converge sempre se $0 < \omega \le 1$ .
Perchè? (si scriva la ragione di tale affermazione): Soluzione: E' una matrice strettamente diagonale dominante.
Si usi il test di arresto sulla norma euclidea del vettore residuo ${\mathbf{r_k}}$ , ${\tt toll}=10^{-8}$ e $k_{\max}=40$ . Per il parametro $\omega$ , si utilizzino i tre valori $\omega_1=0.5, \omega_2=1.0$ e $\omega_3=0.944272$ , scrivendo sui file omega1.dat, omega2.dat e omega3.dat i valori $\displaystyle +\log_{10}\Vert{\mathbf{r_k}}\Vert _2$ ottenuti con la successione di iterate e con i diversi valori assegnati ad $\omega$ .
Si rappresentino su di uno stesso grafico, considerando come ascisse gli indici delle iterate, le curve corrispondenti ai valori $\displaystyle +\log_{10}\Vert{\mathbf{r_k}}\Vert _2$ , verificando che il valore $\omega_3$ è quello a convergenza più rapida. Si memorizzi tale figura nel file sorres.ps.

Soluzioni:

mat2.dat, omega1.dat

omega2.dat

, omega3.dat e sorres.ps

Esercizio 10

Si consideri la seguente matrice (tali dati devono essere memorizzati su di un file di nome matrice.dat)

$\begin{displaymath}A = \left( \begin{array}{rrrrr} 1. & 2.& 3.& 4.& 5.\\ 2. &... ...26.& 148. \\ 5. & 28. & 74. & 148.& 255. \end{array} \right) \end{displaymath}$
Utilizzando il metodo di Gauss SENZA pivoting, si calcolino le due matrici ed della fattorizzazione e si scrivano tali matrici su di un file di nome gauss.dat (al massimo 4 cifre decimali dopo il punto di radice).
Utilizzando il metodo di Gauss-Crout, si calcolino poi le due matrici $L^\prime$ ed $U^\prime$ della fattorizzazione $A=L^\prime U^\prime$ e si scrivano tali matrici su di un file di nome crout.dat (al massimo 4 cifre decimali dopo il punto di radice).
Si consideri poi il sistema $A {\mathbf{x}} = {\mathbf{b}}$ con ${\mathbf{b}}=(15.,74.,207.,363.,510.)^T$ ed utilizzando la fattorizzazione di Gauss-Crout, si determini la soluzione ${\mathbf{x}}$ scrivendola su di un file di nome sol.dat (al massimo 4 cifre decimali dopo il punto di radice).

Soluzioni:

matrice.dat, gauss.dat

crout.dat

e sol.dat

Esercizio 11

Si consideri la seguente matrice simmetrica (tali dati devono essere memorizzati su di un file di nome matrice.dat)

$\begin{displaymath} \left( \begin{array}{rrr} 0.6428 & 0.3475 &-0.8468\\ 0.3475... ...8423 & 0.4759\\ -0.8468 & 0.4759 & 2.2147 \end{array} \right) \end{displaymath}$
Utilizzando il metodo di Cholesky si calcoli la matrice della fattorizzazione $A=L \, L^T$ verificando (con lo stesso programma) che il prodotto $L \, L^T$ restituisca la matrice originale . Si scriva la matrice ed il prodotto $L \, L^T$ su di un file di nome chol.dat (al massimo 4 cifre decimali dopo il punto di radice).
Si consideri poi il sistema $A {\mathbf{x}} = {\mathbf{b}}$ con ${\mathbf{b}}=(0.1435, 2.6657, 1.8438)^T$ e, utilizzando la fattorizzazione di Cholesky, si determini la soluzione ${\mathbf{x}}$ scrivendola su di un file di nome sol.dat (al massimo 4 cifre decimali dopo il punto di radice).
Si modifichi nella matrice la componente $a_{22}$ ponendola uguale a e si riapplichi la fattorizzazione di Cholesky. Con tale modifica la nuova matrice , pur essendo simmetrica, non è più definita positiva. Si scriva quindi nel file nondef.dat la nuova matrice e l'indice per il quale non è possibile calcolare il valore $l_{jj}$ (in quanto l'argomento della radice quadrata risulta essere negativo).

Soluzioni:

matrice.dat, chol.dat

e nondef.dat

Esercizio 12

Si consideri il sistema lineare che ha la seguente matrice aumentata (tali dati devono essere memorizzati su di un file di nome matrice.dat)

$\begin{displaymath} \left( \begin{array}{rrrrrr\vert r} 2 & 7 & 1 & -1 & -2 & 7... ... 2 & 1 & 16\\ -2 & 1 & 4 & 8 & 1 & 3 & 15 \end{array} \right) \end{displaymath}$
Utilizzando il metodo di Gauss CON pivoting, si calcolino le due matrici ed della fattorizzazione ed il vettore ${\mathbf{y}}$ e si scrivano tali dati su di un file di nome gaussp.dat (al massimo 4 cifre decimali dopo il punto di radice).
Si calcoli, risolvendo il sistema triangolare superiore $U{\mathbf{x}}={\mathbf{y}}$ , la soluzione del sistema, scrivendola sul file sol.dat (una componente per riga).
Si calcoli poi il prodotto della due matrici ed e lo si scriva sul file di nome prodlu.dat, verificando che esso corrisponde ad una permutazione di righe della matrice .

Soluzioni:

matrice.dat, gaussp.dat

e prodlu.dat

Esercizio 13

Si consideri il seguente sistema lineare $A{\mathbf{x}}={\mathbf{b}}$ la cui soluzione è ${\mathbf{x}}=(1.,1.,1.,1.,1.)^T$ (matrice e termine noto devono essere memorizzati e fatti leggere da un file di nome sistema.dat)

$\begin{displaymath}A = \left( \begin{array}{rrrrr} 1. & 2.& 3.& 4.& 5.\\ 2. &... ...array}{r} 15. \\ 74.\\ 207.\\ 363. \\ 510. \end{array} \right) \end{displaymath}$
Prendendo come vettore iniziale ${\mathbf{x_0}}=(0,0,0,0,0)^T$ , si applichi il metodo iterativo SOR, utilizzando il test di arresto sulla norma euclidea del vettore residuo ${\mathbf{r_k}}$ , ${\tt toll}=10^{-11}$ e $k_{\max}=100$ . Per il parametro $\omega$ , si utilizzino due valori $\omega_1=1.0$ (ovvero Gauss-Seidel) ed $\omega_2=1.06$ , scrivendo sui file omega1.dat e omega2.dat i valori $\displaystyle +\log_{10}\Vert{\mathbf{r_k}}\Vert _2$ ottenuti con la successione di iterate e con i due valori assegnati ad $\omega$ . Alla fine di ciascun file si scrivano anche i seguenti dati:
Tolleranza
Tolleranza * $\Vert{\mathbf{b}}\Vert _2$
Numero di iterazioni eseguite
Vettore soluzione ${\mathbf{x}}$
Norma residuo finale
Si rappresentino su di uno stesso grafico, considerando come ascisse gli indici delle iterate, le curve corrispondenti ai valori $\displaystyle +\log_{10}\Vert{\mathbf{r_k}}\Vert _2$ , verificando che il valore $\omega_2$ è quello a convergenza più rapida. Si memorizzi tale figura nel file sorres.ps.

Soluzioni:

sistema.dat, omega1.dat

omega2.dat

e sorres.ps