Método iterativo baseado na iteração de Newton para problemas discretos mal postos

Abstract

Propomos um método iterativo para a resolução de problemas discretos mal postos baseado em iterações matriciais geradas através do método de Newton, conhecido por convergir para a pseudo-inversa de uma matriz. Essencialmente, tomando os iterados gerados pelo método de Newton matricial por $X_{k}$, construímos os vetores $x^{ (k)} = X_{k}b $, em que $b $ é o vetor com dados do problema. Por construção, estes iterados convergem para a solução de norma mínima do problema de mínimos quadrados $\min_{x\in\R^{n}} \|Ax-b\|_2$. Mostramos que a sequência $\{x^{ (k)}\} $ é quadraticamente convergente e ilustramos o seu comportamento numérico. No caso de dados de entrada com ruído, analisamos o comportamento de semi-convergência nos iterados e concluímos que as iterações devem ser truncadas para controlar a propagação do ruído. Como resultado, encontramos uma estimativa de erro para o caso em que o princípio da discrepância é utilizado para determinar o parâmetro de truncamento. Na tentativa de contornar o alto esforço computacional, estudamos variantes do método que incluem estratégias de projeção, resultando em alternativas atrativas para aplicação em problemas de grande porte. Diversos resultados numéricos são apresentados para ilustrar a efetividade do método em problemas-teste bem conhecidos da literatura.

Abstract : We propose an iterative method to solve discrete ill-posed problems based on matrix iterations generated by Newton's method, known to converge to the pseudoinverse of a matrix. Essentially, letting the Newton matrix iterate be $X_{k}$, we construct the vectors $x^{ (k)} = X_{k}b $, where $b$ is the data vector of the problem. By construction, these iterates converge to the minimum norm solution of the least squares problem $\min_{x\in\R^{n}} \|Ax-b\|_2$. We show that the sequence $\{x^{ (k)}\} $ is quadratically convergent and illustrate its numerical behavior. In the case of noisy data, we analyze the semi-convergence behavior of the iterates and conclude that the iterations must be truncated to control the propagation of the noise error. As a result, we derive an error estimate for the case when the discrepancy principle is used as stopping parameter rule. In order to overcome the high computational effort, we study variants of the method that include projection strategies, resulting on attractive alternatives that are well suited for large-scale problems. Several numerical results are presented to illustrate the effectiveness of the method on well known test problems from literature.