Teorema di Laplace in C++

15 Giu, 2009  Matematica, Programmazione

laplaceIn questo articolo spiegherò come scrivere un programma in C++ che calcoli il determinante di una matrice utilizzando il Teorema di Laplace.

Il Teorema di Laplace afferma: “Data una matrice quadrata di ordine n, il suo determinante è uguale alla somma dei prodotti degli elementi di una qualsiasi riga (o colonna) per i rispettivi complementi algebrici“.
Il complemento algebrico dell’elemento aij appartenente alla matrice M, è il determinante della matrice che si ottiene cancellando la i-esima riga e la j-esima colonna dalla matrice M, preso con il segno + se i+j è pari, segno – se i+j è dispari.

M = \left( \begin{matrix} a_{11}&\underline{a_{12}}&a_{13}\\ a_{21}&a_{22}&a_{23}\\a_{31}&a_{32}&a_{33} \end{matrix} \right)
A_{12} = (-1)^{1+2}\cdot\left| \begin{matrix} a_{21}&a_{23}\\ a_{31}&a_{33} \end{matrix} \right|
\left|\text{M}\right|=a_{11} \cdot A_{11}-a_{12}\cdot A_{12}+a_{13} \cdot A_{13}

Il determinante di una matrice di ordine 2, è semplicemente:

\left|\begin{matrix}a&b\\c&d\end{matrix}\right|=a\cdot d-b\cdot c

Il Teorema di Laplace ci permette di calcolare il determinante di una matrice di ordine n tramite un determinante di ordine n-1. Applicando ricorsivamente Laplace, possiamo quindi ridurre il calcolo di qualsiasi determinante a quello di una matrice di ordine 2, che è facilmente calcolabile.
Testualmente, ciò che faremo è questo:

Funzione determinante(matrice, ordine)
L’ordine è 2? Allora calcolalo con la semplice formula.
L’ordine è superiore a 2? Richiama questa funzione applicando il Teorema di Laplace…

Così facendo, verrà applicato il Teorema di Laplace finché il programma non si troverà a calcolare un determinante di ordine 2.

Vediamo ora il codice. Queste prime righe servono soltanto a generare la matrice:

#include <iostream>
#include <stdlib>
#define MAX 30
int det(int m[MAX][MAX], int car); //Prototipo

int main()
{
    int m[MAX][MAX], c;
    cout<<"Ordine della matrice: ";
    cin>>c;
    //Genera matrice
    for (int i=0; i<c; i++) {
        cout<<"Riga "<<i<<": ";
        for (int j=0; j<c; j++) cin>>m[i][j];
    }
    //Determinante
    cout<<"Determinante: "<<det(m, c)<<endl<<endl;
    system("pause");
    return 0;
}

Spostiamo ora l’attenzione sulla funzione che genera il determinante: det(). Come abbiamo già visto dal prototipo, questa funzione richiede un array bidimensionale che è la nostra matrice, e un valore intero car, che rappresenta la cardinalità (numero di righe/colonne).

int det(int m[MAX][MAX], int car) {
    int determinante = 0;
    //Cardinalità uno
    if (car == 1) determinante = m[0][0];
    //Cardinalità due
    if (car == 2)
        determinante = m[1][1]*m[0][0]-m[0][1]*m[1][0];
    //Cardinalità > 2
    else {
        for (int row = 0; row < car; row++) {
            int sub_m[MAX][MAX];
            //Sottomatrice di ordine car-1
            for (int i = 0; i < car-1; i++) {
                for (int j = 0; j < car-1; j++) {
                    int sub_row = (i < row ? i : i+1);
                    int sub_col = j+1;
                    sub_m[i][j] = m[sub_row][sub_col];
                }
            }
            //Segno sottomatrice + per pari, - per dispari
            if (row % 2 == 0)
             determinante += m[row][0]*det(sub_m, car-1);
            else
             determinante -= m[row][0]*det(sub_m, car-1);
        }
    }
    return determinante;
}

Se la cardinalità della matrice è 1, il determinante è l’elemento stesso; se è 2 utilizziamo la formula vista prima.
In caso contrario, applichiamo il Teorema di Laplace alla prima colonna. Utilizziamo un for che cicla tutti gli elementi della prima colonna: per ognuno di questi ne determina il complemento algebrico, il cui segno sarà positivo se la riga è pari, negativo altrimenti. Sommando tutti i complementi algebrici ottengo il determinante.

Per determinare il complemento algebrico ho bisogno della matrice che ottengo cancellando la j-esima colonna e i-esima riga: utilizzo quindi altri due for (i, j) che ciclano la matrice iniziale car-1 volte. Avendo scelto di applicare il Teorema alla prima colonna, mi basta selezionare le rimanenti “j+1” colonne; per le righe devo invece utilizzare la i-esima, finché non raggiungo la riga da eliminare e seleziono quindi “i+1“.

\left(\begin{matrix} /&/&/ \\/&a_{22}&a_{23}\\/&a_{32}&a_{33}\end{matrix}\right) \left(\begin{matrix} /&a_{12}&a_{13} \\/&/&/ \\/&a_{32}&a_{33}\end{matrix}\right) \left(\begin{matrix} /&a_{12}&a_{13}\\/&a_{22}&a_{23}\\/&/&/\end{matrix}\right)

Infine, ecco il file già compilato del programma appena visto:
Download – Laplace.zip

Uno screenshot per una matrice diagonale, il cui determinante è dato dal prodotto degli elementi della diagonale:
06152009221901