Aproximação de mínimos quadrados

Fórum sobre técnicas matemáticas úteis na preparação olímpica

Aproximação de mínimos quadrados

Mensagempor hexphreak em Quinta Jan 20, 2011 4:05 pm

Introdução
Consideremos uma determinada experiência de Física, a partir da qual se espera comprovar uma lei ou estimar o valor de um ou mais parâmetros. No decurso da experiência, medem-se vários pares (x_i,y_i) (onde Y é a grandeza medida em função de X), os quais queremos ajustar a uma determinada curva teórica, a dependência funcional que a teoria determina que deve existir entre as duas grandezas em questão. Uma vez que toda e qualquer medida vem afectada de um certo erro experimental, os dados, por muito bons que sejam, não serão perfeitos. Assim, temos dois problemas distintos:

  1. Encontrar uma forma de determinar a distância entre uma dada função aproximante e os nossos dados;
  2. Encontrar os parâmetros da função que minimizam esta distância.

Distância entre duas funções
Há várias formas de resolver o nosso primeiro problema, o que leva desde já a alguma indeterminação no problema de aproximação. Para qualquer uma destas formas, definimos os desvios entre os dados experimentais e a função aproximante f(x) como sendo os valores d_i = y_i - f(x_i),\,\forall i=1,2,\ldots,n (onde n é o número de medições efectuadas). Os desvios medem, então, a distância entre cada medição e o valor teórico correspondente.

Para definir uma distância entre a função aproximante e os dados, podemos adoptar várias estratégias (\bar y é o vector dos y_i e \bar f o vector dos f(x_i)):

  • \displaystyle d(\bar y,\bar f) = \sum_{i=1}^n |d_i|
  • \displaystyle d(\bar y,\bar f) = \max_{1 \le i \le n} |d_i|
  • \displaystyle d(\bar y,\bar f) = \sum_{i=1}^n d_i^2

Estes são os três exemplos mais comuns de distância: a soma dos desvios absolutos; o máximo dos desvios absolutos; e a soma dos quadrados dos desvios. O problema de aproximação mais geral pode ser formulado com uma distância arbitrária (foi o que fizemos na introdução). No entanto, a terceira definição é sem dúvida a mais utilizada, uma vez que ao contrário das outras conduz a sistemas de equações lineares, os quais sabemos bem resolver. Para além disso, é a generalização óbvia e intuitiva da nossa noção de distância física no espaço (a norma euclidiana que vem do teorema de Pitágoras). A utilização desta definição é a origem do nome do método dos mínimos quadrados.

Função aproximante ou ajuste teórico
Dispondo agora de uma definição de distância, passamos ao segundo ponto do método: como encontrar a função que minimiza esta distância.

O problema, posto de forma tão geral, não tem solução fácil. Podemos, por exemplo, utilizar a função interpoladora dos dados, caso em que todos os desvios são nulos e a distância é igualmente nula. No entanto, como os nossos dados estão afectados de erros, "obrigar" a função aproximante a passar por todos os pontos não faz muito sentido. Para além disso, revisitando os dois principais problemas apresentados inicialmente (comprovar uma lei ou encontrar os seus parâmetros), vemos que habitualmente temos à partida uma boa hipótese quanto à forma que esta função deve tomar.

Podemos então considerar que juntamente com os dados experimentais nos é dada uma certa função de ajuste F(x;c_1,c_2,\ldots,c_k), que para além de depender de x depende também de um certo conjunto de parâmetros \{c_i\}. Estes serão parâmetros físicos, da situação experimental, e nosso problema resume-se a encontrar estes valores de forma a que a função se ajuste da melhor forma possível aos dados; por outras palavras, queremos encontrar os c_i tais que d(\bar y, \bar F) seja mínimo. A partir daqui, a forma mais geral possível de proceder é como em qualquer problema de minimização típico: derivar a distância em ordem aos parâmetros, igualar a zero, e resolver.

No entanto, há um vasto número de situações em que a função F pode ser escrita como uma combinação linear de outras funções \phi_i(x) com coeficientes c_i, ou seja, F(x;c_1,\ldots,c_k) = c_1 \phi_1(x) + c_2\phi_2(x) + \ldots + c_k\phi_k(x). Esta situação permite-nos dar uma interpretação geométrica muito mais interessante do problema de aproximação, para além de conduzir a sistemas lineares quando é usada a terceira definição de distância acima, o que não acontece no caso geral.

(Quando procuramos os minimizantes através dos zeros das derivadas e a função F não encaixa no caso descrito, temos sistemas não-lineares, cuja resolução é feita por métodos iterativos semelhantes aos detalhados anteriormente.)

Resolução do problema de mínimos quadrados linear
Consideremos, no espaço tridimensional (\mathbb{R}^3), dois vectores não colineares u_1 e u_2. Estes vectores definem um plano, gerado por todas as combinações lineares possíveis dos dois. Consideremos agora um outro vector v que não se encontre no plano (e que, portanto, não seja combinação linear de u_1 e u_2). Qual é o vector do plano que mais se aproxima, geometricamente, de v?

Intuitivamente, a resposta é fácil: é a projecção perpendicular de v no plano. Ou seja, é o vector a_1 u_1 + a_2 u_2 tal que \langle u_i, v - (a_1u_1+a_2u_2)\rangle = 0 (\langle \cdot,\cdot \rangle é o produto interno do espaço). Este resultado pode, é claro, ser generalizado para espaços de dimensão arbitrária (i.e. hiperplanos de dimensão k em \mathbb{R}^n).

E o que tem isto a ver com o nosso problema? É fácil. Se definirmos os vectores \bar \phi_1,\bar \phi_2,\ldots,\bar \phi_k como \bar \phi_i = [\phi_i(x_1),\,\phi_i(x_2),\,\ldots,\,\phi_i(x_n)], o nosso problema de aproximação pode ser reformulado da seguinte forma: qual é o vector do plano gerado pelos \bar \phi_i que melhor aproxima \bar y? (a figura ilustra o caso k = 2, n = 3)

projeccao.png
projeccao.png (9.07 KiB) Visualizado 2917 vezes

Mas este é precisamente o problema que acabámos de tratar! Apenas temos que resolver as k equações \langle \bar \phi_i, \bar y - (c_1 \bar \phi_1 + \ldots + c_k \bar \phi_k) \rangle = 0 em ordem aos k parâmetros c_i, e teremos a solução do nosso problema. Ora, podemos reescrever as equações da seguinte forma:

\langle \bar \phi_i, \bar y \rangle = \langle \bar \phi_i, c_1 \bar \phi_1 + \ldots + c_k \bar \phi_k \rangle\Leftrightarrow \langle \bar \phi_i, \bar y \rangle = c_1 \langle \bar \phi_i, \bar \phi_1 \rangle + \ldots + c_k \langle \bar \phi_i, \bar \phi_k \rangle

Os únicos valores aqui que desconhecemos são os c_k, pelo que temos o seguinte sistema de equações:

    \langle \bar \phi_1, \bar \phi_1 \rangle c_1 + \langle \bar \phi_1, \bar \phi_2 \rangle c_2 + \ldots + \langle \bar \phi_1, \bar \phi_k \rangle c_k = \langle \bar \phi_1, \bar y \rangle
    \langle \bar \phi_2, \bar \phi_1 \rangle c_1 + \langle \bar \phi_2, \bar \phi_2 \rangle c_2 + \ldots + \langle \bar \phi_2, \bar \phi_k \rangle c_k = \langle \bar \phi_2, \bar y \rangle
      \vdots
    \langle \bar \phi_k, \bar \phi_1 \rangle c_1 + \langle \bar \phi_k, \bar \phi_2 \rangle c_2 + \ldots + \langle \bar \phi_k, \bar \phi_k \rangle c_k = \langle \bar \phi_k, \bar y \rangle

Este sistema é possível e determinado, desde que os vectores \bar \phi_i sejam linearmente independentes. Isto implica, embora não o vá provar, que n \ge k, i.e. que o número de medições seja superior ou igual ao número de parâmetros a determinar. O que é bastante intuitivo: para definir k parâmetros precisamos de pelo menos k medições!

O nosso problema inicial está, assim, resolvido: se a função de ajuste puder ser expressa como uma combinação linear de funções com coeficientes c_i, podemos encontrar os parâmetros simplesmente resolvendo o sistema acima. Para isto há algoritmos eficientes bem conhecidos, mas nos casos em que só temos dois ou três parâmetros - o caso mais comum em provas experimentais e experiências simples - podemos facilmente resolver as equações à mão.

Exemplo
Vamos então ver um exemplo simples e comum: ajustar uma recta a um conjunto de dados experimentais. Os dados encontram-se na seguinte tabela:

\begin{tabular}{lccccccccc}
\text{t (s)} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\
\text{x (m)} & 0.43 & 1.02 & 2.08 & 2.69 & 3.45 & 4.45 & 6.43 & 6.96 & 8.61
\end{tabular}

Se quisermos ajustar uma recta a estes dados, a nossa função será F(t;a,b)=at+b, e portanto c_1 = a, c_2 = b, \phi_1(t) = t e \phi_2(t) = 1. Calculando os valores \langle \bar \phi_i, \bar \phi_j \rangle e \langle \bar \phi_i, \bar x \rangle (note-se que \langle u,v \rangle = \langle v,u \rangle, pelo que não é preciso calcular todos os produtos):

\begin{tabular}{ccccc}
\langle \bar \phi_1, \bar \phi_1 \rangle & \langle \bar \phi_1, \bar \phi_2 \rangle & \langle \bar \phi_2, \bar \phi_2 \rangle & \langle \bar \phi_1, \bar x \rangle & \langle \bar \phi_2, \bar x \rangle\\
204 & 36 & 9 & 205.48 & 36.12
\end{tabular}

Temos então um sistema de duas equações a duas incógnitas:

\left\{\begin{array}{l}
204a+36b=205.48\\
36a+9b=36.12
\end{array}\right.

Resolvendo, encontramos a=1.02 e b=-0.05. Podemos verificar o ajuste graficamente, conforme se mostra na figura em baixo, e constatar que o método funciona mesmo! :D

regressao.png
regressao.png (4.03 KiB) Visualizado 2893 vezes

(Como curiosidade, os dados foram gerados a partir de uma recta "perfeita" para um carro a deslocar-se a 1\,\mathrm{ms^{-1}} a partir da origem, somando-lhes um erro distribuído normalmente com média 0 e variância 1, pelo que o ajuste obtido está dentro do erro que seria de esperar.)

Erros
Como, mais uma vez, os dados são afectados por erros, existe também um erro associado ao ajuste efectuado por mínimos quadrados. Não me vou alongar muito no cálculo destes erros, até porque é difícil fazê-lo sem muitas noções de Estatística. No entanto, uma forma muito fácil de estimar o erro máximo do ajuste é simplesmente calcular o desvio máximo entre a função aproximante e os dados experimentais; no exemplo acima, este valor é 0.5, o que não é muito mau (o número de dados é baixo e parecem um pouco dispersos).

Ajustes não lineares
O que é que acontece quando, como por vezes acontece, queremos ajustar aos dados uma função com parâmetros que não são os coeficientes de nenhuma combinação linear? Em geral, como já referi, este problema não tem solução fácil. No entanto, há casos em que é possível obter um ajuste aproximado linearizando a função.

Por exemplo, se quisermos ajustar a função N(t) = a \exp(-bt) (que corresponde, por exemplo, ao decaimento radioactivo de uma substância) a um conjunto de dados, o parâmetro b não é um coeficiente da exponencial. Mas se calcularmos o logaritmo de N(t), ficamos com \ln N(t) = \ln a - bt, o que já é uma combinação linear de funções (1 e -t). Podemos então efectuar o ajuste não a N(t) mas a \ln N(t), de forma a obter os parâmetros a e b.

É importante notar que este ajuste não é o mesmo que seria obtido por mínimos quadrados; mas, na maioria das situações, é suficiente próximo para ter grande utilidade.

Conclusão e outras aplicações
O método dos mínimos quadrados é surpreendentemente comum. Não se aplica apenas ao ajuste de funções a dados experimentais, mas também em áreas rigorosas como a análise de Fourier ou a Estatística. De facto, a série de Fourier de uma função periódica é precisamente o ajuste por mínimos quadrados dos coeficientes a_k com as funções \exp(-jk\omega_0t) servindo de \phi_k!

Espero que depois disto tudo tenham ficado, pelo menos, com a ideia das bases e da utilidade deste método, e o consigam aplicar em casos simples como o de ajustes lineares e quadráticos :)

Referências
  • Matos, A. Apontamentos de Análise Numérica, 2005
  • Taylor, John R. An Introduction to Error Analysis, 2ª ed., 1997. University Science Books.
Avatar do utilizador
hexphreak
top-Quark!
top-Quark!
 
Mensagens: 1959
Registado: Segunda Nov 05, 2007 8:52 pm
Localização: Maia/Porto

Re: Aproximação de mínimos quadrados

Mensagempor RicardoCampos em Quinta Jan 20, 2011 8:02 pm

Pouco útil para olimpíadas e assim, mas muitíssimo interessante ;)
\emph{Ricardo Campos}\in \delta \bigcap q\overline{q}
O Matemático-Físico de 2008
Avatar do utilizador
RicardoCampos
top-Quark!
top-Quark!
 
Mensagens: 1280
Registado: Sexta Jun 01, 2007 3:49 pm
Localização: Figueira da Foz/Coimbra/DMUC/DFUC, Paris... E agora Zurique!


Voltar para Técnicas matemáticas

Quem está ligado

Utilizadores a navegar neste fórum: Nenhum utilizador registado e 1 visitante

cron