Gavriliu, Marcel (2005) Towards more efficient interval analysis: corner forms and a remainder interval Newton method. Dissertation (Ph.D.), California Institute of Technology. http://resolver.caltech.edu/CaltechETD:etd-06022005-174844
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)|
|Defense Date:||26 May 2005|
|Default Usage Policy:||No commercial reproduction, distribution, display or performance rights in this work are provided.|
|Deposited By:||Imported from ETD-db|
|Deposited On:||03 Jun 2005|
|Last Modified:||26 Dec 2012 02:50|
- Final Version
See Usage Policy.
Repository Staff Only: item control page