No post anterior (Parte I), implementamos o algoritmo para calcular o determinante de uma matriz via teorema de Laplace (ou método do cofator). No caso, fizemos o método recursivo. Nesse post, faremos o método iterativo.
Para isso, temos que pensar em algumas coisas:
- Para calcular o determinante, precisamos calcular cofatores.
- Para calcular cofatores, precisamos calcular o determinante das matrizes reduzidas.
- Para calcular o determinante das matrizes reduzidas, precisamos calcular os cofatores dessas matrizes...
- Até chegarmos nas matrizes reduzidas de ordem 3, que sabemos calcular o determinante de forma direta.
Perceba que, para cada matriz de ordem n, temos n submatrizes de ordem n-1. Para cada matriz de ordem n-1, temos n-1 submatrizes de ordem n-2, e assim por diante. É como se tivéssemos uma árvore de matrizes, cuja base é composta pelas matrizes de ordem 3. A Figura abaixo apresenta um exemplo para uma matriz de ordem 5.
Após calcular o determinante das matrizes de ordem 3, calculamos os determinantes das matrizes de ordem 4, depois das de ordem 5... ou seja, subimos os níveis da árvore de matrizes.
Aqui eu preciso deixar claro que vamos trabalhar com a estrutura de dados de lista e não a de árvore propriamente dita. Porém, continuarei chamando a estrutura de árvore por ser mais fácil de entender a lógica do problema.
Logo, precisamos saber quais são todas essas matrizes. Para isso, vamos implementar uma função que, dada uma matriz de ordem n, calcula as submatrizes de ordem n-1. Assim como no post anterior, para facilitar o problema, vamos escolher sempre a primeira linha da matriz para computar o método do cofator. Vejamos o código:
calc_submatriz = function(A){
auxsub = A[-1,];
subm = list();
for(i in 1:ncol(A)) subm[[i]] = auxsub[,-i]
return(subm)
}
O que estamos fazendo no código acima?
- Retiramos a primeira linha da matriz;
- Iniciamos subm como uma lista para receber as submatrizes.
- Para cada coluna da matriz, retiramos a i-ésima coluna e armazenamos em subm.
- Retornamos o resultado.
Perceba que calculamos as submatrizes apenas para o próximo nível da árvore. Precisamos calcular todas as submatrizes de ordem inferiores dada uma matriz original. Vamos ao código:
calc_all_submatriz = function(A){
n = ncol(A);
if(n<=3){
cat("Não é necessário calcular as submatrizes.\n")
return()
}else{
res = list()
res[[1]] = list(ori = A);
for(i in 2:(n-2)){
auxres = list();
auxj = 1;
for(j in 1:length(res[[i-1]])){
res_ = calc_submatriz(res[[i-1]][[j]])
for(w in 1:length(res_)){
auxres[[auxj]] = res_[[w]]
auxj = auxj +1;
}
}
res[[i]] = auxres;
}
}
return(res)
}
Vejamos novamente o que estamos fazendo:
- Se a dimensão da matriz é igual ou inferior a 3, não é necessário calcular submatrizes.
- Caso contrário, iniciamos nossa lista de resultado res.
- O primeiro nível da árvore conterá a matriz original.
- Para o próximo nível, calculamos as submatrizes da seguinte forma:
- Para cada submatriz do nível anterior, calcule as submatrizes correspondentes.
- Armazene essas submatrizes na lista auxres.
- Repita os passos 5 e 6 até acabarem as submatrizes do nível anterior.
- Armazene auxres na lista de resultado res.
Vamos testar nosso código? Vamos listar a árvore de matrizes de uma matriz de ordem 4.
D = matrix(c(1,2,3,4,2,1,3,4,2,1,9,7,4,5,1,4),ncol=4,byrow=T)
calc_all_submatriz(D)
[[1]]
[[1]]$ori
[,1] [,2] [,3] [,4]
[1,] 1 2 3 4
[2,] 2 1 3 4
[3,] 2 1 9 7
[4,] 4 5 1 4
[[2]]
[[2]][[1]]
[,1] [,2] [,3]
[1,] 1 3 4
[2,] 1 9 7
[3,] 5 1 4
[[2]][[2]]
[,1] [,2] [,3]
[1,] 2 3 4
[2,] 2 9 7
[3,] 4 1 4
[[2]][[3]]
[,1] [,2] [,3]
[1,] 2 1 4
[2,] 2 1 7
[3,] 4 5 4
[[2]][[4]]
[,1] [,2] [,3]
[1,] 2 1 3
[2,] 2 1 9
[3,] 4 5 1
Você pode verificar que todas as submatrizes de ordem 3 estão especificadas corretamente. Também pode testar com uma matriz de ordem maior, de ordem 5 por exemplo.
Logo, já temos nossa função para calcular todas as submatrizes de uma matriz dada. Agora, precisamos calcular o determinante das matrizes de ordem 3 e depois voltar aos níveis da árvore para calcular os determinantes das matrizes de ordem superior.
Vamos começar definindo a função:
calc_det_laplace = function(A){
n = ncol(A);
if(n==2){
return(calc_det2(A));
}else if(n==3){
return(calc_det3(A));
}
(...)
}
Definimos a função e, novamente, se a matriz dada possui ordem 2 ou 3, chamamos a respectiva função para calcular seu determinante de forma direta. Caso a matriz seja de ordem superior a 3, aplicamos o método do cofator.
Vamos continuar com o código da função:
submat = calc_all_submatriz(A);
n_levels = length(submat);
No código acima:
- Calculamos todas as submatrizes da matriz dada e armazenamos em submat,
- Verificamos quantos níveis essa árvore possui.
O próximo passo é calcular o determinante de todas as submatrizes de ordem 3:
for(i in 1:length(submat[[n_levels]])) auxdet1[i] = calc_det3(submat[[n_levels]][[i]])
Ou seja, estamos acessando o último nível da árvore (lembre que estamos utilizando lista e não a estrutura de dados árvore) e, para cada matriz desse nível, calculando seu determinante.
O próximo passo é, dados os determinantes das matrizes de ordem 3, calcular os determinantes das matrizes de ordem 4, depois das de ordem 5 até chegar na matriz original. Vejamos o código:
for(i in (n_levels-1):1){
cofator = NULL;
dim_mat = ncol(submat[[i]][[1]])
auxdet2 = NULL;
for(j in 1:length(submat[[i]])){
aux_sub = submat[[i]][[j]][1,]
cofator = rep(-1,dim_mat)^(1+1:dim_mat) * auxdet1[((j-1)*dim_mat+1):(j*dim_mat)];
auxdet2[j] = sum(aux_sub*cofator);
}
auxdet1 = auxdet2;
}
Analisemos o código acima:
- O primeiro for (da variável i) irá caminhar pelos níveis da árvore, do penúltimo ao primeiro.
- Iniciamos a variável que armazenará os cofatores dos elementos da primeira linha da submatriz.
- Verificamos a dimensão da submatriz desejada.
- Iniciamos a variável auxdet2 para armazenar os determinantes do nível superior da matriz.
- O segundo for (da variável j) irá caminhar pelas matrizes do nível i da árvore.
- Para cada matriz desse nível, pegamos sua primeira linha, calculamos seus respectivos cofatores e, em seguida, calculamos o determinante dessa matriz e armazenamos em auxdet2.
- Repetimos esse processo para todas as matrizes de cada nível da árvore, sempre subindo o nível (que, no caso, significa diminuir o índice i) até chegar à matriz original.
- Quando i=1, calculamos o determinante da matriz desejada.
Após a execução acima, retornamos o resultado.
return(auxdet1);
O código completo da função está abaixo:
calc_det_laplace = function(A){
n = ncol(A);
if(n==2){
return(calc_det2(A));
}else if(n==3){
return(calc_det3(A));
}
submat = calc_all_submatriz(A);
n_levels = length(submat);
auxdet1 = NULL;
for(i in 1:length(submat[[n_levels]])) auxdet1[i] = calc_det3(submat[[n_levels]][[i]])
for(i in (n_levels-1):1){
cofator = NULL;
dim_mat = ncol(submat[[i]][[1]])
auxdet2 = NULL;
for(j in 1:length(submat[[i]])){
aux_sub = submat[[i]][[j]][1,]
cofator = rep(-1,dim_mat)^(1+1:dim_mat) * auxdet1[((j-1)*dim_mat+1):(j*dim_mat)];
auxdet2[j] = sum(aux_sub*cofator);
}
auxdet1 = auxdet2;
}
return(auxdet1);
}
Note que realizamos todo o processo sem o uso da recursão. Porém, pagamos o preço de armazenar toda a árvore de submatrizes.
Vamos testar nosso código com o mesmo exemplo do post anterior:
D = matrix(c(1,2,3,4,2,1,3,4,2,1,9,7,4,5,1,4),ncol=4,byrow=T)
print(D)
[,1] [,2] [,3] [,4]
[1,] 1 2 3 4
[2,] 2 1 3 4
[3,] 2 1 9 7
[4,] 4 5 1 4
det(D)
[1] 72
calc_det_laplace(D)
[1] 72
Agora temos uma função para calcular o determinante de uma matriz utilizando o teorema de Laplace e de forma iterativa! No próximo post, vamos comparar a eficiência das funções que criamos com a função embutida no R.
Espero que tenha gostado da aula.
Até a próxima aula!
Nenhum comentário:
Postar um comentário