Dubbio sul pivoting parziale
Ciao a tutti!
Ho un piccolo dubbio che non riesco a risolvere sulla fattorizzazione PA = LU;
Ora, avendo ben chiaro l'idea che scambiano delle righe della matrice dei coefficienti e gli opportuni termini noti il risultato non cambia, per esercizio sto provando a scambiando alcune righe della matrice dei coefficienti tramite pivoting parziale. Mi sembra di capire che al passo k, devo trovare un coefficiente sotto la colonna $i = k$ $j = k$ tale che sia $a_(ik) >= a_(kk)$, cioè ad esempio al passo 1 devo vedere se sotto l'elemento $a_11$ ci sia un coefficiente maggiore, se lo trovo scambio queste due righe, lo stesso al passo 2 soto $a_(kk) = a_22$ e cosi via fino a $k = n-1$
quindi diciamo che $A =$ $[ [3, 7, 9, 1], [5, 6, 7, 1] , [7, 7, 2, 3] , [4, 2, 1, 2] ]$ diventa, come ho provato io, $A= [ [7, 7, 2, 3], [3, 7, 9, 1], [5, 6, 7, 1], [4, 2, 1, 2] ]$
però matlab mi suggerisce invece $A= [ [7, 7, 2, 3], [3, 7, 9, 1], [4, 2, 1, 2], [5, 6, 7, 1] ]$ . Come mai? chiaramente il risultato non cambia, ma cosi facendo non rispetta il pivoting parziale? ( ho utilizzato [L U P] = lu( A ); )
Ho un piccolo dubbio che non riesco a risolvere sulla fattorizzazione PA = LU;
Ora, avendo ben chiaro l'idea che scambiano delle righe della matrice dei coefficienti e gli opportuni termini noti il risultato non cambia, per esercizio sto provando a scambiando alcune righe della matrice dei coefficienti tramite pivoting parziale. Mi sembra di capire che al passo k, devo trovare un coefficiente sotto la colonna $i = k$ $j = k$ tale che sia $a_(ik) >= a_(kk)$, cioè ad esempio al passo 1 devo vedere se sotto l'elemento $a_11$ ci sia un coefficiente maggiore, se lo trovo scambio queste due righe, lo stesso al passo 2 soto $a_(kk) = a_22$ e cosi via fino a $k = n-1$
quindi diciamo che $A =$ $[ [3, 7, 9, 1], [5, 6, 7, 1] , [7, 7, 2, 3] , [4, 2, 1, 2] ]$ diventa, come ho provato io, $A= [ [7, 7, 2, 3], [3, 7, 9, 1], [5, 6, 7, 1], [4, 2, 1, 2] ]$
però matlab mi suggerisce invece $A= [ [7, 7, 2, 3], [3, 7, 9, 1], [4, 2, 1, 2], [5, 6, 7, 1] ]$ . Come mai? chiaramente il risultato non cambia, ma cosi facendo non rispetta il pivoting parziale? ( ho utilizzato [L U P] = lu( A ); )
Risposte
Allora, se non ho capito male cosa hai fatto te, tu hai preso la matrice A e hai applicato il pivoting prima di eseguire la fattorizzazione giusto?
Quindi hai detto:
- quale riga tra la 1, 2, 3, 4 ha il primo elemento maggiore? La 3, quella sarà messa in cima
- sono rimaste la 1,2,4 (della matrice di partenza). Quale tra queste ha la seconda componente maggiore? la 1, quella sarà messa al secondo posto.
- sono rimaste la 2,4 (della matrice di partenza). Quale tra queste ha la terza componente maggiore? la 2, quella sarà messa al terzo posto.
- è rimasta la 4, sarà la quarta riga.
E hai ottenuto la matrice A che hai definita, con le righe in ordine [3; 1; 2; 4].
Ecco, il procedimento è sbagliato.
Il pivoting non si applica prima, ma durante.
Quando esegui la fattorizzazione LU, al generico passo i tu definisci la matrice di Gauss ecc ecc... e quando fai i conti su A vai ad aggiornare tutti i valori di A delle colonne i+1:n, ti torna?
Ecco, questo significa che a priori non puoi scambiare le tutte righe perché non sai che coefficienti ci saranno nella matrice, perché ogni passo li aggiornerai.
La procedura corretta è:(gli apici ai valori a indicano il passo a cui siamo).
PASSO 1:
cerco [tex]a_{i1} = max|a_{k1}^{(1)}|,\; k=1,2,\ldots ,n[/tex]
scambio riga i con riga 1.
Applico primo passo di LU (che ricalcola quindi tutti i coefficienti di A sulle colonne da 2 a n)(anzi, per la precisione mantiene invariata tutta la riga 1 e la colonna 1 e ricalcola tutto il resto).
PASSO 2:
cerco [tex]a_{i2} = max|a_{k2}^{(2)}|,\; k=2,3,\ldots ,n[/tex]
scambio riga i con riga 2.
Applico secondo passo di LU (che ricalcola quindi tutti i coefficienti di A sulle colonne da 3 a n)(anzi, per la precisione mantiene invariata tutta la riga 1 e la 2, e la colonna 1 e 2, e ricalcola tutto il resto).
...
PASSO j:
cerco [tex]a_{ij} = max|a_{kj}^{(j)}|,\; k=j,j+1,\ldots ,n[/tex]
scambio riga i con riga j.
Applico j-esimo passo di LU (che ricalcola quindi tutti i coefficienti di A sulle colonne da i a n)(anzi, per la precisione mantiene invariata tutte la righe da 1 a j e le colonna da 1 a j e ricalcola tutto il resto).
Quindi il passo di pivoting (ricerca del massimo tra gli elementi sotto-diagonali) va fatto uno alla volta prima di eseguire ogni passo di fattorizzazione LU.
Ripeto, per essere chiaro. In ordine (pseudocodice):
Infatti la fattorizzazione PA = LU viene definita come [tex]U = P_{n-1}\cdot L_{n-1}\cdot P_{n-2}\cdot L_{n-2}\cdot \ldots P_1 \cdot L_1 \cdot A[/tex], in cui ogni [tex]P_i[/tex] scambia 2 righe e ogni [tex]L_i[/tex] è una matrice elementare di Gauss. Poi si dimostra (ma non è questa la sede per farlo) che la fattorizzazione ottenuta è di fatto [tex]U = L^{-1}PA[/tex] da cui [tex]LU = PA[/tex].
Spero di essere stato chiaro.
Quindi hai detto:
- quale riga tra la 1, 2, 3, 4 ha il primo elemento maggiore? La 3, quella sarà messa in cima
- sono rimaste la 1,2,4 (della matrice di partenza). Quale tra queste ha la seconda componente maggiore? la 1, quella sarà messa al secondo posto.
- sono rimaste la 2,4 (della matrice di partenza). Quale tra queste ha la terza componente maggiore? la 2, quella sarà messa al terzo posto.
- è rimasta la 4, sarà la quarta riga.
E hai ottenuto la matrice A che hai definita, con le righe in ordine [3; 1; 2; 4].
Ecco, il procedimento è sbagliato.
Il pivoting non si applica prima, ma durante.
Quando esegui la fattorizzazione LU, al generico passo i tu definisci la matrice di Gauss ecc ecc... e quando fai i conti su A vai ad aggiornare tutti i valori di A delle colonne i+1:n, ti torna?
Ecco, questo significa che a priori non puoi scambiare le tutte righe perché non sai che coefficienti ci saranno nella matrice, perché ogni passo li aggiornerai.
La procedura corretta è:(gli apici ai valori a indicano il passo a cui siamo).
PASSO 1:
cerco [tex]a_{i1} = max|a_{k1}^{(1)}|,\; k=1,2,\ldots ,n[/tex]
scambio riga i con riga 1.
Applico primo passo di LU (che ricalcola quindi tutti i coefficienti di A sulle colonne da 2 a n)(anzi, per la precisione mantiene invariata tutta la riga 1 e la colonna 1 e ricalcola tutto il resto).
PASSO 2:
cerco [tex]a_{i2} = max|a_{k2}^{(2)}|,\; k=2,3,\ldots ,n[/tex]
scambio riga i con riga 2.
Applico secondo passo di LU (che ricalcola quindi tutti i coefficienti di A sulle colonne da 3 a n)(anzi, per la precisione mantiene invariata tutta la riga 1 e la 2, e la colonna 1 e 2, e ricalcola tutto il resto).
...
PASSO j:
cerco [tex]a_{ij} = max|a_{kj}^{(j)}|,\; k=j,j+1,\ldots ,n[/tex]
scambio riga i con riga j.
Applico j-esimo passo di LU (che ricalcola quindi tutti i coefficienti di A sulle colonne da i a n)(anzi, per la precisione mantiene invariata tutte la righe da 1 a j e le colonna da 1 a j e ricalcola tutto il resto).
Quindi il passo di pivoting (ricerca del massimo tra gli elementi sotto-diagonali) va fatto uno alla volta prima di eseguire ogni passo di fattorizzazione LU.
Ripeto, per essere chiaro. In ordine (pseudocodice):
for i=1 to (n-1)
[faccio pivoting confrontando l'elemento aii con quelli sotto]
[eseguo il passo i-esimo di fattorizzazione]
end
Infatti la fattorizzazione PA = LU viene definita come [tex]U = P_{n-1}\cdot L_{n-1}\cdot P_{n-2}\cdot L_{n-2}\cdot \ldots P_1 \cdot L_1 \cdot A[/tex], in cui ogni [tex]P_i[/tex] scambia 2 righe e ogni [tex]L_i[/tex] è una matrice elementare di Gauss. Poi si dimostra (ma non è questa la sede per farlo) che la fattorizzazione ottenuta è di fatto [tex]U = L^{-1}PA[/tex] da cui [tex]LU = PA[/tex].
Spero di essere stato chiaro.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo