Esta tese tem duas partes relativamente independentes. A primeira estuda o problema de construir uma curva suave (C1) que separa dois conjuntos de pontos do plano. Especificamente, a curva é definida por uma equação implícita F(x, y) = 0 onde F é uma spline polinomial de grau 2 com continuidade adequada. O objetivo é determinar uma única cônica se possível, senão uma curva que minimiza uma função quadrática de "energia". O problema é reduzido a um problema de minimização quadrática com restrições, que é resolvido por uma biblioteca existente (CGAL). A segunda parte descreve um algoritmo geral para determinar uma base de elementos finitos em um espaço de splines arbitrário, definido por exemplo por restrições lineares homogêneas de continuidade ou contorno. Neste caso o problema é caracterizado como o problema de encontrar uma base de peso máximo em um matróide e, portanto, pode ser resolvido pelo algoritmo guloso de Edmonds. Esse algoritmo tem custo exponencial no número n de células da malha. Entretanto, esta tese mostra que para casos de interesse - onde existe uma base de elementos finitos com suporte de k células, no máximo - o algoritmo pode ser melhorado de modo a terminar em tempo O(n km3), onde m é a dimensão do espaço (que é geralmente O(n)); This thesis has two relatively independent parts. The first part considers the problem of constructing a smooth (C1) curve separating two sets of points of the plane. Specifically...
Este trabalho apresenta um modelo fluido-dinamico para a simulação da dispersão continua de efluentes miscíveis em rios de geometria irregular. Devido a geometria irregular do rio, as equações de conservação de massa e de momentum são descritas em um sistema de coordenadas generalizadas. Utilizando pontos conhecidos de cada margem de rio, foi usado o Método Spline Cúbico para encontrar as funções mais suaves possíveis que passem por esses pontos. Estas funções tornaram possível a obtenção das linhas de corrente e, então, usando o principio da ortogonalidade, as linhas potenciais foram estimadas. Desta forma, a malha e formada pela intersecção entre as linhas potenciais e as linhas de corrente. Apesar da irregularidade da geometria, as variáveis não costumam apresentar altos gradientes e, por isso, não e necessário utilizar um complexo modelo de turbulência. Portanto, um modelo de turbulência de ordem zero foi escolhido para considerar a turbulência. As equações de conservação de massa e de momentum foram discretizadas através do Método dos Volumes Finitos. Os resultados mostram que o modelo e satisfatório na obtenção dos perfis de velocidade e concentração do efluente de seções de rio de geometria irregular. Alem disso...
Nesta tese, desenvolvemos algoritmos eficientes para a aproximação de funções que tem importantes detalhes de pequena escala confinados em pequenas região do domínio. Assumimos que a função objetivo é amostrada em um número finito de pontos dados, com densidade uniforme ou densidade não uniforme. Neste trabalho optamos por utilizar uma base multinível (ou multiresolução), em que os centros dos elementos em cada nível são um subconjunto de uma grade regular de centros, independentemente dos pontos de amostragem. As bases em questão têm estrutura multiescala semelhante à usada na análise wavelet em d dimensões. No entanto, os seus elementos são funções explícitas definidas pelo produto de d funções univariadas de suporte limitado (tais como pseudo-gaussianas modelada por polinômios truncados ou spline). Descrevemos um algoritmo incremental de aproximação, que procede do nível mais grosseiro para o mais detalhado, sendo que em cada nível são usados apenas os elementos da base localizados nas regiões onde a aproximação é ainda insuficientemente precisa. Em cada nível, usamos um processo iterativo com o método de mínimos quadrados que é projetado para ignorar dados discrepantes e detalhes que só podem ser aproximados em escalas menores.; I this thesis we develop efficient algorithms for the approximation of functions that have important small-scale details confined to small portions of their domain. We assume that the target function is sampled at a finite number of data points...
Fonte: Universidade Federal do Rio Grande do Norte; BR; UFRN; Programa de Pós-Graduação em Matemática Aplicada e Estatística; Probabilidade e Estatística; Modelagem MatemáticaPublicador: Universidade Federal do Rio Grande do Norte; BR; UFRN; Programa de Pós-Graduação em Matemática Aplicada e Estatística; Probabilidade e Estatística; Modelagem Matemática
In this work we have elaborated a spline-based method of solution of inicial value
problems involving ordinary differential equations, with emphasis on linear equations.
The method can be seen as an alternative for the traditional solvers such as Runge-Kutta,
and avoids root calculations in the linear time invariant case.
The method is then applied on a central problem of control theory, namely, the step
response problem for linear EDOs with possibly varying coefficients, where root calculations
do not apply. We have implemented an efficient algorithm which uses exclusively
matrix-vector operations. The working interval (till the settling time) was determined
through a calculation of the least stable mode using a modified power method.
Several variants of the method have been compared by simulation. For general linear
problems with fine grid, the proposed method compares favorably with the Euler method.
In the time invariant case, where the alternative is root calculation, we have indications
that the proposed method is competitive for equations of sifficiently high order.; Coordenação de Aperfeiçoamento de Pessoal de Nível Superior; Neste trabalho desenlvolvemos um método de resolução de problemas de valor inicial
com equações diferenciais ordinárias baseado em splines...
Métodos de deformação são importantes em áreas como modelagem geométrica e animação computacional. Na biologia, a modelagem de forma, crescimento, movimento e patologias de organismos microscópicos vivos ou células requerem deformações suaves, as quais são essencialmente 2D com poucas mudanças de profundidade. Nesta dissertação, apresentamos um método de deformação do espaço 2.5D suave. O modelo 3D do organismo é modificado deformando uma grade de controle formada por prismas que o envolve. A técnica de interpolação spline é usada para satisfazer o requisito de suavidade ('C POT. 1'). Implementamos esse método em um editor que torna possível definir e modificar a deformação de uma forma amigável usando o mouse. Os resultados experimentais mostram que o método é simples e efetivo; Shape deformation methods are important in such fields as geometric modeling and computer animation. In biology, the modeling of shape, growth, movement and pathologies of living microscopic organisms or cells requires smooth deformations, which are essentially 2D with little change in depth. In this master thesis, we present a smooth 2.5D space deformation method. The 3D model of the organism is modified by deforming an enclosing control grid of prisms. Spline interpolation is used to satisfy the smoothness ('C POT. 1') requirement. We implemented this method in an editor which makes it possible to define and modify the deformation with the mouse in a user-friendly way. The experimental results show that the method is simple and effective
Inspired by shape constrained estimation under general nonnegative derivative
constraints, this paper considers the B-spline approximation of constrained
functions and studies the asymptotic performance of the constrained B-spline
estimator. By invoking a deep result in B-spline theory (known as de Boor's
conjecture) first proved by A. Shardin as well as other new analytic
techniques, we establish a critical uniform Lipschitz property of the B-spline
estimator subject to arbitrary nonnegative derivative constraints under the
$\ell_\infty$-norm with possibly non-equally spaced design points and knots.
This property leads to important asymptotic analysis results of the B-spline
estimator, e.g., the uniform convergence and consistency on the entire interval
under consideration. The results developed in this paper not only recover the
well-studied monotone and convex approximation and estimation as special cases,
but also treat general nonnegative derivative constraints in a unified
framework and open the door for the constrained B-spline approximation and
estimation subject to a broader class of shape constraints.
In this paper, we present the development of a many-knot spline method
derived to remove the statistical noise in the spectroscopic data. This method
is an expansion of the B-spline method. Compared to the B-spline method, the
many-knot spline method is significantly faster.; Comment: 3pages, 2 figures
In this paper, we propose a new semiparametric regression estimator by using
a hybrid technique of a parametric approach and a nonparametric penalized
spline method. The overall shape of the true regression function is captured by
the parametric part, while its residual is consistently estimated by the
nonparametric part. Asymptotic theory for the proposed semiparametric estimator
is developed, showing that its behavior is dependent on the asymptotics for the
nonparametric penalized spline estimator as well as on the discrepancy between
the true regression function and the parametric part. As a naturally associated
application of asymptotics, some criteria for the selection of parametric
models are addressed. Numerical experiments show that the proposed estimator
performs better than the existing kernel-based semiparametric estimator and the
fully nonparametric estimator, and that the proposed criteria work well for
choosing a reasonable parametric model.; Comment: 20 pages, 3 figures
In this paper, an approximation of the optimal compressor function using the
quadratic spline functions has been presented. The coefficients of the
quadratic spline functions are determined by minimizing the mean-square error
(MSE). Based on the obtained approximative quadratic spline functions, the
design for companding quantizer for Gaussian source is done. The support region
of proposed companding quantizer is divided on segments of unequal size, where
the optimal value of segment threshold is numerically determined depending on
maximal value of the signal to quantization noise ratio (SQNR). It is shown
that by the companding quantizer proposed in this paper, the SQNR that is very
close to SQNR of nonlinear optimal companding quantizer is achieved.
In this paper, we give a causal solution to the problem of spline
interpolation using H-infinity optimal approximation. Generally speaking,
spline interpolation requires filtering the whole sampled data, the past and
the future, to reconstruct the inter-sample values. This leads to non-causality
of the filter, and this becomes a critical issue for real-time applications.
Our objective here is to derive a causal system which approximates spline
interpolation by H-infinity optimization for the filter. The advantage of
H-infinity optimization is that it can address uncertainty in the input signals
to be interpolated in design, and hence the optimized system has robustness
property against signal uncertainty. We give a closed-form solution to the
H-infinity optimization in the case of the cubic splines. For higher-order
splines, the optimal filter can be effectively solved by a numerical
computation. We also show that the optimal FIR (Finite Impulse Response) filter
can be designed by an LMI (Linear Matrix Inequality), which can also be
effectively solved numerically. A design example is presented to illustrate the
A new nonparametric approach for system identification has been recently
proposed where the impulse response is seen as the realization of a zero--mean
Gaussian process whose covariance, the so--called stable spline kernel,
guarantees that the impulse response is almost surely stable. Maximum entropy
properties of the stable spline kernel have been pointed out in the literature.
In this paper we provide an independent proof that relies on the theory of
matrix extension problems in the graphical model literature and leads to a
closed form expression for the inverse of the first order stable spline kernel
as well as to a new factorization in the form $UWU^\top$ with $U$ upper
triangular and $W$ diagonal. Interestingly, all first--order stable spline
kernels share the same factor $U$ and $W$ admits a closed form representation
in terms of the kernel hyperparameter, making the factorization computationally
inexpensive. Maximum likelihood properties of the stable spline kernel are also
highlighted. These results can be applied both to improve the stability and to
reduce the computational complexity associated with the computation of stable
spline estimators.; Comment: 12 pages. In 2014 IEEE Multi-conference on Systems and Control. IEEE...
This paper is concerned with asymptotic theory for penalized spline estimator
in bivariate additive model. The focus of this paper is put upon the penalized
spline estimator obtained by the backfitting algorithm. The convergence of the
algorithm as well as the uniqueness of its solution are shown. The asymptotic
bias and variance of penalized spline estimator are derived by an efficient use
of the asymptotic results for the penalized spline estimator in marginal
univariate model. Asymptotic normality of estimator is also developed, by which
an approximate confidence interval can be obtained. Some numerical experiments
confirming theoretical results are provided.; Comment: 24 pages, 6 figures
In this paper the approximation of the optimal compressor function using the
first-degree spline functions and quadratic spline functions is done.
Coefficients on which we form approximative spline functions are determined by
solving equation systems that are formed from treshold conditions. For Gaussian
source at the input of the quantizer, using the obtained approximate spline
functions a companding quantizer designing is done. On the basis of the
comparison with the SQNR of the optimal compandor it can be noticed that the
proposed companding quantizer based on approximate spline functions achieved
SQNR arbitrary close to that of the optimal compandor.
Spline wavelet tight frames of Ron-Shen have been used widely in frame based
image analysis and restorations. However, except for the tight frame property
and the approximation order of the truncated series, there are few other
properties of this family of spline wavelet tight frames to be known. This
paper is to present a few new properties of this family that will provide
further understanding of it and, hopefully, give some indications why it is
efficient in image analysis and restorations. In particular, we present a
recurrence formula of computing generators of higher order spline wavelet tight
frames from the lower order ones. We also represent each generator of spline
wavelet tight frames as certain order of derivative of some univariate box
spline. With this, we further show that each generator of sufficiently high
order spline wavelet tight frames is close to a right order of derivative of a
properly scaled Gaussian function. This leads to the result that the wavelet
system generated by a finitely many consecutive derivatives of a properly
scaled Gaussian function forms a frame whose frame bounds can be almost tight.; Comment: 28 pages
One important area of Computer-Aided Geometric Design
(CAGD) is concerned with the approximation and representation
of the surfaces of solid objects. Accurately describing the shape of
an object so that the description is useful to designers who must
decide how to manipulate it is an important problem. B-spline
techniques promise greater versatility in describing complex
surfaces than other techniques, thus the B-spline surface is
highlighted in the field of constructive solid geometric modeling.
A method for drawing complex surfaces by using B-spline
techniques is presented. The tensor product surface scheme is
developed for constructing sculptured surfaces. Also, the basic
principle of multivariate B-splines, i.e., nontensor product
surfaces, the light of tomorrow in CAGD, is introduced.
A technique using least square cubic splines was developed to obtain an
estimate of the MTF from edge response measurements. By making specific
assumptions concerning the general nature of edges to be analyzed, an
optimized procedure was developed to fit noise free cummulative gaussian
edges. The procedure was evaluated using simulated data from various
spread function shapes and levels of additive noise. The spline technique
produced MTF estimates which had less bias and lower variance than the
commonly used derivative - transform technique. Due to the various
constraints which can be imposed on the spline, least square cubic splines
actually comprise a class of edge analysis techniques which spans the range of
characteristics from the derivative transform technique to the exact
functional form fitting technique. Because of the nature of the spline
calculation, the constrained, least square cubic spline can be thought of as a
matched, yet adaptive nonlinear filter.
A brief review of curve fitting terminology is presented, and the cubic spline interpolation scheme is outlined. Parametric and non-parametric curve fitting techniques are compared. The technique to fit parametric cubic splines is derived using the Euler- Lagrange formulation. Previous work on splines in tension is identified. Employing the notion of splines in tension, a method is proposed to fit a parametric curve to a set of (n + 1) points in ^-dimension space satisfying a specified set of boundary conditions. The curve fitted will not have any inflection points within any span and will be invariant with respect to coordinate translation and rotation. Using Euler-Lagrange formulation, a system of linear equations in terms of the unknown second derivatives at knots is developed. Three kinds of boundary conditions are investigated. Software is developed in VAX Fortran to fit both parametric splines in tension and parametric cubic splines. Applications where splines in tension may find use are identified. Some examples of such applications are presented and comparison to cubic spline made. Splines in tension offer a better alternative than Fourier transform in describing boundary of shape in digital image processing application. Possible extensions to the numerical scheme developed and related investigations by other workers in this field are also listed.
B-Splines are a useful tool in signal processing, and are widely used in the analysis of two and three-dimensional images. B-Splines provide a continuous representation of the signal, image, or volume, which is useful for interpolation, resampling, noise removal, and differentiation - all important steps in many signal processing algorithms. These splines are defined entirely by an array of coefficients that is roughly the same size as the original signal and of values in the same order of magnitude, making storage and representation trivial.
What is not trivial, however, is the quick calculation and processing of those coefficients, especially for very large data. As technology improves in fields such as medical imaging, algorithms that use B-Splines will need to process increasingly higher resolution images and voxel volumes. New implementations are needed to make use of modern parallel architectures to keep these algorithms practical.
This thesis presents a library for performing many common B-Splines operations in CUDA, the parallel programming framework for NVIDIA GPUs, and analyzes the considerations necessary when implementing a large-scale parallel version of such a well-established sequential algorithm. This library is meant to be used both by C++ programs as well as algorithms implemented in MATLAB without requiring significant changes.
Significant speedups are obtained using this library to perform various common B-Spline image processing operations (as much as 30x for some)...
The issue of vibration isolation challenges engineers' designs across the engineering spectrum. From an engineering standpoint, vibration control impacts the fields of transportation,
manufacturing, construction and mechanical design. Dynamic systems produce vibrations for various reasons i.e. rotating unbalanced masses (high speed turbines); inertia of reciprocating components (internal combustion engines); irregular rolling contact (automobiles) or induced
eddy current (locomotives) vibrations. In most cases, vibrations cause only physical discomfort and/or loss of accuracy. But in extreme cases, transmitted forces may cause a body to undergo high amplitude resonant vibrations, leading to high cyclic stresses and imminent fatigue failure resulting in a catastrophic occurrence and possible loss of life. Therefore, isolating the vibration's source from other system components becomes essential. Deploying a parallel underdamped spring-damper arrangement achieves this required isolation by suspending the component's mass.
The frequency response function (FRF) of a second order under-damped suspension model suggests that for a given excitation frequency, suspensions with lower natural frequencies benefits vibration isolation. Lowering the natural frequency requires springs with low stiffness. Using soft springs is not always plausible as it significantly reduces the suspension's load carrying capacity. Therefore...
Engineers are researching solutions to resolve many of today's technical challenges. Numerical techniques are used to solve the mathematical models that arise in engineering problems. A numerical technique that is increasingly being used to solve mathematical models in engineering research is called the B-spline Collocation Method. The B-spline Collocation Method has a few distinct advantages over the Finite Element and Finite Difference Methods. The main advantage is that the B-spline Collocation Method efficiently provides a piecewise-continuous, closed form solution. Another advantage is that the B-spline Collocation Method procedure is very simple and easy to apply to many problems involving partial differential equations. The current research involves developing, and extensively documenting, a comprehensive, step-by-step procedure for applying the B-spline Collocation Method to the solution of Boundary Value problems. In addition, the current research involves applying the B-spline Collocation Method to solve the mathematical model that arises in the deflection of a geometrically nonlinear, cantilevered beam. The solution is then compared to a known solution found in the literature.