Appunti completi di Metodi numerici

RIASSUNTI METODI NUMERICI 9 CFU – A.A. 2019/2020

Prof. Fiorella Sgallari

1. Ripasso di algebra lineare

2. Introduzione

3. Derivazione numerica

4. Sistemi non lineari

5. Sistemi lineari

6. Prodotto scalare

7. Sistemi lineari iterativi

8. Interpolazione

9. Approssimazione

10. Formule di quadratura 1

RIPASSO DI ALGEBRA LINEARE

Matrici

Tabella ordinata di elementi:

▪ Matrice m x n è matrice con m righe e n colonne

▪

Indichiamo con () la riga i-esima, con 1 ≤ ≤

▪

Indichiamo con () la colonna j-esima, con 1 ≤ ≤ n

Esempi:

Definizione: Sia A una matrice m x n. Siano 1 ≤ i < i < . . . < i ≤ m e 1 ≤ j < j < . . . < j ≤ n due set di indici.

1 2 k 1 2 l

La matrice S(k×l) di elementi s = a con p = 1, . . ., k, q = 1, . . ., l è detta sottomatrice di A.

pq ipjq

Se k = l e ir = jr per r = 1, . . ., k, allora S è detta sottomatrice principale di A, cioè quando gli indici che

scegliamo per le righe e per le colonne sono gli stessi.

Esempio:

Alcune sottomatrici di A:

- Considerando le righe 1 e 2 e le colonne 1, 2 e 4 di A

- Considerando le righe 1,2 e 3 e le colonne 2 e 4 di A

- Considerandola prima riga e la prima colonna di A

- Righe 1,2 e 3 e colonne 1,2,3 di A 2

Definizione: Data una matrice A m x n, indichiamo con la matrice trasposta di A il cui elemento di posto

(i,j) è l’elemento (j,i) di A. T

In pratica la prima riga di A diventa la prima colonna di A , la i-esima riga di A diventa la i-esima colonna di

T

A . Se A è una matrice m x n, allora sarà una matrice n x m.

Esempi:

Definizione: Data una matrice A, essa è simmetrica se A = , invece è detta antisimmetrica se A = -

Se A è una matrice m x n, allora è una matrice n x m, quindi se A è simmetrica (cioè A = ) allora anche

→

le dimensioni devono coincidere, cioè m=n. Le matrici simmetriche e antisimmetriche sono matrici

quadrate.

Esempi: 3

Operazioni tra matrici

• Somma tra matrici: Date due matrici A e B, entrambe di dimensioni m x n, la somma A+B è una

matrice m x n il cui elemento (i,j) è dato dalla somma dell’elemento (i,j) di A con l’elemento (i,j) di B;

• Prodotto per scalare: Data una Matrice A m x m, e uno scalare λ, il prodotto per scalare tra la matrice

A e lo scalare λ è una matrice m x n ottenuta da A moltiplicando ogni elemento per λ. Indichiamo tale

matrice con λA;

• Prodotto tra matrici: Date due matrici A m x n e B n x p si definisce il prodotto C = AB come la matrice

m x p il cui elemento di posto (i,j) è dato da ;

Regola pratica per calcolare gli elementi del prodotto tra due matrici.

Se voglio calcolare l’elemento di posto (i,j) della matrice prodotto:

o Considero la riga i della matrice A (della prima matrice)

o Considero la colonna j della matrice B (della seconda matrice)

o Moltiplico il primo elemento della riga con il primo della colonna, il secondo della riga con il

secondo della colonna, e così via

o Sommo tutti i prodotti

(In pratica faccio il prodotto scalare tra il vettore della riga i di A e quello della colonna j di B)

Esempio:

Poiché il numero delle colonne della matrice A è uguale al numero delle righe della matrice B posso fare il

prodotto tra le due matrici: esso sarà una matrice 2 x 3. Calcoliamo gli elementi della prima riga della

matrice prodotto C=AB. 4

Seguendo la formula si ha che:

Se voglio calcolare l’elemento di posto (1,3) della matrice prodotto:

o Considero la riga 1 della matrice A: (1 1 2)

o Considero la colonna 3 della matrice B: (1 1 1)

o Moltiplico il primo elemento della riga con il primo della colonna, il secondo della riga con il

,

secondo della colonna, e così via: 1∙ ∙ 1, 2∙ 1

o Sommo tutti i prodotti: 1∙1 + 1∙1 + 1∙2 = 1+1+2 = 4

ATTENZIONE!

• Il prodotto tra due matrici non è sempre definito: poiché per poter fare il prodotto il numero di colonne

della prima matrice deve essere uguale al numero di righe della seconda.

Quindi in questo caso non è possibile fare il prodotto tra matrici, ma invertendole invece si, ciò fa capire un

ulteriore proprietà che è il prodotto tra matrici non è commutativo.

• Il prodotto tra matrici non è commutativo: 5

Matrici speciali

• Matrice triangolare superiore (m x m): è una matrice quadrata dove tutti gli elementi al di sotto

della diagonale principale sono nulli

• Matrice triangolare inferiore (m x m): è una matrice quadrata dove tutti gli elementi al di sopra

della diagonale principale nulli

• Matrici diagonali (n x n): sono matrici triangolari sia superiori che inferiori, cioè hanno gli elementi

sopra e sotto la diagonale principale tutti nulli

• Matrici identità (n x n): matrice quadrata e diagonale con gli elementi della diagonale tutti 1, in

genere indichiamo con la matrice identità di dimensioni (n x n)

Prodotto con la matrice identità: siano A matrice (m x n), e matrici identità, allora quello che

otteniamo è la matrice stessa 6

•

Matrici di permutazione (n x n): è una matrice ottenuta dalla matrice identità scambiando due

righe i e j

Prodotto con una matrice di permutazione:

▪

moltiplicare a sinistra per una matrice di permutazione scambia le righe i e j:

▪

moltiplicare a destra per una matrice di permutazione scambia le colonne i e j:

• Matrici di Hessenberg superiore (n x n): sono matrici quadrate che hanno valori nulli sotto la prima

sottodiagonale

• Matrici di Hessenberg inferiore (n x n): sono matrici quadrate che hanno valori nulli sopra la prima

sopradiagonale 7

• Matrici a banda (n x n): matrici quadrate i cui elementi diversi da zero sono tutti posti in una banda

diagonale che comprende la diagonale principale e, opzionalmente, una o più diagonali alla sua

destra o alla sua sinistra. In particolare, se consideriamo p e q la semiampiezza

di banda, rispettivamente sinistra e destra.

= 0 > + > +

Se p = q = 1 la matrice è detta tridiagonale:

• Matrici a diagonale dominanza per righe (n x n): una matrice A (n x n) è a diagonale dominante per

righe se

• Matrici a diagonale strettamente dominanza (n x n): una matrice A (n x n) è a diagonale

strettamente dominante se il valore assoluto della diagonale è maggiore della somma del valore

assoluto degli altri elementi della riga

• Esistono anche le matrici a diagonale dominanza per colonne

8

Matrici invertibili

Definizione: Una matrice quadrata A (n x n) si dice invertibile (o regolare o non singolare) se esiste una

matrice B (n x n) tale che −

è detta matrice inversa di ed è indicata con

Una matrice non invertibile è detta singolare.

Condizione di non singolarità: Una matrice quadrata è invertibile se e solo se il suo determinante è diverso

da 0 (detA≠0).

Esempi:

Proprietà delle matrici

▪ La trasposta della matrice trasposta corrisponde alla matrice stessa

( ) =

▪ La trasposta di una somma di due matrici è uguale alla trasposta della prima matrice più la trasposta

della seconda matrice )

( + = +

▪ La trasposta di un prodotto di due matrici è uguale al prodotto della seconda matrice trasposta per la

prima matrice trasposta (si inverte l’ordine delle matrici)

)

( ∙ = ∙

▪ La trasposta di un prodotto per scalare è uguale alla matrice trasposta moltiplicata per lo scalare

() =

▪ − − −

Se è invertibile, anche la sua inversa è invertibile e ( ) =

Quindi se ho una matrice quadrata invertibile, ed anche la sua inversa è invertibile, allora facendo

l’inversa della matrice inversa si ottiene la matrice iniziale

▪ − −

) -

Se è invertibile, allora è invertibile e ( ) = ( =

Quindi se ho una matrice quadrata invertibile, ed anche la sua trasposta è invertibile, allora facendo

-

l’inversa della matrice trasposta è uguale alla trasposta della matrice inversa si può scrivere come

▪ ∙

Se e sono due matrici invertibili di ordine n, allora anche il prodotto è invertibile e si ha

− − -1

(∙) = ∙

Quindi se ho due matrici quadrate invertibili dello stesso ordine, allora si può dimostrare che anche il

loro prodotto è invertibile 9

Matrici

Definizione: sia A una matrice (m x n) a valori in C, chiamiamo coniugata trasposta (o aggiunta) di A la

matrice = tale che = dove è il complesso coniugato di

i

Il coniugato di un numero complesso si fa cambiando il segno davanti al termine complesso.

Definizione: sia A una matrice (n x n) a valori in C, diciamo che A è hermitiana (o autoaggiunta) se la

H

=

matrice trasposta è uguale alla matrice coniugata =, cioè se ovvero alla sua matrice

coniugata trasposta. ∙

Definizione: una matrice quadrata A (n x n) a valori complessi in C è detta unitaria se = ∙ = ,

H

−1

cioè se = ovvero l’inversa della matrice A è uguale alla matrice coniugata trasposta.

−1

Definizione: una matrice A (n x n) è detta ortogonale se ∙ = ∙ = , cioè se = ovvero

l’inversa della matrice A è uguale alla sua trasposta.

Esempio: 3 3

Consideriamo un’applicazione lineare da a la cui matrice è simmetrica ed è la seguente

Calcoliamo gli autovalori: 3,-1,1 e i relativi autovettori normalizzati

La matrice degli autovettori è ortogonale, infatti, se moltiplichiamo la

matrice per la sua trasposta si ottiene una matrice identità (I ), e la stessa cosa si ottiene se facciamo

3

T

B *B. 10

Definizione di matrice definita positiva

• Caso complesso: Una matrice A n x n a valori in C si dice definita positiva se è un numero reale

∈

e positivo per ogni vettore del campo complesso di dimensione n , ≠ 0

• Caso reale: Una matrice A n x n a valori in si dice definita positiva se > 0 è un numero

∈

positivo per ogni vettore diverso dal vettore nullo , ≠ 0

Proprietà: Una matrice A n x n simmetrica, è definita positiva se tutti i suoi autovalori sono positivi.

Quindi in un caso reale per vedere se una matrice è definita positiva si lavora sulla trasposta, mentre

in un caso complesso si lavora sulla matrice coniugata trasposta.

Esempi:

- non è definita positiva (poiché tre autovalori sono positivi mentre uno è negativo)

- La Matrice identità è definita positiva (autovalori sono tutti pari a 1)

- Per dimostrare che una matrice è semidefinita positiva, si considera un generico vettore delle

fare z Mz

dimensioni della matrice, > 0 e vedere se questo prodotto è un numero positivo

- 11

METODO DI ELIMINAZIONE DI GAUSS

Un metodo per risolvere equazioni lineari simultanee, quindi possiamo scrivere il sistema di equazioni in

forma vettoriale [A][X]=[C]

Il metodo è costituito da due passi:

1. Forward Elimination

2. Back Substitution (sostituzione all’indietro)

Forward Elimination

L’obiettivo della forward elimination è di trasformare la matrice dei coefficienti in una matrice triangolare

superiore, ovvero in una matrice più semplice per risolvere il sistema.

Per effettuare questa trasformazione, si parte dal considerare n equazioni in n incognite, e dobbiamo

andare ad annullare tutti i termini al di sotto della diagonale:

(n-1) steps of forward elimination

Step 1

Per iniziare a rendere triangolare superiore la matrice dei coefficienti, vogliamo che il primo coefficiente

dell’equazione 2 si annulli.

Sappiamo che il risultato di un sistema non cambia se facciamo operazioni di somma, differenza o

moltiplicazione per scalare tra le righe. Per questo motivo sostituiamo l'equazione 2 con una differenza tra

l'equazione 2 e l'equazione 1 moltiplicata per uno scalare γ, attraverso il quale andiamo ad annullare il

primo termine della seconda equazione: 12

Quindi per modificare l’equazione 2, dividiamo l’equazione 1 per a e la moltiplichiamo per a :

21 11

E sottraiamo il risultato all’equazione 2:

Rinominando i nuovi coefficienti otteniamo la nuova equazione 2, in cui avremo il coefficiente della x 1

nullo:

Ripetiamo la procedura per le rimanenti equazioni in modo che il set di equazioni sia nella forma seguente

(la prima Colonna dei coefficienti ha un valore non nullo solo al primo posto):

13

Step 2

Ripetiamo la stessa procedura “eliminando” il secondo termine delle equazioni dalla terza in poi.

Otteniamo quindi un Sistema in cui la seconda colonna dei coefficienti ha valori nulli dal terzo in poi.

Alla fine degli (n-1) Step di forward elimination, il Sistema di equazioni sarà della seguente forma:

Forma matriciale alla fine dello Step di Forward Elimination:

14

Back Substitution

Esempio di un sistema di 3 equazioni, si risolve ogni equazione partendo dall’ultima poiché è presente una

sola incognita:

Poiché conosciamo x , la penultima equazione ora contiene una sola incognita x -1:

n n

Poiché conosciamo x , x -1, la terzultima equazione ora contiene una sola incognita x -2, e così via,

n n n

continuando a risolvere le equazioni dal basso verso l’alto.

15

Esempio 1 di eliminazione di Gauss: Dato un sistema lineare di 3 equazioni in 3 incognite, troviamo la

soluzione del sistema con il metodo di Gauss.

Forward Elimination: Step 1

Vogliamo che il primo coefficiente della seconda equazione diventi zero, e siccome è già zero possiamo non

fare nessuna operazione sulla matrice, ma in teoria dovremmo sottrarre alla seconda equazione la prima

equazione moltiplicata per 0/0.2425:

E sostituiamo il risultato nella seconda equazione:

Ora vogliamo che il primo coefficiente della terza equazione diventi zero, quindi sottraiamo alla terza

equazione la prima equazione moltiplicata per -0.2357/0.2425:

E sostituiamo il risultato nella terza equazione:

Forward Elimination: Step 2

Ora vogliamo che il secondo coefficiente della terza equazione diventi zero, quindi sottraiamo alla terza

equazione la seconda equazione moltiplicata per -0.2357/0.2425:

16

E sostituiamo il risultato nella terza equazione:

La matrice ottenuta è in forma triangolare superiore.

Back Substitution: Inizio a risolvere il sistema dall’ultima equazione e poi continuo dal basso verso l’alto.

Il vettore soluzione del sistema lineare è: 17

Esempio 2 di eliminazione di Gauss: Dato un sistema lineare di 3 equazioni in 3 incognite, troviamo la

soluzione del sistema con il metodo di Gauss.

→

Forward Elimination: Step 1

Vorremmo che il primo coefficiente della seconda riga si annulli, per fare ciò dovremmo moltiplicare la

prima riga per 6/0, ma non possiamo dividere per zero!!

Allora in questo caso possiamo andare a scambiare l’ordine delle equazioni, tanto la soluzione del sistema

rimane la stessa. Scambiamo quindi la prima e la seconda equazione:

In questo modo il primo coefficiente della seconda riga è già 0, quindi possiamo concentrarci sull’eliminare

il primo coefficiente della terza riga.

Vorremmo che il primo coefficiente della terza riga si annulli, quindi sottraiamo alla terza riga la prima riga

moltiplicata per 5/6:

Da cui: 18

Forward Elimination: Step 2

Vorremmo che il secondo coefficiente della terza riga si annulli, quindi sottraiamo alla terza riga la seconda

riga moltiplicata per (-8/3)/10 = -8/30:

Da cui:

La matrice ottenuta è in forma triangolare superiore.

Back Substitution: Inizio a risolvere il sistema dall’ultima equazione e poi continuo dal basso verso l’alto.

Il vettore soluzione del sistema lineare è: 19

Esempio 3 di eliminazione di Gauss: Dato un sistema lineare di 3 equazioni in 3 incognite, troviamo la

soluzione del sistema con il metodo di Gauss.

→

Risolviamo con il metodo di Gauss Forward Elimination: Step 1

• Sottraiamo alla seconda riga la prima

• Sottraiamo alla terza riga la prima riga moltiplicata per 2

→

• Forward Elimination: Step 2 Sottraiamo quindi alla terza riga la «nuova» seconda riga

N.B. Il sistema non ha soluzione: non tutti i sistemi ammettono una soluzione!

Esempio 4 di eliminazione di Gauss: Dato un sistema lineare di 3 equazioni in 3 incognite, troviamo la

soluzione del sistema con il metodo di Gauss.

→

Risolviamo con il metodo di Gauss Forward Elimination: Step 1

• Sottraiamo alla seconda riga la prima moltiplicata per -1

• Sottraiamo alla terza riga la prima riga

N.B. Il sistema ammette infinite soluzioni! Perché ci ritroviamo con un sistema di 2 equazioni con 3

incognite. 20

Esempio 5 di eliminazione di Gauss: Dato un sistema lineare di 3 equazioni in 3 incognite, troviamo la

soluzione del sistema con il metodo d