[pt] Esta dissertação tem por objetivo estudar um método para aproximação de dados esparços multivariados denominado o método Mínimos Quadrados Móveis por Aproximações Iteradas (Iterated Approximate Moving Least-Square Approximation – IAMLA). Este método é baseado no método de interpolação por funções de base radial (RBF) e no método de aproximação AMLS. Mas diferentemente do método RBF, ele não requer a solução de um sistema de equações lineares. O método IAMLS no limite converge para o interpolante RBF sob certas condições. / [en] The objective of this work is to study an approximation method for multivariate sparse data named Iterated Approximate Moving Least Square Approximation – IAMLS. This method is based on the Radial Basis Functions (RBF) interpolation method and on the AMLS approximation method. Differently from the RBF interpolation method, the IAMLS does not requires to solve a system of linear equations. The IAMLS method converges to the RBF interpolant under some conditions.

[pt] A identificação de sistemas é focalizada sob o ponto de vista da aproximação estocástica. Um sistema sem memória e invariante no tempo, com função completamente desconhecida é identificado por intermédio de uma estimação, que minimiza o critério do erro médio quadrático, tomando como base um conjunto de funções pré- selecionadas e linearmente independentes. A identificação do sistema é obtida através de uma algoritmo recursivo de aproximação estocástica, que converge para o valor real dessa estimativa, com probabilidade 1 e no sentido da média quadrática. Um estudo da aceleração desse algoritmo é efetuado, comprovando a existência de uma seqüência capaz de otimizá-lo. É demonstrada a aplicação desse algoritmo para identificação de um sistema linear e invariante no tempo, entretanto a aceleração da convergência não é mais uma conseqüência do caso anterior. Ainda é apresentada uma tentativa de contornar o problema de acessibilidade dos estados, requerida pelo algoritmo de aproximação estocástica, utilizando simultaneamente à identificação dos parâmetros do sistema, os algoritmos do filtro de Kalman, para estimação dos estados / [en] The stochastic approximation approach is used for systems identification. A memoryless time-invariant system with functional form completely unknow is identified by means of an estimate based on a preselected and linearly independent set of function which minimizes the mean-square-error criterion. The system identification is obtained using a stochastic approximation recursive algorithm, which convergs to a real value of this estimate, with probability 1 and in the mean square sense. The acceleration study of this algorithm is developd by proving the existence of an optimal sequence. The application of this algorithm for a linear timevariant system identification is proved, nevertheless the convergence acceletation is not anymore a consequence of the last case. Next is presented a tentative to by-pass the problem of states accessibility, required for the stochastic approximation, using simultaneously parameters systems identification with the Kalman-filter algorithms for states estimation.

[pt] Frações Contínuas são representações de números reais que independem da base de numeração escolhida. Quando se trata de aproximar números reais por frações, a escolha da base dez oculta, frequentemente, aproximações mais eficientes do que as exibe. Integrar conceitos de aproximações de números reais por frações contínuas com aspectos geométricos traz ao assunto uma abordagem diferenciada e bastante esclarecedora. O algoritmo de Euclides, por exemplo, ao ganhar significado geométrico, se torna um poderoso argumento para a visualização dessas aproximações. Os teoremas de Dirichlet, de Hurwitz-Markov e de Lagrange comprovam, definitivamente, que as melhores aproximações de números reais veem das frações contínuas, estimando seus erros com elegância técnica matemática incontestável. / [en] Continued fractions are representations of real numbers that are independent of the choice of the numerical basis. The choice of basis ten frequently hides more than shows efficient approximations of real numbers by rational ones. Integrating approximations of real numbers by continued fractions with geometrical interpretations clarify the subject. The study of geometrical aspects of Euclids algorithm, for example, is a powerful method for the visualization of continued fractions approximations. Theorems of Dirichlet, Hurwitz-Markov and Lagrange show that, definitely, the best approximations of real numbers come from continued fractions, and the errors are estimated with elegant mathematical technique.

[pt] Este trabalho busca reconstruir a geometria de uma malha partindo de sua conectividade e de um conjunto esparso de pontos com geometria conhecida, denominados pontos de controle. O problema é formulado como a maximização da suavidade da superfície fixando a posição dos pontos de controle. Nessa formulação, o método consiste em resolver um sistema linear esparso aplicando-se mínimos quadrados. Diferentes propostas para a seleção de pontos de controle, o método de minimização e a construção do sistema linear são apresentadas e comparadas. / [en] This work aims at reconstructing the geometry of a mesh from its connectivity and a small set of control points, whose geometry is known.The problem is formulated as a maximization of the surface smoothness restricting the position of the control points. With this formulation, the method reduces to solving a sparse linear system using least squares minimization. Several proposals for the selection of the control points, the minimization method and the linear system construction are presented and compared .

[pt] Métodos de aprendizagem de variedades assumem que um conjunto de dados de alta dimensão possuem uma representação de baixa dimensionalidade. Tais métodos podem ser empregados para simplificar os dados e obter um melhor entendimento da estrutura da qual os dados fazem parte. Nesta tese, utiliza-se o método de aprendizagem de variedades chamado votação por tensores para obter informação da dimensionalidade intrínseca dos dados, bem como estimativas confiáveis da orientação dos vetores normais e tangentes em cada ponto da variedade. Em seguida, propõe-se um método construtivo para aproximar a variedade implícita e realizar uma regressão. O método e chamado de Regressão Construtiva em Variedades Implícitas (RCVI). Com os resultados obtidos no método de votação por tensores, busca-se uma aproximação da variedade através de uma participação do domínio, controlada pelo erro, baseada em malhas 2n-adicas (n denota o numero de características dos dados de entrada) e em arvore binaria com funções de transição suave. A construção consiste em dividir os dados em vários subconjuntos, de maneira a aproximar cada subconjunto de dados com funções implícitas simples. Nesse trabalho empregamos funções polinomiais multivariadas. A forma global pode ser obtida combinando essas estruturas simples. A cada dado de entrada esta associada uma saída e a partir de uma boa aproximação da variedade, utilizando esses dados de entrada, busca-se obter uma boa estimativa da saída. Dessa forma, os critérios de parada da subdivisão do domínio incluem uma precisão, definida pelo usuário, na aproximação da variedade, bem como um critério envolvendo a dispersão das saídas em cada subdomínio. Para avaliar o desempenho do método proposto, realiza-se uma regressão com dados reais, compara-se com métodos de aprendizagem supervisionada e efetua-se ainda uma aplicação na área de dados de poucos de petróleo. / [en] Manifold Learning Methods assume that a high-dimensional data set has a low-dimensional representation. These methods can be employed in order to simplify data, and to obtain a better understanding of the structure of which the data belong. In this thesis, a tensor voting approach is employed as a technique of manifold learning, to obtain information about the intrinsic dimensionality of the data and reliable estimates of the orientation of normal and tangent vectors at each data point in the manifold. Next, a constructive method is proposed to approximate an implicit manifold and perform a regression. The method is called Constructive Regression on Implicit Manifold (RCVI). With the obtained results, search is made in order to obtain a manifold approximation, which consists in a domain partition, error-controlled, based on 2n-trees (n means the number of features of the input data set) and binary partition trees with smooth transition functions. The construction implies in partition the data set into several subsets in order to approximate each subset with a simple implicit function. In this work, it is used multivariate polynomial functions. The global shape can be obtained by combining these simple structures. Each input data set is associated with an output data, then, from a good manifold approximation using those input data set, it is hoped that occurs a good estimate of the output data. Therefore, the stop criteria of the domain subdivision include a precision, deffined by the user, on the manifold approximation, as well as a criterion that involves the output dispersion on each subdomain. To evaluate the performance of the proposed method, a regression on real data is computed, and compared with some supervised learning algorithms and also an application on well data is performed.

[pt] O trabalho apresentou as soluções de equações algébricas polinomiais por radicais e operações elementares nos coeficientes com a pesquisa baseada em livros e artigos; buscou explorar as diversas ideias desenvolvidas nas demonstrações, discussões sobre os casos e os artifícios engenhosos envolvidos, além de algumas demonstrações independentes; foram tratados ainda, os casos especiais onde as raízes estão sujeitas a condições pré estabelecidas e os coeficientes obedecem a uma dada lei; utilizamos a teoria de Abel-Ruffini e as implicações da teoria de Galois para justificar a impossibilidade de solução geral por radicais dos polinômios de grau n maior ou igual a 5 e a resposta a esse impasse com o surgimento de métodos numéricos de aproximação. Essas teorias e os métodos foram tratados em caráter elementar, por necessitarem de outros trabalhos detalhados, o que foge do objetivo desta obra. Sendo assim, vimos algoritmos que nos possibilitam o cálculo, nos casos do primeiro ao quarto graus, das soluções de uma equação algébrica polinomial além de casos especiais e aproximações numéricas. Utilizamos os programas de computação algébrica e geometria: Máxima, Geogebra e Maple para as aproximações, desenhos e gráficos. / [en] The work presented the solutions of polynomial algebraic equations by radicals and elementary operations in the coefficients with research based on books and articles; Sought to explore the various ideas developed in the demonstrations, discussions on the cases and ingenious artifacts involved, as well as some independent demonstrations; Were still treated, the special cases where the roots are subject to pre-established conditions and the coefficients obey a given law; We use Abel-Ruffini s theory and the implications of Galois s theory to justify the impossibility of a general solution by radicals of polynomials of degree greater than or equal 5 and the answer to this impasse with the emergence of numerical approximation methods. These theories and methods were treated in an elementary way, because they require other detailed work, which is beyond the scope of this work. Thus, we have seen algorithms that allow us to calculate, in cases from 1st to 4th degrees, the solutions of a polynomial algebraic equation in addition to special cases and numerical approximations. We use the algebraic computing and geometry programs: Maxima, Geogebra and Maple for approximations, drawings and graphs.

[pt] Desde de 1970, quando Box e Jenkins introduziram os modelos ARMA para análise e previsão de séries temporais, muitos estudos foram desenvolvidos buscando encontrar um método mais eficiente de identificação de tais modelos. Tal fato se deu porque o método por Box e Jenkins, baseado na função de auto-correlação parcial (FACP) não são eficientes quando os modelos apresentam componentes auto- regressivas (AR) e médias móveis (MA). Estudos comparativos realizados anteriormente mostraram que dentre os métodos de identificação já desenvolvidos, o que se mostrou mais eficiente foi o baseado na função de auto-correlação extendida (FACE) de TIAO e TSAY (1992) Recentemente, Kuldeep Kumar introduziu na literatura um método de identificação baseado na teoria de aproximação de Padé. O objetivo deste trabalho é comparar o método da FACE com o método baseado na teoria de aproximação de Padé. / [en] Since 1970, when Box and Jenkins first introduced the ARMA models to analysis and predict of time series data, a lot of studies have been developed to find an efficient identification method for such models. This was due the fact that the identification method proposed by Box and Jenkins, based on Auto-correlation Function (ACF) and Partial Auto-correlation Function (PACF), are inefficient when the models have auto regressive - AR- and moving average - MA- components. Comparative studies undertaken, have shown that, among the identification methods already developed, the method based on the Extended Auto-correlation Fuction of Tiao and Tsay (1982) is the most efficient. More recently, however, Kuldeep Kumar has introduced in the literature an identification method based on the theory of Padé aproximation. The objective of this paper is to compare the Extended Auto-correlation Function method with the method based on the Theory of Padé approximation.

[pt] As teorias clássicas da propagação das ondas eletromagnéticas em presença da terra apresentam soluções gerais que, em vista da complexidade matemática, não se aplicam diretamente aos casos práticos. Desta forma, partindo destas soluções, procura-se determinar aproximações que simplifiquem os cálculos de propagação. Entretanto, devido às condições supostas na obtenção das soluções aproximadas, estas apresentam uma região de validade restrita e a sua aplicação indevida pode acarretar erros inaceitáveis. Este fato, no entanto, não tira o mérito das soluções aproximadas, que, quando empregadas corretamente, fornecem resultados bastante satisfatórios em comparação com os experimentais. O objetivo do presente trabalho é a análise das aproximações efetuadas na obtenção das expressões usualmente empregadas nos cálculos de propagação, onde se procurará evidenciar as limitações inerentes a cada caso particular. O efeito da ionosfera não será considerado, assim como as variações do índice de refração da atmosfera, responsáveis pelo mecanismo da tropodifusão. / [en] In view of the mathematical complexity, the rigorous solutions of the classical theories of radio wave propagation in the presence of the earth are not directly applied to practical problems. Hence, based on these rigorous solutions, approximate expressions are developed to simplify the eveluation of radio wave signal attenuation. However, due to assumptions considered in the derivation of such solutions, they have a limited range of validity and, if erroneously used, can lead to unacceptable errors. Nevertheless, this fact does not take out the merit of the approximate solutions, once when they are correctly employed the numerical results are in accordance with the experimental data. This dissertation intends to analyze the approximations usually carried out in radio wave propagation problems, pointing out limitations associated to each particular case. The effect of the ionosphere will not be considered, as well as, the variability of the refractive index of the troposphere responsibe by the scatter propagation mechanism.

[pt] Os dados adquiridos nos experimentos físicos e nas imagens geométricas ou médicas são tipicamente discretas. Esses dados são interpretados como amostras de uma função desconhecida, porém cujas derivadas servem para caracterizar o dado. Por exemplo, o movimento de um fluido é descrito por um campo de velocidades, uma curva é caracterizada pela evolução da sua curvatura, as imagens médicas são geralmente segmentadas por estimativas de gradiente, entre outros. É possível obter derivadas coerentes a partir de filtragem dos dados. Porém, em dados multi-dimensionais, os filtros usuais privilegiam direções alinhadas com os eixos, o que pode gerar problemas quando essas derivadas são interpretadas geometricamente. Por exemplo, a curvatura estimada dependeria da orientação da curva, perdendo o sentido geométrico da curvatura. O objetivo do presente trabalho é melhorar a invariância geométrica dos filtros de derivadas. / [en] Typical data acquired in physical experiments or in geometrical or medical imaging are discrete. This data is generally interpreted as samples of an unknown function, whose derivatives still serve for the data characterisation. For example, the movement of a fluid is described as a velocity field, a curve is characterised by the evolution of its curvature, images used in medical sciences are usually segmented by estimates of their gradients, among others. It is possible to obtain coherent derivatives by filtering the data. However, with multidimensional data, the usual filters present a bias towards to favor directions aligned with the axis, which may induce problems when the derivatives are interpreted geometrically. For example, the estimated curvature would depend on the orientation of the curve, loosing the geometric meaning of the curvature. The goal of the present work is to improve the geometric invariance of derivative filters.

[pt] Erdal Arıkan introduziu os códigos polares em 2009. Trata-se de uma nova classe de códigos de correção de erros capaz de atingir o limite de Shannon. Usando decodificação de cancelamento sucessivo em lista, concatenada por verificação de redundância cíclica e a construções rápida de código, os códigos polares tornaram-se um código de correção de erros atraente e de alto desempenho para uso prático. Recentemente, códigos polares foram adotados para o padrão de geração 5th para sistemas celulares, mais especificamente para as informações de controle dos canais reverso e direto para os serviços de comunicação eMBB. No entanto, os códigos polares são limitados a comprimentos de bloco a potências de dois, devido a um produto Kronecker recursivo do kernel polarizador 2x2. Para aplicações práticas, é necessário fornecer técnicas de construção de código polar de comprimento flexível. Outro aspecto a ser analisado é o obtenção de uma técnica de construção de códigos polares de baixa complexidade e que tenha um ótimo desempenho em canal de ruído aditivo gaussiano branco, principalmente para blocos longos, inspirada na otimização da construção da aproximação gaussiana. Outro aspecto relevante é o poder de decodificação paralela do decodificador de propagação de crenças. Esta é uma alternativa para atender aos novos critérios de velocidade e latência previstos para o padrão de próxima geração para sistemas celulares. No entanto, ele precisa de melhorias de desempenho para tornar-se operacionalmente viável, tanto para 5G quanto para as gerações futuras. Nesta tese, três aspectos dos códigos polares são abordados: a construção de códigos com comprimentos arbitrários que visam maximizar a flexibilidade e eficiência dos códigos polares, o aprimoramento do método de construção por métodos gaussianos aproximação e a decodificação de códigos usando um algoritmo adaptativo de propagação de crenças reponderadas, bem como analisar quaisquer compromissos que afetem o desempenho da correção de erros. / [en] Erdal Arikan introduced the polar codes in 2009. This is a new class of error correction codes capable of reaching the Shannon limit. Using cyclic redundancy check concatenated list successive cancellation decoding and fast code constructs, polar codes have become an attractive, high-performance error correction code for practical use. Recently, polar codes have been adopted for the 5th generation standard for cellular systems, more specifically for the uplink and downlink control information for the extended Mobile Broadband (eMBB) communication services. However, polar codes are limited to block lengths to powers of two, due to a recursive Kronecker product of the 2x2 polarizing kernel. For practical applications, it is necessary to provide flexible length polar code construction techniques. Another aspect analyzed is the development of a technique of construction of polar codes of low complexity and that has an optimum performance on additive white Gaussian noise channels, mainly for long blocks, inspired by the optimization of the Gaussian approximation construction. Another relevant aspect is the parallel decoding power of the belief propagation decoder. This is an alternative to achieve the new speed and latency criteria foreseen for the next generation standard for cellular systems. However, it needs performance improvements to become operationally viable, both for 5G and for future generations. In this thesis, three aspects of polar codes are addressed: the construction of codes with arbitrary lengths that are intended for maximizing the flexibility and efficiency of polar codes, the improvement of the construction method by Gaussian approximation and the decoding of codes using an adaptive reweighted belief propagation algorithm, as well as the analysis of trade-offs affecting error correction performance.