Programação funcional como exemplo de trabalho com matrizes da teoria da álgebra linear

Introdução

A base do trabalho com matrizes (neste artigo, consideraremos apenas matrizes bidimensionais) é uma poderosa teoria matemática do campo da álgebra linear. Uma definição ou ação segue de outra; uma função chama outra. Portanto, para implementação funcional das operações matemáticas funcionais em matrizes, as linguagens funcionais se encaixam muito bem. Neste artigo, examinaremos exemplos específicos em F # e forneceremos comentários detalhados sobre como isso funciona. Como o F # faz parte da família .NET, a funcionalidade resultante pode ser usada sem problemas em outras linguagens imperativas, por exemplo, C #.

Definição e implementação de matrizes em F #

Matrizes são a parte básica e mais importante da álgebra linear. Matrizes são frequentemente usadas na programação, por exemplo, na modelagem 3D ou no desenvolvimento de jogos. Obviamente, a bicicleta já foi inventada e as estruturas necessárias para trabalhar com matrizes já estão prontas e podem e devem ser usadas. Este artigo não tem como objetivo inventar uma nova estrutura, mas mostra a implementação de operações matemáticas básicas para trabalhar com matrizes em um estilo funcional usando a linguagem de programação F #. Ao examinarmos o material, nos voltaremos para a teoria matemática das matrizes e veremos como ela pode ser implementada no código.

Primeiro, vamos lembrar o que é uma matriz? Teoria nos diz o seguinte

Uma tabela retangular de números contendo m linhas e n colunas é chamada de matriz de tamanho mxn

As matrizes são geralmente indicadas por letras maiúsculas do alfabeto latino e são escritas como

$$

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

Ou em breve

$$

$$A=(aij)$$

Para trabalhar com matrizes em F #, criaremos um registro baseado em uma tabela bidimensional, que expandiremos ainda mais com métodos úteis para executar as operações matemáticas necessárias.

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

Adicione um método auxiliar para inicializar a gravação com uma matriz bidimensional

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

O argumento de entrada para a função será uma matriz bidimensional e, na saída, um registro do tipo Matrix . Abaixo está um exemplo de inicialização de registro.

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

Duas matrizes A = (aij) e B = (bij) são chamadas iguais se coincidirem elementares, ou seja, aij = bij para todos os i = 1,2 ..., m e j = 1,2, ... n

Para implementar essa regra, usaremos o operador substituído == e adicionaremos algumas funções úteis, que também serão necessárias no futuro.

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)

Vamos dar uma olhada no código acima. Como você pode ver, existem três funções. A primeira função de tamanhos retorna a dimensão da matriz como uma tupla. Como trabalhamos apenas com matrizes retangulares, para obter o número de linhas, pegamos uma fatia completa da primeira coluna e retornamos seu comprimento.

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

Determinar o número de colunas funciona de maneira semelhante - obtemos uma fatia completa da primeira linha e retornamos seu comprimento.

A seguinte função isEquallySized compara a dimensão de duas matrizes e retorna true se forem iguais. Para fazer isso, ele usa a função de tamanhos prontos e simplesmente compara os resultados.

O operador == para comparar elementos de duas matrizes parece mais complicado, mas agora você verá que também é simples.

Antes de comparar duas matrizes, comparamos sua dimensão. Se eles não forem iguais, não há mais sentido em verificar, pois já está claro que as matrizes não serão iguais.

if not (Matrix.isEquallySized matrix1 matrix2) then false

Em seguida, com base nas matrizes originais matrix1 e matrix2, formamos uma nova matriz preenchida com true ou false , dependendo se as células correspondentes de ambas as matrizes coincidem.

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

A função Array2D.mapi itera sobre todos os elementos da matriz1 e passa três parâmetros
x para o índice da linha do manipulador
y - índice da coluna
v -
conteúdo da célula Comparamos o conteúdo da célula v com a matriz da célula correspondente2 e, se forem iguais, escreva true , caso contrário, false , caso contrário, false .

Se houver pelo menos uma célula com o elemento false , isso significa que as matrizes não são iguais umas às outras.

Como o Array2D não contém métodos para filtrar ou pesquisar, nós mesmos implementaremos isso. Para fazer isso, decompomos a matriz em uma lista linear

|> Seq.cast<bool>

E encontre pelo menos uma incompatibilidade

|> Seq.contains false

A função Seq.contains retornará true se pelo menos um valor falso for encontrado na lista expandida . Portanto, precisamos inverter o resultado para que o operador == funcione da maneira que queremos

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)

Uma matriz O é chamada de matriz zero ou zero se todos os seus elementos forem iguais a zero.

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

Um exemplo de uso desta função

let AO = Matrix.O 5 5

Acredito que não há nada complicado que exija explicação, por isso continuamos.

Uma matriz cujo número de linhas é igual ao número de colunas e igual a n é chamada de matriz quadrada de ordem n

Assim, a matriz quadrada tem a forma.

$$

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

Como parte dessa regra, criaremos uma função que transforma uma matriz retangular em uma matriz quadrada cortando todos os elementos que não caem no quadrado.

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 }

Os comentários no código-fonte explicam como a função funciona, então vamos continuar.

Uma matriz quadrada é chamada triangular se todos os seus elementos abaixo da diagonal principal forem iguais a zero, ou seja, a matriz triangular tem a forma

$$

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

Abaixo está o código da função que converte a matriz original em uma triangular. Mas, em nossa função, trabalharemos com uma matriz retangular, ou seja, pode não ser quadrada. O leitor pode modificar facilmente o código da função para retornar uma matriz triangular quadrada usando a função que examinamos anteriormente.

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

A função Array2D.mapi converte a matriz bidimensional original em uma nova, usando um manipulador que usa três parâmetros

x - número da linha
y - número da coluna
v - conteúdo da célula

if y < x then 0 else v

Aqui, verificamos se o elemento está abaixo da diagonal principal e, se estiver, preencha a célula 0. Caso contrário, o valor inicial da matriz de entrada.

A seguir, é apresentado um exemplo do uso dessa função.

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

Temos o seguinte resultado

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]]

Uma matriz quadrada é chamada diagonal se todos os seus elementos localizados fora da diagonal principal forem iguais a zero

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

Esta função é muito semelhante à anterior, apenas a condição de verificação é diferente. Abaixo está um exemplo de uso

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]]

A matriz diagonal é a unidade e é denotada por E se todos os seus elementos localizados na diagonal principal forem iguais à unidade

$$

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

A implementação dessa matriz no F # se parece com isso

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

Operações de matriz com F #

Várias ações podem ser executadas em matrizes, bem como em números, algumas das quais são semelhantes às operações em números e outras são específicas.

A soma das duas matrizes Amn = (aij) e Bmn = (bij) do mesmo tamanho é a matriz do mesmo tamanho A + B = Cmn = (cij) , cujos elementos são iguais à soma dos elementos das matrizes A e B localizadas nos locais correspondentes

$$

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

Exemplo, para determinadas matrizes A e B, encontramos a soma 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}$$

Considere o código para adicionar duas matrizes

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"

Antes de adicionar matrizes, você precisa garantir que suas dimensões coincidam, caso contrário, a função gera uma exceção. Abaixo está um exemplo de uso dessa função

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]]

O produto da matriz A = (aij) pelo número k é a matriz kA = (kaij) do mesmo tamanho da matriz A obtida pela multiplicação de todos os elementos da matriz A pelo número k

Exemplo, para uma dada matriz A , encontramos a matriz 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 }

Matriz -A = (- 1) * Um será chamada a matriz oposto Uma . A partir dessa definição, prosseguimos sem problemas para a próxima

A diferença das matrizes A e B de tamanhos iguais é a soma da matriz A e da matriz oposta a B

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

Duas matrizes são chamadas consistentes se o número de colunas da primeira for igual ao número de linhas da segunda

$$

$$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

A verificação de consistência da matriz é necessária para multiplicá-los.

A matriz coerente AB do produto Amn = (aij) e Bnp = (bjk) é a matriz Cmn = (cik) , o elemento cik é calculado como a soma dos elementos i -ésima linha da matriz A e os elementos correspondentes da k- ésima coluna da matriz B

Calcular o produto das matrizes

$$

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

Decisão para determinar o produto das matrizes

$$

$$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}$$

Considere o código para multiplicar duas matrizes

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"

Vamos dar uma olhada no código em mais detalhes.
Antes da multiplicação, você precisa garantir que as matrizes sejam consistentes

if Matrix.isMatched matrix1 matrix2 then

A matriz resultante terá uma dimensão em que o número de linhas é igual à primeira matriz e o número de colunas é o mesmo que a segunda matriz

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

//        
let values = Array2D.zeroCreate row1Count col2Count

Depois disso, percorremos todas as linhas e todas as colunas das matrizes originais

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]

Calculamos o valor total de cada célula

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

A função List.fold2 recebe duas listas na entrada (linha e coluna) e passa os seguintes parâmetros para o manipulador

acc - o acumulador que contém o resultado do cálculo anterior
val1 - o conteúdo da célula da primeira matriz. No nosso caso, esta é a linha da primeira matriz
val2 - o conteúdo da célula da segunda matriz, ou seja, as colunas da segunda matriz.Como

as matrizes são consistentes, temos certeza de que não iremos além das matrizes.

O manipulador adiciona ao acumulador um produto de células de linhas e uma coluna, e o valor resultante será passado para a próxima iteração. Assim, o resultado final da função List.fold2será o valor final dos produtos de duas matrizes. Resta apenas preenchê-los com a matriz vazia criada anteriormente

values.[r,c] <- cell

Que retornará como resultado

{ values = values }

Abaixo está um exemplo de uso dessa função

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]]

Se k ∈ N, então a potência k de uma matriz quadrada A é o produto de k matrizes A

$$

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

Considere o código em F # para o produto de uma matriz em uma fonte. A recursão da cauda será usada aqui para não sobrecarregar a pilha com grandes potências. Recursão de cauda é uma recursão que o compilador eventualmente converte em um loop. Se possível, é recomendável usar sempre a recursão de cauda em vez da usual, mas para isso você precisa de cada quadro de recursão para retornar o valor final calculado. Esse valor geralmente é chamado de acumulador e é passado para o próximo quadro de recursão. Ou seja, diferente da recursão regular, que retorna o valor calculado na pilha, a recursão final passa o valor calculado na pilha. Cada novo quadro de recursão faz seus próprios cálculos e os adiciona ao valor calculado anteriormente, que é armazenado na bateria. Depois disso,Conforme o último quadro da recursão funcionou, o acumulador já possui um valor calculado, que simplesmente retorna como resultado.

Assim, o compilador pode otimizar o código e convertê-lo em um loop regular.

//    
// 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 }

O código contém comentários detalhados sobre como funciona. Requer uma pequena explicação, por que a matriz unitária é usada? É necessário para o primeiro quadro de recursão e serve como o valor base do acumulador, no qual o resultado final será acumulado.
Abaixo está um exemplo de como usar nossa função

$$

$$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}$$

Calculamos o seguinte produto

$$

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

Onde E é a matriz de identidade. Como não podemos adicionar um número à matriz, devemos adicionar 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]]

A matriz A ^T cujas colunas são compostas de linhas da matriz A com os mesmos números e a mesma sequência de elementos é chamada transposta para a matriz 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

Exemplo de uso

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]]

Sumário

Neste artigo, examinamos exemplos da implementação e uso de matrizes da teoria da álgebra linear. Bem como as operações matemáticas básicas sobre eles, usando uma abordagem funcional em F #. Espero que o leitor possa apreciar a flexibilidade que as linguagens funcionais fornecem.

O código fonte completo do módulo da matriz, cujos fragmentos foram considerados na estrutura do artigo, você pode encontrar no github.

Github Matrix.fs