Aula 16 · 24/11 (ter) · Módulo 4 · laboratório

Autovalores, autovetores, diagonalização I

Nesta aula você estuda autovalores e autovetores de uma matriz quadrada A: um escalar λ é autovalor de A se existe um vetor x ≠ 0 tal que Ax = λx, e esse x é um autovetor associado a λ. Na bancada, você procura no plano as direções em que Ax é múltiplo de x, obtém os autovalores como raízes do polinômio característico det(A − λI) e confere que a soma e o produto deles são o traço e o determinante de A. Em dimensão n, você usa o método das potências para aproximar um autovetor associado ao autovalor de maior módulo e, com ele, calcular as notas das páginas de uma rede.

Strang, seção 5.1
Autovalores e autovetores · MIT 18.06, aula 21
Autovetores e autovalores · 3Blue1Brown, cap. 14
Exercícios desta aula no Desmos

Nesta página

Bancada
Os quadros da aula e, ao lado deles, os controles; em telas estreitas, os controles ficam abaixo dos quadros. Numa tela larga, a coluna dos controles fica parada ao lado dos quadros e tem rolagem própria. No alto dessa coluna, o roteiro propõe 8 missões, uma de cada vez. Em cada missão, os nomes em vermelho levam ao quadro, ao painel ou ao controle que ela usa, que fica destacado na bancada.
Em dimensão n
O autovalor dominante e o método das potências. Experimentos e 4 desafios guiados.
Conceitos da aula
6 guias, cada uma com a definição, um exemplo resolvido e o lugar da bancada em que o conceito aparece, e 3 perguntas com resposta em Para pensar.

Os vetores x e Ax

A matriz A é a do painel Matriz A. Em preto, o vetor x, cuja ponta pode ser arrastada; em vermelho, o vetor Ax. A curva vermelha é a imagem por A do círculo cinza em que está a ponta de x, e o arco laranja marca o ângulo entre x e Ax. Quando Ax pertence à reta que passa pela origem e por x, essa reta fica verde: x é um autovetor de A.

A imagem por A − λI

Aqui, λ é o escalar de teste, marcado em azul no quadro Polinômio característico. Em preto, o mesmo vetor x do quadro Os vetores x e Ax; em azul, o vetor (A − λI)x. A curva azul é a imagem do círculo cinza por A − λI. Quando λ é autovalor de A, a matriz A − λI é singular, e a curva se reduz a um segmento: o espaço nulo N(A − λI), uma reta, aparece tracejado em vermelho. A exceção é A = λI: aí A − λI é a matriz nula, e a curva se reduz à origem.

Polinômio característico

O polinômio característico da matriz A do painel Matriz A é p(λ) = det(A − λI), e o quadro mostra o seu gráfico. As raízes reais de p, em vermelho, são os autovalores reais de A; quando são duas, a maior se chama λ₁ e a menor, λ₂. O traço de A, a soma das entradas da diagonal, se escreve tr A. A reta vertical tracejada passa por λ = tr A/2, e o ponto roxo é p(0) = det A. Arraste o ponto azul, o escalar λ de teste, ao longo do eixo horizontal.

Autovalores e autovetores de A

Exemplos de matrizes

Matriz A

As entradas podem ser inteiros, frações como 1/2 ou decimais como 0,8. Você também pode arrastar a primeira e a segunda colunas de A, que se escrevem a₁ e a₂, no quadro Os vetores x e Ax: ligue a opção Colunas a₁ e a₂ arrastáveis, no painel O que mostrar.

O vetor x e o escalar λ

O que mostrar

Pelo teclado: clique numa figura e use as setas (com Shift, o passo é maior); a barra de espaço alterna o ponto que se move.

Em dimensão n

O autovalor dominante e o método das potências

Seja A uma matriz n × n. O seu polinômio característico, det(A − λI), tem grau n, e as suas n raízes, contadas com repetição e incluindo as complexas, são os autovalores de A. Numerados em ordem decrescente de módulo, eles se escrevem λ₁, …, λ_n. A soma deles é o traço tr A, a soma das entradas da diagonal de A, e o produto é det A. Para n ≥ 5, não existe fórmula geral com radicais para as raízes de um polinômio de grau n, e os programas calculam os autovalores por métodos iterativos. O mais simples é o método das potências: ele começa com um vetor x₀ de norma 1 e repete o passo x_k+1 = Ax_k/‖Ax_k‖. Quando |λ₁| > |λ₂|, o autovalor λ₁ se chama dominante. Nesse caso, a direção de x_k se aproxima da direção dos autovetores associados a λ₁, desde que x₀ não pertença a um certo subespaço de dimensão n − 1. A guia Método das potências, nos Conceitos da aula, mostra por quê e com que rapidez. É assim que se calcula o PageRank, a nota criada pelos fundadores do Google para ordenar as páginas da web.

Autovalores no plano complexo

Cada autovalor λ da matriz A do painel A matriz A aparece como o ponto (Re λ, Im λ), formado pela parte real e pela parte imaginária de λ. Os autovalores estão numerados em ordem decrescente de módulo: |λ₁| ≥ |λ₂| ≥ ⋯ ≥ |λ_n|. Em vermelho, λ₁ e o círculo de raio |λ₁|; em azul, λ₂ e o círculo tracejado de raio |λ₂|; em preto, os outros autovalores; em cinza, o círculo tracejado de raio 1.

Convergência

Sejam λ₁ e λ₂ os autovalores de maior e de segundo maior módulo, e v₁ um autovetor de norma 1 associado a λ₁. O vetor x_k do passo k do método das potências pode se aproximar de v₁ ou de −v₁. Por isso, a página troca x_k por −x_k quando x_k^Tv₁ < 0, e o erro no passo k é ‖x_k − v₁‖. A curva preta mostra esse erro, em escala logarítmica. A reta azul tracejada é o erro inicial vezes |λ₂/λ₁|^k, a reta verde marca 10⁻⁶, e o ponto vermelho marca o passo atual. Quando |λ₁| = |λ₂|, não há autovalor dominante, e a curva preta mostra a variação de um passo para o outro: ‖x_k − x_k−1‖, depois de trocar x_k por −x_k quando x_k^Tx_k−1 < 0.

As entradas de x_k

A matriz A

Método das potências

O método começa com um vetor x₀ de norma 1. Cada passo multiplica o vetor atual pela matriz A e divide o resultado pela sua norma: x_k+1 = Ax_k/‖Ax_k‖. A página calcula os vetores de x₀ a x₆₀. O vetor x₀ é sorteado, exceto na rede, em que todas as entradas de x₀ são iguais. Avance um passo de cada vez, ou use o botão de tocar: quando há autovalor dominante, as barras se aproximam do contorno vermelho.

Conceitos da aula

Autovalores e autovetores

Uma guia por conceito, cada um com a definição, um exemplo resolvido e o lugar da bancada em que ele aparece. A notação é a do livro-texto (seção 5.1).

Em geral, multiplicar um vetor por uma matriz muda a sua direção. Os autovetores de uma matriz quadrada A são os vetores não nulos x para os quais Ax é um múltiplo de x.

Autovalor e autovetor

Definição

Seja A uma matriz n × n de entradas reais. Um escalar λ, real ou complexo, é um autovalor de A se existe um vetor x ≠ 0, de n entradas reais ou complexas, tal que

Ax = \lambda x.

Todo vetor x ≠ 0 que satisfaz essa igualdade é um autovetor de A associado a λ. Quando λ é real, existem autovetores associados a ele em ℝⁿ. Quando λ não é real, nenhum autovetor associado a ele tem todas as entradas reais.

Para λ real e x ∈ ℝⁿ, a igualdade Ax = λx diz que Ax pertence à reta que passa pela origem e por x: Ax tem o mesmo sentido de x se λ > 0, o sentido oposto se λ < 0, e é o vetor nulo se λ = 0. A exigência x ≠ 0 é essencial, porque A0 = λ0 para todo escalar λ.

Os múltiplos não nulos de um autovetor também são autovetores: se Ax = λx e μ ≠ 0 é um escalar, então A(μx) = μ(Ax) = λ(μx), e μx também é autovetor associado a λ. Por isso falamos em direções de autovetores.

Exemplo

Para A = 2112,

\begin{aligned}A(1, 1)^{\mathrm{T}} &= (3, 3)^{\mathrm{T}} = 3(1, 1)^{\mathrm{T}}, \\ A(1, -1)^{\mathrm{T}} &= (1, -1)^{\mathrm{T}}, \\ A(1, 0)^{\mathrm{T}} &= (2, 1)^{\mathrm{T}}.\end{aligned}

Logo (1, 1)^T é autovetor associado a λ = 3, (1, −1)^T é autovetor associado a λ = 1, e (1, 0)^T não é autovetor, pois (2, 1)^T não é múltiplo de (1, 0)^T.

Na bancada: no painel Exemplos de matrizes, escolha Covariância de dois sensores. No quadro Os vetores x e Ax, arraste a ponta de x ou use o controle Direção de x: quando Ax pertence à reta que passa pela origem e por x, essa reta fica verde, e a leitura abaixo do quadro mostra λ.

Autovetores de transformações do plano

Em três transformações lineares do plano estudadas na Aula 10, os autovetores da matriz canônica podem ser encontrados pela geometria, sem contas:

na projeção ortogonal sobre uma reta que passa pela origem, os vetores não nulos da reta são autovetores associados a λ = 1, e os vetores não nulos perpendiculares à reta, associados a λ = 0;
na reflexão em relação a uma reta que passa pela origem, os vetores não nulos da reta são autovetores associados a λ = 1, e os perpendiculares, associados a λ = −1;
na rotação de 90° no sentido anti-horário, nenhum vetor real não nulo é autovetor, porque cada vetor x ≠ 0 é levado num vetor perpendicular a x.

Exemplo

A projeção ortogonal sobre a reta gerada por (1, 1)^T tem matriz canônica A = 1/21/21/21/2. Então

\begin{aligned}A(1, 1)^{\mathrm{T}} &= (1, 1)^{\mathrm{T}}, \\ A(1, -1)^{\mathrm{T}} &= (0, 0)^{\mathrm{T}} = 0(1, -1)^{\mathrm{T}},\end{aligned}

e os autovalores de A são λ = 1 e λ = 0.

Na bancada: os exemplos Média de dois canais (projeção), Troca de dois registros (reflexão) e Rotação de 90° de uma imagem (rotação) mostram esses três casos no quadro Os vetores x e Ax. Ligue a opção Direções dos autovetores, tracejadas, no painel O que mostrar, para ver as retas tracejadas.

Para encontrar os autovalores de uma matriz quadrada A, eliminamos o vetor x da equação Ax = λx, da guia Autovalor e autovetor: o escalar λ é autovalor exatamente quando a matriz A − λI é singular.

A equação dos autovalores

Teorema

Seja A uma matriz n × n. Um escalar λ é autovalor de A se, e somente se,

\det (A - \lambda I) = 0.

Por quê. A igualdade Ax = λx equivale a Ax − λIx = 0, isto é, a (A − λI)x = 0. Existe x ≠ 0 com essa propriedade se, e somente se, o espaço nulo N(A − λI) não se reduz a {0}, ou seja, se, e somente se, A − λI é singular. Pela Aula 14, isso equivale a det(A − λI) = 0.

Definição

O polinômio característico de A é p(λ) = det(A − λI). Ele é um polinômio de grau n em λ, e as suas raízes são os autovalores de A.

Numa matriz 2 × 2 de entradas a, b na primeira linha e c, d na segunda, o traço é a soma das entradas da diagonal, tr A = a + d, e

\begin{aligned}p(\lambda ) &= (a - \lambda )(d - \lambda ) - bc \\ &= \lambda ^{2} - (\operatorname{tr} A)\lambda + \det A.\end{aligned}

Assim se calculam os autovalores e os autovetores de A:

encontre as raízes λ₁, …, λ_n de p, que são os autovalores;
para cada raiz λ_i, encontre por eliminação as soluções não nulas de (A − λ_iI)x = 0, que são os autovetores associados a λ_i.

Um exemplo e a transposta

Exemplo

A seção 5.1 do livro-texto usa a matriz A = 4−52−3. Então

\begin{aligned}p(\lambda ) &= (4 - \lambda )(-3 - \lambda ) + 10 \\ &= \lambda ^{2} - \lambda - 2 \\ &= (\lambda - 2)(\lambda + 1),\end{aligned}

e os autovalores são λ₁ = 2 e λ₂ = −1. Os autovetores são calculados na guia Autoespaço.

A transposta. Como det B^T = det B para toda matriz quadrada B, temos det(A^T − λI) = det((A − λI)^T) = det(A − λI). Logo A e A^T têm o mesmo polinômio característico e os mesmos autovalores, embora, em geral, não tenham os mesmos autovetores.

Na bancada: escolha Exemplo do livro no painel Exemplos de matrizes. No quadro Polinômio característico, arraste o ponto azul, o escalar λ de teste, até uma raiz: o quadro A imagem por A − λI mostra a curva azul reduzida a um segmento e o espaço nulo N(A − λI), uma reta, tracejado em vermelho. O quadro Autovalores e autovetores de A mostra p(λ) fatorado.

Os autovetores associados a um mesmo autovalor λ de uma matriz quadrada A, junto com o vetor nulo, formam um subespaço: o espaço nulo de A − λI.

Autoespaço

Definição

Seja λ um autovalor real da matriz A, de entradas reais e de tamanho n × n. O autoespaço de A associado a λ é o conjunto

N(A - \lambda I) = \{x \in \mathbb{R}^{n} : Ax = \lambda x\},

formado pelos autovetores associados a λ e pelo vetor nulo.

Como todo espaço nulo, o autoespaço é um subespaço de ℝⁿ: se x e y pertencem a ele, isto é, Ax = λx e Ay = λy, então A(x + y) = λ(x + y) e A(μx) = λ(μx) para todo escalar μ. A sua dimensão é o número máximo de autovetores linearmente independentes associados a λ.

Exemplo

Para A = 4−52−3, de autovalores 2 e −1,

A - 2I = \begin{bmatrix}2 & -5 \\ 2 & -5\end{bmatrix}.

Para x = (x₁, x₂)^T, as duas linhas dão a mesma equação, 2x₁ − 5x₂ = 0, cujas soluções são os vetores x = (x₂/2)(5, 2)^T, com x₂ ∈ ℝ. Logo

N(A - 2I) = \{\mu (5, 2)^{\mathrm{T}} : \mu \in \mathbb{R}\}.

Da mesma forma, as linhas de A + I são (5, −5) e (2, −2), e as duas equações dão x₁ = x₂:

N(A + I) = \{\mu (1, 1)^{\mathrm{T}} : \mu \in \mathbb{R}\}.

Conferindo: A(5, 2)^T = (10, 4)^T = 2(5, 2)^T e A(1, 1)^T = (−1, −1)^T = −(1, 1)^T.

Raiz dupla

Quando λ é raiz dupla do polinômio característico de uma matriz 2 × 2, o autoespaço pode ser uma reta ou o plano inteiro:

no cisalhamento A = 1101, p(λ) = (λ − 1)², e, para x = (x₁, x₂)^T, o vetor (A − I)x = (x₂, 0)^T é o vetor nulo só quando x₂ = 0: o autoespaço é o eixo horizontal, uma reta;
na matriz 2I, p(λ) = (λ − 2)² e 2I − 2I é a matriz nula: o autoespaço é o plano inteiro, e todo vetor não nulo é autovetor.

No cisalhamento, a raiz é dupla, mas não existem dois autovetores linearmente independentes. Essa diferença é importante na diagonalização, estudada na Aula 17.

Exemplo

No cisalhamento,

\begin{aligned}A(1, 0)^{\mathrm{T}} &= (1, 0)^{\mathrm{T}}, \\ A(0, 1)^{\mathrm{T}} &= (1, 1)^{\mathrm{T}}.\end{aligned}

O vetor (1, 0)^T é autovetor associado a λ = 1; o vetor (0, 1)^T não é, pois (1, 1)^T não é múltiplo dele.

Na bancada: no painel Exemplos de matrizes, escolha Letra em itálico e gire o vetor x no quadro Os vetores x e Ax: só a direção horizontal fica verde. Depois escolha Ampliar uma imagem 2×: todas as direções ficam verdes. O quadro Autovalores e autovetores de A descreve o autoespaço nos dois casos.

A soma e o produto dos autovalores podem ser lidos nas entradas de A, sem calcular as raízes do polinômio característico.

Soma e produto dos autovalores

Definição

Seja A uma matriz n × n, cuja entrada da linha i e da coluna j se escreve a_ij. O traço de A é a soma das entradas da diagonal:

\operatorname{tr} A = a_{11} + a_{22} + \cdots + a_{nn}.

Teorema

Sejam λ₁, …, λ_n as n raízes do polinômio característico p(λ) = det(A − λI), contadas com repetição e incluindo as complexas. Então

\begin{aligned}\lambda _{1} + \cdots + \lambda _{n} &= \operatorname{tr} A, \\ \lambda _{1}\lambda _{2}\cdots \lambda _{n} &= \det A.\end{aligned}

Por quê. O coeficiente de λⁿ em p é (−1)ⁿ, e por isso as raízes dão a fatoração p(λ) = (λ₁ − λ)⋯(λ_n − λ). Com λ = 0, obtemos det A = p(0) = λ₁⋯λ_n. Para a soma, compare os coeficientes de λⁿ⁻¹. Na fatoração, ele é (−1)ⁿ⁻¹(λ₁ + ⋯ + λ_n). Na fórmula do determinante com n! parcelas (Aula 15), só o produto da diagonal, (a₁₁ − λ)⋯(a_nn − λ), contém λⁿ⁻¹, pois cada uma das outras parcelas usa no máximo n − 2 entradas da diagonal. Nesse produto, o coeficiente de λⁿ⁻¹ é (−1)ⁿ⁻¹(a₁₁ + ⋯ + a_nn). Igualando os dois coeficientes, obtemos λ₁ + ⋯ + λ_n = tr A.

Três consequências:

A é singular se, e somente se, 0 é autovalor de A, pois det A = λ₁⋯λ_n é zero exatamente quando um dos fatores é zero;
numa matriz triangular, os autovalores são as entradas da diagonal, pois A − λI também é triangular e p(λ) = (a₁₁ − λ)⋯(a_nn − λ);
numa matriz 2 × 2 de entradas reais com det A < 0, os autovalores são reais e têm sinais opostos, pois dois autovalores conjugados que não são reais têm produto positivo, como mostra a guia Autovalores complexos.

Um exemplo

Exemplo

Para A = 0,80,30,20,7,

\begin{aligned}\operatorname{tr} A &= 0{,}8 + 0{,}7 = 1{,}5, \\ \det A &= 0{,}56 - 0{,}06 = 0{,}5, \\ p(\lambda ) &= \lambda ^{2} - 1{,}5\lambda + 0{,}5 \\ &= (\lambda - 1)(\lambda - 0{,}5).\end{aligned}

Os autovalores são 1 e 0,5, e de fato 1 + 0,5 = 1,5 = tr A e 1 · 0,5 = 0,5 = det A.

Na bancada: abaixo do quadro Polinômio característico, os blocos Traço, Determinante e Discriminante mostram esses números para a matriz escolhida. No gráfico, a reta vertical tracejada passa por λ = tr A/2, a média das duas raízes, e o ponto roxo é p(0) = det A. A conferência da soma e do produto aparece no quadro Autovalores e autovetores de A.

Uma matriz de entradas reais pode ter autovalores que não são números reais: são as raízes não reais do seu polinômio característico. Elas aparecem aos pares, cada uma com a sua conjugada.

Pares conjugados

Definição

Seja i a unidade imaginária, com i² = −1. O conjugado de um número complexo é o número com a mesma parte real e a parte imaginária oposta: o conjugado de 1 + 2i é 1 − 2i, e o de −3i é 3i. O conjugado de um vetor é o vetor obtido trocando cada entrada pela sua conjugada. O módulo de um número complexo é a raiz quadrada da soma dos quadrados da parte real e da parte imaginária: o módulo de 1 + 2i é √(1² + 2²) = √5.

Teorema

Seja A uma matriz n × n de entradas reais, e seja λ um autovalor de A que não é real, com autovetor x. Então o conjugado de λ também é autovalor de A, e o conjugado de x é um autovetor associado a ele.

Por quê. Troque cada número dos dois lados de Ax = λx pelo seu conjugado. O conjugado de uma soma é a soma dos conjugados, e o de um produto é o produto dos conjugados. As entradas de A são reais e não mudam. O resultado diz que A vezes o conjugado de x é igual ao conjugado de λ vezes o conjugado de x. O conjugado de x não é o vetor nulo, porque x não é.

Um número complexo e o seu conjugado têm o mesmo módulo; logo, os dois autovalores de um par conjugado têm o mesmo módulo. Numa matriz 2 × 2, o polinômio característico é p(λ) = λ² − (tr A)λ + det A, com o traço tr A da guia Polinômio característico. Os autovalores não são reais exatamente quando o discriminante, (tr A)² − 4 det A, é negativo. Quando n é ímpar, pelo menos um autovalor é real, porque os que não são reais vêm aos pares e o total, contado com repetição, é n.

Exemplo

A rotação de 90° no sentido anti-horário tem matriz A = 0−110, e

p(\lambda ) = \lambda ^{2} + 1 = (\lambda - i)(\lambda + i).

Os autovalores são i e −i, com autovetores conjugados:

\begin{aligned}A(1, -i)^{\mathrm{T}} &= (i, 1)^{\mathrm{T}} = i(1, -i)^{\mathrm{T}}, \\ A(1, i)^{\mathrm{T}} &= (-i, 1)^{\mathrm{T}} = -i(1, i)^{\mathrm{T}}.\end{aligned}

A soma dos autovalores ainda é o traço, e o produto ainda é o determinante: i + (−i) = 0 = tr A e i(−i) = 1 = det A.

Na bancada: escolha Rotação de 90° de uma imagem no painel Exemplos de matrizes. No quadro Os vetores x e Ax, o ângulo entre x e Ax é sempre 90°, e o gráfico do quadro Polinômio característico fica acima do eixo horizontal. Na parte Em dimensão n, a família Aleatória mostra, no quadro Autovalores no plano complexo, os pares conjugados como pontos simétricos em relação ao eixo horizontal.

Para matrizes grandes, os autovalores não são calculados pelas raízes do polinômio característico. Quando um autovalor tem módulo maior que o de todos os outros, o método das potências aproxima esse autovalor e um autovetor associado a ele usando apenas produtos da matriz por vetores.

O método das potências

Definição

Seja A uma matriz n × n de entradas reais, com autovalores λ₁, …, λ_n, contados com repetição e numerados em ordem decrescente de módulo:

|\lambda _{1}| \geq |\lambda _{2}| \geq \cdots \geq |\lambda _{n}|.

O autovalor λ₁ é dominante quando |λ₁| > |λ₂|.

Um autovalor dominante é real: se não fosse, o seu conjugado seria outro autovalor com o mesmo módulo, como mostra a guia Autovalores complexos. O método das potências tem três passos:

escolha um vetor x₀ de norma 1;
para k = 0, 1, 2, …, calcule Ax_k e divida pela sua norma: x_k+1 = Ax_k/‖Ax_k‖;
pare depois de um número fixo de passos, ou quando x_k+1 ficar perto o bastante de x_k ou de −x_k. A bancada calcula 60 passos.

A divisão pela norma mantém ‖x_k‖ = 1 e evita números enormes ou minúsculos, sem mudar a direção: x_k é o vetor de norma 1 com a direção de A^kx₀. Sob as hipóteses do teorema a seguir, x_k aproxima um autovetor associado a λ₁, e o número x_k^TAx_k aproxima λ₁.

Teorema

Suponha que A tenha n autovetores linearmente independentes v₁, …, v_n, associados a λ₁, …, λ_n, e que λ₁ seja dominante. Esses autovetores formam uma base, e o vetor inicial se escreve x₀ = α₁v₁ + ⋯ + α_nv_n, com coeficientes α₁, …, α_n. Se α₁ ≠ 0, a direção de x_k se aproxima da direção de v₁ quando k cresce: a distância entre x_k e o mais próximo dos vetores v₁/‖v₁‖ e −v₁/‖v₁‖ é, no máximo, uma constante vezes |λ₂/λ₁|^k.

Por quê. Como Av_i = λ_iv_i, temos A^kv_i = λ_i^kv_i e, pela linearidade,

A^{k}x_{0} = \alpha _{1}\lambda _{1}^{k}v_{1} + \cdots + \alpha _{n}\lambda _{n}^{k}v_{n}.

Como |λ₁| > |λ₂| ≥ 0, o autovalor λ₁ não é zero. A soma das parcelas de v₂, …, v_n, dividida por λ₁^k, se escreve w_k = α₂(λ₂/λ₁)^kv₂ + ⋯ + α_n(λ_n/λ₁)^kv_n. Então

A^{k}x_{0} = \lambda _{1}^{k}(\alpha _{1}v_{1} + w_{k}).

Como |λ_i/λ₁| ≤ |λ₂/λ₁| < 1 para i ≥ 2, o comprimento de w_k é, no máximo, (|α₂|‖v₂‖ + ⋯ + |α_n|‖v_n‖)|λ₂/λ₁|^k, que tende a zero. Sobra a direção de α₁v₁, que é a de v₁, pois α₁ ≠ 0. Com α₁ = 0, a parcela de v₁ é nula em todos os vetores A^kx₀, e a direção de x_k não se aproxima da de v₁.

O número x_k^TAx_k se aproxima de λ₁ porque x_k se aproxima de ±v₁/‖v₁‖ e v₁^TAv₁ = λ₁v₁^Tv₁ = λ₁‖v₁‖². A hipótese de n autovetores linearmente independentes simplifica a conta. Com mais trabalho, prova-se que a direção de x_k também se aproxima da de v₁ sem essa hipótese, sempre que λ₁ é dominante e x₀ não pertence a um certo subespaço de dimensão n − 1.

Exemplo

Para A = 2112, com λ₁ = 3, v₁ = (1, 1)^T, λ₂ = 1 e v₂ = (1, −1)^T, tome x₀ = (1, 0)^T = (v₁ + v₂)/2. Então

\begin{aligned}A^{k}x_{0} &= (3^{k}v_{1} + v_{2})/2 \\ &= (3^{k} + 1, 3^{k} - 1)^{\mathrm{T}}/2.\end{aligned}

Para k = 1, 2, 3, os vetores são (2, 1)^T, (5, 4)^T e (14, 13)^T. O quociente entre a segunda e a primeira entrada, (3^k − 1)/(3^k + 1), tende a 1, e a diferença para 1 é 2/(3^k + 1), menor que 2(1/3)^k = 2|λ₂/λ₁|^k. Já com x₀ na direção de v₂, temos α₁ = 0 e A^kx₀ = x₀ para todo k: a direção nunca muda.

Na bancada: na parte Em dimensão n, escolha uma família no painel A matriz A e avance os passos no painel Método das potências. O quadro As entradas de x_k mostra x_k em barras e v₁ em contorno vermelho. O quadro Convergência mostra o erro em escala logarítmica, ao lado da reta azul tracejada, que é o erro inicial vezes |λ₂/λ₁|^k.

As notas de uma rede de páginas

Numa rede de n páginas, numeradas de 1 a n, o número de links que saem da página j se escreve s_j. A matriz de links P tem, na linha i e na coluna j, a entrada 1/s_j se a página j tem um link para a página i, e 0 caso contrário. Se a página j não tem links, todas as entradas da coluna j de P valem 1/n. Escolha um escalar β, com 0 < β < 1, chamado fator de amortecimento, e seja U a matriz n × n com todas as entradas iguais a 1. A matriz da rede é

A = \beta P + ((1 - \beta )/n)U,

A entrada da linha i e da coluna j de A é a fração da nota da página j que vai para a página i. A página j reparte a fração β da sua nota igualmente entre as páginas para onde ela tem link, ou entre todas as n páginas, se não tiver links, e reparte o restante, 1 − β, igualmente entre as n páginas. As entradas de A são positivas, e cada coluna de A soma 1.

Teorema

Seja A uma matriz n × n em que a soma das entradas de cada coluna é 1. Então λ = 1 é autovalor de A.

Por quê. A entrada j de A^T(1, …, 1)^T é a soma da coluna j de A, que é 1. Logo A^T(1, …, 1)^T = (1, …, 1)^T, e 1 é autovalor de A^T, que tem os mesmos autovalores de A (guia Polinômio característico).

Na matriz da rede, pode-se provar ainda que λ = 1 é raiz simples do polinômio característico, que os outros autovalores têm módulo no máximo β e que existe um autovetor associado a λ = 1 com todas as entradas positivas. Assim, λ₁ = 1 é o autovalor dominante. O vetor de notas das páginas é o autovetor x de A associado a λ = 1 cujas entradas somam 1. A entrada i da igualdade x = Ax diz que a nota da página i é a soma das partes de nota que ela recebe das páginas j = 1, …, n. Esse vetor é o PageRank, criado pelos fundadores do Google para ordenar as páginas da web, e ele é calculado pelo método das potências. Quando todas as páginas têm links, mas poucos, quase todas as entradas de P são nulas. Então o produto Ax_k = βPx_k + ((1 − β)/n)Ux_k pode ser calculado com muito menos que n² multiplicações, pois todas as entradas de Ux_k são iguais à soma das entradas de x_k.

Na bancada: na parte Em dimensão n, escolha a família Rede de páginas. O quadro A rede de páginas mostra as notas no passo k, e o quadro Autovalores no plano complexo mostra λ₁ = 1 e os outros autovalores dentro do círculo verde, de raio β, ou sobre ele.

Para pensar

Se x é um autovetor de A associado ao autovalor λ, ele também é autovetor de A² e de A⁻¹? Com que autovalores?

Sim. Como Ax = λx com x ≠ 0, temos A²x = A(λx) = λAx = λ²x: o vetor x é autovetor de A², associado a λ². Se A é invertível, então λ ≠ 0, porque 0 não é autovalor de uma matriz invertível. Multiplicando Ax = λx por A⁻¹, obtemos x = λA⁻¹x, isto é, A⁻¹x = (1/λ)x: o vetor x é autovetor de A⁻¹, associado a 1/λ. A recíproca vale para A⁻¹, cujos autovetores são exatamente os de A, mas não vale para A². Por exemplo, a reflexão A = 0110 tem A² = I: todo vetor não nulo é autovetor de A², mas (1, 0)^T não é autovetor de A. A Aula 17 usa essas ideias para calcular as potências A^k.

Os autovalores de A + B são as somas dos autovalores de A e de B?

Em geral, não. As matrizes A = 0100 e B = 0010 são triangulares com diagonal nula, então cada uma só tem o autovalor 0; mas A + B = 0110 tem autovalores 1 e −1. O que sempre vale é uma igualdade entre somas: a soma de todos os autovalores de A + B é a soma de todos os de A mais a soma de todos os de B, pois a soma dos autovalores é o traço e tr(A + B) = tr A + tr B. Quando B = μI, para um escalar μ, a resposta é sim: para x ≠ 0, a igualdade (A + μI)x = (λ + μ)x equivale a Ax = λx. Assim, os autovalores de A + μI são os de A somados a μ, com os mesmos autovetores.

Por que, numa matriz simétrica, autovetores associados a autovalores diferentes são perpendiculares?

Seja A uma matriz simétrica de entradas reais, isto é, A^T = A, e sejam v₁, v₂ ∈ ℝⁿ autovetores associados a autovalores reais diferentes: Av₁ = λ₁v₁ e Av₂ = λ₂v₂, com λ₁ ≠ λ₂. Então λ₁v₁^Tv₂ = (Av₁)^Tv₂ = v₁^TA^Tv₂ = v₁^TAv₂ = λ₂v₁^Tv₂. Logo (λ₁ − λ₂)v₁^Tv₂ = 0 e, como λ₁ ≠ λ₂, v₁^Tv₂ = 0. Numa matriz simétrica 2 × 2, os autovalores são sempre reais: com a₁₁ = a, a₁₂ = a₂₁ = b e a₂₂ = d, o discriminante do polinômio característico, (tr A)² − 4 det A, é (a + d)² − 4(ad − b²) = (a − d)² + 4b² ≥ 0. No exemplo Covariância de dois sensores, os autovetores (1, 1)^T e (1, −1)^T são perpendiculares.

Autovalores, autovetores, diagonalização I

Os vetores x e Ax

A imagem por A − λI

Polinômio característico

Autovalores e autovetores de A

Exemplos de matrizes

Matriz A

O vetor x e o escalar λ

O que mostrar

O autovalor dominante e o método das potências

A rede de páginas

Autovalores no plano complexo

Convergência

As entradas de xk

A matriz A

Método das potências

Links

Autovalores e autovetores

Autovalor e autovetor

Autovetores de transformações do plano

A equação dos autovalores

Um exemplo e a transposta

Autoespaço

Raiz dupla

Soma e produto dos autovalores

Um exemplo

Pares conjugados

O método das potências

As notas de uma rede de páginas

Para pensar

As entradas de x_k