Completamento di una base

[Ghigo1]

ciao a tutti,

esiste un algoritmo o una procedura per effettuare il completamento della base?? nel mio libro, dice che si completa una base con elementi linearmente indipendenti. grazie al piffero!!!!

ciao e grazie.

[Injo]

Generalmente è abbastanza facile trovare elementi linearmente indipendenti a quelli dati che completino la base cercandoli tra gli elementi della base canonica. Ovviamente per controllare che quella ottenuta sia una base basta osservare che il determinante della matrice aventi come colonne i vettori stessi ha determinante non nullo.

[Ghigo1]

Grazie injo,

quindi devo solo trovare dei vettori linearmente indipendenti e provarli

[dissonance]

Quello a cui fa riferimento Injo è in effetti un algoritmo di algebra lineare. Lui ha proposto una costruzione "in avanti": prendiamo una base nota e costruiamo il completamento scegliendone opportunamente dei vettori.

Una maniera alternativa di procedere è "all'indietro", mediante un algoritmo detto degli scarti successivi. Una esposizione formale può essere questa (metto in spoiler perché è lunga e un po' pallosa):

Sia $V$ uno spazio vettoriale e sia $S={s_1,...,s_n}$ un suo sottoinsieme finito. Allora esiste un sottoinsieme $T$ di $S$ linearmente indipendente (oppure $T={0}$) e tale che lo spazio generato da $T$ sia uguale allo spazio generato da $S$ ($"span"(T)="span"(S)$).
Dimostrazione: Creiamo un algoritmo che costruisca $T$, arrestandosi dopo $n$ passi. Al passo $0$-esimo (ovvero prima ancora di iniziare), definiamo gli insiemi $S^((0))=S, T^((0))={0}$. E' evidente che $"span"(S^((0))uuT^((0)))="span"(S)$.

Ora inneschiamo l'algoritmo. Chiediamoci: l'ultimo vettore di $S$, $s_n$, è lin. dipendente dai vettori $s_1, ...,s_(n-1)$? Se sì, allora definiamo $T^((1))=T^((0))={0}$. Se no, definiamo $T^((1))=T^((0))uu{s_n}={s_n}$. Il vettore $s_n$ non ci serve più, perciò definiamo $S^((1))=S^((0))-{s_n}={s_1,...,s_(n-1)}$.
In entrambi i casi, lo span dell'unione $S^((1))uuT^((1))$ è ancora uguale allo span di $S$. Infatti, se abbiamo scartato $s_n$ sarà stato perché dipende linearmente dai vettori di $S^((1))$.

Facciamo il secondo passo dell'algoritmo. In sostanza rifacciamo tutto daccapo sull'insieme $S^((1))$. L'ultimo elemento di $S^((1))$, il vettore $s_(n-1)$, dipende linearmente dai precedenti? Se sì, non lo ammettiamo nell'insieme $T^((2))$ (=lo scartiamo), definendo $T^((2))=T^((1))$. Se no, lo ammettiamo tra i vettori "buoni", definendo $T^((2))=T^((1))uu{s_(n-1)}$. In entrambi i casi, $S^((2))=S^((1))-{s_(n-1)}$.
Anche adesso abbiamo che $"span"(S^((2))uuT^((2)))="span"(S^((1)))="span"(S)$. Infatti, se avessimo scartato $s_(n-1)$, sarà stato perché dipendeva linearmente dai vettori $s_1, ..., s_(n-2)$.
Cosa altrettanto importante, i vettori di $T^((2))$ sono linearmente indipendenti, oppure $T^((2))$ è fermo al palo, ovvero è rimasto uguale a ${0}$. E' chiaro il motivo di questo fatto? Se no, fammi un fischio che lo spiego.

Comunque, per non portarla troppo alle lunghe, questo algoritmo si arresterà quando avremo svuotato tutto $S$, quindi dopo $n$ passi. A quel punto, avremo due insiemi: $S^((n))=\emptyset$, e $T^((n))$ che può essere ${0}$ oppure un insieme linearmente indipendente. In entrambi i casi, lo span dell'unione di $S^((n))uuT^((n))$ sarà uguale allo $"span"(S)$ per costruzione, ed essendo $S^((n))$ vuoto abbiamo trovato l'insieme $T$ richiesto. /////

Più intuitivamente, si procede così. Prendiamo $S={s_1,..., s_n}$. Consideriamo $s_n$: è linearmente dipendente dai precedenti? Se si, lo scartiamo, altrimenti lo mettiamo da parte. Ora consideriamo $s_(n-1)$: è linearmente dipendente dai precedenti? Se sì, lo scartiamo, altrimenti lo mettiamo da parte. E così via finché non avremo estratto un sistema linearmente indipendente, che risulterà essere una base di $"span"(S)$.

Questo si applica alla domanda di Ghigo. Se abbiamo un sistema $H={h_1,..., h_k}$ linearmente indipendente, come lo completiamo ad una base di $V$? A questo scopo, prendiamo una base di $V$ nota, diciamo ${b_1,..., b_n}$. Costruiamo l'insieme $S$ [size=67](*)[/size] in questa maniera: $S={h_1,...,h_k, b_1,...b_n}$, ovvero mettendo la base nota alla fine. In questa maniera gli scarti successivi scarteranno i vettori della base nota e non quelli di $H$. Questo perché nessun vettore di $H$ dipende linearmente dai precedenti, come è ovvio.

Al termine otteniamo un insieme $T$, contenente $H$, linearmente indipendente e che genera tutto lo spazio. Ovvero quello che ci serviva.

Questa maniera di procedere è quella che usa un programma come ad esempio Maple quando gli si passa il comando "basis()".




_____________________________________
(*) A volere essere proprio fiscali, questi non sono insiemi ma $n$-uple ordinate. Infatti qui l'ordine in cui compaiono gli elementi è importante.

[Ghigo1]

dissonance sei stato perfetto

grazie mille!

[dissonance]

Figurati, di nulla. Voglio sottolineare che, nella pratica, quando si ha a che fare con spazi di dimensione piccola (fino alla quarta o quinta), e si procede "a mano", conviene andare in avanti, come dice Injo. Infatti in questi casi spesso si riesce a concludere a occhio.

Ma se parliamo di dimensione superiore, o se volessimo un algoritmo da implementare al calcolatore, è più sistematico procedere per scarti successivi. Come faresti a dire al calcolatore "prendi dei vettori linearmente indipendenti e provali tutti finché non hai costruito una base"? E se parliamo di uno spazio di dimensione 1000, per quante volte dovresti provare l'indipendenza lineare?

Segnalo comunque che ci sono algoritmi migliori anche di quello degli scarti successivi.