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

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

The investigation is initially a continuation of Neuberger's work on linear boundary value problems. A very general iterative procedure for solution of these problems is described. The alternating-projection theorem of von Neumann is the mathematical starting point for this study. Later theorems demonstrate the validity of numerical approximation for Neuberger's method under certain conditions. A sampling of differential equations within the scope of our iterative method is given. The numerical evidence is that the procedure works well on neutral-state equations, for which no software is written now.

The iterative learning control (ILC) problem considers control tasks that perform a specific tracking command, and the command is to be performed is many times. The system returns to the same initial conditions on the desired trajectory for each repetition, also called run, or iteration. The learning law adjusts the command to a feedback system based on the error observed in the previous run, and aims to converge to zero-tracking error at sampled times as the iterations progress. The ILC problem is an inverse problem: it seeks to converge to that command that produces the desired output. Mathematically that command is given by the inverse of the transfer function of the feedback system, times the desired output. However, in many applications that unique command is often an unstable function of time. A discrete-time system, converted from a continuous-time system fed by a zero-order hold, often has non-minimum phase zeros which become unstable poles in the inverse problem. An inverse discrete-time system will have at least one unstable pole, if the pole-zero excess of the original continuous-time counterpart is equal to or larger than three, and the sample rate is fast enough. The corresponding difference equation has roots larger than one, and the homogeneous solution has components that are the values of these poles to the power of k, with k being the time step. This creates an unstable command growing in magnitude with time step. If the ILC law aims at zero-tracking error for such systems, the command produced by the ILC iterations will ask for a command input that grows exponentially in magnitude with each time step. This thesis examines several ways to circumvent this difficulty, designing filters that prevent the growth in ILC. The sister field of ILC, repetitive control (RC), aims at zero-error at sample times when tracking a periodic command or eliminating a periodic disturbance of known period, or both. Instead of learning from a previous run always starting from the same initial condition, RC learns from the error in the previous period of the periodic command or disturbance. Unlike ILC, the system in RC eventually enters into steady state as time progresses. As a result, one can use frequency response thinking. In ILC, the frequency thinking is not applicable since the output of the system has transients for every run. RC is also an inverse problem and the periodic command to the system converges to the inverse of the system times the desired output. Because what RC needs is zero error after reaching steady state, one can aim to invert the steady state frequency response of the system instead of the system transfer function in order to have a stable solution to the inverse problem. This can be accomplished by designing a Finite Impulse Response (FIR) filter that mimics the steady state frequency response, and which can be used in real time. This dissertation discusses how the digital feedback control system configuration affects the locations of sampling zeros and discusses the effectiveness of RC design methods for these possible sampling zeros. The sampling zeros are zeros introduced by the discretization process from continuous-time system to the discrete-time system. In the RC problem, the feedback control system can have sampling zeros outside the unit circle, and they are challenges for the RC law design. Previous research concentrated on the situation where the sampling zeros of the feedback control system come from a zero-order hold on the input of a continuous-time feedback system, and studied the influence of these zeros including the influence of these sampling zeros as the sampling rate is changed from the asymptotic value of sample time interval approaching zero. Effective RC design methods are developed and tested based for this configuration. In the real world, the feedback control system may not be the continuous-time system. Here we investigate the possible sampling zero locations that can be encountered in digital control systems where the zero-order hold can be in various possible places in the control loop. We show that various new situations can occur. We discuss the sampling zeros location with different feedback system structures, and show that the RC design methods still work. Moreover, we compare the learning rates of different RC design methods and show that the RC design method based on a quadratic fit of the reciprocal of the steady state frequency response will have the desired learning rate features that balance the robustness with efficiency. This dissertation discusses the steady-state response filter of the finite-time signal used in ILC. The ILC problem is sensitive to model errors and unmodelled high frequency dynamics, thus it needs a zero-phase low-pass filter to cutoff learning for frequencies where there is too much model inaccuracy for convergence. But typical zero-phase low-pass filters, like Filtfilt used by MATLAB, gives the filtered results with transients that can destabilize ILC. The associated issues are examined from several points of view. First, the dissertation discusses use of a partial inverse of the feedback system as both learning gain matrix and a low-pass filter to address this problem The approach is used to make a partial system inverse for frequencies where the model is accurate, eliminating the robustness issue. The concept is used as a way to improve a feedback control system performance whose bandwidth is not as high as desired. When the feedback control system design is unable to achieve the desired bandwidth, the partial system inverse for frequency in a range above the bandwidth can boost the bandwidth. If needed ILC can be used to further correct response up to the new bandwidth. The dissertation then discusses Discrete Fourier Transform (DFT) based filters to cut off the learning at high frequencies where model uncertainty is too large for convergence. The concept of a low pass filter is based on steady state frequency response, but ILC is always a finite time problem. This forms a mismatch in the design process, and we seek to address this. A math proof is given showing the DFT based filters directly give the steady-state response of the filter for the finite-time signal which can eliminate the possibility of instability of ILC. However, such filters have problems of frequency leakage and Gibbs phenomenon in applications, produced by the difference between the signal being filtered at the start time and at the final time, This difference applies to the signal filtered for nearly all iterations in ILC. This dissertation discusses the use of single reflection that produced a signal that has the start time and end times matching and then using the original signal portion of the result. In addition, a double reflection of the signal is studied that aims not only to eliminate the discontinuity that produces Gibbs, but also aims to have continuity of the first derivative. It applies a specific kind of double reflection. It is shown mathematically that the two reflection methods reduce the Gibbs phenomenon. A criterion is given to determine when one should consider using such reflection methods on any signal. The numerical simulations demonstrate the benefits of these reflection methods in reducing the tracking error of the system.

I study sets of attractors and non-attractors of finite iterated function systems. I provide examples of compact sets which are attractors of iterated function systems as well as compact sets which are not attractors of any iterated function system. I show that the set of all attractors is a dense Fs set and the space of all non-attractors is a dense Gd set it the space of all non-empty compact subsets of a space X. I also investigate the small trans-finite inductive dimension of the space of all attractors of iterated function systems generated by similarity maps on [0,1].

In the context of fractal geometry, the natural extension of volume in Euclidean space is given by Hausdorff and packing measures. These measures arise naturally in the context of iterated function systems (IFS). For example, if the IFS is finite and conformal, then the Hausdorff and packing dimensions of the limit sets agree and the corresponding Hausdorff and packing measures are positive and finite. Moreover, the map which takes the IFS to its dimension is continuous. Developing on previous work, we show that the map which takes a finite conformal IFS to the numerical value of its packing measure is continuous. In the context of self-similar sets, we introduce the super separation condition. We then combine this condition with known density theorems to get a better handle on finding balls of maximum density. This allows us to extend the work of others and give exact formulas for the numerical value of packing measure for classes of Cantor sets, Sierpinski N-gons, and Sierpinski simplexes.

The Kendall Square Research Machine 1 (KSR1) is a virtual shared memory (VSM) machine. Memory on the KSR1 consists primarily of shared, physically distributed caches. Effective memory utilization of the KSR1 is studied within this thesis. Special emphasis is laid upon how best to optimize iterative Krylov subspace methods using domain decomposition preconditioning. The domain decomposition preconditioner used was developed by J. H. Bramble, J. E. Pasciak, and A. H. Schatz. The Krylov subspace method used was the conjugate gradient algorithm. The linear systems being solved are derived from finite difference discretization of elliptic boundary value problems. Most of the focus of this thesis is upon how data structures affect performance of the algorithm on the KSR1. Implications for other iterative methods and preconditioners are also drawn. / Master of Science

Thesis (M.S.)--Massachusetts Institute of Technology, Dept. of Mechanical Engineering, 1980. / MICROFICHE COPY AVAILABLE IN ARCHIVES AND ENGINEERING. / Bibliography: leaves 89-90. / by Robert Allan Light. / M.S.

Thesis (Ph.D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1982. / MICROFICHE COPY AVAILABLE IN ARCHIVES AND ENGINEERING. / Vita. / Includes bibliographical references. / by Bruce R. Musicus. / Ph.D.