Multiplicação de matrizes

[skiller10 0]

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

[pmg 96]

Wikipedia?

MathWorld? exemplo

[Warrior 68]

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))?

[skiller10 0]

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

[Warrior 68]

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.

[skiller10 0]

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

[Warrior 68]

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.

[skiller10 0]

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?

[Warrior 68]

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?

[skiller10 0]

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

[Warrior 68]

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?)

[djthyrax 10]

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

[skiller10 0]

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

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

[pedrosorio 4]

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.?

[skiller10 0]

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?

[pedrosorio 4]

É 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?

[skiller10 0]

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?

[pedrosorio 4]

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

[skiller10 0]

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 

[pedrosorio 4]

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).

[skiller10 0]

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?

[pedrosorio 4]

Oh yeah! E para N-bonacci?

[skiller10 0]

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?

[pedrosorio 4]

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.

[skiller10 0]

Obrigado a todos pela ajuda