8ª Aula - Eficiência computacional da eliminação de Gauss e sucessiva melhoria. Notas históricas sobre sistemas de equações lineares, eliminação de Gauss e matrizes. Motivação para definição de espaços lineares. Espaços lineares e subespaços lineares: definição, exemplos e condição necessária e suficiente para subconjunto de espaço linear ser subespaço linear com as mesmas operações.

2 outubro 2018, 10:00 Luis Magalhães

Eficiência computacional do método de eliminação de Gauss. Ordem assimptótica do nº de multiplicações e de adições de nºs reais com matrizes genéricas nxn: resolução de sistemas de equações n3/3; inversão de matriz n3; multiplicação directa de matrizes n3. Referência a escolha de pivots e a escalamento de linhas ou colunas para maior precisão quando há pivots muito pequenos, considerados em Análise Numérica.

Métodos computacionais de elevada deficiência para produto de matrizes (logo, também resolução de sistemas de equações lineares e inversão de matrizes) do tipo de Método de Strassen (1967): ordem assimptótica de nº de operações de nºs reais para matrizes nxn genéricas n2,807=nlog27. Melhorias sucessivas em 1978-1987, 2010, 2011 e 2014 (n2,3728639, F. Le Gall).

Notas históricas sobre sistemas de equações lineares, eliminação de Gauss e matrizes.

Motivação para definição de espaços lineares.

Espaço linear (ou vectorial) real: ideia de espaço para formular Princípio de Sobreposição; definição; propriedades 0v=0 e (-1)v=-v para todo vector v .

Exemplos de espaços lineares com operações usuais: ℝn (n nº natural), ℝmxn (m,n nºs naturais) conjunto das matrizes mxn com componentes reais, ℝ (ℕ conjunto dos nºs naturais) conjunto das sucessões de nºs reais; ℝS (S conjunto ≠∅), conjunto das funções com valores reais definidas em S ; exemplos de subconjuntos de ℝ que não são espaços lineares: ℝ(não contém 0 ), ℝ+U {0}  (não contém simétricos de elementos d≠0), ℤ nºs inteiros (não contém  (1/2)1=1/2 ).

Subespaços lineares de espaços lineares: definição; qualquer espaço linear tem subespaços {0} e V, se existem subespaços diferentes contêm o 1º e estão contidos no 2º; um subconjunto S de um espaço linear V é um subespaço linear de V se e só se é ≠∅ e satisfaz as propriedades de fecho da adição e da multiplicação por escalares.