Programmation fonctionnelle comme exemple de travail avec des matrices de la théorie de l'algèbre linéaire

introduction

La base du travail avec les matrices (dans cet article, nous ne considérerons que les matrices bidimensionnelles) est une puissante théorie mathématique du domaine de l'algèbre linéaire. Une définition ou une action en découle, une fonction en appelle une autre. Par conséquent, pour l'implémentation fonctionnelle de la fonctionnelle des opérations mathématiques sur les matrices, les langages fonctionnels s'adaptent très bien. Dans cet article, nous allons examiner des exemples spécifiques en F # et donner des commentaires détaillés sur la façon dont cela fonctionne. Étant donné que F # fait partie de la famille .NET, la fonctionnalité résultante peut être utilisée sans aucun problème dans d'autres langages impératifs, par exemple C #.

Définition et implémentation d'une matrice en F #

Les matrices sont la partie fondamentale et la plus importante de l'algèbre linéaire. Les matrices sont souvent utilisées dans la programmation, par exemple, dans la modélisation 3D ou le développement de jeux. Bien sûr, le vélo a longtemps été inventé et les cadres nécessaires pour travailler avec des matrices sont déjà prêts, et ils peuvent et doivent être utilisés. Cet article ne vise pas à inventer un nouveau framework, mais montre l'implémentation d'opérations mathématiques de base pour travailler avec des matrices dans un style fonctionnel en utilisant le langage de programmation F #. En examinant le matériau, nous nous tournerons vers la théorie mathématique des matrices et verrons comment il peut être implémenté dans le code.

Rappelons d'abord ce qu'est une matrice? La théorie nous dit ce qui suit

Un tableau rectangulaire de nombres contenant m lignes et n colonnes est appelé matrice de taille mxn

Les matrices sont généralement désignées par des majuscules de l'alphabet latin et s'écrivent comme suit:

$$

$$A=\begin{pmatrix}a11&a12&...&a1n\\a21&a22&...&a2n\\...&...&...&...\\am1&am2&...&amn\end{pmatrix}$$

Ou peu

$$

$$A=(aij)$$

Pour travailler avec des matrices en F #, nous allons créer un enregistrement basé sur un tableau à deux dimensions, que nous développerons avec des méthodes utiles afin d'effectuer les opérations mathématiques nécessaires sur celui-ci.

type Matrix = { values: int[,] }
    with
        //    
    end

Ajouter une méthode d'assistance pour initialiser l'enregistrement avec un tableau à deux dimensions

static member ofArray2D (values: int [,]) = 
    { values = values }

L'argument d'entrée de la fonction sera un tableau à deux dimensions et, à sa sortie, un enregistrement de type Matrix . Voici un exemple d'initialisation d'enregistrement.

let a = array2D [[1;0;2]
                 [3;1;0]]
let A = Matrix.ofArray2D a

Deux matrices A = (aij) et B = (bij) sont appelées égales si elles coïncident par élément, c'est-à-dire aij = bij pour tout i = 1,2 ..., m et j = 1,2 ... n

Pour implémenter cette règle, nous utiliserons l'opérateur substitué == et ajouterons quelques fonctions utiles, dont nous aurons également besoin à l'avenir.

static member sizes matrix =
    let rows = matrix.values.[*,0].Length
    let cols = matrix.values.[0,*].Length
    (rows, cols)

static member isEquallySized matrix1 matrix2 =
    let dim1 = Matrix.sizes matrix1
    let dim2 = Matrix.sizes matrix2
    (dim1 = dim2)

static member (==) (matrix1, matrix2) =
    if not (Matrix.isEquallySized matrix1 matrix2) then false
    else
        not (matrix1.values
               |> Array2D.mapi (fun x y v -> if matrix2.values.[x, y] <> v then false else true)
               |> Seq.cast<bool>
               |> Seq.contains false)

Examinons de plus près le code ci-dessus. Comme vous pouvez le voir, il existe trois fonctions. La première fonction de tailles renvoie la dimension de la matrice sous forme de tuple. Puisque nous travaillons uniquement avec des matrices rectangulaires, pour obtenir le nombre de lignes, nous prenons une tranche complète de la première colonne et retournons sa longueur.

let rows = matrix.values.[*,0].Length

La détermination du nombre de colonnes fonctionne de la même manière - nous obtenons une tranche complète de la première ligne et retournons sa longueur.

La fonction isEquallySized suivante compare la dimension de deux matrices et renvoie vrai si elles sont égales. Pour ce faire, il utilise la fonction de tailles prêtes à l'emploi et compare simplement les résultats.

L'opérateur == pour comparer élément par élément deux matrices semble plus compliqué, mais maintenant vous verrez qu'il est également simple.

Avant de comparer deux matrices, nous comparons leur dimension. S'ils ne sont pas égaux, il n'y a pas d'autre point à vérifier, car il est déjà clair que les matrices ne seront pas égales.

if not (Matrix.isEquallySized matrix1 matrix2) then false

Ensuite, sur la base des matrices originales matrice1 et matrice2, nous formons une nouvelle matrice remplie de vrai ou de faux , selon que les cellules correspondantes des deux matrices coïncident.

matrix1.values
|> Array2D.mapi (fun x y v -> if matrix2.values.[x, y] <> v then false else true

La fonction Array2D.mapi itère sur tous les éléments de matrix1 et transmet trois paramètres
x au gestionnaire - index de ligne
y - index de colonne
v -
contenu de la cellule Nous comparons le contenu de la cellule v avec la cellule de matrice correspondante2 et s'ils sont égaux, alors écrire vrai , sinon faux .

S'il y a au moins une cellule avec le faux élément , cela signifie que les matrices ne sont pas égales les unes aux autres.

Comme Array2D ne contient pas de méthodes de filtrage ou de recherche, nous allons l'implémenter nous-mêmes. Pour ce faire, nous décomposons la matrice en une liste linéaire

|> Seq.cast<bool>

Et trouver au moins un décalage

|> Seq.contains false

La fonction Seq.contains renverra true si au moins une fausse valeur est trouvée dans la liste développée . Par conséquent, nous devons inverser le résultat afin que l'opérateur == fonctionne comme nous le voulons

else
    not (matrix1.values
           |> Array2D.mapi (fun x y v -> if matrix2.values.[x, y] <> v then false else true)
           |> Seq.cast<bool>
           |> Seq.contains false)

Une matrice O est appelée matrice nulle ou nulle si tous ses éléments sont égaux à zéro.

static member O rows cols =
    let array2d = Array2D.zeroCreate rows cols
    { values = array2d }

Un exemple d'utilisation de cette fonction

let AO = Matrix.O 5 5

Je crois qu'il n'y a rien de compliqué qui nécessite une explication, alors nous continuons.

Une matrice dont le nombre de lignes est égal au nombre de colonnes et égal à n est appelée matrice carrée d'ordre n

Ainsi, la matrice carrée a la forme.

$$

$$A=\begin{bmatrix}a11&a12&...&a1n\\a21&a22&...&a2n\\...&...&...&...\\an1&an2&...&ann\end{bmatrix}$$

Dans le cadre de cette règle, nous allons créer une fonction qui transforme une matrice rectangulaire en matrice carrée en coupant tous les éléments qui ne tombent pas dans le carré.

static member toSquare matrix =

    //    
    let dim = Matrix.sizes matrix

    //   
    let colCount: int = snd dim
    //   
    let rowCount: int = fst dim

    //    
    let length = System.Math.Min (colCount, rowCount)

    //      
    //     
    let zero = Array2D.zeroCreate length length

    //     
    let square = zero |> Array2D.mapi (fun x y _ -> matrix.values.[x, y])

    //   
    { values = square }

Les commentaires dans le code source expliquent comment fonctionne la fonction, alors continuons.

Une matrice carrée est appelée triangulaire si tous ses éléments en dessous de la diagonale principale sont égaux à zéro, c'est-à-dire la matrice triangulaire a la forme

$$

$$T=\begin{pmatrix}a11&a12&...&a1n\\0&a22&...&a2n\\...&...&...&...\\0&0&...&ann\end{pmatrix}$$

Ci-dessous se trouve le code de fonction qui convertit la matrice d'origine en triangulaire. Mais dans notre fonction, nous travaillerons avec une matrice rectangulaire, c'est-à-dire qu'elle peut ne pas être carrée. Le lecteur peut facilement modifier le code de fonction afin qu'il renvoie une matrice triangulaire carrée en utilisant la fonction que nous avons examinée précédemment.

static member T matrix =
    let values = matrix.values |> Array2D.mapi (fun x y v -> if y < x then 0 else v)
    { values = values }

La fonction Array2D.mapi convertit le tableau bidimensionnel d'origine en un nouveau à l'aide d'un gestionnaire qui prend trois paramètres

x - numéro de ligne
y - numéro de colonne
v - contenu de la cellule

if y < x then 0 else v

Ici, nous vérifions si l'élément est en dessous de la diagonale principale et si oui, remplissons la cellule 0. Sinon, la valeur initiale de la matrice d'entrée.

Voici un exemple d'utilisation de cette fonction.

let a = array2D [[1;2;3]
                 [4;5;6]
                 [7;8;9]
                 [10;11;12]]
let A = Matrix.ofArray2D a
let R = Matrix.triangular A
printfn "origin = \n %A" A.values
printfn "triangular = \n %A" R.values

Nous obtenons le résultat suivant

origin = 
 [[1; 2; 3]
 [4; 5; 6]
 [7; 8; 9]
 [10; 11; 12]]
triangular = 
 [[1; 2; 3]
 [0; 5; 6]
 [0; 0; 9]
 [0; 0; 0]]

Une matrice carrée est appelée diagonale si tous ses éléments situés à l'extérieur de la diagonale principale sont égaux à zéro

static member D matrix =
    let diagonal = matrix.values |> Array2D.mapi (fun x y v -> if x <> y then 0 else v)
    { values = diagonal }

Cette fonction est très similaire à la précédente, seule la condition de vérification est différente. Voici un exemple d'utilisation

let a = array2D [[1;2;3]
                 [4;5;6]
                 [7;8;9]
                 [10;11;12]]
let A = Matrix.ofArray2D a
let R = Matrix.D A
printfn "origin = \n %A" A.values
printfn "diagonal = \n %A" R.values

origin = 
 [[1; 2; 3]
 [4; 5; 6]
 [7; 8; 9]
 [10; 11; 12]]
diagonal = 
 [[1; 0; 0]
 [0; 5; 0]
 [0; 0; 9]
 [0; 0; 0]]

La matrice diagonale est unitaire et est notée E si tous ses éléments situés sur la diagonale principale sont égaux à l'unité

$$

$$E=\begin{pmatrix}1&0&...&0\\0&1&...&0\\...&...&...&...\\0&0&...&1\end{pmatrix}$$

L'implémentation d'une telle matrice sur F # ressemble à ceci

static member E rows cols =
    let array2d = Array2D.init rows cols (fun x y -> if x = y then 1 else 0)
    { values = array2d }

Opérations matricielles avec F #

Un certain nombre d'actions peuvent être effectuées sur des matrices, ainsi que sur des nombres, dont certaines sont similaires aux opérations sur les nombres, et certaines sont spécifiques.

La somme de deux matrices Amn = (aij) et Bmn = (bij) de même taille est la matrice de même taille A + B = Cmn = (cij) , dont les éléments sont égaux à la somme des éléments des matrices A et B situées aux endroits correspondants

$$

$$cij=aij+bij, i=1,2,...,m, j=1,2,...,n$$

Exemple, pour des matrices données A et B, on trouve la somme A + B

$$

$$A=\begin{pmatrix}2&3\\1&-5\\0&6\end{pmatrix}, B=\begin{pmatrix}-3&3\\1&7\\2&0\end{pmatrix}, A+B=\begin{pmatrix}-1&6\\2&2\\2&6\end{pmatrix}$$

Considérez le code pour ajouter deux matrices

static member (+) (matrix1, matrix2) =
    if Matrix.isEquallySized matrix1 matrix2 then
        let array2d = matrix1.values |> Array2D.mapi (fun x y v -> matrix2.values.[x, y] + v)
        { values = array2d }
    else failwith "matrix1 is not equal to matrix2"

Avant d'ajouter des matrices, vous devez vous assurer que leur dimension coïncide, sinon la fonction lève une exception. Voici un exemple d'utilisation de cette fonction

let a = array2D [[2;3]
                 [1;-5]
                 [0;6]]
let A = Matrix.ofArray2D a

let b = array2D [[-3;3]
                 [1;7]
                 [2;0]]
let B = Matrix.ofArray2D b

let R = A+B
printfn "A+B =\n %A" R.values

A+B =
 [[-1; 6]
 [2; 2]
 [2; 6]]

Le produit de la matrice A = (aij) par le nombre k est la matrice kA = (kaij) de même taille que la matrice A obtenue en multipliant tous les éléments de la matrice A par le nombre k

Exemple, pour une matrice A donnée on trouve la matrice 3A

$$

$$A=\begin{pmatrix}2&3&0\\1&5&4\end{pmatrix}, 3A=\begin{pmatrix}6&9&0\\3&15&12\end{pmatrix}$$

static member (*) (value, matrix) = 
    let array2d = matrix.values |> Array2D.mapi (fun _ _ v -> v * value)
    { values = array2d }

Matrice -A = (- 1) * A sera appelée la matrice opposée A . A partir de cette définition, nous procédons en douceur à la suivante

La différence des matrices A et B de tailles égales est la somme de la matrice A et de la matrice opposée à B

static member (-) (matrix1: Matrix, matrix2: Matrix) = 
    if Matrix.isEquallySized matrix1 matrix2 then
        matrix1 + (-1)*matrix2
    else failwith "matrix1 is not equal to matrix2"

Deux matrices sont dites cohérentes si le nombre de colonnes de la première est égal au nombre de lignes de la seconde

$$

$$A=\begin{pmatrix}2&1\\0&3\end{pmatrix}, B=\begin{pmatrix}0&5&2&1\\1&4&3&7\end{pmatrix}$$

static member isMatched matrix1 matrix2 = 
    let row1Count = matrix1.values.[0,*].Length
    let col2Count = matrix2.values.[*,0].Length

    row1Count = col2Count

La vérification de la cohérence de la matrice est nécessaire pour les multiplier.

Le produit AB matrice cohérente Amn = (aij) et Bnp = (bjk) est la matrice Cmn = (cik) , l'élément cik est calculé comme la somme des éléments i- ème ligne de la matrice A et des éléments correspondants de la k ème colonne de la matrice B

Calculer le produit des matrices

$$

$$A=\begin{pmatrix}1&0&2\\3&1&0\end{pmatrix}, B=\begin{pmatrix}-1&0\\5&1\\-2&0\end{pmatrix}$$

Décision de déterminer le produit des matrices

$$

$$AB=\begin{pmatrix}1(-1)+0*5+2(-2)&1*0+0*1+2*0\\3(-1)+1*5+0(-2)&3*0+1*1+0*0\end{pmatrix}= \begin{pmatrix}-5&0\\2&1\end{pmatrix}$$

Considérez le code pour multiplier deux matrices

static member (*) (matrix1, (matrix2: Matrix)) =
    if Matrix.isMatched matrix1 matrix2 then
        let row1Count = matrix1.values.[*,0].Length
        let col2Count = matrix2.values.[0,*].Length

        let values = Array2D.zeroCreate row1Count col2Count

        for r in 0..row1Count-1 do
            for c in 0..col2Count-1 do
                let row = Array.toList matrix1.values.[r,*]
                let col = Array.toList matrix2.values.[*,c]

                let cell = List.fold2 (fun acc val1 val2 -> acc + (val1 * val2)) 0 row col
                values.[r,c] <- cell

        { values = values }

    else failwith "matrix1 is not matched to matrix2"

Examinons le code plus en détail.
Avant la multiplication, vous devez vous assurer que les matrices sont cohérentes

if Matrix.isMatched matrix1 matrix2 then

La matrice résultante aura une dimension dans laquelle le nombre de lignes est le même que la première matrice et le nombre de colonnes est le même que la deuxième matrice

let row1Count = matrix1.values.[*,0].Length
let col2Count = matrix2.values.[0,*].Length

//        
let values = Array2D.zeroCreate row1Count col2Count

Après cela, nous parcourons toutes les lignes et toutes les colonnes des matrices originales

for r in 0..row1Count-1 do
    for c in 0..col2Count-1 do
        let row = Array.toList matrix1.values.[r,*]
        let col = Array.toList matrix2.values.[*,c]

Nous calculons la valeur totale de chaque cellule

let cell = List.fold2 (fun acc val1 val2 -> acc + (val1 * val2)) 0 row col

La fonction List.fold2 reçoit deux listes en entrée (ligne et colonne) et transmet les paramètres suivants au gestionnaire

acc - l'accumulateur contenant le résultat du calcul précédent
val1 - le contenu de la cellule du premier tableau. Dans notre cas, il s'agit de la ligne de la première matrice
val2 - le contenu de la cellule du deuxième tableau, c'est-à-dire les colonnes de la deuxième matrice.

Puisque les matrices sont cohérentes, nous sommes sûrs de ne pas aller au-delà des tableaux.

Le gestionnaire ajoute à l'accumulateur un produit de cellules provenant de lignes et d'une colonne, et la valeur résultante sera passée à l'itération suivante. Ainsi, le résultat final de la fonction List.fold2sera la valeur finale des produits de deux matrices. Il ne reste plus qu'à les remplir avec la matrice vide précédemment créée

values.[r,c] <- cell

Qui reviendra en conséquence

{ values = values }

Voici un exemple d'utilisation de cette fonction

let a = array2D [[1;0;2]
                 [3;1;0]]
let A = Matrix.ofArray2D a

let b = array2D [[-1;0]
                 [5;1]
                 [-2;0]]
let B = Matrix.ofArray2D b

let R = A*B

printfn "A*B =\n %A" R.values

A1*B1 =
 [[-5; 0]
 [2; 1]]

Si k ∈ N, alors la kième puissance d'une matrice carrée A est le produit de k matrices A

$$

$$A^k=A*A*...A (k- )$$

Considérez le code sur F # pour le produit d'une matrice à une puissance. La récursivité de la queue sera utilisée ici afin de ne pas faire déborder la pile avec de grandes puissances. La récursivité de queue est une récursivité que le compilateur convertit finalement en boucle. Si possible, il est recommandé que vous utilisiez toujours la récursivité de queue au lieu de la normale, mais pour cela, vous avez besoin de chaque trame de récursivité pour retourner la valeur calculée finale. Cette valeur est généralement appelée accumulateur et est transmise à la trame de récursivité suivante. Autrement dit, contrairement à la récursivité régulière, qui renvoie la valeur calculée vers le haut de la pile, la récursivité de queue transmet la valeur calculée vers le bas de la pile. Chaque nouvelle trame de récursivité effectue ses propres calculs et les ajoute à la valeur précédemment calculée, qui est stockée dans la batterie. Après ça,Comme la dernière image de la récursivité a fonctionné, l'accumulateur a déjà une valeur calculée, qui revient simplement en conséquence.

Ainsi, le compilateur peut optimiser le code et le convertir en boucle régulière.

//    
// matrix -  
// value -  
static member (^^) (matrix, value) =

    //  ,    
    // m - 
    // p =  
    let inRecPow m p =

        //  
        // acc -  .   Matrix
        // p -     
        //         
        let rec recPow acc p =
            //   
            match p with
            | x when x > 0 ->
                //    
                //      ,      
                let nextAcc = acc*m
                //           
                recPow nextAcc (x-1)
            //    ,    
            | _ -> acc

        //   ,         
        let dim = Matrix.sizes matrix
        let colCount = snd dim
        let rowCount = fst dim

        let u = Matrix.E rowCount colCount
        //           
        recPow u p

    //  ,      
    let powMatrix = inRecPow matrix value
    //   
    { values = powMatrix.values }

Le code contient des commentaires détaillés sur son fonctionnement. Nécessite une petite explication, pourquoi la matrice unitaire est-elle utilisée? Il est nécessaire pour la première trame de récursivité et sert de valeur de base à l'accumulateur, dans lequel le résultat final sera accumulé.
Voici un exemple d'utilisation de notre fonction

$$

$$A=\begin{pmatrix}1&0\\2&-1\end{pmatrix}$$

$$

$$A^2=AA=\begin{pmatrix}1&0\\2&-1\end{pmatrix}\begin{pmatrix}1&0\\2&-1\end{pmatrix}=\begin{pmatrix}1&0\\0&1\end{pmatrix}$$

$$

$$A^3=AA^2=\begin{pmatrix}1&0\\2&-1\end{pmatrix}\begin{pmatrix}1&0\\0&1\end{pmatrix}=\begin{pmatrix}1&0\\2&-1\end{pmatrix}$$

Nous calculons le produit suivant

$$

$$f(A)=2A^3-4A^2+3E$$

Où E est la matrice d'identité. Puisque nous ne pouvons pas ajouter un nombre à la matrice, nous devons ajouter 3E .

$$

$$2\begin{pmatrix}1&0\\2&-1\end{pmatrix}- 4\begin{pmatrix}1&0\\0&1\end{pmatrix}+ 3\begin{pmatrix}1&0\\0&1\end{pmatrix}= \begin{pmatrix}1&0\\4&-3\end{pmatrix}$$

//     
static member (+) (matrix, (value: int)) =
    let dim = Matrix.sizes matrix
    let r = fst dim
    let c = snd dim

    //   
    let unit = Matrix.E r c
    //          
    value*unit + matrix

let a = array2D [[1;0]
                 [2;-1]]
let A = Matrix.ofArray2D a

let R = 2*(A^^3) - 4*(A^^2) + 3
printfn "2*A^3 - 4*A^2 + 3 =\n %A" R.values

2*A5^3 - 4*A5^2 + 3 =
 [[1; 0]
 [4; -3]]

Une matrice A ^T dont les colonnes sont composées de rangées de matrice A avec les mêmes nombres et la même séquence d'éléments est appelée transposée en matrice A

static member transpose matrix =
    let dim = Matrix.sizes matrix
    let rows = fst dim
    let cols = snd dim

    //      
    let tMatrix = Matrix.O cols rows
    //       
    matrix.values |> Array2D.iteri(fun x y v -> tMatrix.values.[y, x] <- v)

    //  
    tMatrix

Exemple d'utilisation

let a = array2D [[1;2;3]
                 [4;5;6]
                 [7;8;9]
                 [10;11;12]]
let A = Matrix.ofArray2D a
let R6 = Matrix.T A
printfn "origin = \n %A" A.values
printfn "transpose = \n %A" R.values

origin = 
 [[1; 2; 3]
 [4; 5; 6]
 [7; 8; 9]
 [10; 11; 12]]
transpose = 
 [[1; 4; 7; 10]
 [2; 5; 8; 11]
 [3; 6; 9; 12]]

Sommaire

Dans cet article, nous avons examiné des exemples de mise en œuvre et d'utilisation de matrices issues de la théorie de l'algèbre linéaire. Ainsi que les opérations mathématiques de base sur celles-ci, en utilisant une approche fonctionnelle en F #. J'espère que le lecteur pourra apprécier la flexibilité offerte par les langages fonctionnels.

Le code source complet du module de matrice, dont des fragments ont été examinés dans l'article, vous pouvez le trouver sur le github.

Github Matrix.fs