Algoritmo de Gauss-Newton

Dada "m" funções r = (r1, …, rm) de n variáveis 'β = (β1, …, βn), com m ≥ n', o Algoritmo de Gauss-Newton iterativamente encontra o mínimo das somas dos quadrados Começando com uma estimativa inicial β ( 0 ) {\displaystyle {\boldsymbol {\beta }}^{(0)}} para o mínimo, o método prossegue com as iterações é 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 (xi, yi), as funções ri são os resíduos Então, o método de Gauss-Newton pode ser expresso em termos da Jacobiana da função "f" como

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: É desejado encontrar uma curva (função modelo) com a fórmula que melhor se adapte aos dados, no sentido dos mínimos quadrados, com os parâmetros V max {\displaystyle V_{\text{max}}} e K M {\displaystyle K_{M}} a serem determinados. Denotado por x i {\displaystyle x_{i}} e y i {\displaystyle y_{i}} o valor de [ S ] {\displaystyle [S]} e a taxa da tabela i = 1 , … , 7. {\displaystyle i=1,\dots ,7.} Seja β 1 = V max {\displaystyle \beta _{1}=V_{\text{max}}} e β 2 = K M . {\displaystyle \beta _{2}=K_{M}.} Encontraremos β 1 {\displaystyle \beta _{1}} e β 2 {\displaystyle \beta _{2}} tal que a soma dos quadrados dos resíduos

Pode ser mostrado 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. O algoritmo pode convergir lentamente ou nunca se a suposição inicial estiver longe do mínimo ou se a matriz J r T J r {\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: A otimização é em β = 0 {\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.

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 β, é onde g denota o vetor gradiente de S e H denota a Matriz de Hessian de S. Uma vez que S = ∑ i = 1 m r i 2 {\displaystyle S=\sum _{i=1}^{m}r_{i}^{2}} , o gradiente é dado por: Elementos de Hessien são calculados através da diferenciação dos elementos do gradiente, g j {\displaystyle g_{j}} , com respeito a β k {\displaystyle \beta _{k}} 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: onde J i j = ∂ r i ∂ β j {\displaystyle J_{ij}={\frac {\partial r_{i}}{\partial \beta _{j}}}} são entradas da Jacobiana Jr. O gradiente e o Hessien aproximado podem ser escritos numa notação matricial como:

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 S ( β s ) {\displaystyle S({\boldsymbol {\beta }}^{s})} seja um ponto estacionário, mantem-se que S ( β s + α Δ ) < S ( β s ) {\displaystyle S({\boldsymbol {\beta }}^{s}+\alpha \Delta )<S({\boldsymbol {\beta }}^{s})} para todos suficientemente pequenos α > 0 {\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. 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 0 < α < 1 {\displaystyle 0<\alpha <1} .