Etapas do ajuste por quadrados mínimos

A resolução do problema de ajuste de curvas por quadrados mínimos lineares está divida em três etapas.

A etapa mais importante do problema de ajuste de curva por pelo método de quadrados mínimos é a definição das funções de base, ou o espaço de aproximação, usadas para gerar a função de melhor ajuste.

A escolha mais comum é trabalhar com polinômios. Isso porque polinômios são funções simples e versáteis, podendo representar uma gama grande de comportamentos observados. Uma ressalva é que polinômios são funções infinitamente diferenciáveis. Sendo assim, se o seu conjunto de dados tem um comportamento não tão suave, pode ser difícil representar esse comportamento usando apenas polinômios (ou usando apenas polinômios de grau baixo).

Caso seu conjunto de dados tenha um comportamento esperado periódico (temperatura de uma região ao longo de anos, por exemplo), pode ser útil considerar funções geradas pela combinação de funções trigonométricas, como senos e cossenos.

Situações com variação abrupta da função podem ser melhor representadas utilizando-se exponenciais.

Por fim, esses exemplos não são mutuamente excludentes, isto é, eles podem ser combinados. Imagine a situação em que a temperatura média de uma região está subindo ao longo dos anos. Ainda há o comportamento oscilatório devido às diferenças entre estações do ano, mas de ano a ano a temperatura média cresce. Neste caso seria adequado combinar funções trigonométricas, para representar a oscilação sazonal, com um polinômio, talvez de grau 1, para representar o crescimento da temperatura média no decorrer dos anos.

Se o método de ajuste de curvas por quadrados mínimos garante que solução encontrada seja a melhor possível dentro do espaço de aproximação escolhido, o mesmo não pode ser dito quando a função ajustada é comparada com outra, gerada por funções diferentes. Neste caso, a maneira de saber qual das duas ajusta melhor os dados é verificando qual delas tem o menor resíduo.

A construção da matriz $\mathsf{\Phi}$ é um processo mecânico. Cada uma de suas colunas é uma das funções $\phi_j$ avaliada em todos os pontos $x_i$ amostrados.

O interessante é perceber que a matriz do sistema normal, $A=\mathsf{\Phi}^T\mathsf{\Phi}$ tem propriedades especiais que podem ser aproveitadas no momento da resolução do sistema linear.

A matriz $A$ é simétrica, uma vez que $$ A^T = (\mathsf{\Phi}^T \mathsf{\Phi})^T = \mathsf{\Phi}^T (\mathsf{\Phi}^T)^T = \mathsf{\Phi}^T\mathsf{\Phi} = A. $$ Além disso, a matriz $A$ também é definida positiva, o que significa que para qualquer vetor $u$ não nulo, $u^TAu \gt 0.$ Com efeito, $$ u^TAu = u^T \mathsf{\Phi}^T\mathsf{\Phi} u = (\mathsf{\Phi} u)^T(\mathsf{\Phi} u) = \|\mathsf{\Phi} u\|_2^2 > 0, $$ se $\mathsf{\Phi} u\neq 0,$ o que é verdade se as funções $\phi_1, \ldots,\phi_n$ forem linearmente independentes.

A importância de saber que a matriz $A$ é definida positiva é que para esse tipo de matriz existem algoritmos mais eficientes para a resolução do sistema linear, como a decomposição de Cholesky.

Diversos métodos podem ser utilizados para resolver o sistema normal. Podemos por exemplo utilizar a Eliminação de Gauss, cujo custo computacional é de ${2\over 3} n^3$ operações.

A decomposição de Cholesky é uma decomposição específica para o caso em que a matriz do sistema linear é simétrica e definida positiva, como acontece no caso do sistema normal. Resolver um sistema linear utilizando a decomposição de Cholesky tem custo computacional de ${1\over 3}n^3$ operações, ou seja, metade do custo da resolução através da eliminação de Gauss.

Em problemas de quadrados mínimos a decomposição mais utilizada, por ter melhores propriedades numéricas, é a decomposição QR. Neste caso o custo computacional é ${4\over 3}n^3.$

Por fim, para problema mais complexos do ponto de vista numérico, pode-se empregar a decomposição em valores singulares ou decomposição SVD. Essa decomposição tem custo computacional fixo de $4n^3,$ além de uma fase iterativa.

Para encerrar o problema de ajuste, na próxima aula, vamos trabalhar com dados reais. Vamos ver que além do ajuste em si, temos que investir também na preparação dos dados.

1. Dê exemplos de problemas de ajuste para os quais faz sentido escolher um espaço de aproximação em particular.

2. A tabela a seguir mostra o tempo médio ($t$), em segundos, gasto no cálculo da decomposição LU de matrizes aleatórias, computadas pelo MATLAB, em função da ordem da matriz ($n$).

$n$	$t$ (s)		$n$	$t$ (s)		$n$	$t$ (s)
100	0.0003		1000	0.0425		6000	2.5825
200	0.0014		2000	0.2163		7000	3.7516
400	0.0043		3000	0.5015		8000	5.2557
600	0.0126		4000	0.9702		9000	7.0075
800	0.0244		5000	1.6451		10000	9.0550

O termo dominante no número de operações realizadas no algoritmo convencional da decomposição LU é ${2\over 3} n^3.$ Supondo que o tempo gasto no cálculo da decomposição seja proporcional ao número de operações realizadas, encontre os parâmetros $a$ e $b$ de modo que a função $t(n) = an^b$ melhor se ajuste aos dados.
Dica: defina $u=\log(t)$ e resolva problema de ajuste nas variáveis $n$ e $u.$

Com base no que você descobriu, é possível afirmar que o algoritmo se comporta como previsto? Que outras perguntas você imagina que possam surgir dessa análise? Formule algumas.