MAC 300 / MAC6920 / MAP5904 - Métodos Numéricos de Álgebra Linear

Professor: Ernesto G. Birgin (egbirgin at ime.usp.br)

Monitor PAE: Kennedy Anderson Guimarães de Araujo (kennedy94 at ime.usp.br)

Os livros "Fundamentals of Matrix Computations" de David S. Watkins (John Wiley & Sons, 1991) e "Numerical Computing with IEEE Floating Point Arithmetic" de Michael L. Overton (SIAM, Philadelphia, 2001) contêm todo o material do curso. Sugerimos fortemente que os alunos consultem estes livros e façam os exercícios de cada capítulo.

Não deixe de ler nenhuma das páginas da disciplina, especialmente, a referente ao critério de avaliação.

• Programa do curso MAC300, MAC6920, MAP5904.
• Motivação
• Critério de avaliação
• Bibliografia básica recomendada
• Datas importantes (provas e exercícios-programa) ATENÇÃO: Data limite para a entrega de EP1-EP3 e L1-L8 13/12/20. Data limite para a entrega de EP4 e L9-L12, 15/01/21.
• Informações importantes sobre exercício-programas
• Enunciados dos exercício-programas: EP1, EP2, EP3, EP4.
• Listas de exercícios:
  • L1: 4.1, 5.1 e 5.8 do livro do Overton. (Data de entrega sugerida 04/09/20.)
  • L2: 6.4, 6.10 e 7.5 do livro do Overton. (Data de entrega sugerida 11/09/20.)
  • L3: 1.2.4, 1.3.7, 1.3.15 do livro do Watkins. (Data de entrega sugerida 20/09/20.)
  • L4: .1.7.34, 1.7.44, 1.7.45 do livro do Watkins. (Data de entrega sugerida 30/09/20.)
  • L5: 2.2.23 (interpretem "large" com "o maior possível") e 2.3.13 (seguindo as dicas dos exercícios 2.3.12 e 2.3.13) do livro do Watkins. (Data de entrega sugerida 12/10/20.)
  • L6: 2.7.29 do livro do Watkins. (Data de entrega sugerida 19/10/20.)
  • L7: 3.1.5, 3.1.6 e 3.1.7 do Watkins. (Data de entrega sugerida 26/10/20.)
  • L8: 3.2.25 e 3.2.27 do Watkins. (Data de entrega sugerida 2/11/20.)
  • L9: 3.4.26 do Watkins. (Data de entrega sugerida 9/11/20.)
  • L10: 5.2.20 e 5.3.7 do Watkins. (Data de entrega sugerida 16/11/20.)
  • L11: 5.3.15 e 5.3.17 do Watkins. (Data de entrega sugerida 23/11/20.)
  • L12: Esta lista consiste em fazer uma versão simplificada deste trabalho. Pode ser feito em Matlab ou Octave. A ideia é ver como a decomposição SVD pode ser usada no armazenamento ou transmissão de imagens. (Não é para fazer tudo o que está escrito no enunciado desse trabalho.) (Data de entrega sugerida 30/11/20.)
• Clique aqui se quiser dar uma espiada nos EPs e exercícios que faremos ao longo do semestre.
• Notas
Horário

	Segunda	Terça	Quarta	Quinta	Sexta
8:00 às 9:40		Aula clique aqui
10:00 às 11:40				Aula clique aqui
12:00 às 13:40			Monitoria clique aqui
14:00 às 15:40
16:00 às 17:40

MATERIAL:

• As aulas da disciplina não serão expositivas. O conteúdo do curso está contido nos livros do M. L. Overton e do D. S. Watkins mencionado acima. Existe também uma série de videoaulas da Prof. Wen Shen da Penn State University que cobre a maioria dos tópicos da disciplina. Interessam nesta disciplinas as videoaulas de 1 a 6 associadas ao capítulo 1 do livro dela, videoaulas 65 a 72 (capítulo 6) e algumas videoaulas dos capítulos 7 e 9. Novidade: Tem um curso pronto, com uma quantidade enorme de videoaulas em http://www.cs.utexas.edu/users/flame/laff/alaff/index.html. No horario das aulas comentaremos brevemente o tópico do dia, tiraremos dúvidas e resolveremos exercícios.

PROGRAMAÇÃO (que definitivamente sofrerá alterações em função do andamento do curso):

• Teremos uma semana de break de 28/OUT a 03/NOV.
• Tópico 1 (4 aulas): Introdução e representação em ponto flutuante.
• As aulas desta semana correspondem aos vídeos 1 a 6. O vídeo 1 é apenas introdutório e o vídeo 4 é uma introdução a Matlab. Logo, os vídeos mais importantes são os vídeos 2, 3, 5 e 6. Os exercícios sugeridos nos vídeos podem ser feitos em Octave ou em qualquer linguagem de programação.
• Como complemento aos vídeos, devem ler os capítulos 1 até 7 do livro do Michael Overton. Atenção especial aos números subnormais e a representação em ponto flutuante usando 64 bits, que não são mencionados nos vídeos. Na dúvida, não deixem de consultar a lista de correções da primeira edição aqui.
• Não deixem de ler também o link de "motivação" acima.
• A seção 2.5 (que começa na página 139) do livro do Watkins também cobre parte do conteúdo desta semana. Dessa subseção, precisam ler apenas até a linea 7 da página 145.
• A este tópico estão associadas as listas de exercícios 1 e 2.
• Tópico 2 (3 aulas): (Capítulo 1) Sistemas lineares triangulares, matrizes definidas positivas e decomposição de Cholesky.
• Este tópico, assim como o próximo, deve ser estudado do capítulo 1 do livro do Watkins. Como complemento podem asistir os videos 65, 66 e 67 da Wen Shen. Eles tratam de (a) sistemas lineares e eliminação Gaussiana, (b) decomposição LU e (c) decomposição de Cholesky, respectivamente. Como ela apresenta LU e Cholesky na ordem inversa à do livro, teriam que assistir os 3 videos juntos. Esses videos não cobrem todos os temas do tópico. No curso online da UTexas (link acima) há MUITAS aulas sobre este tópico. Estão todas no capítulo 5.
• A seção 1.1 trata de multiplicação de matrizes. Este é o tema do EP1.
• A seção 1.2 apresenta de forma geral o problema de sistemas lineares. Quem tiver dúvidas sobre o Teorema 1.2.3 precisa consultar um livro de Álgebra linear. A parte da circuitos elétricos e os outros exemplos podem deixar de lado se quiserem.
• A seção 1.3 trata de sistemas triangulares. Ela é toda importante para o que vem depois.
• A seção 1.4 trata da decomposição de Cholesky. A seção toda é importante. A primeira parte do EP2 é sobre isto.
• Vamos pular as seções 1.5 e 1.6. Para quem tiver interesse, há uma disciplina de pós-graduação chamada Métodos Diretos para Sistemas Lineares Esparsos (MAC5795) que trata específicamente sobre o tema dessas seções.
• A lista de exercícios 3 corresponde a estes tópicos.
• Tópico 3 (3 aulas): (Capítulo 1) Decomposição LU.
• A seção 1.7 trata de decomposição LU. Ela é toda importante. A segunda parte do EP2 é sobre isto.
• A seção 1.8 trata de decomposição LU com pivoteamento. Ela é toda importante. A segunda parte do EP2 é sobre isto.
• Vamos pular a seção 1.9. Para quem tiver interesse, há uma disciplina de pós-graduação chamada Métodos Diretos para Sistemas Lineares Esparsos (MAC5795) que trata específicamente sobre o tema dessa seção.
• A lista de exercícios 4 corresponde a estes tópicos.
• Tópico 4 (4 aulas): (Capítulo 2) Sensibilidade de sistemas lineares.
• Este tópico inclui uma revisão de normas de vetores, normas de matrizes e número de condição; problemas bem condicionados e problemas mal condicionados; métodos estáveis e aplicações a Cholesky e LU.
• O material de referência é o capítulo 2 do livro do Watkins. Os videos 68, 69 e 70 da Wen Shen tratam de normas e número de condição. O capítulo 1 do curso online da UTexas fala dessas coisas também. O resto do conteúdo deste tópico é coberto pelo capítulo 6 do curso online da UTexas.
• As listas de exercícios 5 e 6 correspondem a estes tópicos.
• Tópico 5 (6 aulas): (Capítulo 3) Matrizes ortogonais e problemas de quadrados mínimos.
• A fonte principal deste tópico é o capítulo 3 do livro do Watkins. O video 71 (Ch06n3) da Wen Shen pode ser considerado uma introdução. No curso online da UTexas teriam que assistir os tópicos 2.2, 3.2, 3.3, 4.1, 4.2 e 4.4.
• Problema de quadrados mínimos discreto (Seção 3.1), Matrizes ortogonais, rotações e reflexões (Seção 3.2), Solução do problema de quadrados mínimos (Seção 3.3), Ortonormalização com Gram-Schmidt (Seção 3.4) e Interpretação geométrica (Seção 3.5). O resto do capítulo fica de fora, embora seja importante.
• As listas de exercícios 7, 8 e 9 correspondem a estes tópicos, assim como o EP3.
• Tópico 6 (3 aulas): (Capítulo 4) Autovalores e autovetores. Método da potência e método da potência inverso.
A fonte principal deste tópico corresponde às seções 5.2 e 5.3 do livro do Watkins. O resto do capítulo é importante mas não teremos tempo de abordá-lo no curso. No curso online da UTexas teriam que assistir os tópicos do capítulo 9.
• As listas de exercícios 10 e 11 correspondem a estes tópicos.
• Tópico 7 (2 aulas): (Capítulo 4) Transformações de similaridade, redução às formas Hessenberg e tridiagonal. Algortimo QR.
• Tópico 8 (3 aulas): (Capítulo 4) Decomposição SVD.
• A fonte principal deste tópico é o capítulo 4 do livro do Watkins. No curso online da UTexas teriam que assistir os tópicos do capítulo 2, da seção 4.3 e, para os mais interessados, o capítulo 11.
• A lista de exercícios 12 corresponde a este tópico.