Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Implemente uma função recursiva que calcule a n-ésima potência de uma matriz quadrada e obtenha \( \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n \) para \( n = 1,2,…,10 \).

0 votos
16 visitas
perguntada Out 8 em Programação Computacional por Thiago Trafane (21 pontos)  
editado Out 8 por Thiago Trafane

Exercício 4.3 do capítulo 4 do livro "Introduction to Recursive Programming" de Manuel Rubio-Sanchez. O enunciado completo segue abaixo:

Implemente uma função recursiva que calcule a n-ésima potência de uma matriz quadrada, que é uma outra matriz quadrada de mesma dimensão. Use o pacote NumPy e seus métodos:

  • identity: retorna uma matriz identidade.
  • shape: indica as dimensões de uma matriz.
  • dot: multiplica matrizes.

Finalmente, calcule a matriz
\( \begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}^n \)
para \( n = 1,2,…,10 \) e imprima o elemento na primeira linha e segunda coluna de cada matriz. O que são esses números?

Compartilhe

1 Resposta

0 votos
respondida Out 8 por Thiago Trafane (21 pontos)  

A implementação da função recursiva que calcula a n-ésima potência de uma matriz quadrada é apresentada abaixo. Como se vê, o código é bastante simples. Inicialmente, importa-se o pacote Numpy. Então, a função é definida. Essa função pode ser aplicada apenas para matrizes quadradas. Logo, se a matriz não for quadrada, a execução é interrompida e um aviso de erro é apresentado.

Caso a matriz seja quadrada, são tratados separadamente os casos de expoente 0, quando o resultado é a matriz identidade, e de expoente 1, quando o resultado é a própria matriz. Esse último caso funciona como critério de parada da recursão, que é chamada nos demais casos (isto é, quando o expoente é estritamente maior que 1).

# 0) Importando pacote Numpy
import numpy as np

# 1) Definindo a função
def npower(M,n): #M = matriz e n = expoente  
    if M.shape[0] != M.shape[1]: #Função é definida apenas para matrizes quadradas
        print('Erro: matriz não é quadrada')
        return    
    else:
        if n==0: #Caso expoente 0
            return np.identity(M.shape[0])
        if n==1: #Caso expoente 1, que funciona como critério de parada da recursão
            return M
        else: #Demais casos - recursão
            return np.dot(M,npower(M,n-1))

Com base nessa função, podemos obter os resultados solicitados no enunciado usando o código abaixo. Vale citar que, apesar de não ter sido pedido, eu fiz o cálculo também para o expoente 0. As matrizes resultantes foram salvas como ipower_M, em que i é a potência considerada. Com relação aos resultados para o elemento na primeira linha e na segunda coluna das matrizes, temos: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 e 55. Ou seja, trata-se da sequência de Fibonacci.

# 2) Calculando as matrizes pedidas
if __name__ == '__main__':
    M = np.array([[1,1],[1,0]])

    for n in range(11):
        locals()[str(n)+'power_M'] = npower(M,n)
        print(locals()[str(n)+'power_M'][0,1])
...