Jump to content

Multiplicação de matrizes


skiller10
 Share

Recommended Posts

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

Link to comment
Share on other sites

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 😄

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

Link to comment
Share on other sites

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

Link to comment
Share on other sites

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

Link to comment
Share on other sites

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?

Link to comment
Share on other sites

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

Link to comment
Share on other sites

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!

Link to comment
Share on other sites

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?

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

Link to comment
Share on other sites

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.

Link to comment
Share on other sites

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

Link to comment
Share on other sites

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

Link to comment
Share on other sites

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

Link to comment
Share on other sites

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.

Link to comment
Share on other sites

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

Link to comment
Share on other sites

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.

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.