math.math-mp math.math-gm nlin phys.meca
Roberto Luo 
  
Michel Tosin 
  
Americo Cunha 
  
Formas de energia mínima na representação de sistemas lineares como grafos

 

Formas de Energia Mínima na Representação de Sistemas Lineares como Grafos Roberto Luo Yuan Cai Michel Antonio Tosin Caldas Americo Barbosa da Cunha Junior robertoluoo@gmail.com michel.tosin@uerj.br americo@ime. • Sistemas lineares possuem correspondência com matrizes e grafos;

       2x 1 + x 2 + x 3 = 1 x 1 + 2x 2 + x 3 = 1 x 1 + x 2 + 2x 3 = 1 ⇔    2 1 1 1 2 1 1 1 2       x 1 x 2 x 3    =    1 1 1   
Existem diversas aplicações para grafos, tais como:

-Fluxograma de rede de transporte; -Redes sociais; -Redes elétricas; -Banco de dados. • Grafos podem apresentar diversas configurações;

• Cada configuração pode ser associado uma função de energia; Qual a melhor (mais bela) configuração para um grafo?

A DE MENOR ENERGIA! Objetivo Determinar a configuração de menor energia do grafo associado a um sistema linear, otimizado à sua melhor forma por meio do método de Newton-Raphson.

Energia de um grafo

Seja um sistema n×n simétrico

AX = B.
Existe uma analogia entre esse sistema e um grafo, de modo que:

• os n vértices indicam as variáveis do sistema linear original; • A representa a matriz de adjacência do grafo, tal que -a diagonal principal reúne as massas m j dos vértices, -os demais elementos caracterizam contantes de rigidez k ij das arestas do grafo. • Por fim, os valores na matriz B expressam as cargas elétricas q i de cada vértice. Dessa analogia resulta um grafo onde atuam forças elásticas, elétricas e gravitacionais. Posicionando o primeiro vértice na posição de origem do sistema, a energia deste grafo é dada pelo somatório das energias atuantes, por meio da função

E = 1≤i =j≤n 1 2 k ij r 2 ij energia elástica + 1≤i =j≤n 1 2 k e q i q j r ij energia elétrica + n j=2
-m j gr 1j cos θ 1j energia gravitacional , onde k e é a constante de Coulomb, r ij a distância entre os i-ésimo e j-ésimo vértices e g a aceleração da gravidade. Além disso, a função E está sujeita às seguintes restrições:

r 2 ij = r 1j cos θ 1j -r 1i cos θ 1i 2 + r 1j sin θ 1j -r 1i sin θ 1i 2 , i = j .

Caso de dois vértices

A função da energia para o caso de dois vértices é dado por E(r 12 , θ 12 ) = 1 2 k 12 r 2 12 + k e q 1 q 2 r 12 -m 2 r 12 g cos θ 12

x y

1 2 + + + + + + g Modelo físico.

Problema otimização

Dentre as configurações possíveis para o grafo, será buscada a que gera mínima energia. Seja x o vetor que reúne os argumentos da função de energia E. O problema de otimização da energia se define em encontrar o vetor x * que satisfaz x * = arg min E(x) ⇒ ∇E(x) = 0.

Método de Newton-Raphson

• Método iterativo baseado em gradiente;

• É necessário que a função objetivo E seja de classe C 2 ;

• Um critério de parada é estabelecido de acordo com uma tolerância.

A partir de um chute inicial x 0 , a m-ésima iteração do método é da forma

x m+1 = x m -H(x m ) -1 ∇E(x m ), onde ∇E(x) =           ∂E ∂x 1 (x) ∂E ∂x 2 (x) . . . ∂E ∂x n (x)           e H(x) =           ∂ 2 H ∂x 2 1 (x) ∂ 2 H ∂x 2 ∂x 1 (x) . . . ∂ 2 H ∂x n ∂x 1 (x) ∂ 2 H ∂x 1 ∂x 2 (x) ∂ 2 H ∂x 2 2 (x) . . . ∂ 2 H ∂x n ∂x 2 (x) . . . . . . . . . . . . ∂ 2 f ∂x 1 ∂x n (x) ∂ 2 f ∂x 2 ∂x n (x) . . . ∂ 2 f ∂x 2 n (x)          
, são, respectivamente, o vetor gradiente e a matriz hessiana de E, e x m+1 é a m + 1-ésima aproximação para x * .

Caso de dois vértices

Substituindo k 12 , q 1 , q 2 , g e m 2 por 1, a energia a ser minimizada neste caso é dada por 

Caso de três vértices

Aplicando k 12 = k 13 = k 23 = k e = q 1 = q 2 = q 3 = g = m 2 = m 3 = 1, a expressão da energia neste caso se torna

E(r 12 , r 13 , r 23 , θ 12 , θ 13 ) = 1 2 r 2 12 + 1 r 12 -r 12 cos θ 12 + 1 2 r 2 13 + 1 r 13 -r 13 cos θ 13 + 1 2 r 2 23 + 1 r 23 .
De forma a respeitar a restrição R = r 2 23 -(r 13 cos θ 13 -r 12 cos θ 12 ) 2 + (r 13 sin θ 13 -r 12 sin θ 12 ) 2 = 0 , a função objetivo a ser minimizada passa a ser a função lagrangeana definida por, L(r 12 , r 13 , r 23 , θ 12 , θ 13 , λ) = E(r 12 , r 13 , r 23 , θ 12 , θ 13 ) -λ R(r 12 , r 13 , r 23 , θ 12 , θ 13 ) , onde λ é o multiplicador de Lagrange.

Vetor gradiente:

∇L =                 
r 12 -cos θ 13 + λ(2r 12 -2αr 13 ) - 

                
, com α = cos (θ 13 -θ 12 ) e β = sin (θ 13 -θ 12 ).

Matriz hessiana: 

H =              2λ + 2

Grafo

Resultados da literatura

Fonte: [START_REF] Granjean | Introduction à la visualisation de données: l'analyse de réseau en histoire[END_REF].

Fonte: [START_REF] Belmonte | Force Directed Layouts, JavaScript InfoVis Toolkit project[END_REF].

Considerações finais

• Um algoritmo para calcular configurações de energia mínima em grafos foi estudado e implementado;

• Esse algoritmo é baseado no método de Newton-Raphson, sendo muito eficiente do ponto de vista computacional;

• Por ser um método de busca de extremos que usa apenas informações locais, o algoritmo é fortemente dependente do chute inicial.

  uerj.br NUMERICO -Núcleo de Modelagem e Experimentação Computacional Introdução • Diversas aplicações podem ser modeladas por equações diferenciais; • Por meio do método numérico essas equações podem ser discretizadas para obter sistemas lineares. Exemplo de aplicações: -Simulações de velocidades de fluidos, como as ondas na Baia de São Francisco; -Sistema elétrico RLC; -Sistemas mecânicos; -Dinâmica estrutural.

  c r e t i z a çã o

3 -

 3 sin θ 13 + 2βλr 13 2βλr 12 0 r 12 cos θ 13 + 2αλr 12 r 13 -2αλr 12 r 13 2βr 12 r 13 -2βλr 13 sin θ 12 -2βλr 12 0 -2αλr 12 r 13 r 13 cos θ 12 + 2αλr 12 r 13 -2βr 12 r 13 2αr 12 -2r 13 2αr 13 -2r 12 -2r 23 -2βr 2 r

Agradecimentos Referências