Métodos de Gauss-Newton para problemas de qualidade mínimos não lineares : teoria, validação numérica e aplicação em Geofísica

Abstract

Resumo: Algoritmos de programação não-linear sao importantes na resolução de problemas de quadrados mínimos. Neste trabalho apresentamos um estudo teórico e computacional dos metodos de Newton e Gauss-Newton, analisando algumas de suas características, tais como o passo do metodo, principais pré-requisitos para funcionamento, e a convergencia. Abordamos os metodos de busca pseudo-aleatoria de Monte Carlo e Quasi-Monte Carlo, e mostramos exemplos de construcao de uma das sequencias de baixa dis-crepancia (a sequencia de Sobol) utilizadas na geracao das amostras do metodo de Quasi-Monte Carlo. Analisamos os resultados numericos de experimentos com versães classicas de cada metodo e versões híbridas (ou seja, metodos que combinam o metodo de (Quasi-)Monte Carlo com o metodo de Gauss-Newton). Os experimentos foram realizados com uma biblioteca de funcoes-objetivo em linguagem Fortran proposta por More, Garbow e Hillstrom. Comparamos os resultados observando o erro residual, quantidade de iterações utilizadas, eficiencia e robustez na resolucao de problemas clássicos da literatura, e aplicamos os míetodos a um problema de inversãao de dados sísmicos considerando um modelo elástico para meios estratificados.

Abstract: Nonlinear programming algorithms are important in solving least squares problems. We have presented a theoretical and computational study of Newton and Gauss-Newton methods by analyzing their characteristics (such as the step size and main assumptions) and convergence. We considered pseudo random search methods, namely the Monte Carlo and Quasi-Monte Carlo methods, showing examples of construction of one of the low discrepancy sequences (Sobol sequence) used on samples generation of QuasiMonte Carlo method. We analyzed numerical results of experiments using classical versions of each method and hybrid versions (i.e., combining QuasiMonte Carlo with the Gauss-Newton methods). The numerical experiments were carried out with a library of objective functions in Fortran programming language proposed by More, Garbow, and Hillstrom. We compared the results obtained looking at the residual error, number of iterations used, efficiency and robustness in solving classic literature problems, and applied the methods to a seismic inverse problem considering an elastic model for layered media.