|
|
Riga 1: |
Riga 1: |
|
|
<center> |
|
<center><font size="3">''Lezione 7:''</font><br/> |
|
|
<font size="5"> '''Sistemi lineari''' </font></center> <!-- non lapidatemi, e' solo una prova per vedere come viene --> |
|
<font size="5"> '''Sistemi lineari''' </font><br />{{avanzamento|25%|lezione|18 febbraio 2008}}</center> |
|
<br/> |
|
|
<br/> |
|
<br/> |
|
|
|
|
Sistemi lineari
Avanzamento lezione:
25% al 26-04-2024.
In questa lezione vedremo alcune tecniche per risolvere dei sistemi di equazioni lineari generici, quindi non per forza quadrati.
Un sistema lineare è di m equazioni in n incognite del tipo
![{\displaystyle \left\{{\begin{matrix}a_{1,1}x_{1}+a_{1,2}x_{2}+\cdots +a_{1,n}x_{n}&=&b_{1}\\a_{2,1}x_{1}+a_{2,2}x_{2}+\cdots +a_{2,n}x_{n}&=&b_{2}\\&\vdots &\\a_{m,1}x_{1}+a_{m,2}x_{2}+\cdots +a_{m,n}x_{n}&=&b_{m}\end{matrix}}\right.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/54575aa70321a944d2900eca9723eaf50f8fdef8)
abbiamo già visto che possiamo provare a risolvere utilizzando il metodo di sostituzione oppure l'eliminazione di Gauss nel caso il sistema sia quadrato, cioè
. Vediamo ora dei metodi più efficaci per risolvere un qualunque sistema lineare.
Riduzione a Scala e Algoritmo di Gauss-Jordan
È un metodo senz'altro efficiente e pratico da implementare in un calcolatore, tuttavia (e questa è un'opinione personale), richiede dei notevoli calcoli numerici e spesso l'utilizzo dei determinanti e la Regola di Cramer sono migliori se dobbiamo risolvere il sistema a mano senza l'impiego di un calcolatore.
Definizione: Una matrice si dice a scala se è siffatta
![{\displaystyle \left({\begin{array}{cccccccccc}0&\cdots &0&p_{1}&\cdots &&\cdots &&\cdots &*\\0&\cdots &\cdots &0&\cdots &p_{2}&\cdots &&\cdots &*\\\vdots &&&\vdots &&\vdots &&&&\vdots \\0&\cdots &&\cdots &&0&\cdots &p_{r}&\cdots &*\\0&\cdots &&\cdots &&0&\cdots &&&0\\0&\cdots &&\cdots &&0&\cdots &&&0\end{array}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4de36f3f3f178d160b9b6a61623f1a92e04e0b47)
- Gli * indicano che può esserci qualsiasi cosa e i
(quindi tutti non nulli) sono gli
pivot della matrice a scala.
Il sistema lineare associato si dice sistema a scala.
La matrice a scala ed il Metodo di Gauss-Jordan non è altro che la generalizzazione di quello che avevamo visto brevemente per le matrici quadrate. Prima di studiarne le proprietà teoriche, vediamo come funziona e facciamo qualche esempio pratico per fissare le idee.
Come anticipato prima, il metodo di Gauss-Jordan è molto simile all'eliminazione di Gauss per le matrici quadrate, cioè è un metodo che tramite operazioni elementari (quali lo scambio di righe, combinazioni lineari, ecc...) trasforma una matrice qualsiasi
in una matrice a scala
e di conseguenza trasforma il generico sistema
in un sistema a scala equivalente
.
Partendo da un sistema lineare
, il metodo consiste nei seguenti passaggi:
- Se
è la matrice nulla, abbiamo ovviamente finito.
- Se
non è la matrice nulla, consideriamo la prima colonna che presenta un coefficiente non nullo (se necessario è possibile scambiare di posto le righe della matrice per avere tale coefficiente il piu' a sinistra possibile e nella prima riga, all'inizio della matrice). Sia
questa colonna e chiamiano tale valore non nullo pivot, in questo caso ![{\displaystyle A_{1,j}=p_{1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7323e88e2e73b1de69e18e5db63bb58885ea2abc)
- Rendiamo nulli tutti i valori della colonna j-esima sommando alle righe
una opportuna combinazione lineare.
- Andiamo avanti considerando la colonne successiva ad
della riga 2 fino a che non troviamo una colonna
avente coefficiente non nullo. Sia
tale valore e procediamo come prima fino alla riga ![{\displaystyle h}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b26be3e694314bc90c3215047e4a2010c6ee184a)
- Se dalla riga
in poi sono tutte nulle o
è l'ultima riga, abbiamo finito. Altrimenti continuiamo il procedimento.
- Una volta ottenuta una matrice a scala, ripetiamo il procedimento all'indietro per ottenere le soluzioni.
Come si nota subito, il procedimento è molto simile a quello dell'eliminazione di Gauss. Ma un esempio dovrebbe chiarire molto meglio il l'algoritmo.
- Esempio (1): Consideriamo il seguente sistema lineare
![{\displaystyle \left\{{\begin{array}{cccccc}2x_{1}&-x_{2}&+4x_{3}&+x_{4}&=&-2\\-2x_{1}&+x_{2}&-7x_{3}&+x_{4}&=&-1\\4x_{1}&-2x_{2}&+5x_{3}&+4x_{4}&=&-7\end{array}}\right.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b4f0264d0ab990fceccf0189543dbcb355db6bee)
- e la sua matrice associata
![{\displaystyle c=\left({\begin{array}{c}-2\\-1\\-7\end{array}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a7cd90bf9d533b66172b924530193d9d6e9e1b09)
- A non è nulla e il primo elemento diverso da zero che incontriamo è proprio
. Quindi
e procediamo ad annullare tutti i termini della prima colonna dalla riga 2 in poi con una combinazione lineare del tipo
, con
fissato.
![{\displaystyle \left({\begin{array}{cccc}2&-1&4&1\\0&0&-3&2\\0&0&-3&2\end{array}}\right)\left({\begin{array}{c}-2\\-3\\-3\end{array}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/05cc10ec493b375ec0c0690cff7771af949bb5ea)
- cioè abbiamo sostiuito la riga
con
e la riga
con
. La sostituzione comprende anche la colonna dei termini noti.
- Ripetiamo il procedimento passando alla colonna (e riga) successive, notando che la seconda riga ha un termine non nullo (nella colonna 3). Poniamo allora
e ripetiamo il procedimento di prima. Questa volta abbiamo
che ci da' la matrice
![{\displaystyle \left({\begin{array}{cccc}2&-1&4&1\\0&0&-3&2\\0&0&0&0\end{array}}\right)\left({\begin{array}{c}-2\\-3\\0\end{array}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0c095a64d579f174fb5925d76ed6094204172979)
- Ci accingiamo a ripetere nuovamente il procedimento, ma questa volta notiamo che al di sotto della riga che abbiamo appena considerato, non abbiamo altre righe contenenti elementi non nulli. Perciò abbiamo finito, ottendo un sistema a scala e il corrispondente sistema lineare:
![{\displaystyle \left\{{\begin{array}{cccccc}2x_{1}&-x_{2}&+4x_{3}&+x_{4}&=&-2\\&&-3x_{3}&+2x_{4}&=&-3\end{array}}\right.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/59e6279cac582e673c3dbcb7bfd654e0c986591f)
- Il sistema ha due pivot e il vettore dei termini noti ha dimensione 2. Un corollario che vedremo dopo ci assicurerà che, a queste condizioni, il sistema ammette soluzioni.
- Risolviamolo all'indietro, cioè ripetiamo l'algoritmo di Gauss-Jordan stavolta partendo dal basso:
- abbiamo la matrice
e partiamo da basso prendendo come pivot il primo valore da destra non nullo, cioe'
e, di nuovo, sostiuiamo alla prima riga di
e di
la combinazione lineare ottenuta come avevamo fatto prima, cioè
ottenendo la matrice
.
- Abbiamo ora terminato l'algoritmo di Gauss e procediamo a risolvere il sistema lineare equivalente ottenuto. Risolviamo allora il sistema:
![{\displaystyle \left\{{\begin{array}{cccccc}2x_{1}&-x_{2}&+{\frac {11}{2}}x_{3}&&=&-{\frac {1}{2}}\\&&-3x_{3}&+2x_{4}&=&-3\end{array}}\right.\rightarrow }](https://wikimedia.org/api/rest_v1/media/math/render/svg/ffd6ad72f4c167537a4169f7d7d68de0c2cd9f9b)
![{\displaystyle \left\{{\begin{array}{cccccc}2x_{1}&=&-{\frac {1}{2}}&+x_{2}&-{\frac {11}{2}}x_{3}&\\-3x_{3}&=&-3&-2x_{4}&&\end{array}}\right.\rightarrow }](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3bb4ee821c2212fa78eb51b42edcef913ee1fbe)
![{\displaystyle \left\{{\begin{array}{cccccc}x_{1}&=&-{\frac {1}{4}}&+{\frac {1}{2}}x_{2}&-{\frac {11}{4}}x_{3}&\\x_{3}&=&1&+{\frac {2}{3}}x_{4}&&\end{array}}\right.\rightarrow }](https://wikimedia.org/api/rest_v1/media/math/render/svg/f9a3d6492f50682ff73ee6d8d1e13bee3c60d4dd)
![{\displaystyle \left\{{\begin{array}{cccccc}x_{1}&=&-{\frac {1}{4}}&+{\frac {1}{2}}x_{2}&-{\frac {11}{4}}\left(1+{\frac {2}{3}}x_{4}\right)&\\x_{3}&=&1&+{\frac {2}{3}}x_{4}&&\end{array}}\right.\rightarrow }](https://wikimedia.org/api/rest_v1/media/math/render/svg/28965b2bf8119c0243647be0801c60b1dcdc5007)
![{\displaystyle \left\{{\begin{array}{cccccc}x_{1}&=&-{\frac {1}{4}}&+{\frac {1}{2}}x_{2}&-{\frac {11}{4}}-{\frac {11}{6}}x_{4}&\\x_{3}&=&1&+{\frac {2}{3}}x_{4}&&\end{array}}\right.\rightarrow }](https://wikimedia.org/api/rest_v1/media/math/render/svg/19ee042fba2fc01beeacf1de9a2cf4c62a21abe1)
![{\displaystyle \left\{{\begin{array}{cccccc}x_{1}&=&-3&+{\frac {1}{2}}x_{2}&-{\frac {11}{6}}x_{4}&\\x_{3}&=&1&+{\frac {2}{3}}x_{4}&&\end{array}}\right.\rightarrow }](https://wikimedia.org/api/rest_v1/media/math/render/svg/b5a020de6807f06c2da2c22b09291dac72ad34c5)
Abbiamo dunque trovate le soluzioni di questo sistema, con
variabili dipendenti e
variabili libere.
Adesso che abbiamo visto come risolvere i sistemi lineari ridotti a scala, vediamone le proprietà fondamentali.
Proprietà dei sistemi lineari a scala
Lemma
- Sia
una matrice a scala con
pivot. Poniamo
![{\displaystyle V_{r}=\left\{\left({\begin{matrix}b_{1}\\\vdots \\b_{r}\\0\\\vdots \\0\end{matrix}}\right)\in \mathbb {R} ^{m}\mid b_{1},\cdots ,b_{r}\in \mathbb {R} \right\}=<e_{1},\cdots ,e_{r}>}](https://wikimedia.org/api/rest_v1/media/math/render/svg/de92aa9b39b3a78522bf78acac91ce2893c0e11e)
- con
la base canonica di
.
- Poniamo inoltre con
la colonna j-esima di
in cui compare il h-esimo pivot
.
- Allora:
![{\displaystyle V_{r}={\rm {Im}}S}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1187e2dc3fca168091cf5fb2eecd448ad6bac935)
![{\displaystyle r={\rm {rg}}S}](https://wikimedia.org/api/rest_v1/media/math/render/svg/40fbe85d03219fa91171ae608c236139c2c9edc7)
è una base di ![{\displaystyle {\rm {Im}}S}](https://wikimedia.org/api/rest_v1/media/math/render/svg/225515e8c24d24462a390fe0b138ffede051592c)
Dimostrazione.
- Tutte le colonne di
sono della forma
, dunque appartengono a
e sono un sistema di generatori (per il significato di applicazione lineare di una matrice) di
, quindi sicuramente
. Tuttavia, abbiamo che
, cioè
e quindi
.
- 2 . Sappiamo dall'ipotesi che
, ma
e se due insiemi sono uguali è evidente che eguale è anche la loro dimensione. Quindi ![{\displaystyle {\rm {rg}}S=r}](https://wikimedia.org/api/rest_v1/media/math/render/svg/61afce30143dba965aa1eab1c1100dc74c56de62)
Corollario
- Sia
una matrice a scala di rango
.
- Allora il sistema lineare associato ha soluzione se e solo se le ultime
coordinate della colonna dei termini noti sono zero, e lo spazio delle soluzioni del sistema omogeneo associato ha dimensione
.
Dimostrazione .
- Il sistema a scala
ha soluzione se e solo se
e questo accade se e solo
è un vettore come quelli appartenenti a
, quindi con le ultime
componenti nulle.
- Lo spazio delle soluzioni di un sistema omogeneo
è per definizione
che ha dimensione ![{\displaystyle n-{\rm {rg}}S.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eecc119003215c606cbf7ed3dc38c13c8dee5274)
Teorema