Ir para o conteúdo
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

skiller10

Multiplicação de matrizes

Mensagens Recomendadas

skiller10

Boas,

Alguém me consegue explicar ou indicar alguns bons sítios onde aprender como se multiplica matrizes e dada uma matriz de tamanho DXD, obter a sua i-ésima potência em O(D^3log(N)).

Cumprimentos,

skiller10


"Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Warrior

A multiplicação de matrizes está bem explicada nessa página.

Para obteres a n-ésima potência em log(n) é só utilizar o mesmo algoritmo que utilizas para números. Consegues calcular k^n em O(log(n))?

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
skiller10

Já entendi como funciona a multiplicação de matrizes, mas confirma-me se estou certo sff, exemplo:

|1 1| 2 = |2 1|

|1 0|      |1 1|

Sim consigo :D


"Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Warrior

Não consigo perceber o teu exemplo de multiplicação de matrizes. Pareces estar a multiplicar uma matriz por um número, mas ainda assim com resultado diferente.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
skiller10

No exemplo que fiz estou a multiplicar a matriz {{1,1},{1,0}} por ela própria, ou seja, a matriz ao quadrado.


"Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Warrior

Desculpa, perdi a fiada ao tópico.

Sim, está bem multiplicada.

Tenta resolver um "tribonacci" depois do Fibonacci, para ver se realmente percebeste a solução.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
skiller10

Não pensei muito mas pelo que percebi para um "tribonacci" que pelo que vi é uma sequência igual à de fibonacci mas em que um elemento é a soma dos três elementos anteriores será com o mesmo método, apenas com a alteração que a matriz será de três:

Sequência: 1 1 2 4 7 13 ...

Matriz: {{2,1,1},{1,1,0},{1,0,0}}^N

|2 1 1|^N

|1 1 0|

|1 0 0|

O meu raciocínio está correcto?


"Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Warrior

Podes multiplicar "à mão" (ou usar um qualquer programa para isso, como o excel..) a matriz por si própria algumas vezes e verificar se dá os resultados correctos.

Digo isto porque assumo que já resolveste o teu problema inicial.

PS: Consegues generalizar para N?

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
skiller10

O problema inicial ainda não tive tempo para o implementar mas já fiz os cálculos para verificar que estava certo e perceber como funcionava. Vou implementar ainda hoje, se não houver nenhum imprevisto, e depois fazer o mesmo para o "tribonacci". Quanto ao generalizar para N parece-me fácil usando o mesmo raciocínio até agora, ou seja, para "quadribonacci" ficaria uma matriz:

| f(n+3) f(n+2) f(n+1) f(n)    | ^ N

| f(n+2) f(n+1) f(n)    f(n-1) |

| f(n+1) f(n)    f(n-1)  f(n-2) |

| f(n)    f(n-1)  f(n-2)  f(n-3) |

PS: peço desculpa pelo esquema um pouco confuso :x


"Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Warrior

Não me parece que seja isso.

Aliás, a tua solução para o tribonacci não me parece correcta. (o primeiro elemento é 2?)

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
djthyrax

Pelo que percebi do teu post inicial, não sabes como multiplicar matrizes.

Considerando 2 matrizes, A e B, 3x3, tens a matriz 3x3 C=A*B, em que os seus elementos c i,j (elemento j da linha i) são dados por (a i,1*b 1,j + a i,2*b 2,j + a i,3*b 3,j).

Se quiseres mais informação sobre o uso de matrizes basta consultares os apontamentos de uma cadeira de Álgebra, se quiseres manda-me PM que arranjo-te uns.

Para experimentares brincar um pouquinho com matrizes, usa o Matlab. http://www.math.osu.edu/~overman.2/matlab.pdf


Não peças ajuda por PM! A tua dúvida vai ter menos atenção do que se for postada na secção correcta do fórum!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
skiller10

Estive a ver e percebi como se multiplicam matrizes mas não percebi a solução do fibonacci bem :D

Consegues-me explicar ou dar umas dicas para eu tentar entender?


"Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
pedrosorio

A solução do Fibonnaci está explicada aqui:

http://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form

Ao multiplicares o vector com os elementos (Fk+1; Fk) pela matriz [1 1; 1 0] obténs o vector (Fk+2, Fk+1) da sequência de fibonnaci. Percebes porquê?

E percebes que se multiplicares várias vezes seguidas pela matriz obténs sucessivamente os vectores (Fk+3, Fk+2), (Fk+4, Fk+3), etc.?


Não respondo a dúvidas por mensagem.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
skiller10

Obrigado pelos apontamentos djthyrax  B)

Ao multiplicares o vector com os elementos (Fk+1; Fk) pela matriz [1 1; 1 0] obténs o vector (Fk+2, Fk+1) da sequência de fibonnaci. Percebes porquê?

Não, tive a ver o link que mandaste da wikipedia, e mais alguns sites sobre este assunto mas ainda não consegui perceber bem  ;)

EDIT: Estive a fazer os cálculos em papel e já percebi.

Na primeira posição do vector resultado (FK+2) vai aparecer a soma dos dois elementos do primeiro vector, visto a primeira linha da matriz ser {1,1}.

A segunda posição do vector resultado (FK+1) vai ser o o valor da primeira posição do primeiro vector.

Exemplo:

|5| x |1 1| = |5*1 + 3*1| = |8|

|3|    |1 0|    |5*1 + 3*0|    |5|

Certo?


"Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
pedrosorio

É exatamente isso.

Tem cuidado que a multiplicação faz-se Matriz x vector e não vector x Matriz, essa forma que colocaste não é válida (Em multiplicação matricial, AxB, o número de colunas da matriz A tem que ser igual ao número de linhas da matriz B).

Consegues então perceber que vai gerar todos os elementos da sequência de fibonnaci, ao multiplicar por essa matriz sucessivamente?

E para o caso do tribonnaci como seria?


Não respondo a dúvidas por mensagem.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
skiller10

Consegues então perceber que vai gerar todos os elementos da sequência de fibonnaci, ao multiplicar por essa matriz sucessivamente?

Sim, mas ainda não percebi muito bem como é que a matriz multiplicada por ela própria vai gerar todos os elementos, sei que gera e já fiz os cálculos para testar, mas não percebi muito bem a lógica.

E para o caso do tribonnaci como seria?

Para um"tribonacci" seria:

|1 1 1|    x    | f(n+2) |    =    | f(n+3) |

|1 0 0|          | f(n+1) |            | f(n+2) |

|0 1 0|          | f(n)    |            | f(n+1) |

Certo?


"Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
pedrosorio

Sim, mas ainda não percebi muito bem como é que a matriz multiplicada por ela própria vai gerar todos os elementos, sei que gera e já fiz os cálculos para testar, mas não percebi muito bem a lógica.

Se calhar se pensares em código ajuda. Ao multiplicar:

|R2| = |1 1| x |F2|

|R1| = |1 0|    |F1|

(em que F1, e F2 são o primeiro e segundo elemento da sequência de fibonnaci)

estás a fazer:

R2 = F2+F1;
R1 = F2;

Concordas que ao executar este código, vamos ter R2 == F3, R1 == F2, certo? Para multiplicar duas vezes pela matriz (i.e. pela matriz ao quadrado),  basta pegar nos resultados que obtivemos e executar o mesmo código sobre eles. Para isso guardamos os valores de R2 e R1 nas variáveis iniciais, e executamos o mesmo código outra vez:

//multiplica
R2 = F2+F1;
R1 = F2;
//mete o resultado no "vector" que é multiplicado
F2 = R2;
F1 = R2;
//multiplica outra vez
R2 = F2+F1;
R1 = F2;

E agora vamos ter R2==F4 e R1==F3, certo? Para multiplicar N vezes basta-nos fazer um ciclo:

int i=0;
while(i++ < N) {
  //multiplica
  R2 = F2+F1;
  R1 = F2;
  //mete resultado no vector que vai multiplicar
  F2 = R2;
  F1 = R1;
}

No final temos R2 == F(N+2), R1 == F(N+1).

Para um"tribonacci" seria:

|1 1 1|    x    | f(n+2) |    =    | f(n+3) |

|1 1 0|          | f(n+1) |            | f(n+2) |

|1 0 0|          | f(n)    |            | f(n+1) |

Certo?

Não, se fizeres a multiplicação no papel vês que o vector resultado não é esse. Pensa bem. Repara que já tens f(n+2) e f(n+1) no vector que está a ser multiplicado...


Não respondo a dúvidas por mensagem.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
skiller10

Eu tinha alterado a matriz, inicialmente meti assim mas depois pensei melhor e vi que estava mal B)

EDIT: Quanto ao fibonacci acho que já percebi, mas mais logo vou implementar para garantir que entendi bem a solução  ;)


"Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
pedrosorio

Eu tinha alterado a matriz, inicialmente meti assim mas depois pensei melhor e vi que estava mal B)

Então como é que fica? ;)

EDIT: Quanto ao fibonacci acho que já percebi, mas mais logo vou implementar para garantir que entendi bem a solução  B)

Tu sabes isto, mas para ficar bem claro a quem ler isto posteriormente, aquilo que meti ali é apenas a implementação da multiplicação sucessiva pela matriz O(N).

A solução que tu queres, calcula directamente a matriz elevada a N, o que bem implementado é O(logN).


Não respondo a dúvidas por mensagem.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
skiller10

Tribonacci:

|1 1 1|    x    | f(n+2) |    =    | f(n+3) |

|1 0 0|          | f(n+1) |            | f(n+2) |

|0 1 0|          | f(n)    |            | f(n+1) |

Certo?


"Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
skiller10

Para N-bonacci multiplica-se uma matriz em que:

- A primeira linha é preenchida por 1 e as restantes linhas é tudo 0 com excepção de uma diagonal (cima esquerda para inferior direito) a começar na primeira coluna da segunda linha.

Por um vector de dimensão N, com os valores conhecidos 1 a K, por exemplo, e obtem-se então um vector com os valores de 2 a K+1.

Certo?


"Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
pedrosorio

Para N-bonacci multiplica-se uma matriz em que:

- A primeira linha é preenchida por 1 e as restantes linhas é tudo 0 com excepção de uma diagonal (cima esquerda para inferior direito) a começar na primeira coluna da segunda linha.

Por um vector de dimensão N, com os valores conhecidos 1 a K, por exemplo, e obtem-se então um vector com os valores de 2 a K+1.

Certo?

Exatamente. Multiplicas por um vector de dimensão N com os valores conhecidos de N até 1 (os termos de maior ordem aparecem primeiro, na representação que estamos a utilizar) e obténs o vector com os valores de N+1 até 2.


Não respondo a dúvidas por mensagem.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
skiller10

Obrigado a todos pela ajuda ;)


"Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora

×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.