LucioDemeioDipartimentodiScienzeMatematiche CorsodiAnalisiNumerica

(1)

Corso di Laurea in Ingegneria Informatica

Corso di Analisi Numerica

6 - METODI DIRETTI PER I SISTEMI LINEARI

Lucio Demeio

Dipartimento di Scienze Matematiche

(2)

1

Introduzione algebrica

2

Metodo di Gauss

3

Metodo di Gauss con pivoting

(3)

Formulazione matriciale

Sappiamo che un sistema lineare, di m equazioni in n incognite,



 



 



a

11

x

1

+ a

12

x

2

+ ... + a

1n

x

n

= b

1

a

21

x

1

+ a

22

x

2

+ ... + a

2n

x

n

= b

2

... ... ...

a

m1

x

¹

+ a

m2

x

²

+ ... + a

mn

x

n

= b

m

pu` o essere rappresentato in forma matriciale, come

A x = b dove A `e la matrice dei coefficienti, data da

 a a ... a 

(4)

Formulazione matriciale

mentre x e b sono i vettori colonna contenenti le incognite ed i termini noti, dati da

x =





 x

1

x

²

...

x

n







b =





 b

1

b

²

...

b

m







Spesso indicheremo con x

^T

= (x

1

, x

2

, ..., x

n

) e b

^T

= (b

1

, b

2

, ..., b

m

) i vettori riga, trasposti di x e b. La matrice m × (n + 1) data da

B =







a

¹¹

a

¹²

... a

¹n

b

¹

a

²¹

a

²²

... a

²n

b

²

... ... ... ...

a

m1

a

m2

... a

mn

b

m







`e detta matrice orlata o matrice completa.

(5)

Theorem (Teorema di Rouche’-Capelli)

Il sistema lineare di m equazioni in n incognite A x = b

ha soluzioni se e solo se il rango della matrice dei coefficienti A ed il rango della matrice completa B sono uguali. Se k `e il rango comune alle due matrici, allora le soluzioni del sistema formano uno spazio affine di dimensione n − k (cio`e il sistema ammette ∞

^n−k

soluzioni).

Quando n = k, il sistema ammette una ed una sola soluzione (cio`e si

conviene di porre ∞

⁰

= 1).

(6)

Sistemi con n = m

Quando il numero di incognite eguaglia il numero delle equazioni

allora il teorema si riduce al seguente:

(7)

Sistemi con n = m

Quando il numero di incognite eguaglia il numero delle equazioni allora il teorema si riduce al seguente:

Se det(A) 6= 0 il sistema ammette una ed una sola soluzione;

(8)

Sistemi con n = m

Quando il numero di incognite eguaglia il numero delle equazioni allora il teorema si riduce al seguente:

Se det(A) 6= 0 il sistema ammette una ed una sola soluzione;

se det(A) = 0 il sistema ammette infinite soluzioni se la matrice

completa ha rango < n (ed uguale al rango di A), se invece ha

rango massimo (n) il sistema `e incompatibile (non ha nessuna

soluzione).

(9)

Sistemi equivalenti Consideriamo il sistema

Ax = b

con A una matrice n × n, ed x e b vettori ad n componenti.

Indicando con R

j

gli elementi della riga j-esima del sistema, sappiamo

dall’algebra che le seguenti operazioni conducono ad un sistema

equivalente a quello di partenza (cio`e con la stessa soluzione):

(10)

Sistemi equivalenti Consideriamo il sistema

Ax = b

con A una matrice n × n, ed x e b vettori ad n componenti.

Indicando con R

j

gli elementi della riga j-esima del sistema, sappiamo dall’algebra che le seguenti operazioni conducono ad un sistema equivalente a quello di partenza (cio`e con la stessa soluzione):

moltiplicazione di un’equazione (cio`e degli elementi di una riga

della matrice completa) per uno scalare, λR

j

→ R

j

;

(11)

Sistemi equivalenti Consideriamo il sistema

Ax = b

con A una matrice n × n, ed x e b vettori ad n componenti.

Indicando con R

j

gli elementi della riga j-esima del sistema, sappiamo dall’algebra che le seguenti operazioni conducono ad un sistema equivalente a quello di partenza (cio`e con la stessa soluzione):

moltiplicazione di un’equazione (cio`e degli elementi di una riga della matrice completa) per uno scalare, λR

j

→ R

j

;

scambio di due equazioni (righe della matrice completa),

R

i

↔ R

j

;

(12)

Sistemi equivalenti Consideriamo il sistema

Ax = b

con A una matrice n × n, ed x e b vettori ad n componenti.

Indicando con R

j

gli elementi della riga j-esima del sistema, sappiamo dall’algebra che le seguenti operazioni conducono ad un sistema equivalente a quello di partenza (cio`e con la stessa soluzione):

moltiplicazione di un’equazione (cio`e degli elementi di una riga della matrice completa) per uno scalare, λR

j

→ R

j

;

scambio di due equazioni (righe della matrice completa), R

i

↔ R

j

;

sostituzione di un’equazione (di una riga) con una sua

combinazione lineare con altre equazioni (righe), ad esempio

αR

i

+ βR

j

→ R

j

(con β 6= 0).

(13)

Eliminazione di Gauss

(14)

Eliminazione di Gauss

L’eliminazione di Gauss consiste nell’eseguire una successione di

operazioni tra quelle descritte sopra fino a porre la matrice dei

coefficienti in forma triangolare.

(15)

Eliminazione di Gauss

L’eliminazione di Gauss consiste nell’eseguire una successione di operazioni tra quelle descritte sopra fino a porre la matrice dei coefficienti in forma triangolare.

Come esempio consideriamo il sistema







2 x

1

− x

2

+ 3x

3

= 1

−2 x

1

+ 3 x

2

− x

3

= −2

3 x

1

− 2 x

2

+ 2 x

3

= −1

(16)

Eliminazione di Gauss

L’eliminazione di Gauss consiste nell’eseguire una successione di operazioni tra quelle descritte sopra fino a porre la matrice dei coefficienti in forma triangolare.

Come esempio consideriamo il sistema







2 x

1

− x

2

+ 3x

3

= 1

−2 x

1

+ 3 x

2

− x

3

= −2 3 x

1

− 2 x

2

+ 2 x

3

= −1

Le operazioni R

1

+ R

2

→ R

2

e 3 R

1

− 2 R

3

→ R

3

trasformano il

sistema in 





2 x

1

− x

2

+ 3x

3

= 1

2 x

2

+ 2 x

3

= −1

x

2

+ 5 x

3

= 5

(17)

Eliminazione di Gauss 8

<

:

2 x

1

− x

²

+ 3x

3

= 1

2 x

²

+ 2 x

³

= −1

x

2

+ 5 x

3

= 5

(18)

Eliminazione di Gauss 8

<

:

2 x

1

− x

²

+ 3x

3

= 1 2 x

²

+ 2 x

³

= −1 x

2

+ 5 x

3

= 5

Ora R

2

− 2 R

³

→ R

³

trasforma il sistema in 8

<

:

2 x

1

− x

²

+ 3x

3

= 1 2 x

2

+ 2 x

3

= −1

−8 x

³

= −11

(19)

Eliminazione di Gauss 8

<

:

2 x

1

− x

²

+ 3x

3

= 1 2 x

²

+ 2 x

³

= −1 x

2

+ 5 x

3

= 5

Ora R

2

− 2 R

³

→ R

³

trasforma il sistema in 8

<

:

2 x

1

− x

²

+ 3x

3

= 1 2 x

2

+ 2 x

3

= −1

−8 x

³

= −11

Una volta ridotto in questa forma, il sistema pu` o essere risolto

facilmente per sostituzione all’indietro:

(20)

Eliminazione di Gauss

La procedura vista ora pu` o anche essere eseguita semplicemente sulla matrice orlata; nell’esempio precedente avremmo la successione:





2 −1 3 1

−2 3 −1 −2

3 −2 2 −1









2 −1 3 1 0 2 2 −1

0 1 5 5









2 −1 3 1

0 2 2 −1

0 0 −8 −11





Mathematica file Sistemi1.nb

(21)

Eliminazione di Gauss

La procedura ora pu` o essere formulata in generale.

(22)

Eliminazione di Gauss

La procedura ora pu` o essere formulata in generale.

Data la matrice orlata

B =







a

¹¹

a

¹²

... a

¹n

b

¹

a

²¹

a

²²

... a

²n

b

²

... ... ... ...

a

n1

a

n2

... a

nn

b

n







al primo passo sostituiamo la riga R

j

, j = 2, 3, ..., n, con la combinazione lineare R

j

− a

j1

R

¹

/a

¹¹

, ottenendo cos`ı zero come primo elemento di ogni riga dopo la prima; indicando sempre con R

j

la riga j -esima della matrice cos`ı ottenuta, al secondo passo sostituiamo la riga R

j

, j = 3, 4, ..., n, con la combinazione lineare R

j

− a

j2

R

2

/a

22

, ottenendo cos`ı zero anche come secondo

elemento di ogni riga dopo la seconda; e cos`ı via fino a rimanere

con un solo elemento nell’ultima riga.

(23)

Scambio di righe

(24)

Scambio di righe

Gli elementi diagonali a

¹¹

, a

²²

, ..., a

nn

che si vengono via via generando nella procedura sopra descritta vengono detti pivot.

E evidente che il metodo di Gauss, cos`ı come esposto nelle righe `

precedenti, fallisce quando uno dei pivot si annulla, cio`e se al

k-esimo passo della procedura, si ha a

kk

= 0.

(25)

Scambio di righe

Gli elementi diagonali a

¹¹

, a

²²

, ..., a

nn

che si vengono via via generando nella procedura sopra descritta vengono detti pivot.

E evidente che il metodo di Gauss, cos`ı come esposto nelle righe ` precedenti, fallisce quando uno dei pivot si annulla, cio`e se al k-esimo passo della procedura, si ha a

kk

= 0.

In tal caso, si cerca tra le righe successive la prima che presenta

un elemento non nullo nella medesima colonna e la si scambia con

R

k

. Questo metodo viene detto metodo dello scambio di

righe . Illustriamo il problema con un esempio.

(26)

Scambio di righe

Gli elementi diagonali a

¹¹

, a

²²

, ..., a

nn

che si vengono via via generando nella procedura sopra descritta vengono detti pivot.

E evidente che il metodo di Gauss, cos`ı come esposto nelle righe ` precedenti, fallisce quando uno dei pivot si annulla, cio`e se al k-esimo passo della procedura, si ha a

kk

= 0.

In tal caso, si cerca tra le righe successive la prima che presenta un elemento non nullo nella medesima colonna e la si scambia con R

k

. Questo metodo viene detto metodo dello scambio di righe . Illustriamo il problema con un esempio.

Se non si riesce a trovare un pivot, vuol dire che il sistema non ha

un’unica soluzione (possono essercene infinite oppure nessuna).

(27)

Scambio di righe

Gli elementi diagonali a

¹¹

, a

²²

, ..., a

nn

che si vengono via via generando nella procedura sopra descritta vengono detti pivot.

E evidente che il metodo di Gauss, cos`ı come esposto nelle righe ` precedenti, fallisce quando uno dei pivot si annulla, cio`e se al k-esimo passo della procedura, si ha a

kk

= 0.

In tal caso, si cerca tra le righe successive la prima che presenta un elemento non nullo nella medesima colonna e la si scambia con R

k

. Questo metodo viene detto metodo dello scambio di righe . Illustriamo il problema con un esempio.

Se non si riesce a trovare un pivot, vuol dire che il sistema non ha

un’unica soluzione (possono essercene infinite oppure nessuna).

(28)

Metodo del pivoting parziale

(29)

Metodo del pivoting parziale

Con alcuni sistemi, risulta necessario effettuare lo scambio di

righe anche se uno degli elementi sulla diagonale non `e

rigorosamente nullo, ma soltanto molto piccolo.

(30)

Metodo del pivoting parziale

Con alcuni sistemi, risulta necessario effettuare lo scambio di righe anche se uno degli elementi sulla diagonale non `e rigorosamente nullo, ma soltanto molto piccolo.

Sia, ad esempio, a

kk

questo elemento. In tal caso, si cerca tra le righe successive quella che presenta l’elemento pi` u grande (in valore assoluto) nella medesima colonna e la si scambia con R

k

. Questo metodo viene detto metodo del pivoting parziale.

Illustriamo il problema con un esempio.

(31)

Metodo del pivoting parziale

Con alcuni sistemi, risulta necessario effettuare lo scambio di righe anche se uno degli elementi sulla diagonale non `e rigorosamente nullo, ma soltanto molto piccolo.

Sia, ad esempio, a

kk

questo elemento. In tal caso, si cerca tra le righe successive quella che presenta l’elemento pi` u grande (in valore assoluto) nella medesima colonna e la si scambia con R

k

. Questo metodo viene detto metodo del pivoting parziale.

Illustriamo il problema con un esempio.

Vedi Mathematica file Sistemi3.nb

(32)

Metodo del pivoting parziale riscalato

(33)

Metodo del pivoting parziale riscalato

Con alcuni sistemi, il metodo del pivoting parziale non `e

sufficiente. Si ricorre allora al metodo del pivoting parziale

riscalato

(34)

Metodo del pivoting parziale riscalato

Con alcuni sistemi, il metodo del pivoting parziale non `e sufficiente. Si ricorre allora al metodo del pivoting parziale riscalato

Il metodo `e del tutto simile a quello del pivoting parziale, solo

che la ricerca della riga con cui effettuare lo scambio avviene

determinando il pivot che ha il rapporto massimo con gli elementi

della propria riga.

(35)

Metodo del pivoting parziale riscalato

Con alcuni sistemi, il metodo del pivoting parziale non `e sufficiente. Si ricorre allora al metodo del pivoting parziale riscalato

Il metodo `e del tutto simile a quello del pivoting parziale, solo che la ricerca della riga con cui effettuare lo scambio avviene determinando il pivot che ha il rapporto massimo con gli elementi della propria riga.

Illustriamo il metodo solo relativamente al primo passo, poi si

procede allo stesso modo. Ricordiamo che, al primo passo, lo

scopo dell’eliminazione di Gauss `e di ottenere degli zeri nella

prima colonna dalla seconda riga in poi.

(36)

Metodo del pivoting parziale riscalato

Con alcuni sistemi, il metodo del pivoting parziale non `e sufficiente. Si ricorre allora al metodo del pivoting parziale riscalato

Il metodo `e del tutto simile a quello del pivoting parziale, solo che la ricerca della riga con cui effettuare lo scambio avviene determinando il pivot che ha il rapporto massimo con gli elementi della propria riga.

Illustriamo il metodo solo relativamente al primo passo, poi si procede allo stesso modo. Ricordiamo che, al primo passo, lo scopo dell’eliminazione di Gauss `e di ottenere degli zeri nella prima colonna dalla seconda riga in poi.

...

(37)

Metodo del pivoting parziale riscalato

(38)

Metodo del pivoting parziale riscalato

Sia s

i

il massimo elemento (in valore assoluto) della riga i−esima,

cio`e s

i

= max

j=1,n

|a

ij

|, per i = 1, ..., n; per ogni riga, calcoliamo

il rapporto |a

i1

|/s

i

e sia p la riga per cui questo rapporto `e

massimo;

(39)

Metodo del pivoting parziale riscalato

Sia s

i

il massimo elemento (in valore assoluto) della riga i−esima, cio`e s

i

= max

j=1,n

|a

ij

|, per i = 1, ..., n; per ogni riga, calcoliamo il rapporto |a

i1

|/s

i

e sia p la riga per cui questo rapporto `e massimo;

allora effettuiamo lo scambio R

1

↔ R

p

.

(40)

Metodo del pivoting parziale riscalato

Sia s

i

il massimo elemento (in valore assoluto) della riga i−esima, cio`e s

i

= max

j=1,n

|a

ij

|, per i = 1, ..., n; per ogni riga, calcoliamo il rapporto |a

i1

|/s

i

e sia p la riga per cui questo rapporto `e massimo;

allora effettuiamo lo scambio R

1

↔ R

p

.

E pi` ` u difficile a spiegarsi che a farne un esempio!

Vedi Mathematica file Sistemi3.nb