Orientador: Marcia Aparecida Gomes Ruggiero / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-08T19:52:35Z (GMT). No. of bitstreams: 1 Begiato_RodolfoGotardi_M.pdf: 3148290 bytes, checksum: 7f7f71d43fda9f9eaf918892f0f89468 (MD5) Previous issue date: 2007 / Resumo: o principal objetivo deste trabalho é a proposta de uma estratégia híbrida de globalização para o método de Newton-inexato. Assim como o método de Newton, o método de Newton-inexato tem sua convergência garantida somente em vizinhanças adequadas da solução do sistema e uma estratégia de globalização deve, portanto, ser incorporada. Estratégias de globalização se baseiam na minimização de funções de mérito e duas abordagens podem ser consideradas: busca linear e regiões de confiança. Neste trabalho optamos pelo uso conjunt0 das duas abordagens, resultando numa estratégia híbrida, envolvendo inicialmente uma seqüência de buscas lineares, e se necessário, prossegue-se com uma variação da estratégia Dogleg, proposta por Powell em 1970. Para a resolução aproximada de sistemas lineares foi utilizado o método GMRES, que faz parte de métodos de projeções sobre subespaços de Krylov. Este método possibilita a implementação com a estratégia matrix-free. Para reduzir o uso de requerimentos de memória, optamos ainda pelo uso do método GMRES com recomeços. A eficiência dos algoritmos desenvolvidos foi avaliada através da resolução -de um conjunto de sistemas não lineares acadêmicos e um conjunto de sistemas sistemas não-lineares resultantes' da discretização de problemas de valor de contorno. Estes testes compravaram a eficiência da estratégia híbrida empregada no processo de globalização / Abstract: The main objective of this work is to propose a hybrid globalization strategie for inexact-Newton method. Globalization strategies are based on line search or trust region procedures. In this work, we choose a hybrid strategy which involves a cycle of line search and a variation of Powell dogleg trust region. For solving the linear systems we chose the GMRES method with restarts and to avoid the calculation of Jacobian matrices we used a matrix-free strategie. The numerical performance of the algorithms was evaluated by means a set of academic problems and a set of nonlinear systems of boundary value problem discretization. These results showed the good performance of hybrid globalization strategy / Mestrado / Otimização Matematica / Mestre em Matemática Aplicada

Orientadores: Aurelio Ribeiro Leite de Oliveira, Carla Taviane Lucke da Silva Ghidini / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-20T05:01:05Z (GMT). No. of bitstreams: 1 Berti_LilianFerreira_M.pdf: 11222489 bytes, checksum: 8a581cf3762be9e96b4f77b7206e3112 (MD5) Previous issue date: 2012 / Resumo: Os métodos de pontos interiores têm sido amplamente utilizados para determinar a solução de problemas de programação linear de grande porte. O método preditor corretor, dentre todas as variações de métodos de pontos interiores, é um dos que mais se destaca, devido à sua eficiência e convergência rápida. Este método, em cada iteração, necessita resolver dois sistemas lineares para determinar a direção preditora corretora. Resolver estes sistemas lineares corresponde ao passo que requer mais tempo de processamento, devendo assim ser realizada de forma eficiente. Para resolver estes sistemas lineares a abordagem mais utilizada é a fatoração de Cholesky. No entanto, realizar a fatoração de Cholesky em cada iteração tem um alto custo computacional. Dessa forma, na busca de redução de esforços, precisamente, na redução do número de iterações foi desenvolvida a iteração continuada. Iteração continuada é uma iteração subsequente, realizada após o cálculo da direção preditora corretora, onde é determinada uma nova direção sem que seja necessário realizar uma nova fatoração de Cholesky. Os resultados computacionais dos testes realizados, principalmente em problemas de médio e grande porte mostraram que esta abordagem obtém bom desempenho em comparação com o método preditor corretor / Abstract: Interior point methods have been widely used in the solution of large linear programming problems. The predictor corrector method, among ali interior point variants, is one of mostly used due to its efficiency and convergence properties. This method needs the solution of two linear systems to determine the predictor corrector direction, in each iteration. Solving such systems corresponds to the step which requires more processing time. Therefore, it should be done efficiently. The most common approach to solve the linear systems is the Cholesky factorization, demanding in each iteration a high computacional effort. Thus, in search of effort reduction, in particular, to reduce the iterations number continued iteration was developed. The continued iteration is a subsequent iteration performed after the predictor corrector direction is computed, where a new direction is calculated without need to of Cholesky refactorization. The numerical tests show that the continued iteration performs better in comparison with the preditor corretor method / Mestrado / Matematica Aplicada / Mestre em Matemática Aplicada

Orientadores: Maria Cristina de Castro Cunha, Fermín Sinforiano Viloche Bazán / Tese (doutorado) - Universidade Estadual de Campionas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-21T19:25:47Z (GMT). No. of bitstreams: 1 Borges_LeonardoSilveira_D.pdf: 3354099 bytes, checksum: 22e0646185a1b6a6832ca570c099cde8 (MD5) Previous issue date: 2013 / Resumo: A resolução estável de problemas mal-postos discretos requer o uso de métodos de regularização. Dentre vários métodos de regularização existentes na literatura, um dos mais utilizados é o método de regularização de Tikhonovçuja eficiência depende da escolha do parâmetro de regularização. Existem vários métodos para selecionar um parâmetro apropriado tais como o princípio da discrepância de Morozov e métodos heurísticos como o critério da curva-L de Hansen, a Validação Cruzada Generalizada de Golub, Heath e Wahba e o método de ponto fixo de Bazán. Problemas mal-postos discretos de grande porte podem ser resolvidos por métodos iterativos como CGLS e LSQR desde que as iterações sejam interrompidas antes que a influência do ruído deteriore a qualidade das iteradas. Esta é uma tarefa difícil que ainda não foi abordada satisfatoriamente na literatura. Em uma tentativa de atenuar a dificuldade na escolha da iteração de parada, tais métodos podem ser combinados com o método de regularização de Tikhonov gerando os métodos híbridos como GKB-FP e W-GCV (ambos usam a matriz identidade como matriz de regularização). As contribuições desta tese incluem primeiramente novas informações referentes ao algoritmo GKB-FP e como este pode ser eficientemente implementado para o método de regularização de Tikhonov com a matriz de regularização sendo diferente da matriz identidade. Como segunda contribuição tem-se o desenvolvimento de um critério de parada automático para métodos iterativos para problemas "de grande porte", incluindo meios para incorporar informações a priori da solução (como regularidade, por exemplo) no processo iterativo. O método de regularização de Tikhonov usualmente está confinado apenas a um único parâmetro. Entretanto, alguns problemas apresentam soluções com distintas características que devem ser incorporadas na solução regularizada. Isso conduz ao método de regularização de Tikhonov com múltiplos parâmetros. A terceira contribuição desta tese é o desenvolvimento de um método baseado em iterações de ponto fixo para a seleção destes parâmetros e um algoritmo do tipo GKB-FP para problemas de grande porte. Por fim, os resultados teóricos obtidos nesta pesquisa são avaliados na construção de soluções numéricas para diversos problemas como restauração e super-resolução de imagens, problemas de espalhamento e outros obtidos de equações integrais de Fredholm / Abstract: Discrete ill-posed problems need to be regularized in order to be stably solved. Amongst several regularization methods, perhaps the most used is the method of Tikhonov whose effectiveness depends on a proper choice of the regularization parameter. There are considerable amount of parameter choice rules in the literature; these include the Discrepancy Principle by Morozov and heuristic methods like the L-curve criterion by Hansen, Generalized Cross Validation by Golub, Heath and Wahba, and a fixed point method due to Bazán. Large-scale discrete ill-posed problems can be solved by iterative methods like CGLS and LSQR provided that the iterations are stopped before the noise starts deteriorating the quality of the iterates. This is a difficult task which has not yet been addressed satisfactorily in the literature. In an attempt to alleviate the difficulty associated with selecting the regularization parameter, iterative methods can be combined with Tikhonov regularization giving rise to the so-called hybrid methods such as GKB-FP and W-GCV (both using the identity matrix as regularization matrix). The contributions of this thesis include further results concerning the theoretical properties of GKB-FP algorithm as well as the extension of GKB-FP to Tikhonov regularization using a general regularization matrix. Apart from this, as a second contribution, we propose an automatic stopping rule for iterative methods for large-scale problems, including the case where the methods are preconditioned via smoothing norms. Tikhonov regularization has been widely applied to solve linear ill-posed problems, but almost always confined to a single regularization parameter. Nevertheless, some problems have solutions with distinctive characteristics that must be included in the regularized solution. This leads to multi-parameter Tikhonov regularization problems. The third contribution of the thesis is the development of a fixed point method to select the regularization parameters in this multi-parameter case as well as a GKB-FP type algorithm which is well suited for large-scale problems. The proposed algorithms are numerically illustrated by solving several problems such as reconstruction and super-resolution image problems, scattering problems and others from Fredholm integral equations / Doutorado / Matematica Aplicada / Doutor em Matemática Aplicada

Orientador: Leonardo de Souza Mendes / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-24T11:34:10Z (GMT). No. of bitstreams: 1 Carvalho_SergioAntenorde_D.pdf: 4540873 bytes, checksum: 3ca0c6e6987e0376dfe4cf13e2294530 (MD5) Previous issue date: 1998 / Resumo: Este trabalho usa uma formulação volumétrica para calcular os campos gerados pela interação entre um corpo tridimensional e uma onda eletromagnética. Usamos o princípio equivalente para obter, das equações de Maxwell, uma equação integral que relaciona as correntes volumétricas equivalentes ao campo incidente. O método dos momentos é aplicado para transformar a equação integral em um sistema de equações algébricas, que pode ser resolvido numericamente. Para aplicar o método dos momentos expandimos as correntes equivalentes em termos de funções de base solenoidais. Estas funções não geram cargas espúrias dentro das regiões homogêneas do corpo, assim nós podemos aplicar o método a corpos com altos valores de constante dielétrica. As funções são definidas sobre tetraedros, o que permite uma melhor discretização do corpo. Até onde conhecemos, esta é a primeira vez que estas funções são usadas para analisar problemas harmônicos no tempo. Um novo método iterativo de solução da equação integral é desenvolvido. O método consiste em dividir o corpo em partes, cada uma com a sua matriz momento, que determina o campo induzido por uma excitação. A solução completa é construída pela interação entre todas as partes, sendo o campo incidente a excitação inicial. Apresentamos resultados mostrando a aplicabilidade da formulação com o uso das funções solenoidais e do método iterativo. Analisamos o espalhamento por um cubo dielétrico homogêneo e não homogêneo, esfera homogênea e não homogênea e por conjuntos de cubos. Os resultados concordaram com aqueles disponíveis na literatura e com os obtidos com o uso de funções pulso. No caso da esfera comparamos os resultados com os obtidos através da serie de Mie, com uma boa concordância / Abstract: This work deals with the use of a volume formulation to calculate the field distribution of tridimensional bodies. We use the equivalente principle to obtain, from Maxwell's equations, an integral equation that relates the equivalent volume polarization currents to the incident field. The method of moments is applied to transform the integral equation into a system of algebraic equations that can be solved numerically. To apply the method of moments we first expand the equivalent currents in terms of solenoidal basis functions. These functions do not generate spurious charges inside the homogeneous portion of body so we can apply this method to the bodies with high values of dielectric constant. The functions are defined on tetrahedrons permitting a better fitting of the object to be discretized. As far as we know, this is the first time that these functions are used to analyze time-harmonic problems. A new iterative method of solution of the integral equation is developed. The method consists in the division of the body in parts, with every part being characterized by a matrix moment that determines the induced field by excitation. The entire solution is built by interaction among the parts with the incident field like initial excitation. We present results showing the effectiveness of the formulation with the use of solenoidal iunctions. We analyze scattering by homogeneous and inhomogeneous dielectric cube, homogeneous and inhomogeneous sphere and by ensemble of cubes. The results are in good agreement with results found in the published literature and with those obtained using pulse basis functions. In the case of the sphere we compare the results with those obtained using the Mie's series / Doutorado / Doutor em Engenharia Elétrica

Orientadores: Marcia A. Gomes Ruggiero, Vera Lucia da Rocha Lopes / Tese (doutorado) - Universidade Estadual de Campinas. Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-04T14:53:24Z (GMT). No. of bitstreams: 1 ToledoBenavides_JuliaVictoria_D.pdf: 2835915 bytes, checksum: 1b77270a65a21cc42d9aa81819e4acc4 (MD5) Previous issue date: 2005 / Resumo: Neste trabalho, apresentamos um método de Newton inexato através da proposta de uma nova escolha para o termo forçante. O método obtido é globalizado através de uma busca linear robusta e suas propriedades de convergência são demonstradas. O passo de Newton inexato é obtido pela resolução do sistema linear através do método GMRES com recomeços, GMRES(m). Em testes computacionais observamos a ocorrência da estagnação em GMRES(m) e um acréscimo inaceitável na norma da função nas primeiras Iterações do método. Para contornar estas dificuldades são propostas estratégias de implementação computacional simples e que não exigem alterações internas no algoritmo do GMRES, possibilitando a interação com softwares já disponíveis. Exaustivos testes numéricos foram realizados, os quais nos permitiram concluir que a proposta para o termo for¸cante e as estratégias introduzidas foram bem sucedidas, resultando em um algoritmo robusto, com propriedade de convergência global e taxa superlinear de convergência / Abstract: In this work it is presented an inexact Newton method by a new choice for the forcing term. A globalization of the new method is done by introducing a robust line search strategy. Convergence properties are proved. The inexact Newton step is obtained through the restarted GMRES, GMRES (m), applied for solving the linear systems. Numerical experiments showed a stagnation of the GMRES (m) and also an occurrence of a great increase in the norm of the function at the initial iterations. Some strategies were proposed to avoid these drawbacks. These strategies are characterized by their simplicity of implementation and also by the fact that they do not need internal modifications of the GMRES algorithm. So, the interaction with available softwares are trivial. A bunch of numerical experiments were performed. With them it can be concluded that the new choice for the forcing term and the strategies incorporated in the algorithm were successfull. The resulting algorithm is then robust and has global convergence property with supelinear convergence rate / Doutorado / Doutor em Matemática Aplicada

Orientador: Hugo Enrique Hernández-Figueroa / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-16T06:54:22Z (GMT). No. of bitstreams: 1 Claudio_Kleucio_D.pdf: 3139134 bytes, checksum: 900508bd03693258d7011b6af9debd55 (MD5) Previous issue date: 2010 / Resumo: O método de elementos finitos é largamente empregado na modelagem de problemas de eletromagnetismo. A modelagem implícita deste método recai em resolver sistemas de equações lineares esparsas, esta etapa é de alto custo computacional. Este trabalho propõe alternativas com o objetivo de melhorar o desempenho computacional das aplicações provenientes de formulações via elementos finitos, através do aproveitamento de soluções de sistemas de equações lineares por métodos direto e iterativo, para simular dispositivos ópticos com as características físicas alteradas constantemente. Na solução dos sistemas de equações, utilizou-se o método direto com Small Rank Adjustment e o método iterativo gradiente bi-conjugado estabilizado precondicionado com análises de reaproveitamento do precondicionador ILUT. Nos estudos desenvolvidos obteve-se um melhor desempenho computacional quando se utilizou o método iterativo. Estes resultados são de grande importância na área de otimização de dispositivos fotônicos tais como acopladores, filtros, demultiplexadores, etc, pois a otimização destes dispositivos consiste em avaliar várias configurações do espaço de busca, implicando em resolver vários sistemas de equações lineares similares provenientes do método de elementos finitos. / Abstract: The Finite Element Method is one of the most popular numerical tools in electromagnetics. Implicit schemes require the solution of sparse linear equation systems, this step demands a lot of computational time. This work proposes alternatives enhancements to obtain better computational performance of such implicit schemes. This was made through the improvement of direct and iterative methods, for problems which may be interpreted as perturbations of a given original one. This is very important specially in the optimization process of devices, due to the fact that one needs to solve many linear systems with little changes at each step, to explore the search space, so many perturbed linear systems are solved to obtain the optimum device. For direct methods the Small Rank Adjustment technique was used, while for iterative methods, the Preconditioned Gradient Stabilized Biconjugate Method reusing the preconditioner, were adopted. The applications were focused on the design of photonic devices, like couplers, filters, demultiplexers, etc. / Doutorado / Telecomunicações e Telemática / Doutor em Engenharia Elétrica

Orientador: Vera Lucia da Rocha Lopes / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-10T21:50:16Z (GMT). No. of bitstreams: 1 LopezErazo_TulioEmiro_M.pdf: 12666478 bytes, checksum: df86afcc58096ac12697d7d0fefe8ee5 (MD5) Previous issue date: 2007 / Resumo: No presente trabalho estudamos métodos numéricos que resolvem um problema de programação não linear com restrições lineares de desigualdade e de igualdade, os quais não fazem uso explícito do gradiente da função objetivo nem tampouco de aproximações ao mesmo. Um método de decréscimo su_ciente e um método de decréscimo simples são estudados. O primeiro, procura melhores valores para a função objetivo ao longo de um conjunto de direções, as quais geram positivamente o cone poliedral convexo no ponto atual. O segundo método procura melhorar o valor da função objetivo ao longo de um conjunto de direções, as quais, dependendo do ponto atual, ou geram positivamente todo o espaço Rn, ou geram positivamente o cone poliedral convexo em tal ponto. Algoritmos dos métodos, comentários das implementa ções feitas e testes numéricos de tais implementações com problemas da coleção Hock-Schittkowski são feitos ao final do trabalho / Abstract: In the present work we study numerical methods that solve a problem of nonlinear programming with linear inequality and equality constraints, which do not make explicit use either neither of the gradient of the objective function nor approaches to the same one. A method of su_cient decrease and a method of simple decrease are studied. The _rst one, looks for better values for the objective function throughout a set of directions, which positively generate the convex polyhedral cone in the current point. The second method looks for to improve the value of the objective function throughout a set of directions, which, depending on the current point, either generates positively the whole spaces, or positively generates the convex polyhedral cone in this point. Algorithms of the methods, commentaries of the implementations done and numerical tests of such implementations with problems of the Hock-Schittkowski collection are made at the end of the work / Mestrado / Mestre em Matemática Aplicada

Orientadores: Carla Taviane Lucke da Silva Ghidini, Aurelio Ribeiro Leite de Oliveira / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica / Made available in DSpace on 2018-08-26T07:23:54Z (GMT). No. of bitstreams: 1 Silva_Marileneda_M.pdf: 942860 bytes, checksum: 97260f526fda7ee0cb3346887580c3fa (MD5) Previous issue date: 2014 / Resumo: Neste trabalho, consideramos o método preditor-corretor, que é uma das variantes mais importantes dos métodos de pontos interiores devido à sua eficiência e convergência rápida. No método preditor-corretor, é preciso resolver dois sistemas lineares a cada iteração para determinar a direção preditora-corretora. A resolução desses sistemas é o passo que requer mais tempo de processamento, devendo, assim, ser realizada de maneira eficiente. Para obter a solução dos sistemas lineares do método preditor-corretor, consideramos dois métodos do subespaço de Krylov: MINRES e GC (método dos gradientes conjugados). Para que esses métodos convirjam mais rapidamente, um precondicionador especialmente desenvolvido para os sistemas lineares oriundos dos métodos de pontos interiores é usado. Experimentos computacionais, em um conjunto variado de problemas de programação linear, foram realizados com o intuito de analisar a eficiência e robustez dos métodos de solução dos sistemas lineares / Abstract: In this work, we consider the predictor-corrector method, which is one of the most important variants of interior point methods due to its efficiency and fast convergence. In the predictor-corrector method, we must solve two linear systems at each iteration to determine the predictor-corrector direction. The solution of these systems is the step that requires more processing time and should therefore be performed efficiently. For the solution of linear systems are two Krylov subspace methods considered: MINRES and CG(the conjugate-gradient method). For these methods a preconditioner specially developed for linear systems arising from interior point methods is used. Computational experiments on a set of linear programming problems were performed in order to analyze the efficiency and robustness of the methods when solving such linear systems / Mestrado / Matematica Aplicada / Mestra em Matemática Aplicada

Orientador: Roberto Andreani / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-04T05:03:19Z (GMT). No. of bitstreams: 1 Gaujoux_RenaudGilles_M.pdf: 1743739 bytes, checksum: a3548a59bc983f4398cb0136c62c1d6a (MD5) Previous issue date: 2005 / Resumo: Esta dissertação trata da aplicação de um método de tipo Newton generalizado aos sistemas KKT. Graças às funções chamadas de NCP, o sistema KKT pode ser reformulado como uma equação do tipo H(z) = O, onde H é uma função semi-suave. Nos preliminares teóricos apresentamos os conceitos importantes para a análise desse tipo de sistema quando a função involvida não é diferenciável. Trata-se de subdiferencial, semi-suavidade, semi-derivada. Então, usando um ponto de vista global, descrevemos de uma vez só as diferentes generalizações do método de Newton, apresentando as condições suficientes de convergência local. Uma versão globalizada do método é também detalhada. Com o fim de aplicar o algoritmo à reformulação semi-suave do sistema KKT, estudamos as propriedades da função H, primeiro independentemente da função NCP usada. Então analisamos o caso de três funções NCP particulares: a função do Mínimo, a função de Fischer-Burmeister, a função de Fischer-Burmeister Penalizada. Apresentamos os resultados de testes numéricos que comparam o desempenho do algoritmo quando usa as diferentes funções NCP acima / Abstract: This work deals with the use of generalized Newton type method to solve KKT systems. By the mean of so called NCP functions, any KKT system can be writen as an equation of type H(z) = O, where H is a semismooth function. In a teorical preliminaries part, we present some key notions for the analysis of such a type of system, whose the involved function is not differentiable. It deals with subdifferential, semismoothness, semiderivative. Then, tackling the problem with a very general point of view, we make a unified description of different generalizations of N ewton method, giving sufficient local convergence conditions. More over, we detail a possible globalization of such methods. In order to use this global algorithm to solve semismooth form of KKT systems, we study some of the H function's properties, first without specifying any underlying NCP function, and then in the case of three known NCP functions: the minimum function, the Fischer-Burmeister function and the penalized Fischer-Burmeister function. Finally, we give the results of numerical tests, which compare the algorithm's performance for each of these three NCP functions / Mestrado / Matematica Aplicada / Mestre em Matemática Aplicada

CAPES / Este trabalho objetiva apresentar as ideias matemáticas principais da Samambaia de Barnsley, um fractal que recria uma imagem que assemelha-se a uma folha de samambaia da variedade Black Spleenwort e tem como base quatro transformações afins elementares. Algumas mutações da Samambaia de Barnsley são também apresentadas. / This work aims to present the main mathematical ideas of Barnsley’ Fern, a fractal that recreates an image that resembles a fern leaf of the Black Spleenwort variety and is based on four elementary affine transformations. Some mutations of Barnsley’ Fern are also presented.