In this thesis, we study numerical analysis for random processes and fields. We investigate the behavior of the approximation accuracy for specific linear methods based on a finite number of observations. Furthermore, we propose techniques for optimizing performance of the methods for particular classes of random functions. The thesis consists of an introductory survey of the subject and related theory and four papers (A-D). In paper A, we study a Hermite spline approximation of quadratic mean continuous and differentiable random processes with an isolated point singularity. We consider a piecewise polynomial approximation combining two different Hermite interpolation splines for the interval adjacent to the singularity point and for the remaining part. For locally stationary random processes, sequences of sampling designs eliminating asymptotically the effect of the singularity are constructed. In Paper B, we focus on approximation of quadratic mean continuous real-valued random fields by a multivariate piecewise linear interpolator based on a finite number of observations placed on a hyperrectangular grid. We extend the concept of local stationarity to random fields and for the fields from this class, we provide an exact asymptotics for the approximation accuracy. Some asymptotic optimization results are also provided. In Paper C, we investigate numerical approximation of integrals (quadrature) of random functions over the unit hypercube. We study the asymptotics of a stratified Monte Carlo quadrature based on a finite number of randomly chosen observations in strata generated by a hyperrectangular grid. For the locally stationary random fields (introduced in Paper B), we derive exact asymptotic results together with some optimization methods. Moreover, for a certain class of random functions with an isolated singularity, we construct a sequence of designs eliminating the effect of the singularity. In Paper D, we consider a Monte Carlo pricing method for arithmetic Asian options. An estimator is constructed using a piecewise constant approximation of an underlying asset price process. For a wide class of Lévy market models, we provide upper bounds for the discretization error and the variance of the estimator. We construct an algorithm for accurate simulations with controlled discretization and Monte Carlo errors, andobtain the estimates of the option price with a predetermined accuracy at a given confidence level. Additionally, for the Black-Scholes model, we optimize the performance of the estimator by using a suitable variance reduction technique.

No description available.

Au cours des deux dernières décennies, les signaux chaotiques ont été de plus en plus pris en compte dans les télécommunications, traitement du signal ou transmissions sécurisées. De nombreux articles ont été publiés qui étudient la densité spectrale de puissance (DSP) des signaux générés par des transformations spécifiques. La concentration sur la DSP est due à l'importance de la fréquence dans les télécommunications et la transmission sécurisée. Grâce au grand nombre de systèmes sans fil, la disponibilité des fréquences de transmission et de réception est de plus en plus rare pour les communications sans fil. Aussi, les médias guidés ont des limitations liées à la bande passante du signal. Dans cette thèse, nous étudions certaines propriétés associées à la bifurcation collision de frontière pour une transformation unidimensionnelle linéaire par morceaux avec trois pentes et deux paramètres. Nous calculons les expressions analytiques de l'autocorrélation et de la densité spectrale de puissance des signaux chaotiques générés par les transformations linéaires par morceaux. Nous montrons l'existence d'une forte relation entre les différents types de densité spectrale de puissance (passe-bas, passe-haut ou coupe-bande) et les paramètres de bifurcation. Nous notons également en évidence une relation entre le type de spectre et l'ordre des cycles attractifs. Le type du spectre dépend de l'existence des orbites périodiques au-delà de la bifurcation de collision de frontière qui a donné naissance au chaos. Nous utilisons ensuite les transformations chaotiques pour étudier la fonction d'ambiguïté. Nous combinons quelques transformations chaotiques bien déterminées pour obtenir un spectre large bande avec une bonne fonction d'ambiguïté qui peut être utilisée en système radar.

Neste trabalho é apresentada uma ferramenta de otimização para análise de problemas de alocação de água em bacias hidrográficas utilizando técnicas de programação linear e linear por partes, integradas a um modelo de amortecimentos de ondas em canais. A otimização é feita de forma global, com uso de softwares de programação linear baseados nos métodos de pontos interiores. A metodologia de uso do sistema consiste em se obter uma solução ?ótima? para situações de disponibilidade de água insuficiente a todos os usos conflitantes na bacia. A ferramenta está sendo acoplada e incorporada ao AcquaNet, um Sistema de Suporte a Decisões (SSD) para análise de sistemas de recursos hídricos, que utiliza um algoritmo de rede de fluxo afim de otimizar a alocação de água. A formulação utilizando programação linear permite a análise global do sistema e por isso, espera-se melhor aproveitamento da água disponível, seja no menor déficit de atendimento às demandas ou maior armazenamento nos reservatórios. A programação linear com utilização de métodos de pontos interiores é atualmente uma técnica bastante conhecida e bem desenvolvida. Existem vários pacotes computacionais gratuitos com implementações eficientes dos métodos de pontos interiores que motivaram sua utilização neste trabalho. / This work presents an optimization tool for analyzing the problems of water allocation in watersheds by utilizing techniques of linear and piecewise linear programming integrated to a pattern of stream flow routing. The optimization is done in a global way with the usage of linear programming packages based upon the Internal Point Methods. The methodology of the usage consists in the acquirement of an optimal solution for situation of insufficient water availability for all conflicting consumptions from the watershed. The tool is being attached and incorporated to AcquaNet, which is a decision support system (DSS) for analysis of water resources systems that utilizes a network flow algorithm, with the purpose of optimizing the water allocation. The formulation that uses the linear programming leads to the analysis of the system as a whole and for this reason it is expected a better usage of the available water with a lower deficit in the supply or a greater storage in the reservoirs. Linear Programming with Internal Point Methods is nowadays a well known and very well developed technique. There are several computational packages with efficient implementations of the Internal Points Methods freely available, and that, has brought great motivation in its usage in the present work.

This work is dedicated to dynamic time warping in biosignal processing, especially it´s application for ECG signals. On the beginning the theoretical notes about cardiography are summarized. Then, the DTW analysis follows along with conditions and demands assessments for it’s successful application. Next, several variants and application possibilities are described. The practical part covers the design of this method, the outputs comprehension, settings optimization and realization of methods related with DTW

This thesis examines the optimal scheduling of a hydroelectric power plant with cascaded reservoirs each with multiple generating units under uncertainty after testing three linearization methods. These linearization methods are Successive Linear Programming, Piecewise Linear Approximations, and a Hybrid of the two together. There are two goals of this work. The first goal of this work aims to replace the nonconvex mixed-integer nonlinear program (MINLP) with a computationally efficient linearized mixed-integer linear program (MILP) that will be capable of finding a high quality solution, preferably the global optimum. The second goal is to implement a stochastic approach on the linearized method in a pseudo-rolling horizon method which keeps the ending time step fixed. Overall, the Hybrid method proved to be a viable replacement and performs well in the pseudo-rolling horizon tests. / Thesis / Master of Applied Science (MASc)

Dans cette thèse, nous étudions trois types de problèmes stochastiques : les problèmes avec contraintes probabilistes, les problèmes distributionnellement robustes et les problèmes avec recours. Les difficultés des problèmes stochastiques sont essentiellement liées aux problèmes de convexité du domaine des solutions, et du calcul de l’espérance mathématique ou des probabilités qui nécessitent le calcul complexe d’intégrales multiples. A cause de ces difficultés majeures, nous avons résolu les problèmes étudiées à l’aide d’approximations efficaces.Nous avons étudié deux types de problèmes stochastiques avec des contraintes en probabilités, i.e., les problèmes linéaires avec contraintes en probabilité jointes (LLPC) et les problèmes de maximisation de probabilités (MPP). Dans les deux cas, nous avons supposé que les variables aléatoires sont normalement distribués et les vecteurs lignes des matrices aléatoires sont indépendants. Nous avons résolu LLPC, qui est un problème généralement non convexe, à l’aide de deux approximations basée sur les problèmes coniques de second ordre (SOCP). Sous certaines hypothèses faibles, les solutions optimales des deux SOCP sont respectivement les bornes inférieures et supérieures du problème du départ. En ce qui concerne MPP, nous avons étudié une variante du problème du plus court chemin stochastique contraint (SRCSP) qui consiste à maximiser la probabilité de la contrainte de ressources. Pour résoudre ce problème, nous avons proposé un algorithme de Branch and Bound pour calculer la solution optimale. Comme la relaxation linéaire n’est pas convexe, nous avons proposé une approximation convexe efficace. Nous avons par la suite testé nos algorithmes pour tous les problèmes étudiés sur des instances aléatoires. Pour LLPC, notre approche est plus performante que celles de Bonferroni et de Jaganathan. Pour MPP, nos résultats numériques montrent que notre approche est là encore plus performante que l’approximation des contraintes probabilistes individuellement.La deuxième famille de problèmes étudiés est celle relative aux problèmes distributionnellement robustes où une partie seulement de l’information sur les variables aléatoires est connue à savoir les deux premiers moments. Nous avons montré que le problème de sac à dos stochastique (SKP) est un problème semi-défini positif (SDP) après relaxation SDP des contraintes binaires. Bien que ce résultat ne puisse être étendu au cas du problème multi-sac-à-dos (MKP), nous avons proposé deux approximations qui permettent d’obtenir des bornes de bonne qualité pour la plupart des instances testées. Nos résultats numériques montrent que nos approximations sont là encore plus performantes que celles basées sur les inégalités de Bonferroni et celles plus récentes de Zymler. Ces résultats ont aussi montré la robustesse des solutions obtenues face aux fluctuations des distributions de probabilités. Nous avons aussi étudié une variante du problème du plus court chemin stochastique. Nous avons prouvé que ce problème peut se ramener au problème de plus court chemin déterministe sous certaine hypothèses. Pour résoudre ce problème, nous avons proposé une méthode de B&B où les bornes inférieures sont calculées à l’aide de la méthode du gradient projeté stochastique. Des résultats numériques ont montré l’efficacité de notre approche. Enfin, l’ensemble des méthodes que nous avons proposées dans cette thèse peuvent s’appliquer à une large famille de problèmes d’optimisation stochastique avec variables entières. / In this thesis, we studied three types of stochastic problems: chance constrained problems, distributionally robust problems as well as the simple recourse problems. For the stochastic programming problems, there are two main difficulties. One is that feasible sets of stochastic problems is not convex in general. The other main challenge arises from the need to calculate conditional expectation or probability both of which are involving multi-dimensional integrations. Due to the two major difficulties, for all three studied problems, we solved them with approximation approaches.We first study two types of chance constrained problems: linear program with joint chance constraints problem (LPPC) as well as maximum probability problem (MPP). For both problems, we assume that the random matrix is normally distributed and its vector rows are independent. We first dealt with LPPC which is generally not convex. We approximate it with two second-order cone programming (SOCP) problems. Furthermore under mild conditions, the optimal values of the two SOCP problems are a lower and upper bounds of the original problem respectively. For the second problem, we studied a variant of stochastic resource constrained shortest path problem (called SRCSP for short), which is to maximize probability of resource constraints. To solve the problem, we proposed to use a branch-and-bound framework to come up with the optimal solution. As its corresponding linear relaxation is generally not convex, we give a convex approximation. Finally, numerical tests on the random instances were conducted for both problems. With respect to LPPC, the numerical results showed that the approach we proposed outperforms Bonferroni and Jagannathan approximations. While for the MPP, the numerical results on generated instances substantiated that the convex approximation outperforms the individual approximation method.Then we study a distributionally robust stochastic quadratic knapsack problems, where we only know part of information about the random variables, such as its first and second moments. We proved that the single knapsack problem (SKP) is a semedefinite problem (SDP) after applying the SDP relaxation scheme to the binary constraints. Despite the fact that it is not the case for the multidimensional knapsack problem (MKP), two good approximations of the relaxed version of the problem are provided which obtain upper and lower bounds that appear numerically close to each other for a range of problem instances. Our numerical experiments also indicated that our proposed lower bounding approximation outperforms the approximations that are based on Bonferroni's inequality and the work by Zymler et al.. Besides, an extensive set of experiments were conducted to illustrate how the conservativeness of the robust solutions does pay off in terms of ensuring the chance constraint is satisfied (or nearly satisfied) under a wide range of distribution fluctuations. Moreover, our approach can be applied to a large number of stochastic optimization problems with binary variables.Finally, a stochastic version of the shortest path problem is studied. We proved that in some cases the stochastic shortest path problem can be greatly simplified by reformulating it as the classic shortest path problem, which can be solved in polynomial time. To solve the general problem, we proposed to use a branch-and-bound framework to search the set of feasible paths. Lower bounds are obtained by solving the corresponding linear relaxation which in turn is done using a Stochastic Projected Gradient algorithm involving an active set method. Meanwhile, numerical examples were conducted to illustrate the effectiveness of the obtained algorithm. Concerning the resolution of the continuous relaxation, our Stochastic Projected Gradient algorithm clearly outperforms Matlab optimization toolbox on large graphs.

Au cours des deux dernières décennies, les signaux chaotiques ont été de plusen plus pris en compte dans les télécommunications, traitement du signal ou transmissionssécurisées. De nombreux articles ont été publiés qui étudient la densitéspectrale de puissance (DSP) des signaux générés par des transformations spécifiques.La concentration sur la DSP est due à l’importance de la fréquence dans lestélécommunications et la transmission sécurisée. Grâce au grand nombre de systèmessans fil, la disponibilité des fréquences de transmission et de réception est de plus enplus rare pour les communications sans fil. Aussi, les médias guidés ont des limitationsliées à la bande passante du signal. Dans cette thèse, nous étudions certainespropriétés associées à la bifurcation collision de frontière pour une transformationunidimensionnelle linéaire par morceaux avec trois pentes et deux paramètres. Nouscalculons les expressions analytiques de l’autocorrélation et de la densité spectralede puissance des signaux chaotiques générés par les transformations linéaires parmorceaux. Nous montrons l’existence d’une forte relation entre les différents typesde densité spectrale de puissance (passe-bas, passe-haut ou coupe-bande) et les paramètresde bifurcation. Nous notons également en évidence une relation entre le typede spectre et l’ordre des cycles attractifs. Le type du spectre dépend de l’existencedes orbites périodiques au-delà de la bifurcation de collision de frontière qui a donnénaissance au chaos. Nous utilisons ensuite les transformations chaotiques pour étudierla fonction d’ambiguïté. Nous combinons quelques transformations chaotiquesbien déterminées pour obtenir un spectre large bande avec une bonne fonction d’ambiguïtéqui peut être utilisée en système radar / During the two last decades, chaotic signals have been increasingly consideredin telecommunications, signal processing or secure transmissions. Many papers haveappeared which study the power spectral density (PSD) of signals issued from somespecific maps. This interest in the PSD is due to the importance of frequency in thetelecommunications and transmission security. With the large number of wirelesssystems, the availability of frequencies for transmission and reception is increasinglyuncommon for wireless communications. Also, guided media have limitations relatedto the bandwidth of a signal. In this thesis, we investigate some properties associatedto the border-collision bifurcations in a one-dimensional piecewise-linear map withthree slopes and two parameters. We derive analytical expressions for the autocorrelationsequence, power spectral density of chaotic signals generated by our piecewiselinearmap. We prove the existence of strong relation between different types of thepower spectral density (low-pass, high-pass or band-stop) and the parameters. Wealso find a relation between the type of spectrum and the order of attractive cycleswhich are located after the border collision bifurcation between chaos and cycles.We use the chaotic transformations to study the ambiguity function. We combinesome chaotic transformations well determined to obtain a broadband spectrum witha good ambiguity function that can be used in radar systems

Cette thèse étudie des ondes localisées pour certaines classes d'équations différentielles non linéaires décrivant des systèmes mécaniques excitables. Ces systèmes correspondent à une chaîne infinie de blocs reliés par des ressorts et qui glissent sur un surface en présence d'une force de frottement non linéaire dépendant de la vitesse. Nous analysons à la fois le modèle de Burridge-Knopoff (avec des blocs attachés à des ressorts tirés à une vitesse constante) et une chaîne de blocs libres glissant sur un plan incliné sous l'effet de la gravité. Pour une classe de fonctions de frottement non-monotones, ces deux systèmes présentent une réponse de grande amplitude à des perturbations au-dessus d'un certain seuil, ce qui constitue l'une des principales propriétés des systèmes excitables. Cette réponse provoque la propagation d'ondes solitaires ou des fronts, en fonction du modèle et des paramètres. Nous étudions ces ondes localisées numériquement et théoriquement pour une grande gamme de lois de frottement et des régimes de paramètres, ce qui conduit à l'analyse d'équations différentielles non linéaires avec avance et retard. Les phénomènes d'extinction de propagation et d'apparition d'oscillations sont également étudiés pour les ondes progressives. L'introduction d'une fonction de frottement linéaire par morceaux permet de construire explicitement des ondes localisées sous la forme d'intégrales oscillantes et d'analyser certaines de leurs propriétés telles que la forme et la vitesse d'ondes. Une preuve de l'existence d'ondes solitaires est obtenue pour le modèle de Burridge-Knopoff pour un couplage faible. / This thesis analyses localized travelling waves for some classes of nonlinearlattice differential equations describing excitable mechanical systems. Thesesystems correspond to an infinite chain of blocks connected by springs and sliding on a surface in the presence of a nonlinear velocity-dependent friction force. We investigate both the Burridge-Knopoff model (with blocks attached to springs pulled at constant velocity) and a chain of free blocks sliding on an inclined plane under the effect of gravity. For a class of non-monotonic friction functions, both systems display a large response to perturbations above a threshold, one of the main properties of excitable systems. This response induces the propagation of either solitary waves orfronts, depending on the model and parameter regime. We study these localized waves numerically and theoretically for a broad range of friction laws and parameter regimes, which leads to the analysis of nonlinear advance-delay differential equations. Phenomena of propagation failure and oscillations of the travelling wave profile are also investigated. The introduction of a piecewise linear friction function allows one to construct localized waves explicitly in the form of oscillatory integrals and to analyse some of their properties such as shape and wave speed. An existence proof for solitary waves is obtained for the excitable Burridge-Knopoff model in the weak coupling regime.

Made available in DSpace on 2014-07-29T16:02:18Z (GMT). No. of bitstreams: 1 Dissertacao Tharsis Souza Silva.pdf: 1389814 bytes, checksum: c28dfe55ac776a4de30d43875907dc64 (MD5) Previous issue date: 2011-03-25 / In this work, we consider classes of discontinuous piecewise linear systems in the plane and continuous in the space. In the plane, we analyze systems of focus-focus (FF), focusparabolic (FP) and parabolic-parabolic (PP) type, separated by the straight line x = 0, and we prove that can appear until two limit cycles depending of parameters variations. Also we study a specific system, piecewise, with two saddles (one fixed in the origin and the other in the neighborhood of point (1;1)) separated by the straight line y= -x+1, and we show that can appear until two limit cycles depending of parameters variations. Finally, we examine a continuous piecewise linear system in R³ and we prove the existence of invariant cones and, through this structures, we determine some stable and unstable behavior. / Neste trabalho, consideramos classes de sistemas lineares por partes descontínuos no plano e contínuos no espaço. No plano, analisamos sistemas do tipo foco-foco (FF), parabólico-foco (PF) e parabólico-parabólico (PP) separados pela reta x = 0 e demonstramos que podem aparecer até dois ciclos limite, dependendo de variações de parâmetros. Também estudamos um sistema específico, linear por partes, com duas selas (uma sela fixa na origem e outra na vizinhança do ponto (1;1)) separadas pela reta y= -x+1 , e mostramos que podem aparecer até dois ciclos limite dependendo de variações de parâmetros. Por fim, examinamos um sistema linear por partes contínuo em R³ e demonstramos a existência de cones invariantes e, através destas estruturas, determinamos alguns comportamentos estáveis e instáveis.