Nel primo caso risolvere un sistema lineare coincide con l'intersezione tra due rette nel piano cartesiano, mentre nel secondo caso con l'intersezione di tre piani nello spazio euclideo.
Per risolvere i sistemi lineari si possono adottare vari metodi risolutivi: si va dai classici confronto e sostituzione, che possono essere utilizzati anche per i sistemi non-lineari, alla riduzione e ai metodi di Gauss e Cramer, tutti e tre specifici per i sistemi lineari. In particolare l'ultimo è noto anche come metodo dei determinanti, e venne sviluppato nella metà del 1700 indipendentemente da Gabriel Cramer, matematico francese, e da Colin Maclaurin, matematico scozzese. Il metodo di Gauss e quello di Cramer, ad ogni modo, condividono un concetto fondamentale per la loro comprensione, quello di matrice.
Per matrice si intende una griglia di numeri che in genere viene utilizzata per rappresentare le trasformazioni, di simmetria e non, negli spazi vettoriali. All'interno di un sistema lineare è possibile costruire la matrice dei coefficienti delle variabili, chiamata, per esempio, $A$: \[A x = b\] dove $x$ è il vettore colonna delle variabili e $b$ il vettore colonna dei termini noti.
Una volta costruita questa si può capire se un sistema lineare è risolvibile semplicemente calcolando la caratteristica nota come determinante, $\det (A)$: quando questo risulta non nullo, la matrice è invertibile e quindi il sistema possiede un'unica soluzione. A questo punto si può utilizzare il metodo di Cramer, secondo cui il valore di ciascuna variabile è dato dalla formula: \[x_i = \frac{\det (A_i)}{\det A}\] dove la matrice $n \times n$ ($n$ righe, $n$ colonne) $A_i$ è costruita sostituendo in $A$ l'i-sima colonna con quella dei termini noti.
Carroll, come spesso succedeva quando si trovava di fronte a un problema di calcolo, immaginava soluzioni alternative e possibilmente più semplici rispetto alle strade usualmente battute, e il caso del calcolo di determinanti di matrici ricche di elementi (tipo $16 \times 16$ o $25 \times 25$ o anche più grandi) rientrava sicuramente tra quelli interessanti per il matematico-scrittore. La condensazione di Dodgson(1) (o di Carroll!) si concentra sulla ricerca dei singoli blocchi in cui è possibile partizionare la matrice e si basa su quattro regole:
1) Sistemare il dato blocco, se necessario, tale che nessuna cifra compaia al suo interno (qui per "interno" Carroll intende il blocco che rimane quando le prime e le ultime riga e colonna sono cancellate). Ciò potrebbe essere fatto con la trasposizione delle righe o delle colonne, o aggiungendo a certe righe i termini di altre righe moltiplicati per certi valori.
2) Calcolare il determinante di ogni minore costituito da quattro termini adiacenti. Questi valori costituiranno un secondo blocco, formato da $(n-1)$ righe ed $(n-1)$ colonne.
3) Condensare questo secondo blocco nella stessa maniera, dividendo ogni termine, quando trovato, per il termine corrispondente nell'interno del primo blocco.
4) Ripetere questo processo tante volte quanto necessario, finché il blocco è condensato a un singolo termine, che sarà il valore richiesto.(1)
Date queste regole, Carroll prima prova a calcolare un paio di determinanti, quindi ad applicarli a sistemi lineari reali. In questo modo lo scrittore di Alice prova a mostrare come, su matrici veramente estese, la condensazione sia un metodo preferibile per il calcolo dei determinanti.2) Calcolare il determinante di ogni minore costituito da quattro termini adiacenti. Questi valori costituiranno un secondo blocco, formato da $(n-1)$ righe ed $(n-1)$ colonne.
3) Condensare questo secondo blocco nella stessa maniera, dividendo ogni termine, quando trovato, per il termine corrispondente nell'interno del primo blocco.
4) Ripetere questo processo tante volte quanto necessario, finché il blocco è condensato a un singolo termine, che sarà il valore richiesto.(1)
Se, ad esempio, prendiamo una matrice $3 \times 3$ \[\begin{pmatrix} a & b & c\\ d & e & f\\ g & h & i \end{pmatrix}\] applicando la condensazione una prima volta si ottiene(3): \[\begin{pmatrix} ae-bd & bf-ce\\ dh-eg & ei-fh \end{pmatrix}\] e infine un unico elemento(3). Però il metodo sviluppato da Carroll sembra avere un errore fatale: il determinante di ciascuna matrice interna non può essere nullo(2).
Sebbene alcuni rimedi come lo scambio riga/colonna possono essere efficaci nell'eliminare il difetto, non possono sempre funzionare. D'altra parte il principale vantaggio è ora ovvio: a differenza dell'espansione standard laplaciana, nulla costringe a dover calcolare un determinante di ordine superiore al secondo. L'algoritmo implica che il determinante di una matrice quadrata è una funzione razionale di tutti i suoi minori.(2)Inoltre, Bressoud e Propp scrivono(3):
Sebbene l'utilizzo della divisione può sembrare uno svantaggio, in realtà fornisce un'utile forma di controllo degli errori per i calcoli a mano con matrici intere: quando l'algoritmo è eseguito correttamente, tutte le entrate di tutte le matrici che intervengono sono interi, così che quando una divisione non esce, si può essere sicuri che deve esserci stato un errore da qualche parte. Il metodo è anche utile per i calcoli al computer, specialmente perché possono essere eseguiti in parallelo da diversi processori.(2, 3)La condensazione di Carroll venne, in effetti, ripresa nel 1986 da Robbins e Rumsey sempre per il calcolo dei determinanti, mentre giusto nell'ottobre del 2013 Okoh Ufuoma ha proposto un metodo risolutivo dei sistemi lineari che è una combinazione del metodo dei determinanti di Cramer e della condensazione di Carroll, in cui si costruiscono delle matrici rettangolari seguendo la filosofia di Cramer e si applica a queste il metodo di calcolo dell'autore di Alice(4).
Sui sistemi lineari, vedi anche:
Systems of linear equations, matrices, determinants
Systems of Linear Equations
(1) Dodgson C.L. (1866). Condensation of Determinants, Being a New and Brief Method for Computing their Arithmetical Values, Proceedings of the Royal Society of London, 15 150-155. DOI: 10.1098/rspl.1866.0037 (jstor.org)
(2) Abeles F.F. (2008). Dodgson condensation: The historical and mathematical development of an experimental method, Linear Algebra and its Applications, 429 (2-3) 429-438. DOI: 10.1016/j.laa.2007.11.022
(3) David Bressoud, James Propp (1999). How the Alternating Sign Matrix Conjecture Was Solved (pdf), Notices of the American Mathematica Society, vol.46, n.6 (637-646)
(4) Okoh Ufuoma (2013). A New and Simple Method of Solving Large Linear Systems: Based on Cramer's Rule but Employing Dodgson's Condensation (pdf), Proceedings of the World Congress on Engineering and Computer Science 2013 Vol I, (123-128)
(5) Esiste anche una interpretazione geometrica del metodo di Cramer, che è valida per qualunque dimensione. Ad esempio il determinante di una matrice $2 \times 2$ è uguale all'area di un parallelogrammo che ha per lati i vettori colonna della matrice (ovviamente si può facilmente generalizzare alle tre dimensioni e più dove il determinante coincide con il volume del parallelepipedo costituito dai vettori). Questo vuol dire che il metodo di Cramer può essere inteso come il rapporto tra le aree (o i volumi) di due parallelogrammi (o parallelepipedi).
Vedi anche: Baker R.P. (1904). The Expression of the Areas of Polygons in Determinant Form, The American Mathematical Monthly, 11 (12) 227-228. DOI: 10.2307/2968016
Nessun commento:
Posta un commento