Algoritmo de Newton-Gauss

O algoritmo de Gauss-Newton (ou método de Gauss-Newton) é um método usado para resolver problemas de mínimos quadrados não-lineares. O algoritmo de Gauss-Newton pode ser visto como uma variante do método de Newton para encontrar um mínimo de uma função. Ao contrário do método de Newton, o algoritmo de Gauss-Newton somente pode ser usado para minimizar uma soma dos quadrados dos valores de uma função, mas ele tem a vantagem de que as derivadas segundas, que muitas vezes são difíceis de serem calculadas, não são usadas.

Problemas de mínimos quadrados não-lineares surgem, por exemplo, em regressão não-linear, quando se deseja encontrar os parâmetros em um modelo que melhor o ajustem aos valores observados.

O método leva o nome dos matemáticos Carl Friedrich Gauss e Isaac Newton.

Descrição

Dadas m funções r = (r₁, …, r_m) de n variáveis β = (β₁, …, β_n), com m ≥ n, o algoritmo de Gauss–Newton encontra o mínimo do somatório dos quadrados

$S(\boldsymbol \beta)= \sum_{i=1}^m r_i^2(\boldsymbol \beta).$

Partindo de um valor aproximado inicial $\boldsymbol \beta^{(0)}$ para o mínimo, o método é aplicado de forma iterativa

$\boldsymbol \beta^{(s+1)} = \boldsymbol \beta^{(s)}+\Delta,$

onde Δ é um passo pequeno. Temos então

$S(\boldsymbol \beta^{(s)} + \Delta) = S(\boldsymbol \beta^{(s)}) + \left[\frac{\partial S}{\partial \beta_i}\right] \Delta + \frac{1}{2} \Delta^\top \left[\frac{\partial^2 S(\beta)}{\partial \beta_i\partial \beta_j}\right] \Delta$.

Se definirmos a matriz Jacobiana

$\mathbf{J_r}(\boldsymbol \beta) = \left.\frac{\partial r_i}{\partial \beta_j}\right|_{\boldsymbol \beta}$,

podemos substituir

$\left[\frac{\partial S}{\partial \beta_i}\right]$ por $2\mathbf{J_r}^\top \mathbf{r}$

e a matriz Hessiana no lado direito pode ser aproximada por $2\mathbf{J_r}^\top \mathbf{J_r}$ (assumindo que os resíduos são pequenos), dando:

$S(\boldsymbol \beta^{(s)} + \Delta) \approx S(\boldsymbol \beta^{(s)}) + 2\mathbf{J_r}^\top \mathbf{r}\Delta + \Delta^\top \mathbf{J_r}^\top \mathbf{J_r}\Delta$.

Tomando a derivada com respeito a $\Delta$ e igualando-a a zero para encontrar uma solução:

$\frac{\partial{S(\boldsymbol \beta^{(s)} + \Delta)}}{\partial{\Delta}} \approx 2\mathbf{J_r}^\top \mathbf{r} + 2\mathbf{J_r}^\top \mathbf{J_r} \Delta = 0$.

Esta expressão pode ser rearranjada para dar as equações normais, as quais podem ser resolvidas para Δ:

$\left(\mathbf{J_r}^\top \mathbf{J_r} \right)\Delta = - \mathbf{ J_r} ^\top \mathbf{r}.$

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

$r_i(\boldsymbol \beta)= y_i - f(x_i, \boldsymbol \beta).$

Então, o incremento $\Delta$ pode ser expresso em termos do Jacobiano da função f, como

$\left( \mathbf{ J_f}^\top \mathbf{J_f} \right)\Delta = \mathbf{J_f}^\top \mathbf{r}.$

Referências

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