Fatorações

Question 1

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

Answer 1

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.

Question 2

Quais matrizes admitem fatoração de Cholesky?

Answer 2

Matrizes simétricas positivas definidas.

Question 3

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

Answer 3

• Fatoração de Cholesky
• Fatoração LU

Question 4

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

Answer 4

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.

Question 5

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

Answer 5

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.

Question 6

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?

Answer 6

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.

Question 7

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

Answer 7

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

Question 8

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

Answer 8

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.

Question 9

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 ?

Answer 9

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.

Question 10

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

Answer 10

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.

Question 11

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

Answer 11

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.

Question 12

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

Answer 12

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

Question 13

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

Answer 13

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

Question 14

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

Answer 14

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

Question 15

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

Answer 15

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 = Λ