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

Los autovalores y autovectores son elementos muy utilizados en diversos problemas como análisis de estructuras, reconocimiento de imágenes, compresión de datos, solución de problemas electrodinámicos, entre otros. Existen muchos algoritmos para calcular y tratar con autovalores y autovectores mediante el uso de computadoras, sin embargo, cuando solo se requiere uno o unos pocos autovalores (los más significativos) y autovectores, se puede optar por Power Method o la Iteración Lanczos. Por otro lado, factores como la cantidad de información a procesar o la precisión deseada pueden significar tiempos de ejecución no aceptables para ciertas aplicaciones, surgiendo la alternativa de realizar implementaciones paralelas, siendo la arquitectura CUDA una de la mejores opciones actualmente. En la presente tesis se propone diseñar e implementar un algoritmo paralelo para la iteración Lancos en arquitectura CUDA, el cual es un método para el cálculo del mayor autovalor y su correspondiente autovector. La propuesta esta dividia en tres bloques principales. El primer bloque realiza la tridiagonalización parcial de una matriz cuadrada simétrica. El segundo bloque calcula la descomposición de Schur de la matriz tridiagonal obteniendo los autovectores y autovalores de esta. El tercer bloque calcula el mayor autovalor y su correspondiente autovector de la matriz inicial a partir de lo obtenido en etapas anteriores y determinará si es necesario seguir realizando cálculos. Los bloques trabajan iterativamente hasta encontrar resultados que se ajusten a la precisión deseada. Además de la implementación paralela en CUDA, se realizaron implementaciones en el entorno de simulación MATLAB y en lenguaje C secuencial, con el propósito de comparar y verificar una correcta y eficiente implementación paralela. Los resultados computacionales evaluados para una matriz de 4000 _ 4000 elementos reflejan un rendimiento de 13;4 y 5;8 al compararse la implementación en CUDA con MATLAB y C secuencial respectivamente. Estos rendimientos tienden a crecer mientras mayor sea el tamaño de la matriz. La organización de la tesis es: en el primer capítulo se describe la problemática del tema. En el segundo capítulo se explica la teoría correspondiente a Power Method y Lanczos, así como los algoritmos necesarios. En el capítulo tres se exponen conceptos fundamentales sobre arquitectura CUDA. El diseño del algoritmo paralelo se desarrolla en el capítulo cuatro. Finalmente, en el capítulo cinco, se muestran y analizan los resultados computacionales, seguidos de las conclusiones, recomendaciones y bibliografía.

[ES] El diseño de métodos iterativos para resolver ecuaciones y sistemas de ecuaciones no lineales es una tarea importante y desafiante en el campo del Análisis Numérico. La no linealidad es una característica de muchos de los fenómenos físicos. Mecánica de fluidos y plasma, dinámica de gases, reacciones químicas, combustión, ecología, biomecánica, problemas de modelado económico, teoría del transporte y muchos otros fenómenos están todos gobernados inherentemente por ecuaciones no lineales. Por esta razón, una proporción cada vez mayor de la investigación matemática moderna se dedica al análisis de sistemas y procesos no lineales. En una era caracterizada por la disponibilidad de grandes cantidades de datos, el procesado y análisis de esta información se traduce de forma directa en la resolución de problemas cuya dimensión es cada vez mayor. Aunque en las últimas décadas se ha producido un desarrollo exponencial en la computación, sigue siendo esencial el diseño de algoritmos iterativos que garanticen la convergencia a la solución de un problema de forma rápida y eficiente. Siguiendo estas premisas, el objetivo fundamental que se persigue con el diseño de nuevos métodos iterativos, siendo también uno de los principales objetivos de la presente Tesis Doctoral, es la aproximación de soluciones de problemas no lineales garantizando un cierto equilibrio entre la velocidad con que se obtiene dicha aproximación, la fiabilidad de la misma y el coste computacional requerido en el conjunto de todo el proceso iterativo. Poder medir o cuantificar este equilibrio es, por tanto, una de las piezas esenciales de todo este proceso. Por medio del orden de convergencia, somos capaces de comparar la velocidad con que los esquemas iterativos se aproximan a la solución buscada. El coste computacional requerido a cada iteración del proceso es directamente proporcional al número de iteraciones que se necesitan para aproximar esta solución. Por tanto, acelerar la convergencia de un método se convierte en una necesidad en el diseño de esquemas eficientes. Por otro lado, todo algoritmo iterativo requiere de al menos un punto inicial para comenzar el proceso de cálculo de las iteraciones sucesivas. Por este motivo, el estudio de la influencia de las estimaciones iniciales en la convergencia de un método es también de una gran relevancia, ya que permite determinar la estabilidad de éste en función de los iterados iniciales. Este estudio se realiza utilizando herramientas de dinámica discreta, tanto real como compleja, para determinar, además de otras caracterizaciones, los puntos iniciales más adecuados y los métodos más estables de una familia de esquemas iterativos. El análisis numérico y dinámico realizado en esta memoria hace posible la propuesta de métodos iterativos eficientes que aproximen soluciones de problemas multidimensionales no lineales y ecuaciones en derivadas parciales de forma eficaz. A partir del estudio completo desarrollado utilizando las herramientas anteriormente descritas, presentamos esta Tesis Doctoral para la obtención del título de Doctora en Matemáticas. / [EN] The design of iterative methods for solving nonlinear equations and nonlinear systems is an important and challenging task in the Numerical Analysis. Nonlinearity is a characteristic of many of the physical phenomena. Fluid and plasma mechanics, gas dynamics, chemical reactions, combustion, ecology, biomechanics, economic modeling problems, transport theory and many other phenomena are all inherently governed by nonlinear equations. For this reason, an increasing proportion of mathematical modern research is devoted to the analysis of systems and nonlinear processes. In a period characterized by the availability of large amounts of data, the processing and analysis of this information translates directly into the resolution of problems whose dimension is increasing. Although there has been an exponential development in computing in the last decades, it is still essential to design iterative algorithms that guarantee the convergence to the solution of a problem in a fast and efficient way. Following these assumptions, the main goal followed in the design of new iterative methods, being also one of the main objectives of this Doctoral Thesis, is the approximation of the solutions of nonlinear problems ensuring a certain balancing between the speed at which this approximation is obtained, the reliability of the approximation and the computational cost required in the whole iterative process. Being able to measure or quantify this balance is therefore one of the essential parts of this whole process. By means of the order of convergence, we are able to compare the speed with which the iterative schemes approximate the requested solution. The required computational cost for each iteration of the process is directly proportional to the number of iterations needed to approximate this solution. Therefore, accelerating the convergence of a method becomes a need in the design of efficient schemes. On the other hand, any iterative algorithm requires at least a starting point to begin the calculation of the successive iterations. For this reason, the study of the influence of initial estimates on the convergence of a method is also of high relevance, since it allows to determine the stability of the method depending on the initial iterations. This study is carried out using tools of discrete dynamics, both real and complex, to determine, in addition to other characterizations, the most suitable starting points and the most stable methods in a family of iterative schemes. The numerical and dynamical analysis carried out in this work makes it possible to propose efficient iterative methods that approximate solutions to nonlinear multidimensional problems and partial differential equations in an effective way. Based on the complete study developed using the tools described above, we present this Doctoral Thesis for gaining the title of Doctor in Mathematics. / [CA] El diseny de mètodes iteratius per resoldre equacions i sistemes d'equacions no lineals es una tasca important i desafiant al domini de l'Anàlisi Numèric. La no linealitat és una característica de molts dels fenòmens físics. Mecànica de fluids i plasma, dinàmica de gasos, reaccions químiques, combustió, ecologia, biomecànica, problemes de models econòmics, teoria del transport i molts altres fenòmens estan tots governats inherentment per equacions no lineals. Per aquest motiu, una proporció cada vegada major de la investigació matemàtica moderna es dedica a l'anàlisi de sistemes i processos no lineals. En una era caracteritzada per la disponibilitat de grans quantitats de dades, el processat i anàlisi d'aquesta informació es tradueix de forma directa en la resolució de problemes la dimensió dels quals es cada vegada major. Malgrat que a les últimes dècades s'ha produït un desenvolupament exponencial a la computació, segueix sent essencial el diseny d'algorismes iteratius que garanteixen la convergència a la solució d'un problema de forma ràpida i eficient. Seguint aquestes premisses, l'objectiu fonamental que es persegueix amb el disseny de nous mètodes iteratius, sent també un dels principals objectius de la present Tesi Doctoral, és l'aproximació de solucions de problemes no lineals garantint un cert equilibri entre la velocitat amb què obtenen aquesta aproximació, la fiabilitat de la mateixa i el cost computacional requerit al conjunt de tot el procés iteratiu. Poder medir o quantificar aquest equilibri és, per tant, una de les peces essencials de tot aquest procés. Mitjançant l'ordre de convergència, tenim la capacitat de comparar la velocitat amb la qual els esquemes iteratius s'aproximen a la solució buscada. El cost computacional requerit a cada iteració del procés és directament proporcional al nombre d'iteracions que es necessiten per a aproximar aquesta solució. Per tant, accelerar la convergència d'un mètode es converteix en una necessitat al disseny d'esquemes eficients. D'una altra banda, tot algorisme iteratiu requereix d'almenys un punt inicial per començar el procés de càlcul de les iteracions successives. Per aquest motiu, l'estudi de la influència de les estimacions inicials a la convergència d'un mètode és també molt rellevant, ja que permet determinar l'estabilitat d'aquest en funció dels iterats inicials. Aquest estudi es realitza utilitzant eines de dinàmica discreta, tant real com complexa, per determinar, a més d'altres caracteritzacions, els punts inicials més adients i els mètodes més estables d'una familia d'esquemes iteratius. L'anàlisi numèric i dinàmic realitzat en aquesta memòria fa possible la proposta de mètodes iteratius eficients que aproximen solucions de problemes multidimensionals no lineals i equacions en derivades parcials de forma eficaç. A partir de l'estudi complet desenvolupat utilitzant les eines descrites anteriorment, presentem aquesta Tesi Doctoral per a l'obtenció del títol de Doctora en Matemàtiques. / Garrido Saez, N. (2020). Diseño, análisis y estabilidad de métodos iterativos con memoria para la resolución de ecuaciones y sistemas no lineales [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/149573

Many problems in science, engineering or economy involve the search of the solution of an equation. Since ancient times, the modelling of nature problems has attracted a lot of interest, in order to predict the behaviour of a system. There are several techniques to find the solution of an equation. We are focusing in the iterative methods. From an iterative scheme we are able to know the solution of a nonlinear function, provided there exist suitable methods. In addition to the well-known Newton's and Steffensen's methods, we are implementing methods with higher order of convergence. The classification of the methods depending on their intrinsic features is giving us the chance to evaluate the goodness or the convenience of an iterative method. As in every engineering or mathematical problem, we will find a tradeoff solution. Another way to classify methods, complementary to the previous one, is the complex dynamics study. The fixed point operator associated to every iterative methods when it is applied over a nonlinear function is the seed for developing tools to characterize every scheme on the complex plane. The graphical representation of the iterative methods dynamics has occupied a broad part of the time of the current research. The dynamical plane is a powerful tool to visualize the stability of a method, the size of their basins of attraction or the suitability of some starting points to initialize the iterations. As well, for uniparametric families, the parameters plane will cooperate in the chose of the right member of the family. Dynamical planes can be interpreted as an approach to fractals. The fractal dimension is being introduced as a way to measure how intricate is the Julia set of an iterative method. Fractals belong to the borderline between the determinism and the theory of chaos. So we are transferring concepts of both issues on the fractal study. As an application of the iterative methods and the complex dynamics, we are showing the preliminary orbit determination of artificial satellites. From the position of a satellite in two different times, it is possible to guess the parameters of the ellipse described by the satellite. For this purpose, we are applying an algorithm that includes a classical resolution method. Our contribution consists in the use of our iterative methods to improve the performance of the system. The possible applications of iterative methods for finding solutions of equations are beyond orbital mechanics. The design of digital filters, the digital image processing or the characterization of radio-frequency links are some of the examples. From the previous concepts, we introduce this Doctoral Thesis for gaining the title of Philosophae Doctor in Mathematics. First chapters contextualize the involved topics, while the following ones present the papers published in international scientific journals as the fruit of the research. / Numerosos problemas de la ciencia, la ingeniería o la economía requieren de la búsqueda de soluciones de una ecuación. Desde tiempos remotos se ha tratado de modelizar problemas presentes en la naturaleza con expresiones que, al fin y al cabo, permitan conocer a priori cómo se va a comportar un sistema. Entre las técnicas utilizadas para dicha búsqueda de soluciones encontramos los métodos iterativos. Iterar a partir de una serie de expresiones nos va a permitir conocer la solución de una función no lineal a partir de esquemas adecuados para ello. Además de los conocidos métodos de Newton y Steffensen, se van a implementar métodos con mayor orden de convergencia. Clasificar los métodos iterativos en función de sus características intrínsecas nos va a permitir valorar la bondad o la conveniencia del uso de un método iterativo u otro. Como en todos los problemas de ingeniería y matemáticas, tendremos que obtener una solución de compromiso. Otra de las caracterizaciones existentes, complementaria a la anterior, es el estudio de la dinámica compleja. El operador de punto fijo asociado a cada uno de los métodos iterativos cuando se aplica sobre una función no lineal va a permitir que caractericemos cada uno de los esquemas en el plano complejo. Buena parte del trabajo desarrollado se ha centrado en la representación gráfica de la dinámica de los métodos iterativos. El plano dinámico es una herramienta que nos permite visualizar la estabilidad de un método, el tamaño de sus cuencas de convergencia o la idoneidad de determinados puntos iniciales para comenzar a iterar. Asimismo, para familias de métodos uniparamétricas, el plano de parámetros va a colaborar en la elección del miembro de la familia más adecuado. Interpretando los planos dinámicos como una aproximación a los fractales, presentaremos la dimensión fractal como un factor de medida de lo intrincado que puede resultar el conjunto de Julia asociado a un método iterativo. Los fractales pertenecen a la frontera entre el determinismo y la teoría del caos, de forma que podremos transferir conceptos de ambas disciplinas sobre el estudio fractal. Mostraremos como aplicación de los métodos iterativos y la dinámica compleja la determinación de órbitas preliminares de satélites artificiales. A partir de la posición de un satélite en dos instantes diferentes, es posible determinar los parámetros de la elipse que describe. Para ello, utilizaremos un algoritmo en el que se incluye un método clásico de resolución para, a continuación, mejorar sus prestaciones con nuestras propuestas de métodos iterativos. Basándonos en la búsqueda de soluciones y en los métodos iterativos como técnica de obtención de soluciones, las aplicaciones abarcan campos más allá de la mecánica orbital. El diseño de filtros digitales, el procesado digital de imágenes o la caracterización de enlaces de radiofrecuencia son algunos de los ejemplos de aplicación. A partir de los conceptos anteriores, presentamos esta Tesis Doctoral para la obtención del título de Doctor en Matemáticas, contextualizando la temática en los primeros capítulos para, a continuación, presentar las publicaciones en revistas internacionales como fruto de la investigación. / Nombrosos problemes de la ciència, la ingenieria o l'economia requereixen de la cerca de solucions d'una ecuació. Des de temps llunyans s'ha tractat de modelitzar problemes presents a la natura amb expressions que, al cap i a la fi, permeten conèixer a priori el comportament d'un sistema. Entre les tècniques emprades per tal cerca de solucions trobem els mètodes iteratius. Iterar a partir d'una sèrie d'expressions ens permetrà conèixer la solució d'una funció no lineal a partir d'esquemes adequats. A més dels coneguts mètodes de Newton i Steffensen, s'implementaran mètodes amb major ordre de convergència. Classificar els mètodes iteratius en funció de les seues característiques intrínseques ens permetrà avaluar la bondat o la conveniència de l'ús d'un mètode iteratiu o d'un altre. Com a la majoria de problemes d'ingenieria i matemàtiques, haurem de trobar una solució de compromís. Altra de les caracteritzacions existents, complementària a l'anterior, és l'estudi de la dinàmica complexa. L'operador de punt fix associat a cadascun dels mètodes iteratius quan s'aplica sobre una funció no lineal permetrà la caracterització de cada esquema al pla complex. Bona part del treball desenvolupat s'ha centrat en la representació gràfica de la dinàmica dels mètodes iteratius. El pla dinàmic es una eina que ens permet visualitzar l'estabilitat d'un mètode, la mida de les seues conques de convergència o la idoneïtat de determinats punts inicials per a començar a iterar. Així mateix, per a famílies de mètodes uniparamètriques, el pla de paràmetres col·laborarà en l'elecció del membre de la família més adequat. Interpretant els plànols dinàmics com una aproximació als fractals, presentarem la dimensió fractal com un factor per a mesurar quant d'intrincat es troba el conjunt de Julia associat a un mètode iteratiu. Els fractals pertanyen a la frontera entre el determinisme i la teoria del caos, de manera que podrem transferir conceptes d'ambdues disciplines sobre l'estudi fractal. Mostrarem com aplicació dels mètodes iteratius i la dinàmica complexa la determinació d'òrbites preliminars de satèl·lits artificials. A partir de la posició d'un satèl·lit en dos instants diferents, és possible determinar els paràmetres de l'el·lipse que descriu. Per això, utilitzarem un algoritme en el qual s'inclou un mètode clàssic de resolució per, a continuació, millorar les seues prestacions amb les nostres propostes de mètodes iteratius. Basant-nos en la cerca de solucions i en els mètodes iteratius com a tècnica d'obtenció de solucions, les aplicacions abasten camps més enllà de la mecànica orbital. El disseny de filtres digitals, el processament digital d'imatges o la caracterització d'enllaços de radiofrequència son alguns dels exemples d'aplicació. A partir dels conceptes anteriors, presentem aquesta Tesi Doctoral per a l'obtenció del títol de Doctor en Matemàtiques, contextualitzant la temàtica als primers capítols per, a continuació, presentar les publicacions en revistes internacionals com a fruit de la investigació. / Chicharro López, FI. (2017). ANÁLISIS DINÁMICO Y APLICACIONES DE MÉTODOS ITERATIVOS DE RESOLUCIÓN ECUACIONES NO LINEALES [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/83582

Proyecto DGSIC PB98-0977

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

El problema de la resolución de ecuaciones y sistemas de ecuaciones no lineales figura entre los más importantes en la teoría y la práctica, no sólo de las matemáticas aplicadas, sino también de muchas ramas de las ciencias, la ingeniería, la física, la informática, la astronomía, las finanzas, . . . El gran número de científicos que han trabajado recientemente en este tema muestran un alto nivel de interés contemporáneo. Aunque el rápido desarrollo de las computadoras digitales llevó a la aplicación efectiva de muchos métodos numéricos, en la realización práctica, es necesario resolver varios problemas tales como la eficiencia computacional basado en el tiempo usado por el procesador, el diseño de métodos iterativos que posean una rápida convergencia a la solución deseada, el control de errores de redondeo, la información sobre los límites de error de la solución aproximada obtenida, indicando las condiciones iniciales de cómputo verificables que garantizan una convergencia segura, etc. Dichos problemas constituyen el punto de partida de esta memoria. El objetivo general de esta memoria radica en la búsqueda de nuevos y eficientes métodos iterativos para ecuaciones y sistemas de ecuaciones no lineales. El origen es el trabajo realizado por Weerakoon y Fernando en el que desarrollan en dimensión uno la variante del método de Newton que utiliza la fórmula de cuadratura trapezoidal, consiguiendo orden de convergencia tres. Özban amplió esta idea, y obtuvo algunos métodos nuevos con convergencia de tercer orden. Por otra parte, dichos métodos son casos particulares de la familia de variantes del método de Newton de orden tres definida por M. Frontini y E. Sormani, utilizando una fórmula de cuadratura interpolatoria genérica de nodos equiespaciados. / Penkova Vassileva, M. (2011). MÉTODOS ITERATIVOS EFICIENTES PARA RESOLUCIÓN DE SISTEMAS NO LINEALES [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/12892