CaltechTHESIS
  A Caltech Library Service

Towards More Efficient Interval Analysis: Corner Forms and a Remainder Interval Newton Method

Citation

Gavriliu, Marcel (2005) Towards More Efficient Interval Analysis: Corner Forms and a Remainder Interval Newton Method. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/C196-9R88. https://resolver.caltech.edu/CaltechETD:etd-06022005-174844

Abstract

In this thesis we present two new advancements in verified scientific computing using interval analysis:

1. The Corner Taylor Form (CTF) interval extension. The CTF is the first interval extension for multivariate polynomials that guarantees smaller excess width than the natural extension on any input interval, large or small. To help with the proofs we introduce the concept of Posynomial Decomposition (PD). Using PD we develop simple and elegant proofs showing the CTF is isotonic and has quadratic or better (local) inclusion convergence order. We provide methods for computing the exact local order of convergence as well as the magnitude of excess width reduction the CTF produces over the natural extension.

2. The Remainder Interval Newton (RIN) method. RIN methods use first order Taylor Models (instead of the mean value theorem) to linearize (systems of) equations. We show that this linearization has many advantages which make RIN methods significantly more efficient than conventional Interval Newton (IN). In particular, for single multivariate equations, we show that RIN requires only order of the square root as many solution regions as IN does for the same problem. Therefore, RIN realizes same order savings in both time and memory for a significant overall improvement.

We also present a novel application of the two contributions to computer graphics: Beam Tracing Implicit Surfaces.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:corner taylor form; global nonlinear optimization; inclusion functions; interval analysis; interval newton; remainder interval newton; root finding; taylor form
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Computer Science
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Barr, Alan H.
Thesis Committee:
  • Barr, Alan H. (chair)
  • Marsden, Jerrold E.
  • Desbrun, Mathieu
  • Schroeder, Peter
Defense Date:26 May 2005
Funders:
Funding AgencyGrant Number
NSFASC-89-20219
NSFACI-9982273
Air Force Office of Scientific ResearchF49620-96-1-0471
JPL/NASA Manifold Approximation projectUNSPECIFIED
Office of the Director of Defense Research and EngineeringUNSPECIFIED
Record Number:CaltechETD:etd-06022005-174844
Persistent URL:https://resolver.caltech.edu/CaltechETD:etd-06022005-174844
DOI:10.7907/C196-9R88
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:2393
Collection:CaltechTHESIS
Deposited By: Imported from ETD-db
Deposited On:03 Jun 2005
Last Modified:10 Dec 2020 20:35

Thesis Files

[img]
Preview
PDF (thesis.pdf) - Final Version
See Usage Policy.

7MB

Repository Staff Only: item control page