Orientador: Cleonice Fátima Bracciali / Banca: Jorge Alberto Borrego Morell / Banca: Vanessa Avansini Botta Pirani / Banca: Alagacone Sri Ranga / Banca: Jo˜ao Carlos Ferreira Costa / Resumo: A partir dos zeros dos polinômios que satisfazem uma relação de recorrência do tipo R_II especial, obtemos uma fórmula de quadratura na reta real com fórmulas simples para o cálculo de seus pesos. Alguns polinômios para-ortogonais no círculo unitário podem ser obtidos por uma relação de recorrência de três termos. As duas relações de recorrência mencionadas são conectadas por uma transformação que leva a reta real ao círculo unitário. Desta maneira, obtemos também fórmulas de quadratura no círculo unitário. Os nós e pesos das fórmulas de quadratura no círculo unitário são facilmente obtidos através dos nós e pesos da primeira fórmula. Foram feitas algumas adaptações em métodos numéricos muito bem conhecidos para obter os nós e pesos destas fórmulas de quadratura / Abstract: From polynomials that satisfy a special recurrence relation of type RII we derive a quadrature formula in the real line with simple formulas to obtain the respective weights. Some para-orthogonal polynomials in the unit circle can be expressed by a three terms recurrence relation. The two mencioned recurrence relations are connected by a transformation that takes the real line onto the unit circle. Hence, we obtain also quadrature formula on the unit circle. The nodes and the weights of the quadratura on the unit circle are obteined easily from the nodes and the weights of the first quadrature formula. We have also made some adaptions in well known numerical methods to obtain the nodes and weights of these quadrature formulas / Doutor

Este trabalho apresenta uma demonstração completa do Teorema de L. Hörmander sobre a divisão de distribuições (temperadas) por polinômios. O caso n=1 é apresentado detalhadamente e serve como motivação para as técnicas utilizadas no caso geral. Todos os pré-requisitos para a demonstração de Hörmander (os Teoremas de Seidenberg-Tarski, de Puiseux e da Extensão de Whitney) são discutidos com detalhes. Como conseqüência do Teorema, segue que todo operador diferencial parcial linear com coeficientes constantes não nulo admite solução fundamental temperada. / This dissertation presents a thorough proof of L. Hörmander\'s theorem on the division of (tempered) distributions by polynomials. The case n=1 is discussed in detail and serves as a motivation for the techniques that are utilised in the general case. All the prerequisites for Hörmander\'s proof (the Theorems of Seidenberg-Tarski, of Puiseux and Whitney\'s Extension Theorem) are discussed in detail. As a consequence of this theorem, it follows that every non zero partial diffe\\-rencial operator with constant coefficients has a tempered fundamental solution.

Este trabalho apresenta algumas concepções sobre a álgebra e o ensino dela no ensino médio. Tais concepções sob uma análise curricular da educação básica no Brasil, com relação aos conteúdos algébricos. Visando contribuir com a formação de professores de Matemática do Ensino Básico apresentamos um estudo sobre os polinômios no qual elencamos algumas propriedades. Abordamos algumas ideias para o ensino de álgebra (anel polinomial), destacamos a localização das raízes de equações polinomiais e sua aplicação e apresentamos alguns métodos para resolução de equações polinomiais do 2o grau. Salientamos a importância do ensino de álgebra (polinômios e funções polinomiais) e sua presença em duas grandes avaliações nacionais, Exame Nacional do Ensino Médio (ENEM) e Olimpíada Brasileira de Matemática das Escolas Públicas (OBMEP), evidenciando os conteúdos algébricos em algumas questões dessas avaliações e apresentando a resolução sob uma organização de três componentes fundamentais para o ensino de matemática: Conceituação, Manipulação e Aplicação. / This work presents some conceptions about algebra and her teaching in high school. Such conceptions under a curricular analysis of basic education in Brazil, with respect to algebraic contents. Aiming to contribute to the formation of Mathematics teachers in Basic Education we present a study on the polynomials in which we list some properties. We address some ideas for the teaching of algebra (polynomial ring), we highlight the location of the roots of polynomial equations and their application and we present some methods for solving polynomial equations of 2o degree. We highlight the importance of teaching algebra (polynomials and polynomial functions) and its presence in two large national assessments, the National High School Examination (ENEM) and the Brazilian Mathematics Olympiad of Public Schools (OBMEP), highlighting the algebraic contents in some of these questions Assessments and presenting the resolution under an organization of three fundamental components for the teaching of mathematics: Conception, Manipulation and Application.

by Luk Wai Shing. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1993. / Includes bibliographical references (leaves 44-45). / ABSTRACT --- p.i / ACKNOWLEDGMENTS --- p.ii / Chapter CHAPTER 1. --- INTRODUCTION --- p.1 / Chapter CHAPTER 2. --- DRAWBACKS OF CLASSICAL THEORY --- p.4 / Chapter 2.1 --- Review of Sequential Iterative Methods --- p.4 / Chapter 2.2 --- Visualization Techniques --- p.8 / Chapter 2.3 --- Review of Deflation --- p.10 / Chapter CHAPTER 3. --- THE IMPROVEMENT OF THE ABERTH METHOD --- p.11 / Chapter 3.1 --- The Durand-Kerner method and the Aberth method --- p.11 / Chapter 3.2 --- The generalized Aberth method --- p.13 / Chapter 3.3 --- The modified Aberth Method for multiple-zero --- p.13 / Chapter 3.4 --- Choosing the initial approximations --- p.15 / Chapter 3.5 --- Multiplicity estimation --- p.16 / Chapter CHAPTER 4. --- THE HIGHER-ORDER ITERATIVE METHODS --- p.18 / Chapter 4.1 --- Introduction --- p.18 / Chapter 4.2 --- Convergence analysis --- p.20 / Chapter 4.3 --- Numerical Results --- p.28 / Chapter CHAPTER 5. --- PARALLEL DEFLATION --- p.32 / Chapter 5.1 --- The Algorithm --- p.32 / Chapter 5.2 --- The Problem of Zero Component --- p.34 / Chapter 5.3 --- The Problem of Round-off Error --- p.35 / Chapter CHAPTER 6. --- HOMOTOPY ALGORITHM --- p.36 / Chapter 6.1 --- Introduction --- p.36 / Chapter 6.2 --- Choosing Q(z) --- p.37 / Chapter 6.3 --- The arclength continuation method --- p.38 / Chapter 6.4 --- The bifurcation problem --- p.40 / Chapter 6.5 --- The suggested improvement --- p.41 / Chapter CHAPTER 7. --- CONCLUSION --- p.42 / REFERENCES --- p.44 / APPENDIX A. PROGRAM LISTING --- p.A-l / APPENDIX B. COLOR PLATES --- p.B-l

The problem under consideration is that of determining a simple and effective invariant of knots. To this end, the Conway polynomial is defined as a generalization of Alexander's original knot polynomial. It is noted, however, that the Conway polynomial is not a complete invariant. If two knots are equivalent, as defined in this investigation, then they receive identical polynomials. Yet, if two knots have identical polynomials, no information about their equivalence may be obtained. To define the Conway polynomial, the Axioms for Computation are given and many examples of their use are included. A major result of this investigation is the proof of topological invariance of these polynomials and the proof that the axioms are sufficient for the calculation of the knot polynomial for any given knot or link.

Dans cette thèse nous étudions les algèbres des polynômes qui sont bornés sur un ensemble semi-algébrique non borné. Tout d'abord nous abordons le problème consistant à déterminer si un polynôme est borné sur un ensemble. Nous résolvons ce problème pour les polynômes à deux variables définis sur des ensembles semi-algébriques quelconques. Dans la section suivante nous donnons une méthode pour déterminer des générateurs de l'algèbre des polynômes bornés et ce pour une large classe de semi-algébriques du plan réel. Dans la section 3 nous établissons une relation entre les valeurs de bifurcation du complexifié d'un polynôme $f$ à deux variables et la stabilité de la famille d'algèbres des polynômes bornés sur les ensembles ${fle c}$. Dans la section 4 nous décrivons la structure de l'algèbre des polynômes bornés sur un certain type de sous-ensembles de $mathbb{R}^n$ avec $n$ arbitraire, que nous appelons tentacules pondérées. Nous donnons aussi une preuve géométrique du fait que l'algèbre d'un sous-ensemble non borné d'un ensemble algébrique propre n'est pas de type fini. Dans la section suivante nous établissons une correspondance entre les cônes convexes et les algèbres des ensembles obtenus par des inégalités sur des monômes appropriés. Enfin, nous démontrons une version du Positivstellensatz de Schmudgen pour les polynômes bornés sur un ensemble non compact. / The main topic of the thesis is a study of algebras of polynomials which are bounded on a given unbounded semialgebraic set. First we tackle the problem of deciding the boundedness of a polynomial on a set. We achieve it for polynomials in two variables for any semialgebraic set. We give also a method of finding generators of the algebra of bounded polynomials for a large class of semialgebraic subsets of the real plane. In Section 3 we have established a relation between bifurcation values of a complexification of polynomial $f$ in two variables and the family of algebras of bounded polynomials on the sets ${fle c}$. In section 4 we describe the algebras of bounded polynomials for subsets of $mathbb{R}^n$, where $n$ is arbitrary, which we call weighted tentacles. We also provide a geometric proof of the fact that for a unbounded subset of a proper algebraic set its algebra cannot be finitely generated. In the next section we establish a correspondence between convex cones and algebras of bounded polynomials on the sets described by monomial inequalities. At the end of this thesis we prove a version of Schmudgen's Positivstellensatz for bounded polynomials.

本论文着重研究了带有Lp模球约束以及二次约束的多项式优化问题的计算复杂度以及关于此类问题的近似算法。在本论文中，利用张量对称化的技巧，我们首次证明了当P∈ [2 ，∞] ，任意高阶的带有Lp模球约束的多项式优化问题均为NP 困难。借助模的对偶性质，我们将这类优化问题转化为求解凸体半径的问题，从而使得我们获得了之前研究所无法使用的算法工具。具体来说，利用计算凸几何的算法工具，对于Lp模球约束的多项式优化问题，我们得到了近似比为[附圖]的确定性多项式时间近似算法，其中d为目标多项式的阶次， n 为问题的维度。使用随机算法，我们将近似比进一步提高为此类问题的己知最优值。[附圖]。此外，我们发展了计算凸几何当中对于凸体半径的计算方法，从而设计出了一种对二次约束多项式优化问题近似比为[附圖]的近似算法，其中m为问题的约束个数。我们的结果涵盖并提高了之前关于此类问题的研究结果。我们相信在本论文中使用的新的算法工具，将在今后的多项式优化问题研究中得到更广泛的应用。 / In this thesis, we present polynomial time approximation algorithms for solving various homogeneous polynomial optimization problems and their multilinear relaxations. Specifically, for the problems with Lp ball constraint, where P∈ [2 ，∞], by reducing them to that of determining the Lq-diameter of certain convex body, we show that they can be approximated to within a factor of [with formula] in deterministic polynomial time, where q = p=(p - 1) is the conjugate of p, n is the number of variables, and d is the degree of the polynomial. We further show that with the help of randomization, the approximation guarantee can be improved to [with formula], which is independent of p and is currently the best for the aforementioned problems. Moreover, we extend the argument of deterministic algorithm mentioned above to solve the quadratically constrained polynomial optimization problems. In particular, for any intersection of ellipsoids K, we can, in polynomial time, construct a random polytope P, which satisfies [with formula]. Then, by reducing the problem to that of evaluating the maximum polytopal norm [with formula] induced by P, over certain convex body, we can approximate the quadratically constrained problem within a factor of [with formula] in polynomial time. Our results unify and generalize those in the literature, which focus either on the quadratic case or the case where [with formula]. We believe that the wide array of tools used in this thesis will have further applications in the study of polynomial optimization problems. / Detailed summary in vernacular field only. / Hou, Ke. / On title page "p" is subscript. / Thesis (Ph.D.) Chinese University of Hong Kong, 2013. / Includes bibliographical references (leaves 106-111). / Abstracts also in Chinese.

Modern problems arising in many domains are driving a need for more capable, state-of-the-art optimization tools. A sharp focus on performance and accuracy has appeared, for example, in science and engineering applications. In particular, we have seen a growth in studies related to Polynomial Optimization: a field with beautiful and deep theory, offering flexibility for modeling and high impact in diverse areas. The understanding of structural aspects of the feasible sets in Polynomial Optimization, mainly studied in Real Algebraic Geometry, has a long tradition in Mathematics and it has recently acquired increased computational maturity, opening the gate for new Optimization methodologies to be developed. The celebrated hierarchies due to Lasserre, for example, emerged as good algorithmic templates. They allow the representation of semi-algebraic sets, possibly non-convex, through convex sets in lifted spaces, thus enabling the use of long-studied Convex Optimization methods. Nonetheless, there are some computational drawbacks for these approaches: they often rely on possibly large semidefinite programs, and due to scalability and numerical issues associated with SDPs, alternatives and complements are arising. In this dissertation, we will explore theoretical and practical Integer-Programming-based techniques for Polynomial Optimization problems. We first present a Linear Programming relaxation for the AC-OPF problem in Power Systems, a non-convex quadratic problem, and show how such relaxation can be used to develop a tractable MIP-based algorithm for the AC Transmission Switching problem. From a more theoretical perspective, and motivated by the AC-OPF problem, we study how sparsity can be exploited as a tool for analysis of the fundamental complexity of a Polynomial Optimization problem, by showing LP formulations that can efficiently approximate sparse polynomial problems. Finally, we show a computationally practical approach for constructing strong LP approximations on-the-fly, using cutting plane approaches. We will show two different frameworks that can generate cutting planes, which are based on classical methods used in Mixed-Integer Programming. Our methods mainly rely on the maturity of current MIP technology; we believe these contributions are important for the development of manageable approaches to general Polynomial Optimization problems.

In this dissertation we study groups of automorphisms of rooted trees arising from the transformations of the boundaries of these trees. The boundary of every regular rooted tree can be endowed with various algebraic structures. The transformations of these algebraic structures under certain conditions induce endomorphisms or automorphisms of the tree itself that can be described using the language of Mealy automata. This connection can be used to study boundarytransformations using the propertiesof the induced endomorphisms, or vice versa. We concentrate on two ways to interpret the boundary of the rooted d-regular tree. In the first approach discussed in detail in Chapter 3 we treat it as the ring Zd of d-adic integers. This is achieved by naturally identifying the nth level of the rooted d-ary tree with the ring Z/(dnZ). Under this interpretation we study transformations of Zd induced by polynomials in Z[x]. We show that they always induce endomorphisms of the tree, completely describe these endomorphisms using the language of automata and show that all of their sections are again induced by polynomials in Z[x] of the same degree. In the case of permutational polynomials acting on Zd by bijections the induced endomorphisms are automorphisms of the tree. For d = 2 such polynomials were completely characterized by Rivest in [Riv01]. As our main application we utilize the result of Rivest to derive the conditions on the coefficients of a permutational polynomial f(x) ∈ Z[x] that are necessary and sufficient for f to induce a level transitive automorphism of the binary tree, which is equivalent to the ergodicity of the action of f(x) on Z2 with respect to the normalized Haar measure. Such polynomials have applications in cryptography and are used in certain generators of random numbers. In the second approach, to be discussed in Chapter 4, we treat the boundary of the rooted binary tree as the ring (Z/2Z)[[t]] of formal power series over Z/2Z. This view allowed us to completely describe the structure of a certain group generated by a 4-state 2-letter bireversible automaton. Namely, we show that it is isomorphic to the lamplighter group (Z/2Z)2 ≀ Z of rank two. We show that the action of the generators of this group on the boundary of the tree can be induced by affine transformations of (Z/2Z)[[t]]. To our best knowledge, this is the first realization of the rank 2 lamplighter group by a bireversible automaton.

Multi-Polynomial Higher Order Neural Network Group Models (MPHONNG) program developed by the author will be studied in this thesis. The thesis also investigates the use of MPHONNG for financial data and rainfall data simulation and prediction. The MPHONNG is combined with characteristics of Polynomial function, Trigonometric polynomial function and Sigmoid polynomial function. The models are constructed with three layers Multi-Polynomial Higher Order Neural Network and the weights of the models are derived directly from the coefficents of the Polynomial form, Trignometric polynomial form and Sigmoid polynomial form. To the best of the authors knowledge, it is the first attempt to use MPHONNG for financial data and rainfall data simulation and prediction. Results proved satisfactory, and confirmed that MPHONNG is capable of handling high frequency, high order nonlinear and discontinuous data. / Master of Science (Hons)