Álgebra Linear Computacional - ALC - 1 Flashcards

1
Q

Quando tentamos fazer uma operação que exige uma precisão matemática grande (como por exemplo, calcular o limite de (1 - seno(x))/x³ quando x tende a 0), os resultados inicialmente convergem para o limite desejado mas posteriormente divergem. Por que isso ocorre?

A
  1. Nem todos os números reais são representáveis em um computador digital.
  2. As operações aritméticas envolvendo representações ou aproximações de
    números reais estão sujeitas a erros numéricos.
  3. e, finalmente, a combinação dos fatores acima faz com que diferenças muito pequenas entre grandezas não sejam corretamente representáveis (isso não significa que não consigamos representar números muito pequenos).
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Quais são as duas grandes fontes de erro em operações de ponto flutuante?

A

1 - Subtração de quantidades de magnitude muito próxima.
2 - Soma de quantidades de magnitudes muito díspares.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

O que é o produto escalar entre dois vetores [a1, a2, … an] e [b1, b2, … bn]? Quais são suas principais notações?

A

É a soma de 1 até n de ai*bi. Ela pode ser denotada por ⟨a, b⟩ ou por aTb.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

O que é o produto interno de um vetor? Como ele é chamado?

A

O produto interno de um vetor é o produto escalar de um vetor por si próprio. Ele é popularmente conhecido como o quadrado da Norma Euclideana.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Como o conceito de produto escalar se relaciona com o conceito de ortogonalidade entre vetores ?

A

Podemos afirmar que dois vetores são ortogonais (ou seja, possuem ângulo de 90 graus entre si) se e somente se o produto escalar entre eles for 0.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Quais são as duas condições necessárias para que um conjunto de vetores V contido em Rn precisa possuir para ser considerado um espaço vetorial?

A

Mais precisamente, V é um espaço vetorial se e somente se as duas propriedades de fechamento seguintes forem satisfeitas:

1 - Dados quaisquer número real a e vetor v pertencente a V, o produto escalar a*v também pertence a V. Nesse caso, dizemos que V é fechado na multiplicação por escalar.

2 - Dados quaisquer vetores u e v pertencentes a V, a soma vetorial u + v também pertence a V. Nesse caso, dizemos que V é fechado na soma de seus elementos.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Dê dois exemplos de formas de mostrar que um conjunto de vetores definido a partir da teoria dos conjuntos ( por exemplo : {(x, y) : x² + y² = 0, x, y ∈ R} ) ou a partir do span de um vetor (por exemplo: span{[1, 2, 3]^T}) não é um espaço vetorial?

A

1 - Mostre que o vetor {0} não pertence ao conjunto.

2 - Mostre que o conjunto não é fechado para a adição: encontre dois vetores u e v que se encaixam na definição e então mostre que u + v não pertence ao conjunto.

3 - Mostre que o conjunto não é fechado para multiplicação: encontre um escalar a e vetor u que se encaixa na definição. Então mostre que a * u não pertence ao conjunto.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Dado dois conjuntos de vetores W1 e W2, W1 ∪ W2 será um subespaço se e somente se W1 estiver contido em W2 ou vice-versa. Verdadeiro ou falso? Justifique.

A

Falso. Isso acontecerá somente se W1 e W2 forem também subespaços. Caso contrário, é possível pegar um subespaço W e dividir ele em dois subconjuntos W1 e W2 de modo que nenhum dos dois seja um subespaço mas sua união (W) ainda seja.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Dê três exemplos de propriedades dos espaços vetoriais

A

Proriedades no espaço vetorial, para todo u, v,w ∈ X :

  • Associatividade da adição: u + (v + w) = (u + v) + w
  • Comutabilidade da adição: u + v = v + u
  • Existência de um elemento nulo: 0 + v = v + 0 = v
  • Existência do inverso aditivo: para todo v ∈ X existe −v ∈ X tal que v + (−v) = (−v) + v = 0
  • Propriedades da multiplicação por escalar: α(u + v) = αu + αv, (α + β)u = αu + βu, (αβ)u = α(βu), 1u = u.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Defina dependência e independência linear a partir de um sistema linear homogêneo.

A

Uma coleção de vetores {x1, x2, …, xn} é linearmente independente se e somente se o sistema linear homogêneo formado pelas somas de ai*xi igualadas a zero só tiver solução trivial (ou seja, se a única forma de essa soma ser zero é se os coeficientes a1, a2, …, an forem iguais a zero). Caso contrário, o sistema é linearmente dependente.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Defina a dimensão de um espaço vetorial associado a um conjunto C = {x1, x2, …, xn}

A

A dimensão de um espaço associado a um conjunto C é a quantidade de elementos (ou seja, a cardinalidade) do maior subconjunto de C formado por elementos linearmente independentes.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

O que significa dizer que uma matriz é singular? Qual é seu determinante?Qual pré-requisito uma matriz precisa atingir para ser considerada singular?

A

Uma matriz é singular quando ela é não invertível (ou seja, quando não existe uma matriz que, multiplicada por ela, resulta na matriz identidade). Ela será singular se e somente se seu determinante for zero e suas colunas (ou linhas) forem Linearmente Dependentes. Por consequência desses fatores, também possuirá deficiência de posto.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Quais são as três propriedades que devem ser seguidas por normas em um espaço vetorial X?

A

1 - ||x|| >= 0 para todo x pertencente a X e ||x|| = 0 se e somente se x = 0
2 - ||x + y || <= ||x|| + ||y|| para todo x, y em X.
3 - ||a*x|| = |a| * ||x|| para todo a real e x pertencente a X.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

O que é a norma p de um vetor x? Cite três exemplos notáveis de normas p.

A

A norma p é a raiz p da soma das coordenadas do vetor elevadas a p.
Normas p notáveis surgem quando p = 1 (nesse caso, a norma será a soma de todas as coordenadas do vetor), p = 2 (nesse caso, temos a norma euclideana) e p = ∞ (nesse caso, a norma será a maior coordenada do vetor).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Dê um exemplo de aplicação prática do conceito de normas vetoriais.

A

As normas vetoriais são instrumentos importantes para se caracterizar a convergência de algoritmos em Álgebra Linear Computacional, Otimização e Aprendizado de Máquina.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Quais são as características quantificadas pela norma da matriz?

A

1 - O quão grande a matriz é.
2 - Em quanto a transformação linear que a matriz induz pode transformar a magnitude (ou melhor dizendo, a norma) do vetor de entrada.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Quais são as quatro propriedades que devem ser seguidas por normas de matrizes?

A

1 - ||A|| >= 0 e ||A|| = 0 apenas se A é identicamente nula.
2 - ||A + B || <= ||A|| + ||B||.
3 - ||aA|| = |a| * ||A||
4 - ||A
B|| <=||A|| * ||B||

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Dê três exemplos de normas populares de matrizes.

A

1 - ||A|| 1 := max j=1,…,n||Aj||1. Esta norma é chamada de norma de máxima coluna, pois todas as colunas de A são comparadas e a norma da coluna de maior norma 1 é a norma 1 da matriz.

2 -||A||∞ := max i=1,…,m||ai||1. De modo análogo, esta norma é chamada de norma de máxima linha, pois todas as linhas de A são comparadas e
a norma ∞ de A é norma 1 de sua linha de maior norma 1.

3 - Norma de Frobenius que é obtida tomando a raiz quadrada da soma de todos os elementos da matriz ao quadrado

4 - Normal Espectral : Ela será o autovalor com maior módulo de A se A for igual à sua transposta. Caso contrário, será o maior valor singular de A que pode ser obtido tirando a raiz quadrada do maior autovalor da matriz formada pela multiplicação de A por sua transposta.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

O que é o produto externo entre dois vetores a = [a1, a2, …, an] e b=[b1, b2, …, bm]?

A

É o produto abT que pode ser representada pela matriz A mxn = [a1b1 a1b2 … a1bm]
|a2b1 a2b2 … a2* bm|
|………. …….. ….. ………. |
[anb1 anb2 …. an*bm]

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Cite três subespaços vetoriais associados a uma matriz A n x m qualquer.

A
  1. Espaço coluna de A: C(A) = {x = Ay|y ∈ Rm}. Corresponde ao subespaço vetorial do Rm gerado pela combinação linear das colunas de A, A1, . . . , Am. O espaço coluna de A também é conhecido como espaço imagem de A.
  2. Espaço linha de A: C(A^T) = {y = A^Tx|x ∈ Rn}. Corresponde ao subespaço do Rn gerado pela combinação linear das linhas a1, a2, . . . , am de A.
  3. Espaço nulo de A: N(A) = {x ∈ Rn : Ax = 0}. Corresponde ao subespaço
    do Rn formado pelas soluções do sistema linear homogêneo Ax = 0. O espaço nulo de A também é chamado de núcleo ou kernel de A.
  4. Espaço nulo de A^T(ou espa¸co nulo à esquerda de A): N(A^T) = {y ∈ Rm :A^T y= 0}. Corresponde ao subespaço do Rm formado pelas soluções do sistema
    linear homogêneo A^T y = 0.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

O que é o Posto (ou rank) de uma matriz A ∈ R m×n?

A

É a quantidade de linhas (ou colunas) linearmente independentes de A.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

O que significa dizer que uma matriz A ∈ R m×n possui posto ou rank completo? O que significa dizer que A possui deficiência de posto? Como calcular a deficiência de posto de A?

A

A matriz A possui posto completo quando seu posto é igual ao menor entre m e n. Em outras palavras, é quando A possui o maior posto possível para sua dimensão.

A possui deficiência de posto quando o posto não é completo. Seu valor é dado pela expressão min (m, n) - rank(A).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

O que é o subespaço linear associado a um conjunto de vetores? Como ele é denotado?

A

O subespaço linear de um conjunto de vetores {x1,…, xn} denotado por span ({x1,…,xn}) é o conjunto de todos os vetores que podem ser formados a partir de combinações lineares de {x1,…, xn}.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Qual condição um conjunto de vetores C precisa possuir para formar uma base para span(C)?

A

Todos os vetores em C precisam ser linearmente independentes.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

O que diz a primeira parte Teorema Fundamental da Álgebra Linear?

A

Para uma matriz A m x n com posto r, valem as seguintes propriedades para as dimensões dos 4 espaços fundamentais de A:
1 - dim(C(A)) = r
2 - dim(C(A^T)) = r
3 - dim(N(A)) = n - r
4 - dim(N(A^T)) = m - r

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

Quando podemos afirmar que dois subespaços vetoriais são ortogonais?

A

Dois subespaços vetoriais U e V são ortogonais se e somente se eles possuem as mesmas dimensões e para quaisquer vetores u ∈ U e v ∈ V, <u * v> = 0.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

O que é o complemento ortogonal de um subespaço V?

A

O complemento ortogonal de V é a coleção de todos os vetores do Rn que são ortogonais a todos os vetores em V. Ou seja, matematicamente temos:
V⊥ = {x ∈ Rn: x^T y = 0, para qualquer y ∈ V}.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

Se dois espaços são ortogonais entre si, um é necessariamente o complemento ortogonal do outro. Verdadeiro ou falso? Justifique.

A

Falso. Dois espaços podem ser ortogonais entre si sem que um seja o complemento ortogonal do outro.

Para que um espaço seja o complemento ortogonal de outro, é preciso que a soma de suas dimensões seja igual à dimensão do espaço vetorial total e que cada vetor de um espaço seja ortogonal a todos os vetores do outro. A ortogonalidade entre dois espaços é uma condição necessária, mas não suficiente para que um seja o complemento ortogonal do outro.

Por exemplo, no espaço R³, os subespaços X = {[1, 0, 0]} e Y = {[0, 1, 0]} são ortogonais, porém não são o complemento ortogonal um do outro visto que nenhum deles inclui o eixo Z.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

O que diz a segunda parte do Teorema Fundamental da Álgebra Linear?

A
  • Qualquer par de vetores x, z: x ∈ N(A) e z ∈ C(A^T) satisfazem x^T z = 0
    e N(A) = (C(A^T))⊥.
  • Qualquer par de vetores u, v: u ∈ N(A^T) e v ∈ C(A) satisfazem u^T v = 0 e N(A^T) = (C(A))⊥
30
Q

O que significa dizer que λ é um autovalor associado a um autovetor x de uma matriz A?

A

Um par (λ, x) : λ ∈ C, x ∈ Cn, x != 0n é um autopar (autovalor + autovetor) para A se e somente se Ax = λx.

31
Q

Quando um sistema linear da forma Ax = b terá uma única solução? E quando ele terá infinitas soluções? Explique a partir dos quatro espaços fundamentais e dê exemplos.

A

Primeiro, é necessário encontrar uma solução para Ax = b. Tendo uma solução em mãos, ela será quando o espaço nulo N(A) tiver dimensão 0 (ou seja, admitir somente solução trivial), o que ocorrerá quando o posto coluna for completo.

Para encontrar soluções alternativas, vamos supor que exista x1 != 0, x1 ∈ N(A). Veja que:
Ax = b
Ax1 = 0
A(x + x1) = b

Ou seja, qualquer vetor formado pela combinação entre x e x1, x1 ∈ N(A) será também uma solução.

32
Q

O sistema linear Ax = b terá uma única solução sempre que A tiver posto completo. Verdadeiro ou falso? Justifique.

A

Falso. Mesmo que A possua posto completo, o sistema Ax = b pode não possuir solução. A única certeza que podemos extrair dos 4 espaços fundamentais é que se existe uma solução, ela será única.

33
Q

Explique quantas soluções o sistema linear Ax = b, A ∈ R ^ m x n terá em função do posto de A e de suas dimensões.

A

Se m = n, A terá exatamente uma solução se o posto de A for completo. Se o posto for incompleto, podem existir infinitas soluções ou nenhuma solução.

Se m > n, existem mais equações que variáveis. Por isso, mesmo se o posto de A for completo, pode não existir nenhuma solução, porém ela será única se existir. Se o posto for incompleto, pode não existir nenhuma solução mas se uma existir, existirão infinitas soluções.

Se n < m, existem mais variáveis que equações. Se o posto for completo, existirão infinitas soluções. Se o posto for incompleto, pode não existir nenhuma solução mas se uma existir, existirão infinitas.

34
Q

Qual a relação entre os autovalores/autovetores de uma matriz A e os de sua inversa A^-1?

A

Se x é um autovetor de A associado a um autovalor λ, x também será um autovetor de A^-1 associado a um autovalor 1/λ.

35
Q

Qual a relação entre os autovalores/autovetores de uma matriz A e os de sua potência A^k?

A

Se x é um autovetor de A associado a um autovalor λ, x também será um autovetor de A^k associado a um autovalor λ^k.

36
Q

Qual a diferença entre uma base ortogonal e uma base ortonormal?

A

Em uma base ortogonal, vi^T vj = {0} para todo vi, vj.
Em uma base ortonormal, vi^T vj = {0} sempre que i != j, caso contrário, vi^T vj = 1.

37
Q

O que significa dizer que uma soma de subespaços U1 + U2 + … + Um forma uma soma direta? Como essa soma é representada? Cite dois exemplos de consequências dessa definição.

A

Estamos particularmente interessados em casos em que cada vetor em U1+U2+· · ·+Um pode ser representado na forma acima, de uma única forma (os uj são únicos). Se U1+U2+· · ·+Um ´e uma soma direta, representamos
como U1⊕U2⊕· · ·⊕Um.

Alguns resultados adicionais:
1. U + U⊥ formam uma soma direta de V, se U é subespaço de V .
2. Se U, W são subespaços de V , então U + W é uma soma direta se e somentese U ∩ W = {0}.
3. Se U1, U2, . . . , Um são subespaços de V, então U1 + U2 + · · · + Um é uma soma direta se e somente se a única forma de escrevermos o vetor 0 (zero) como uma soma de u1 + u2 + · · · + um é tomando cada um dos uj ’s como o próprio vetor 0.

38
Q

O que são matrizes ortogonais? Quais pré-requisitos precisam ser atingidos para que uma matriz seja considerada ortogonal?

A

Uma matriz ortogonal é uma matriz cuja inversa é igual à sua transposta. Para ser considerada ortogonal, é necessário que a matriz seja quadrada, a norma euclideana de suas colunas seja unitária (1) e todo par de colunas distintas seja ortogonal.

39
Q

O que são matrizes ortonormais? Quais pré-requisitos precisam ser atingidos para que uma matriz seja considerada ortonormal?

A

São matrizes que não são quadradas mas que possuem norma euclideana unitária e colunas ortogonais entre si.

40
Q

Dê três exemplos de motivos pelos quais matrizes ortogonais são consideradas extremamente importantes na Ciência da Computação.

A
  1. A norma Euclideana e os ângulos formados entre vetores não são alterados pela matriz Q.
  2. As colunas de uma matriz ortogonal são uma base ortonormal para Rn.
  3. As linhas de uma matriz ortogonal são uma base ortonormal (possivelmente diferente) para Rn.
  4. Usar transformações lineares induzidas por Q não acarreta erro numérico substancial.
  5. Usar transformações lineares induzidas por Q não acarreta overflow.
  6. A inversa de uma matriz ortogonal é a sua transposta.
41
Q

O que é uma matriz simétrica positiva definida?

A

Uma matriz simétrica positiva definida é uma matriz que tem as seguintes características:
- É simétrica, ou seja, é igual à sua transposta
- É positiva definida, ou seja, a forma quadrática associada a ela é positiva

42
Q

O que é a forma quadrática de uma matriz? Qual é seu outro nome? O que ela diz sobre o tipo da matriz?

A

A forma quadrática de uma matriz (também conhecida como energia) S é o resultado da transformação x^T *S *x. Ela nos dá os seguintes resultados:

  • S será positiva definida (SPD) se e somente se f(x) > 0 para qualquer x ∈ R
    n, x != 0n.
  • S é simétrica semipositiva definida se e somente se f(x) ≥ 0 para qualquer x ∈ Rn, x != 0n.
  • S é simétrica negativa definida se e somente se f(x) < 0 para qualquer x ∈ R
    n, x != 0n.
  • Sn é simétrica seminegativa definida se e somente se f(x) ≤ 0 para qualquer x ∈ R n, x != 0n.
  • S é indefinida se nenhuma das classificações acima se aplicar, ou seja, se existirem x, y tais que f(x) > 0, f(y) < 0
43
Q

Dê três exemplos de testes possíveis para verificar se uma matriz é SPD. Quantos testes precisam ser aprovados para que a matriz possa ser considerada SPD?

A
  • A energia f(x) de S é sempre positiva para qualquer x != 0n.
  • Todos os autovalores de S são positivos.
  • S admite uma fatoração S = M^TM, onde M é uma matriz de posto completo n. Em particular, S admite uma fatoração de Cholesky S =LL^T, onde L é triangular inferior, com todos os elementos ao longo de sua diagonal sendo positivos.
  • Os determinantes das submatrizes principais de S são positivos.
    (A submatriz principal Sk : k = 1, . . . , n de A é a matriz formada pelas primeiras k linhas e colunas de S.)
  • Possui todos os pivôs positivos no processo de Eliminação de Gauss.

Basta que a matriz passe em um desses testes para que possa ser considerada SPD.

44
Q

O que é o traço de uma matriz?

A

É a soma de seus elementos da diagonal principal.

45
Q

Como obter o determinante de uma matriz a partir de seus autovalores?

A

Basta multiplicar todos os autovalores da matriz.

46
Q

Como encontrar os autovetores válidos de uma matriz A a partir dos seus autovalores usando os quatro espaços fundamentais?

A

Para cada autovalor λ de A, calcule S = A - λI. Os autovalores possíveis para λ correspondem ao espaço nulo de S.

47
Q

Sabendo que A é uma matriz quadrada n x n e possui n autovalores diferentes, o que podemos afirmar sobre seus respectivos autovetores? Qual espaço eles geram?

A

Se todos os autovalores são diferentes, A terá n autovetores linearmente independentes que gerarão o espaço R^n.

48
Q

Suponha uma matriz A de dimensão n x n com n autovalores diferentes. O que podemos afirmar sobre o limite quando k vai para infinito de (A^k * v) /
∥A ^ k * v∥² ?

A

Se A tem n autovalores diferentes, podemos afirmar que esse limite no infinito converge para um vetor pertencente ao span de x1, sendo x1 o autovetor associado ao autovalor de maior módulo de A.

49
Q

Cite três características de matrizes simétricas S n x n.

A
  • Elas possuem n autovalores reais.
  • São iguais à sua transposta.
  • É possível escolher seus autovetores de modo que sejam ortonormais.
  • Toda matriz simétrica pode ser fatorada na forma S = Q Λ Q^T onde Q é ortogonal e Λ é diagonal.
  • Toda matriz simétrica é similar a uma matriz diagonal.
50
Q

O que significa dizer que A é uma matriz diagonalizável?

A

Quer dizer que A é similar a uma matriz diagonal, ou seja, quer dizer que existe uma matriz P P tal que P^−1AP é uma matriz diagonal.

51
Q

Dê três exemplos de condições suficientes para que A seja uma matriz diagonalizável. Essas condições são necessárias ou são apenas suficientes?

A
  • Todos os autovalores de A são diferentes. Condição suficiente.
  • A é simétrica. Condição suficiente.
  • A admite fatoração de Cholesky. Condição suficiente.
52
Q

O que significa dizer que duas matrizes A e C são similares?

A

Quer dizer que elas possuem o mesmo conjunto de autovalores.

53
Q

O que o número de autovalores não-nulos de uma matriz nos diz sobre seu rank?

A

Rank(A) = número de autovalores não nulos, contando suas multiplicidades.

54
Q

O que o rank de uma matriz quadrada nos diz sobre seus autov

A
55
Q

O que significa topologia no contexto de matrizes? Dê dois exemplos de topologias de matrizes.

A

É a definição de onde a matriz pode ter elementos não-nulos. Exemplos de topologias incluem triangular superior (elementos dentro e acima da diagonal principal podem ser não-nulos), triangular inferior (elementos dentro e abaixo da diagonal principal podem ser não-nulos) e diagonal (apenas elementos na diagonal principal podem ser não-nulos).

56
Q

Dê três exemplos de fatorações de matrizes.

A
  1. Fatoração PA = LU, onde L é triangular inferior, com a diagonal unitária, U é uma triangular superior e P é uma matriz de permutação.
  2. Fatoração de Cholesky A = R^T R, onde R é triangular inferior, com a diagonal positiva. A precisa ser SPD.
  3. Fatoração Espectral A é simétrica e A = QΛQ^T, onde Λ é uma matriz
    diagonal com os autovalores de A e Q é ortogonal, com os autovetores de
    A em suas colunas.
  4. Fatoração de Schur A = Q T Q^T onde Q é ortogonal, T é uma triangular
    superior. A matriz A não precisa ser simétrica nem diagonalizável. A diagonal de T armazena os autovalores de A.
  5. Fatoração A = QR, onde Q é uma matriz com colunas ortonormais e R é
    uma triangular superior.
  6. Decomposição em Valores Singulares (Singular Value Decomposition -
    SVD): A = UΣV^T, A ∈ R m×n, U ∈ R m×n, V ∈ R n×n, Σ ∈ R n×n, V^T V = I n, U^TU = I m e a matriz Σ é uma matriz de zeros, exceto pelas r primeiras entradas de sua diagonal, que guarda valores positivos σ1 ≥ σ2 ≥ · · · σr, sendo r o posto de A.
57
Q

Quais matrizes admitem fatoração de Cholesky?

A

Matrizes simétricas positivas definidas.

58
Q

Dê dois exemplos de fatorações que apresentam o posto de uma matriz.

A
  • Fatoração de Cholesky
  • Fatoração LU
59
Q

Por que as fatorações de Cholesky e LU são consideradas fatorações básicas?

A
  1. Os elementos algorítmicos que empregam são bastante simples.
  2. As bases fornecidas para C(A), C(A^T) não são ortonormais.
  3. Com estas fatorações somos capazes de resolver boa parte dos sistemas lineares com os quais nos deparamos em aplicações, desde que sejam bem condicionados.
60
Q

O que são sistemas bem condicionados?

A

Informalmente, sistemas lineares bem condicionados são definidos por matrizes de coeficientes que, no processo de fatoração, não tendem a gerar fatores com grande acúmulo de erros numéricos. Erros numéricos grandes nos fatores se traduzem em erros numéricos grandes, por exemplo, nas soluções dos sistemas lineares onde as matrizes aparecem.

61
Q

Dê três exemplos de razões para se fatorar uma matriz A ∈ R m×n.

A
  1. Resolver um ou vários sistemas lineares, possivelmente definidos pela mesma matriz de coeficientes A.
  2. Analisar a existência e unicidade das soluções de sistemas lineares.
  3. Calcular o determinante de uma matriz quadrada.
  4. Conhecer espaços vetoriais associados à matriz: C(A), C(A^T), N(A), N(A^T).
    Eventualmente, podemos desejar que as bases para estes espaços sejam
    ortonormais. Para tanto, as fatorações empregadas devem levar estes aspectos em consideração.
  5. Obter o espectro de A, ou seja seus autovetores e, eventualmente, seus autovetores.
  6. Conhecer os valores singulares de A, assim como seus vetores singulares, de fundamental utilidade para o item abaixo.
  7. Aproximar matrizes com muitas colunas ou muitas linhas por matrizes de
    posto baixo. Com isso podemos resolver problemas aplicados da Ciência
    da Computação em Otimização, em Inteligência Artificial, em Processamento de Imagens e de Sinais, apenas para citar algumas aplicações.
  8. As fatoraões de matrizes nos permitem reformular problemas de Matemática Aplicada, de uma forma mais conveniente, desde que o problema seja representado ou aproximado por um sistema linear.
62
Q

O que é uma matriz de permutação? Como usar uma matriz de permutação para permutar as linhas de uma matriz A? Como usar uma matriz de permutação para permutar as colunas de uma matriz A?

A

Uma matriz de permutação é uma matriz resultante de uma ou mais operações de troca de linha realizadas na matriz identidade. Para permutar as linhas de uma matriz A, basta calcular o produto PA. Para permutar as colunas de uma matriz A, basta calcular o produto AP.

63
Q

Como descobrir o posto de uma matriz a partir de sua forma fatorada de Cholesky?

A

O posto da matriz é representado pela quantidade de colunas não-nulas na forma fatorada L L^T

64
Q

Explique o conceito por detrás do algoritmo que realiza a fatoração de Cholesky de uma matriz simétrica A.

A

Suponha que a matriz A possua fatoração de Cholesky. Isso significa que existe uma matriz L tal que L L^T = A. Inicialize a matriz L com incógnitas e obtenha seus valores a partir de multiplicações de matrizes.

65
Q

Por que a fatoração de Cholesky exige que os elementos da diagonal principal sejam todos positivos? O que acontece se escolhermos um valor negativo ?

A

Uma parte importante da fatoração de Cholesky envolve a obtenção das raízes dos elementos da diagonal principal da matriz. Para que a fatoração de Cholesky seja única para cada matriz, estabeleceu-se como referência sempre a raiz positiva. Ao escolhermos um valor negativo, a fatoração prosseguirá sendo válida e da forma A = L L ^ T, porém não será única.

66
Q

Em qual etapa da fatoração de Cholesky descobrimos de forma definitiva se a matriz é SPD? Por que isso acontece ?

A

Só podemos afirmar que a matriz é SPD ao tirarmos a raiz do n-ésimo elemento; se ele for positivo, a matriz é SPD. Isso acontece porque a forma através da qual a fatoração de Cholesky informa que uma matriz não é SPD é ao tirar a raiz de um elemento aii menor ou igual a 0.

67
Q

Cite uma vantagem e uma desvantagem da fatoração de Cholesky em relação à fatoração LU.

A

Vantagens:
- Menos complexa computacionalmente em termos de tempo.
- Menos complexa computacionalmente em termos de espaço.
- A fatoração é mais estável.

Desvantagens:
- Se aplica somente a matrizes SPD
- Se aplica somente a matrizes simétricas.

68
Q

Qual a diferença entre os algoritmos inner Cholesky e outer Cholesky?

A

O algoritmo inner Cholesky procede identificando o elemento aii e usando operações elementares dentro da própria matriz para obter a matriz resultante e então identificar o elemento ai+1i+1.

Já, o outer Cholesky identifica o elemento aii, usa-o para construir uma matriz formada pelo produto externo do vetor resultante da linha i e usa da subtração de matrizes para obter a matriz na qual prosseguirá.

69
Q

Explique de maneira resumida um algoritmo capaz de fatorar A em PA = LU

A
  • Repita para todas as colunas i = 1, 2, …, n em A:
    - Identifique a posição k do maior elemento da coluna i
    - Armazene o valor 1 na posição (i, k) da matriz L_aux
    - Use operações elementares para anular os valores na coluna i. Armazene na matriz L o oposto de seus respectivos valores na posição correspondente
  • Ao final do processo, troque as linhas de A de modo que A seja uma matriz triangular superior (U). A matriz L será dada pela troca de linhas de L_aux de modo que ela seja uma triangular inferior. A matriz de permutação P será dada pela matriz L_aux com todos os elementos diferentes de 1 igualados a 0.
70
Q

Na fatoração PA = LU, qual o critério para a escolha do pivô em cada etapa? Por que usa-se esse critério?

A

Deve-se escolher o pivô de maior módulo visando minimizar erros numéricos.

71
Q

Suponha que uma matriz A possua n autovetores linearmente independentes. Como usar essa informação para realizar a diagonalização de A?

A

Se A possui n autovetores linearmente independentes, a matriz S formada por esses autovetores em suas colunas é não-singular (e portanto, invertível). Sendo Λ a diagonalização de A (ou seja, a matriz com os autovalores de A em sua diagonal principal), temos:
A S = S Λ
S^ -1 A S = S^-1 Λ
S^ -1 A S = Λ

72
Q
A