| Search the Collection|Browse Subjects|Services|Library Information|Community |News & Events | |
|
|
|
|
|
|
|
|
||||
|
|||||||
Type of Document Dissertation Author Cheng, Hao , URN etd-10072002-150220 Title Theory and algorithms for cubic L1 splines Degree PhD Graduate Program Operations Research Advisory Committee
Advisor Name Title Shu-Cherng Fang Committee Chair Henry L.W. Nuttle Committee Co-Chair Elmor L. Peterson Committee Member Hien T. Tran Committee Member John E. Lavery Committee Member Yahya Fathi Committee Member Keywords
- L1 splines
- geometric programming
- nonlinear programming
- optimization
- shape preservation
- interpolating splines
- smoothing splines
Date of Defense 2002-10-07 Availability unrestricted Abstract In modern geometric modeling, one of the requirements for interpolants is that they ?preserve shape well.? Shape preservation has often been associated with preservation of monotonicity and convexity/concavity. While shape preservation cannot yet be defined quantitatively, it is generally agreed that shape preservation involves eliminating extraneous non-physical oscillation. Classical splines, which exhibit extraneous oscillation, do not ?preserve shape well.?
Recently, Lavery introduced a new class of cubic L1 splines. Empirical experiment has shown that cubic L1 splines are cable of providing C1-smooth, shape-preserving, multi-scale interpolation of arbitrary data, including data with abrupt changes in spacing and magnitude, with no need for monotonicity or convexity constraints, node adjustment or other user input. However, the shape-preserving capability of cubic L1 splines has not been proved theoretically. The currently available algorithm only provides an approximation to the coefficients of cubic L1 splines.
To lay the groundwork for theoretical analysis and the development of an exact algorithm, this dissertation proposes to treat cubic L1 spline problems in a geometric programming framework. Such a framework leads to a geometric dual problem with a linear objective function and convex quadratic constraints. It also provides a linear system for dual-to-primal conversion.
We prove that cubic L1 splines preserve shape well, in particular, in eliminating non-physical oscillations, without review of raw data or any human intervention. We also show that cubic L1 splines perform well for multi-scale data, as well as preserve linearity and convexity/concavity under mild conditions.
An exact algorithm based on the geometric programming model is proposed for solving cubic L1 splines. It decomposes the geometric programming problem into several independent small-sized sub-problems and applies a specialized active set algorithm to solve the sub-problems. The algorithm is numerically stable and highly parallelizable. It requires only simple algebraic operations.
Files
Filename Size Approximate Download Time (Hours:Minutes:Seconds)
28.8 Modem 56K Modem ISDN (64 Kb) ISDN (128 Kb) Higher-speed Access etd.pdf 852.23 Kb 00:03:56 00:02:01 00:01:46 00:00:53 00:00:04