Algoritmo di riduzione di Gauss per la discussione e soluzione dei sistemi lineari
Rosalba Barattero
ESERCITAZIONE N.2
8 marzo 2010
SISTEMI LINEARI : ESEMPI due equazioni e due incognite
Esempio 1
1 y x
0 y
x
Esempio 2
2 y x
0 y - x
Esempio 3
2 2y 2x
1 y -
x
Nessuna soluzione
Disegni nel piano reale affine
Una (ed una sola) soluzione
infinite soluzioni (x, x-1) al variare di x in R
y
x 2
P(1,1) 1
O 1 2 y
O x
1
1
y
x -1
O 1
Nella pagina precedente sono illustrati tre esempi di sistemi lineari di due equazioni e due incognite, a
coefficiente reali e la relativa interpretazione geometrica nel piano reale.
Nel piano reale l’insieme delle soluzioni di un’ equazione di primo grado corrisponde all’insieme dei punti di una retta.
Trovare le soluzioni di un sistema lineare di due equazioni in due incognite equivale a determinare l’insieme dei punti di coordinate (x,y) che soddisfano entrambe le equazioni.
Dunque il problema algebrico di risolvere un sistema di due equazioni in due incognite si traduce nello studiare l’intersezione di due rette nel piano.
Nel piano reale due rette o sono coincidenti o sono distinte e in questo ultimo caso sono parallele o incidenti in un punto.
Questo ci dice che per i sistemi a due equazioni e due incognite si presentano tre casi : nessuna soluzione, un’unica soluzione, infinite soluzioni.
Vedremo che questa casistica vale per tutti i sistemi lineari.
ESERCIZIO1.
Sistema lineare – riduzione di Gauss
Dato il seguente sistema lineare a coefficienti reali
0 z y x
2 z y x
3 z y x
Stabilire, usando l’algoritmo di riduzione di Gauss, se ha soluzioni reali e, in caso affermativo determinarle tutte.
Notiamo che il sistema si può scrivere in forma matriciale, tenendo conto della definizione del prodotto righe per colonne di matrici:
0 2 3 z
y x 1 1 - 1
1 - 1 1
1 1 1
Il sistema è esprimibile così : A X = b A
matrice dei coefficienti
X
matrice delle indeterminate b
matrice dei termini noti
L’ALGORITMO DI GAUSS
OBIETTIVO : A)Individuare criteri per stabilire se un sistema lineare ha soluzioni e quante sono.
B) Usare un algoritmo per determinare le solu- zioni.
LE TRE OPERAZIONI ELEMENTARI SULLE EQUAZIONI DI UN SISTEMA:
1. Scambio di due equazioni
2. Moltiplicazione di un’equazione per un numero non nullo
3. Somma di un’equazione con un multiplo di un’altra equazione
Le 3 operazioni trasformano il sistema in un sistema equivalente ( avente le stesse soluzioni). Le operazioni agiscono sulle equazioni (righe) del sistema
(equivalentemente sulle righe della matrice completa A|b ).
Infatti la 1. è ovvia poiché lo scambio di due equazioni non altera le soluzioni del sistema, lo stesso vale per 2., poiché la moltiplicazione di un’equazione per un numero non nullo non altera le soluzioni dell’equazione stessa.
Meno banale la 3.
Usiamo l’algoritmo di Gauss per trasformare un sistema in uno equivalente e più semplice da risolvere.
Lavoriamo sulla matrice completa
A/b =
0 2 3 1 1 1
1 1 1
1 1 1
1. Passo: ricerca nella 1a colonna di un termine non nullo (coefficiente della prima incognita), se esiste questo termine scelto si chiama pivot (della prima incognita).
Se non esiste, si passa a considerare la seconda inco- gnita …etc.
Scelto il pivot, scambiare R1 con la riga che contiene il pivot per portarla ad occupare R1
Qui a11=1≠0non è necessario scambiare righe 2. PASSO : creare una colonna di zeri sotto il pivot
0 2 3 1 1 1
1 1 1
1 1 1
3 -
1 -
3 0 2 0
2 0 0
1 1 1
N.B. nel passo 1. possono esserci più scelte,in generale conviene scegliere il pivot più semplice per effettuare a mano facilmente i calcoli (1 è il più indicato). Per un calcolatore il pivot migliore è il numero di valore assoluto maggiore, per minimizzare gli errori (a seguito della divisione, infatti ad es. per mettere uno zero sotto l’elemento a11 l’operazione da fare sarà R2 R2- 1
11 22R a
a ).
R2 R2- R1 R3 R3- R1
Operiamo su R2 , R3 facendo sempre riferimento ad R1
Osservazione Fare R2 R2- R1 equivale a sostituire la x nella R2 .
Infatti : R1 x+y+z -3=0 R2 x+y-z-2=0
R2- R1 x+y-z-2 –( x+y+z-3)=0
L’algoritmo di Gauss nasce dalla tecnica di sostituzione
3. Passo : controllare se
qualche riga sotto R1 è diventata nulla e in tal caso eliminarla
qualche riga sotto R1 è diventata del tipo 0 0 0 … 0 | k con k ≠0,
cioè se il sistema contiene l’equazione incompatibile 0 = k , con k≠0.
In tal caso ci si ferma : il sistema dato è incompatibile ( non ha soluzioni ).
In caso contrario si prosegue con il passo 4.
Espressione della x ricavata da R1
4. Passo : spostarsi, a partire dal pivot, in diagonale di un elemento
Ossia trascurare la riga R1 e ripartire con l’algoritmo appli- cato al sistema formato dalle righe restanti (R2,R3,… ), quindi cercare nella colonna contenente P2 ( C2) se c’è un elemento non nullo…
Attenzione ! Se la colonna contenente P2 è tutta nulla, allora spostarsi all’incognita successiva ( nella riga R2 )!
Altrimenti non si ottiene una matrice a scalini ! cioè una matrice in cui il primo coefficiente non nullo di ogni riga è più a sinistra del primo coefficiente non nullo della riga successiva. I primi elementi non nulli di ogni riga sono i pivot .
Esempio di matrici a scalini ( echelon)
indicano i pivot, i primi elementi non nulli delle righe
indicano numeri che possono avere qualunque valore, anche zero P1
P2
sì
no P1
P2
3 -
1 -
3 0 2 0
2 0 0
1 1 1
R2 R3
1 -
3 -
3 2 - 0 0
0 2 - 0
1 1 1
1 -
3 -
3 2 - 0 0
0 2 - 0
1 1 1
1 -
3 -
3 2 - 0 0
0 2 - 0
1 1 1
Il sistema associato ridotto è
1 - 2z -
3 - 2y
3 z y x
Cerchiamo un elemento non nullo nella C2 ( R1 esclusa )
Nuovo pivot Sotto c’è già lo zero !
L’algoritmo termina passando alla R3
Siamo arrivati alla forma a scalini
( o ridotta)
In questo caso tutte e tre le incognite sono pivotali ( con pivot risp. : 1, -2, -2).
Passiamo alla risoluzione : è ora facile procedere dal basso verso l’alto per sostituzione , ottenendo la soluzione
2 ,1 2 ,3
1 , che è unica ( x1,y 23,z 21 : unica terna ) .
Conclusione :
In questo caso le incognite sono tutte pivotali. Il loro numero uguaglia il numero non nullo delle righe della matrice ridotta a scalini e il sistema ha UNA SOLA SOLUZIONE .
Da notare che ci sono più sistemi ridotti equivalenti al sistema dato, in corrispondenza alle scelte dei pivot.
ESERCIZIO2.
Sistema lineare
Dato il seguente sistema lineare a coefficienti reali
2 2t z 2 y x
2 t z y 2 2x
1 t z y x
Stabilire, usando l’algoritmo di riduzione di Gauss, se ha soluzioni reali.
A/b=
2 2 1 2 2 1 1
1 1 2 2
1 1 1 1
1 0 1 1 1 0 0
1 1 0 0
1 1 1 1
1 0 1 0 0 0 0
1 1 0 0
1 1 1 1
Passo 3. L’ultima riga è del tipo 0 =1 ( 0 x = 1 ) : assurdo. Quindi il sistema è incompatibile ( non ha soluzioni ).
N.B. da non confondere con il caso 1=0 , ad esempio 0 0 0 1 | 0, da cui si ricava t=0 !!
R2 R2-2R1
R3 R3-R1
R3 R3+R2
ESERCIZIO3.
Sistema lineare – riduzione – numero delle soluzioni
Dato il seguente sistema lineare
0 x - x
1 x
x
2 x - x x x x
5 4
5 3 2
5 4 3 2 1
x
Stabilire, usando l’algoritmo di riduzione totale di Gauss, se ha soluzioni e, in caso affermativo, dire quante sono e determinarle tutte.
A|b =
0 1 2 1 1 0 0 0
1 0 1 1 0
1 1 1 1 1
E’ già ridotta ! Le incognite pivotali sono x1, x2, x4. Isoliamo a primo membro le incognite pivotali :
5 4
5 3 2
5 3 4
2 1
x x
x x 1 x
x x - 2
x x x
5 4
5 3 2
5 5 3 5
3 1
x x
x x 1 x
x ) x x (1 ) x x - (2 x
5 4
5 3 2
5 3 1
x x
x x 1 x
x 2x - 1 x
Le soluzioni sono : (1-2t+s, 1+t-s,t,s,s ) al variare di s, t in R
( abbiamo posto x5=s , x3=t)
Sostituiamo dal basso verso l’alto
In generale per i sistemi che hanno soluzioni procediamo così:
lasciamo a I membro le incognite pivotali che chiamiamo x1, x2 , … xp e portiamo a II membro le incognite non pivotali.
La situazione è del tipo :
x
a
. ....
...
a
...
p p pp
2 2
22
1 1
11
x
x a
Se le incognite sono n=p il sistema ha un’unica soluzione !
Se le incognite sono n>p il sistema ha infinite soluzioni e poiché ci sono n-p possibilità di assegnazioni arbitrarie (le in- cognite non pivotali) , si dice che il sistema ha np soluzioni ( n=n incognite,
p=n righe non nulle della matrice ridotta = n incognite pivotali)
Nel caso n=p si scrive simbolicamente (=1!) soluzioni. 0 Il sistema ha la matrice dei coeffi- cienti quadrata pxp, ed essendo tutti i pivot non nulli , risolvendolo dal basso verso l’alto, ha un’unica soluzione, che però dipende dai valori assegnati alle eventuali variabili a II membro.
ESERCIZIO4.
L'algoritmo di riduzione totale di Gauss
Usare l'algoritmo di riduzione totale di Gauss per risolvere il sistema dell'esercizio1.
0 z y x
2 z y x
3 z y x
L’algoritmo di riduzione totale di Gauss serve per portare il sistema in una forma in cui le soluzioni sono immediate.Come passare dalla forma ridotta (a scalini) a quella totalmente ridotta (ogni pivot è uguale a 1 e ogni altro termine nella colonna del pivot è zero) ?
Partiamo dalla matrice ridotta ( ex.1)
1 -
3 -
3 2 - 0 0
0 2 - 0
1 1 1
1. Passo . Rendere uguale a 1 ogni pivot con l’operazione elementare 2. di moltiplicazione della riga per un numero non nullo.
R2 12R2
R3 12R3
1/2 2 / 3
3 1 0 0
0 1 0
1 1 1
2.Passo. Partendo dall’ultima riga contenente un’incognita pivotale annullare tutti i coefficienti al di sopra dei pivot
mediante le operazioni elementari 3. di C.L. di righe.
1/2 2 / 3
3 1 0 0
0 1 0
1 1 1
R1 R1 – R3
1/2 2 / 3
5/2 1 0 0
0 1 0
0 1 1
R1 R1 – R2
1/2 2 / 3
1 1 0 0
0 1 0
0 0 1
Siamo arrivati alla forma totalmente ridotta ( i pivot tutti uguali ad 1 e ogni elemento nella colonna di un pivot è nullo) , il cui sistema associato ( equivalente al sistema originario) è di immediata risoluzione !
2 / 1 z
2 / 3 y
1 x
stesso risultato già ottenuto nell'ex.1 !
CONCLUSIONE : ogni sistema lineare è equivalente ad un (unico) sistema lineare totalmente ridotto.
Mentre abbiamo visto che ci sono più sistemi ridotti equiva- lenti al sistema dato, in corrispondenza alle scelte dei pivot.
ESERCIZIO 5.
Sistema lineare omogeneo con parametro
Date le matrici S=
1 1 0
0 1
1 e T=
λ 1
4 2
2 1
a) stabilire per quali R il sistema omogeneo (ST)X= 0 ha soluzioni
b) Nel caso in cui il sistema abbia soluzioni determinarle, precisando quante sono.
a) ST =
1 1 0
0 1 1
λ 1
4 2
2 1
=
4 3
2
1 X=
y x
(ST) X = 0
λ 4 3
2
1
y
x =
0 0
(4 λ)y 3x
2y - x
- =
0 0
3xx(42yλ)y0 0
Un sistema omogeneo ha sempre almeno la soluzione banale ( assegnando zero a tutte le incognite, qua (0,0)).
2x3 3x2 2x2
b)Quando ha anche soluzioni non nulle ( e quindi infinite ) ? Possiamo ridurlo ( inutile scrivere la colonna di zeri dei
termini noti) :
4 3
2 1
2 0
2 1
Ora si tratta di discutere, ci sono 2 casi :
-2+ ≠ 0 ≠2 Il sistema è ridotto, è un sistema quadrato, ha due equazioni e 2 incognite pivotali.
Ha 1! Soluzione , la soluzione nulla (0,0)
-2+ =0 =2 L’ultima riga è nulla, il sistema si riduce alla sola prima equazione –x-2y=0 che ha infinite soluzioni , più precisamente np 21 1soluzioni ( un’unica incognita pivotale, ad es. x , con y variabile libera ) . Da x= -2y si hanno le soluzioni (-2y,y) al variare di y in R.
Osservazione. Questo esercizio mostra come l’uso della riduzione di Gauss può diventare poco praticabile per lo studio dei sistemi con parametro. La tecnica dei minori in questo caso (che segue nell’appendice) è molto più vantaggiosa.
R2 R2+3R1
