Algoritmo de Gauss-Newton – Wikipédia, a enciclopédia livre

O algoritmo de Gauss-Newton é um método usado para resolver problemas de mínimos quadrados não lineares. Ele pode ser visto como uma modificação do Método de Newton para achar o mínimo de uma função. Diferentemente do Método de Newton, o Algoritmo de Gauss-Newton apenas pode ser usado para minimizar uma soma dos valores quadrados da função, mas tem a vantagem de que as derivadas segundas, que podem ser difíceis de calcular, não são necessárias.

Problemas de mínimos quadrados não lineares surgem, por exemplo, em regressão não linear, onde os parâmetros de um modelo são procurados de forma que o modelo esteja em concordância com as observações disponíveis.

O método foi nomeado a partir dos matemáticos Carl Friedrich Gauss e Isaac Newton.

Descrição[editar | editar código-fonte]

Dada "m" funções r = (r₁, …, r_m) de n variáveis 'β = (β₁, …, β_n), com m ≥ n', o Algoritmo de Gauss-Newton iterativamente encontra o mínimo das somas dos quadrados^[1]

${\displaystyle S({\boldsymbol {\beta }})=\sum _{i=1}^{m}r_{i}^{2}({\boldsymbol {\beta }}).}$

Começando com uma estimativa inicial ${\displaystyle {\boldsymbol {\beta }}^{(0)}}$ para o mínimo, o método prossegue com as iterações

${\displaystyle {\boldsymbol {\beta }}^{(s+1)}={\boldsymbol {\beta }}^{(s)}-\left(\mathbf {J_{r}} ^{\top }\mathbf {J_{r}} \right)^{-1}\mathbf {J_{r}} ^{\top }\mathbf {r} ({\boldsymbol {\beta }}^{(s)})}$

onde

${\displaystyle \mathbf {J_{r}} ={\frac {\partial r_{i}}{\partial \beta _{j}}}({\boldsymbol {\beta }}^{(s)})}$

é a Matriz Jacobiana de "r" e o símbolo ${\displaystyle ^{\top }}$ denota a matriz transposta.

Na montagem de dados, onde o objetivo é encontrar os parâmetros β tais que uma dada função modelo y = f(x, β) ajuste melhor alguns pontos de dados (x_i, y_i), as funções r_i são os resíduos

${\displaystyle r_{i}({\boldsymbol {\beta }})=y_{i}-f(x_{i},{\boldsymbol {\beta }}).}$

Então, o método de Gauss-Newton pode ser expresso em termos da Jacobiana da função "f" como

${\displaystyle {\boldsymbol {\beta }}^{(s+1)}={\boldsymbol {\beta }}^{(s)}-\left(\mathbf {J_{f}} ^{\top }\mathbf {J_{f}} \right)^{-1}\mathbf {J_{f}} ^{\top }\mathbf {r} ({\boldsymbol {\beta }}^{(s)}).}$

Notas[editar | editar código-fonte]

A suposição m ≥ n na demonstração do algoritmo é necessária, senão a matriz J_r^TJ_r não será invertível e as equações normais não poderão ser resolvidas (pelo menos exclusivamente).

O Algoritmo de Gauss-Newton pode ser obtido por aproximação linear do vetor das funções r_i. Usando o Teorema de Taylor, podemos escrever em cada iteração:

${\displaystyle \mathbf {r} ({\boldsymbol {\beta }})\approx \mathbf {r} ({\boldsymbol {\beta }}^{s})+\mathbf {J_{r}} ({\boldsymbol {\beta }}^{s})\Delta }$

com ${\displaystyle \Delta ={\boldsymbol {\beta }}-{\boldsymbol {\beta }}^{s}.}$

A tarefa de encontrar Δ minimizando a soma dos quadrados do lado direito, por exemplo:

${\displaystyle \mathbf {min} \|\mathbf {r} ({\boldsymbol {\beta }}^{s})+\mathbf {J_{r}} ({\boldsymbol {\beta }}^{s})\Delta \|_{2}^{2}}$

é um problema linear de mínimos quadrados, que pode ser resolvido explicitamente, obtendo-se as equações normais no algoritmo.

As equações normais são m equações normais simultâneas no desconhecido incremento Δ. Elas podem ser solucionadas em um passo, usando decomposição de Cholesky, ou, melhor, a fatoração QR de J_r. Para sistemas de grandes dimensões, um método iterativo, tal como o método do gradiente conjugado, pode ser mais eficiente. Se existe uma dependência linear entre as colunas de J_r, as iterações falharão, já que J_r^TJ_r se tornará singular.

Exemplo[editar | editar código-fonte]

Neste exemplo, o Algoritmo de Gauss-Newton será usado para ajustar um modelo a alguns dados, minimizando os erros das somas dos quadrados entre os dados e as previsões do modelo.

Numa experiência de biologia, estudando a relação entre a concentração de substrato ["S"] e a taxa de reação de uma reação mediada por enzimas, foram obtidos os dados da tabela a seguir:

i	1	2	3	4	5	6	7
[S]	0,038	0,194	0,425	0,626	1,253	2,500	3,740
taxa	0,050	0,127	0,094	0,2122	0,2729	0,2665	0,3317

É desejado encontrar uma curva (função modelo) com a fórmula

${\displaystyle {\text{taxa}}={\frac {V_{\text{max}}[S]}{K_{M}+[S]}}}$

que melhor se adapte aos dados, no sentido dos mínimos quadrados, com os parâmetros ${\displaystyle V_{\text{max}}}$ e ${\displaystyle K_{M}}$ a serem determinados.

Denotado por ${\displaystyle x_{i}}$ e ${\displaystyle y_{i}}$ o valor de ${\displaystyle [S]}$ e a taxa da tabela ${\displaystyle i=1,\dots ,7.}$ Seja ${\displaystyle \beta _{1}=V_{\text{max}}}$ e ${\displaystyle \beta _{2}=K_{M}.}$ Encontraremos ${\displaystyle \beta _{1}}$ e ${\displaystyle \beta _{2}}$ tal que a soma dos quadrados dos resíduos

${\displaystyle r_{i}=y_{i}-{\frac {\beta _{1}x_{i}}{\beta _{2}+x_{i}}}}$ (${\displaystyle i=1,\dots ,7}$)

será minimizada.

A Jacobiana ${\displaystyle \mathbf {J_{r}} }$ do vetor dos resíduos ${\displaystyle r_{i}}$ em relação às incógnitas ${\displaystyle \beta _{j}}$ é uma matriz ${\displaystyle 7\times 2}$ com ${\displaystyle i}$-th linhas de entrada

${\displaystyle {\frac {\partial r_{i}}{\partial \beta _{1}}}=-{\frac {x_{i}}{\beta _{2}+x_{i}}},\ {\frac {\partial r_{i}}{\partial \beta _{2}}}={\frac {\beta _{1}x_{i}}{\left(\beta _{2}+x_{i}\right)^{2}}}.}$

Começando com as estimativas iniciais de ${\displaystyle \beta _{1}}$=0,9 e ${\displaystyle \beta _{2}}$=0,2, depois de cinco iterações do Algoritmo de Gauss-Newton os valores otimizados ${\displaystyle {\hat {\beta }}_{1}=0,362}$ e ${\displaystyle {\hat {\beta }}_{2}=0,556}$ são obtidos. Podemos também determinar as erros: ${\displaystyle {\hat {\beta }}_{1}=0,36}$ ± ${\displaystyle 0,07}$ e ${\displaystyle {\hat {\beta }}_{2}=0,56}$ ± ${\displaystyle 0,35}$ com 80% de confiança.^[2] A soma dos quadrados dos resíduos diminuiu desde o valor inicial de 1.445 para 0,00784 depois da quinta iteração. O gráfico à direita mostra a curva determinada pelo modelo dos parâmetros otimizados e os dados observados.

Propriedades de Convergência[editar | editar código-fonte]

Pode ser mostrado^[3] que o incremento Δ é um sentido descendente para "S", e, se o algoritmo converge, então o limite é um ponto estacionário de "S". Contudo, a convergência não é garantida, nem mesmo a convergência local como no Método de Newton.

A taxa de convergência do Algoritmo de Gauss-Newton pode se aproximar do quadrático.^[4] O algoritmo pode convergir lentamente ou nunca se a suposição inicial estiver longe do mínimo ou se a matriz ${\displaystyle \mathbf {J_{r}^{T}J_{r}} }$ estiver mal condicionada. Por exemplo, considere o problema com m=2 equações e n=1 variáveis, dadas por:

${\displaystyle {\begin{aligned}r_{1}(\beta )&=\beta +1\\r_{2}(\beta )&=\lambda \beta ^{2}+\beta -1.\end{aligned}}}$

A otimização é em ${\displaystyle \beta =0}$. Se |λ| = 0, então o problema é de fato linear e o método converge em uma iteração. Se |λ| < 1, então o método converge linearmente e o erro decresce assintóticamente com um fator |λ| em cada iteração. No entanto, se |λ| > 1, então o método não converge nem mesmo localmente.^[5]

Derivação com o Método de Newton[editar | editar código-fonte]

No que segue, o Algoritmo de Gauss-Newton será derivado com o Método de Newton por otimização da função através de uma aproximação. Como consequência, a taxa de convergência do Algoritmo de Gauss-Newton será no máximo quadrática.

A relação de recorrência do Método de Newton para minimizar uma função "S" de parâmetros β, é

${\displaystyle {\boldsymbol {\beta }}^{(s+1)}={\boldsymbol {\beta }}^{(s)}-\mathbf {H} ^{-1}\mathbf {g} \,}$

onde g denota o vetor gradiente de S e H denota a Matriz de Hessian de S. Uma vez que ${\displaystyle S=\sum _{i=1}^{m}r_{i}^{2}}$, o gradiente é dado por:

${\displaystyle g_{j}=2\sum _{i=1}^{m}r_{i}{\frac {\partial r_{i}}{\partial \beta _{j}}}.}$

Elementos de Hessien são calculados através da diferenciação dos elementos do gradiente, ${\displaystyle g_{j}}$, com respeito a ${\displaystyle \beta _{k}}$

${\displaystyle H_{jk}=2\sum _{i=1}^{m}\left({\frac {\partial r_{i}}{\partial \beta _{j}}}{\frac {\partial r_{i}}{\partial \beta _{k}}}+r_{i}{\frac {\partial ^{2}r_{i}}{\partial \beta _{j}\partial \beta _{k}}}\right).}$

O método de Gauss-Newton é obtido ignorando os termos derivados de segunda ordem (o segundo termo nesta expressão). Isto é, o Hessian é aproximado por:

${\displaystyle H_{jk}\approx 2\sum _{i=1}^{m}J_{ij}J_{ik}}$

onde ${\displaystyle J_{ij}={\frac {\partial r_{i}}{\partial \beta _{j}}}}$ são entradas da Jacobiana J_r. O gradiente e o Hessien aproximado podem ser escritos numa notação matricial como:

${\displaystyle \mathbf {g} =2\mathbf {J_{r}} ^{\top }\mathbf {r} ,\quad \mathbf {H} \approx 2\mathbf {J_{r}} ^{\top }\mathbf {J_{r}} .\,}$

Estas expressões são substituídas na relação de recorrência acima pra obter as equações operacionais.

${\displaystyle {\boldsymbol {\beta }}^{(s+1)}={\boldsymbol {\beta }}^{(s)}+\Delta ;\quad \Delta =-\left(\mathbf {J_{r}} ^{\top }\mathbf {J_{r}} \right)^{-1}\mathbf {J_{r}} ^{\top }\mathbf {r} .}$

A convergência do método de Gauss-Newton não é garantida em todas as instâncias. A aproximação

${\displaystyle \left|r_{i}{\frac {\partial ^{2}r_{i}}{\partial \beta _{j}\partial \beta _{k}}}\right|\ll \left|{\frac {\partial r_{i}}{\partial \beta _{j}}}{\frac {\partial r_{i}}{\partial \beta _{k}}}\right|}$

que precisa ser capaz de ignorar os termos derivados de segunda ordem, pode ser válida em dois casos, nos quais a convergência é de se esperar.^[6]

1. Os valores da função ${\displaystyle r_{i}}$ são pequenos em magnitude, ao menos em torno do mínimo.
2. As funções são apenas "ligeiramente" não lineares, de modo que ${\displaystyle {\frac {\partial ^{2}r_{i}}{\partial \beta _{j}\partial \beta _{k}}}}$ seja relativamente pequena em magnitude.

Versões Aperfeiçoadas[editar | editar código-fonte]

Com o método de Gauss-Newton a soma dos quadrados S pode não decrescer em cada iteração. Contudo, uma vez que Δ é um sentido descendente, a menos que ${\displaystyle S({\boldsymbol {\beta }}^{s})}$ seja um ponto estacionário, mantem-se que ${\displaystyle S({\boldsymbol {\beta }}^{s}+\alpha \Delta )<S({\boldsymbol {\beta }}^{s})}$ para todos suficientemente pequenos ${\displaystyle \alpha >0}$. Assim, se ocorre divergência, uma solução é a de empregar uma fração ${\displaystyle \alpha }$, do vetor incremento Δ na atual fórmula.

${\displaystyle {\boldsymbol {\beta }}^{s+1}={\boldsymbol {\beta }}^{s}+\alpha \ \Delta }$.

Em outras palavras, o vetor incremento é muito longo, mas ele aponta "para baixo", então somente uma parte irá decrescer o objetivo da função S. Um valor ideal para ${\displaystyle \alpha }$ pode ser encontrado usando um algoritmo de linha de pesquisa, ou seja, a magnitude de ${\displaystyle \alpha }$ é determinada encontrando o valor que minimiza S, geralmente usando um método de pesquisa direto no intervalo ${\displaystyle 0<\alpha <1}$.

Nos casos em que a direção do vetor de deslocamento é tal que a fração otimizada, ${\displaystyle \alpha }$, é próxima de zero, um método alternativo para o tratamento de divergência é a utilização do algoritmo de Levenberg-Marquardt, também conhecido como o "método da região de segurança". As equações normais são modificadas de tal forma que o vetor de incremento seja virado na direção de descida mais acentuada.

${\displaystyle \left(\mathbf {J^{T}J+\lambda D} \right)\Delta =\mathbf {J} ^{T}\mathbf {r} }$,

onde D é uma matriz diagonal positiva. Note que quando D é a matriz identidade e ${\displaystyle \lambda \to +\infty }$, então ${\displaystyle \Delta /\lambda \to \mathbf {J} ^{T}\mathbf {r} }$, portanto a direção de Δ se aproxima da direção do gradiente ${\displaystyle \mathbf {J} ^{T}\mathbf {r} }$.

O chamado parâmetro de Marquardt, ${\displaystyle \lambda }$, também pode ser otimizado por uma linha de pesquisa, mas é ineficiente já que o vetor de deslocamento deve ser recalculado toda vez que ${\displaystyle \lambda }$ for alterado. Uma estratégia mais eficiente é a seguinte: quando a divergência ocorre, deve-se aumentar o parâmetro de Marquartdt até que haja uma diminuição em S. Então deve-se manter o valor de uma iteração para a outra, mas, se possível, diminuí-lo até que um valor de corte seja atingido quando o parâmetro de Marquardt pode ser definido em zero; a minimização de S se torna então um padrão de minimização de Gauss-Newton.

Referências[editar | editar código-fonte]

Fontes[editar | editar código-fonte]

• Björck, A. (1996). Numerical methods for least squares problems. [S.l.]: SIAM, Philadelphia. ISBN 0-89871-360-9 
• Fletcher, Roger (1987). Practical methods of optimization 2nd ed. New York: John Wiley & Sons. ISBN 978-0-471-91547-8 .
• Nocedal, Jorge; Wright, Stephen (1999). Numerical optimization. [S.l.]: New York: Springer. ISBN 0-387-98793-2