• Non ci sono risultati.

Sistemi di equazioni lineari a

N/A
N/A
Protected

Academic year: 2021

Condividi "Sistemi di equazioni lineari a"

Copied!
14
0
0

Testo completo

(1)

Sistemi di equazioni lineari

a 00 x 0 + a 01 x 1 + a 02 x 2 = b 0 a 10 x 0 + a 11 x 1 + a 12 x 2 = b 1 a 20 x 0 + a 21 x 1 + a 22 x 2 = b 2

Per N equazioni

N −1 X j=0

a ij x j = b i i = 0, N − 1

sono equivalenti ad una equazione matriciale

a 0,0 . . . a 0N −1 . . . . . . . . .

a N −1,0 . . . a N −1,N −1

x 0 . . . x N −1

 =

b 0 . . . b N −1

la soluzione ` e unica se det(A) 6= 0 e vale

~

x = A −1 ~b

(2)

Matrici triangolari

U ` e triangolare superiore se:

u ij = 0 per i > j.

U =

u 00 u 01 u 02 0 u 11 u 12 0 0 u 22

U~ x = ~b ` e molto facile da risolvere. Analoga- mente L ` e triangolare inferiore se l ij = 0 per i < j .

L =

l 00 0 0 l 10 l 11 0 l 20 l 21 l 22

U =

u 00 u 01 u 02 0 u 11 u 12 0 0 u 22

u 00 x 0 + u 01 x 1 + u 02 x 2 = b 0

u 11 x 1 + u 12 x 2 = b 1

u 22 x 2 = b 2

(3)

la cui soluzione ` e data da

x 2 = b 2 /u 22

x 1 = (b 1 − u 12 x 2 ) /u 11

x 0 = (b 0 − u 01 x 1 − u 02 x 2 ) /u 00

ogni x i viene usato solo dopo essere stato calcolato.

Per un sistema di N equazioni in N incognite la soluzione sar` a:

x i =

 b i

N −1 X k=i+1

u ik x k

 /u ii

che va applicata calcolando gli x i a partire dall’ultimo all’indietro.

Data l’efficacia di questo metodo, cerco di ridurre

ogni sistema di equazioni A~ x = ~b ad un sistema

triangolare U~ x = ~ b con opportuni U e b ~ .

(4)

Eliminazione gaussiana

Prendo un sistema di tre equazioni in tre inco- gnite

a 00 x 0 + a 01 x 1 + a 02 x 2 = b 0 a 10 x 0 + a 11 x 1 + a 12 x 2 = b 1 a 20 x 0 + a 21 x 1 + a 22 x 2 = b 2

sommando ad un’equazione il multiplo di un’altra la soluzione non cambia. Sottraggo allora alla seconda equazione la prima moltiplicata per λ e ottengo

(a 10 − λa 00 ) x 0 + (a 11 − λa 01 ) x 1 + (a 12 − λa 02 ) x 2

= b 1 − λb 0 voglio eliminare il termine che moltiplica x 1 ,

cosa che posso fare se scelgo λ = a 10 /a 00

ottenendo in questo modo che a 10 = 0

(5)

Posso ora ripetere il procedimento per la terza riga sottraendo la prima moltiplicata per a 20 /a 00 e ottengo

a 00 x 0 + a 01 x 1 + a 02 x 2 = b 0 a 11 x 1 + a 12 x 2 = b 1 a 21 x 1 + a 22 x 2 = b 2

con

a 11 = a 11a a 10

00 a 01 a 12 = a 12 − a 10 a 00 a 02 a 21 = a 21a a 20

00 a 01 a 22 = a 22 − a 20 a 00 a 02 b 1 = b 1a a 10

00 b 0 b 2 = b 2 − a 20

a 00 b 0

(6)

Sottraggo ora alla terza riga la seconda molti- plicata per a 21 /a 11 e ottengo

a 00 x 0 + a 01 x 1 + a 02 x 2 = b 0 a 11 x 1 + a 12 x 2 = b 1 a ′′ 22 x 2 = b ′′ 2

dove

a ′′ 22 = a 22 − a 21

a 11 a 12 e b ′′ 2 = b 2 − a 21 a 11 b 1

A~ x = ~b ` e stata quindi trasformata in U~ x = ~b e

il sistema pu` o ora essere risolto per backsub-

stitution.

(7)

Pivoting

Il metodo fin qui descritto non ` e molto stabile, cio` e gli errori si propagano amplificandosi, e possono portare a soluzioni molto sbagliate.

Si vede con la pratica che l’eliminazione gaus- siana ` e molto pi` u stabile se gli elementi di ma- trice sulla diagonale principale sono pi` u grandi degli altri in valore assoluto.

Ci` o si ottiene scambiando tra loro righe della matrice (pivoting parziale) oppure righe e colonne (full pivoting).

Se |a 20 | = max (|a 00 ||a 10 ||a 20 |) il pivoting parziale richiede lo scambio della prima e terza riga.

Guardo ora la seconda e terza riga: se |a 21 | >

|a 11 | scambio la seconda e la terza riga.

(8)

Come risultato su ogni diagonale sono piazzati gli elementi di massimo modulo tra quelli che stanno sotto l’elemento diagonale.

Scambiando le righe gli x i sono invariati. Se

scambio le colonne i e j , anche x i viene scam-

biato con x j .

(9)

Inversa di una matrice

AA −1 = A −1 A = 1

Se chiamo c ij gli elementi di matrice di A −1

X j

a ij c jk = δ ik

Sono N sistemi di N equazioni. Per una ma- trice di ordine 3 ad esempio

a 00 a 01 a 02 a 10 a 11 a 12 a 20 a 21 a 22

c 00 c 01 c 02 c 10 c 11 c 12 c 20 c 21 c 22

 =

1 0 0 0 1 0 0 0 1

Che pu` o essere spezzato in 3 sistemi di 3 equazioni lineari ciascuno il primo dei quali ` e

a 00 a 01 a 02 a 10 a 11 a 12 a 20 a 21 a 22

c 00 c 10 c 20

 =

1 0 0

(10)

Fisso un valore di k e chiamo ~b (i) il vettore che ha la i-esima componente uguale a uno, e nulle tutte le altre.

X j

a ij c jk = b (i) k

• Risolvere uno dei sistemi di equazioni vuole dire trovare gli elementi di matrice di una colonna della matrice inversa.

• Ripetendo per tutti i valori di i trovo la matrice intera.

• Non ` e necessario fare N volte l’eliminazione

gaussiana, perch´ e questa si pu` o fare con-

temporaneamente per tutte le equazioni.

(11)

Rappresentazione delle matrici

• nel linguaggio C tutti gli array sono monodimen- sionali

• una espressione del tipo a[i][j] indica un array monodi- mensionale di array monodimensionali

• l’accesso alla memoria ` e lento

• conviene definire array lineari di dimensione N × N e stabilire se si memorizza per riga o per colonna

• in questo modo ` e pi` u facile allocare dinamicamente la memoria

• una scelta possibile ` e che a[0] . . . a[N − 1] sia la riga zero, a[k · N ] . . . a[k · N + N − 1] la k-esima riga

• l’elemento con indice di riga uno pi` u di a[j] ` e a[j +1]

• l’elemento con indice colonna uno pi` u di a[j] ` e a[j + N ]

(12)

Tempo di calcolo

• La backsubstitution comporta 1. 1 divisione per l’ultima riga

2. 1 divisione + 1 prodotto + 1 sottrazione per la penultima riga

3. 1 divisione + k prodotti + k sottrazioni per la riga N − k

4. O(N

2

) operazioni

• L’eliminazione gaussiana comporta

1. Per azzerare la prima colonna N + 1 prodotti e sottrazioni pi` u una divisione da ripetere per N − 1 righe; quindi ` e O(N

2

)

2. bisogna ripetere per N − 2, N − 3, . . . , 1

3. si ottiene un procedimento O(N

3

)

(13)

Determinante

• Il determinante di una matrice non cam- bia aggiungengo ad una riga il multiplo di un’altra

• l’eliminazione gaussiana non cambia il de- terminante

• dopo l’eliminazione tutti gli elementi sotto la diagonale principale sono nulli

• il determinante, a questo punto, ` e dato dal

prodotto degli elementi diagonali

(14)

Esercizio

Considero la matrice

1 1 1 a b c a 2 b 2 c 2

Calcolo il determinante in funzione di a tenendo fissi b e c e faccio un grafico di quello che ot- tengo. Poi faccio la stessa operazione con una matrice 4 × 4 della forma

1 1 1 1

a b c d

a 2 b 2 c 2 d 2 a 3 b 3 c 3 d 3

e cerco di trovare una formula generale per una

matrice N × N di questo tipo

Riferimenti

Documenti correlati

Esempio: la formula inserita in \lefteqn comincia alla pun- ta della freccia orientata verso destra → FORMULA ← e finisce alla punta della freccia orientata verso sinistra...

Tengo ad esempio a far notare una notevole analogia tra ci che ho finora introdotto, e la cinematica di un punto nello spazio: data una legge oraria di un moto, ossia un insieme

Un metodo alternativo per stabilire il carattere di una forma quadratica (definita o semidefinita) si basa sull’analisi del segno dei minori principali della matrice associata

Nella parte relativa alle serie di funzioni, abbiamo visto che possi- amo sviluppare in serie di Taylor una funzione, se la funzione ammette derivate di tutti gli ordini in un punto

ESERCIZI

Si vede con la pratica che l’eliminazione gaus- siana ` e molto pi` u stabile se gli elementi di ma- trice sulla diagonale principale sono pi` u grandi degli altri in valore

Si vede con la pratica che l’eliminazione gaussiana ` e molto pi` u stabile se gli elementi di matrice sulla diago- nale principale sono pi` u grandi degli altri in valore asso-

Per i limiti di funzioni di pi` u variabili valgono teoremi analoghi a quelli visti per le funzioni di una variabile (teorema sul limite di una somma, di un prodotto, di un

Ci concentriamo sul modo in cui l’errore dipende dal parametro h e ignoriamo dettagli meno importanti come il valore

Per avere un metodo predictor-corrector di ordine 4 usando il metodo di Adams-Bashforth a due passi (metodo di ordine 2) come predictor e il metodo di Adams-Moulton a tre passi

- Variazione delle aree per trasformazioni lineari, teorema di cambiamento di variabili negli integrali doppi, calcolo di integrali mediante coordinate polari.. -

Nella seconda parte del corso, viene completato lo studio delle funzioni di una variabile reale con ulteriori capitoli riguardanti lo studio delle successioni e delle serie di

Per un sistema omogeneo la prima alternativa non si realizza mai, dunque o esiste un’unica soluzione, la banale, o esistono infi- nite soluzioni.. Come conseguenza del teorema di

Le suddette derivate sono differenziabili, in quanto combinazione o composizione di funzioni differenziabili.. Derivate di ordine superiore: matrice

Dobbiamo salvare gli scambi effettuati su A, per poterli applicare anche al termine noto in un secondo momento. Utilizziamo un’altra matrice P, inizialmente uguale

Ad esempio, se estraiamo a caso (magari tramite generazione casuale con R) 1000 punti da una gaussiana di media µ e matrice di covarianza Q, dove ci aspettiamo di torvare i 1000 punti

`e soddisfatta solo per x=3, valore per il quale il primo membro assume

Quindi le funzioni di una variabile hanno grafico in R 2 (e nella II parte di questo corso abbiamo imparato a trovare il grafico di tali funzioni), le funzioni di due variabili

Se invece il gradiente secondo `e definito, ad esempio positivo, (e anche qui si riveda la definizione del termine) in tutte le direzioni i valori della funzione aumentano e pertanto

Ciao a tutti, ecco i miei riassunti, ovviamente non posso garantire la correttezza (anzi garantisco la non totale correttezza) quindi se per caso trovate un errore se me le segnalate

l’equazione va risolta applicando lo schema di risoluzione per disequazioni irrazionali con una sola radice con radici cubiche (o in generale con radici ad indice dispari).

Marino Belloni – marino.belloni@unipr.it () Una breve introduzione al Teorema di Nash provvisorio 1 /

E’ accettabile x=2 nel primo sistema, il secondo sistema