ATRACTOR

Vejamos o porquê da convergência do método iterativo apresentado nos exemplos. Seja:

- \(x=\left(x_{1},x_{2},...,x_{n}\right)\) um vector cujas componentes são o valor exacto do PageRank de cada página, ou seja, tal que \(x_{i}=PR\left(P_{i}\right)\)

- \(H=\left(h_{i,j}\right)_{1\leq i,j\leq n}\) a matriz \(n\times n\) tal que \(h_{ij}\) é \(\frac{1}{C\left(P_{j}\right)}\) se existe um link da página de índice \(j\) para a página de índice \(i\) e \(0\) caso contrário

- \(e=\left(1,1,...,1\right)\)

Então, a fórmula do PageRank pode ser reescrita da seguinte forma \[x=pHx+\left(1-p\right)e\]

uma vez que \(x_{i}=p\sum_{j=1}^{n}h_{ij}x_{j}+\left(1-p\right),\forall i\epsilon\left\{ 1,...,n\right\}\). Notemos ainda que a equação acima é equivalente a \[\left(I-pH\right)x=\left(1-p\right)e\]

onde \(I\) representa a matriz identidade. Pretende-se encontrar uma solução para o sistema \(Ax=b\), onde \(A=I-pH\) e \(b=\left(1-p\right)e\).

O método iterativo mais usual de resolução de sistemas de equações lineares do tipo \(Ax=b\), onde \(A\) representa uma matriz invertível e \(b\) representa um vector, consiste em escrever a matriz \(A\) na forma \(C-M\) para alguma matriz \(C\) invertível. Assim, temos \[\begin{array}{ccl} Ax & = & b\Leftrightarrow\\ & \Leftrightarrow & (C-M)x=b\Leftrightarrow\\ & \Leftrightarrow & Cx=Mx+b\Leftrightarrow\\ & \Leftrightarrow & x=C^{-1}Mx+C^{-1}b\Leftrightarrow\\ & \Leftrightarrow & x=M'x+b' \end{array}\] onde \(M'=C^{-1}M\) e \(b'=C^{-1}b\). Então, se considerarmos uma sucessão de vectores definida iterativamente por \[x^{\left(k+1\right)}=M'x^{\left(k\right)}+b'\] em determinadas condições verifica-se que \(\left\Vert x^{\left(k\right)}-x\right\Vert \rightarrow0\) para uma certa norma vectorial \(\left\Vert .\right\Vert\) em \(\mathbb{\mathbb{\mathbb{R}}}^{n}\), onde \(x\) é a solução do sistema dado. De facto, temos \[\begin{array}{ccl} x^{\left(1\right)}-x & = & \left(M'x^{\left(0\right)}+b'\right)-\left(M'x+b'\right)=M'x^{\left(0\right)}-M'x=\\ & = & M'\left(x^{\left(0\right)}-x\right)\\ x^{\left(2\right)}-x & = & \left(M'x^{\left(1\right)}+b'\right)-\left(M'x+b'\right)=M'x^{\left(1\right)}-M'x=\\ & = & M'\left(x^{\left(1\right)}-x\right)=\left(M'\right)^{2}\left(x^{\left(0\right)}-x\right)\\ x^{\left(3\right)}-x & = & \left(M'x^{\left(2\right)}+b'\right)-\left(M'x+b'\right)=M'x^{\left(2\right)}-M'x=\\ & = & M'\left(x^{\left(2\right)}-x\right)=\left(M'\right)^{3}\left(x^{\left(0\right)}-x\right) \end{array}\]

Em geral, temos \[x^{\left(k\right)}-x=\left(M'\right)^{k}\left(x^{\left(0\right)}-x\right)\]

Logo, vem \[\left\Vert x^{\left(k\right)}-x\right\Vert =\left\Vert \left(M'\right)^{k}\left(x^{\left(0\right)}-x\right)\right\Vert\]

Relativamente às matrizes, podemos também definir uma norma \(\left\Vert .\right\Vert \) dada por \[\left\Vert A\right\Vert =max_{x\leq0}\frac{\left\Vert Ax\right\Vert }{\left\Vert x\right\Vert }\]

(se \(y=0\), a desigualdade é trivial; se \(y\neq0\), vem \[\left\Vert Ay\right\Vert =\frac{\left\Vert Ay\right\Vert }{\left\Vert y\right\Vert }\left\Vert y\right\Vert \leq\left\Vert A\right\Vert \left\Vert y\right\Vert )\]

\((\left\Vert AB\right\Vert =max_{x\neq0}\frac{\left\Vert ABx\right\Vert }{\left\Vert x\right\Vert }\leq max_{x\neq0}\frac{\left\Vert A\right\Vert \left\Vert Bx\right\Vert }{\left\Vert x\right\Vert }=\left\Vert A\right\Vert max_{x\neq0}\frac{\left\Vert Bx\right\Vert }{\left\Vert x\right\Vert }=\left\Vert A\right\Vert \left\Vert B\right\Vert )\)

Em particular, se \(B=A\) temos

Mais geralmente, prova-se por indução que

Assim, temos \[\left\Vert x^{\left(k\right)}-x\right\Vert =\left\Vert \left(M'\right)^{k}\left(x^{\left(0\right)}-x\right)\right\Vert \leq c\left\Vert \left(M'\right)^{k}\right\Vert \leq c\left\Vert M'\right\Vert ^{k}\] onde \(c=\left\Vert x^{\left(0\right)}-x\right\Vert \) é um valor constante. Logo, desde que tenhamos \(\left\Vert M'\right\Vert <1\), vem \(\left\Vert x^{\left(k\right)}-x\right\Vert \leq c\left\Vert M'\right\Vert ^{k}\rightarrow0\), pelo que \(\left\Vert x^{\left(k\right)}-x\right\Vert \rightarrow0\) tal como queríamos mostrar.

Assim, podemos concluir que \(x_{i}^{\left(k\right)}\rightarrow x_{i},\forall i\epsilon\left\{ 1,...,n\right\} \) e, portanto, temos um método iterativo que nos permite encontrar valores aproximados dos valores exactos da solução do sistema dado.

Um caso particular deste método é denominado por método de Jacobi e consiste em tomar a matriz \(C\) como sendo a matriz diagonal cujas entradas são as mesmas da matriz \(A\). Relativamente ao sistema que queremos resolver, desde que não haja nenhum link de uma página para ela própria temos que as entradas da diagonal da matriz \(H\) são todas nulas, pelo que as entradas da diagonal da matriz \(A=I-pH\) são todas iguais a \(1\). Assim, temos \(C=I\) (logo, \(C\) é invertível), \(M'=M=pH\) e \(b'=b=\left(1-p\right)e\), pelo que a sucessão de vectores é dada por \[x^{\left(k+1\right)}=pHx^{\left(k\right)}+\left(1-p\right)e\] ou seja, \(x_{i}^{\left(k+1\right)}=p\sum_{j=1}^{n}h_{ij}x_{j}^{\left(k\right)}+\left(1-p\right),\forall i\epsilon\left\{ 1,...,n\right\} \).

Isto significa que, partindo de um conjunto de valores quaisquer que representam o valor do PageRank atribuído inicialmente a cada página e que são dados pelo vector inicial \(x^{\left(0\right)}=\left(x_{1}^{\left(0\right)},x_{2}^{\left(0\right)},...,x_{n}^{\left(0\right)}\right)\), vamos obtendo novos valores para o PageRank de cada página simplesmente aplicando a fórmula do PageRank ao conjunto de valores obtidos em cada iteração. Para analisar a convergência dos valores obtidos por este processo e compará-los com os valores exactos, pode experimentar esta app.

Notas:

- Para o sistema que pretendemos resolver, é conveniente utilizar a norma de vectores \(\left\Vert .\right\Vert _{1}\) dada por \(\left\Vert y\right\Vert _{1}=\sum_{i=1}^{n}\left|y_{i}\right|\).

Assim, dada uma matriz \(A=\left(a_{ij}\right)_{1\leq i,j\leq n}\), a sua norma é dada por \[\left\Vert A\right\Vert _{1}=max_{x\neq0}\frac{\left\Vert Ax\right\Vert _{1}}{\left\Vert x\right\Vert _{1}}=max_{1\leq j\leq n}\sum_{i=1}^{n}\left|a_{ij}\right|\] (ou seja, é igual ao valor máximo da soma dos módulos das entradas de cada coluna).

Relativamente à matriz \(H\), note-se que a soma dos módulos das entradas da coluna \(j\) é \(1\) se a página de índice \(j\) possui algum link e \(0\) caso contrário. Logo, vem \[\left\Vert M'\right\Vert _{1}=\left\Vert pH\right\Vert _{1}=p\left\Vert H\right\Vert _{1}\leq p<1\]

Além disso, dado que \(\left\Vert x^{\left(k\right)}-x\right\Vert _{1}\leq c\left\Vert M'\right\Vert _{1}^{k}\leq c.p^{k}\), podemos concluir que quanto menor for o valor de \(p\) mais rápida será a convergência.

- Outro caso particular deste método é denominado por método de Gauss-Seidel e consiste em tomar a matriz \(C\) como a matriz cujas entradas coincidem com as da matriz \(A\) na diagonal e abaixo da diagonal, sendo nulas acima da diagonal. Relativamente ao sistema que queremos resolver, desde que não haja nenhum link de uma página para ela própria temos \(H=L+U\) onde \(L\) é uma matriz cujas entradas coincidem com as da matriz \(H\) abaixo da diagonal, sendo nulas na diagonal e acima da diagonal, e \(U\) é uma matriz cujas entradas coincidem com as da matriz \(H\) acima da diagonal, sendo nulas na diagonal e abaixo da diagonal. Assim, temos \(C=I-pL\) e \(M=pU\), pelo que, partindo da equação \(Cx=Mx+b\) temos \[\begin{array}{rcl} \left(I-pL\right)x^{\left(k+1\right)} & = & pUx^{\left(k\right)}+b\\ x^{\left(k+1\right)} & = & pLx^{\left(k+1\right)}+pUx^{\left(k\right)}+b \end{array}\] ou seja, \[x_{i}^{\left(k+1\right)}=p\sum_{j=1}^{i-1}h_{ij}x_{j}^{\left(k+1\right)}+p\sum_{j=1+1}^{n}h_{ij}x_{j}^{\left(k\right)}+\left(1-p\right),\forall i\epsilon\left\{ 1,...,n\right\} \]

Em termos práticos, este método difere do anterior na medida em que os novos valores de PageRank calculados em cada iteração são usados ainda nessa iteração para calcular o PageRank das restantes páginas em vez de serem utilizados apenas na iteração seguinte.