Investigación de las propiedades de un operador de reconstrucción no lineal en mallados no uniformes

Abstract

[SPA] Esta tesis doctoral se presenta bajo la modalidad de compendio de publicaciones. Los esquemas de subdivisión y multiresolucion se han utilizado en las últimas décadas en muchas aplicaciones que requieren del diseño geométrico. Estas aplicaciones son numerosas en la industria, por ejemplo, para la fabricación de coches y barcos, y también en la industria cinematográfica para generar diferentes formas tanto en 2D como en 3D: Los esquemas de subdivisión se basan en un proceso de refinamiento sucesivo de un conjunto inicial de datos discretos. Se genera un nuevo conjunto de datos más denso de acuerdo con algunas reglas específicas. A su vez, este nuevo conjunto se refinará aún más. En este punto surgen diversas cuestiones matemáticas importantes, y que van desde asegurar la convergencia de los esquemas a estudiar la suavidad de la función límite, la estabilidad de los esquemas de subdivisión, el orden de aproximación y los requisitos necesarios para su aplicabilidad en problemas de la vida real. En particular, es importante el análisis de las capacidades de preservación de los esquemas para algunas propiedades cruciales que podrán estar presentes en el conjunto inicial de datos, tal como la convexidad. Los esquemas de subdivisión generan algoritmos rápidos para la fácil construcción de curvas y superficies [26], [29]. Todas estas cualidades los convierten en una herramienta interesante para diversas aplicaciones industriales. Además, su estrecha relación con esquemas de multirresolución abre la puerta a más aplicaciones en el campo del procesamiento de datos y señales. Los procesos de compresión y eliminación de ruido son fáciles de implementar mediante el uso de esquemas de multiresolución y se ha comprobado que son bastante eficientes. Véase, por ejemplo [35], [5], [2]. Una cuestión principal a la hora de elegir un esquema de subdivisión adecuado es la propiedad de conservación de la convexidad, porque muchas aplicaciones la requieren. Se han hecho muchos esfuerzos en este sentido, véase por ejemplo [27], [32], [33], [37]. La estabilidad es también un problema principal en las aplicaciones de la vida real, ya que los diseños finales se generan mediante el refinamiento de un conjunto inicial de puntos que suele estar afectado por algún error. Por lo tanto, es esencial hacer un seguimiento del error y mantenerlo por debajo de una tolerancia prescrita. Algunas referencias recomendadas sobre la estabilidad de los esquemas de subdivisión y multiresolución pueden consultarse en [24], [9], [11], [1], [3], [15]. Harten derivó una teoría que conecta estrechamente los operadores de reconstrucción con los esquemas de subdivisión y multiresolución [35], [5]. Las reconstrucciones no lineales aparecen como una buena opción para minimizar los efectos adversos de las posibles singularidades y para mejorar la adaptación a los datos dados. Esta teoría no es tan fácil de estudiar como para el caso lineal. Los operadores de reconstrucción no lineales dan lugar a esquemas de subdivisión y multiresolución no lineales. Para dejar claro el tipo de dificultades que se pueden encontrar, mencionamos por ejemplo el caso del análisis de estabilidad. A este respecto, se ha demostrado que todos los esquemas de subdivisión y multiresolución lineales son estables, mientras que se necesita un análisis particular para cada esquema no lineal concreto. Los esquemas de multiresolución están profundamente conectados con los esquemas de subdivisión y heredan muchas de sus propiedades. Para más información sobre estas herramientas se puede consultar [5] como primera referencia. En [6] se introdujo una reconstrucción no lineal denominada PPH y se estudio el esquema de subdivisión asociado. Esta reconstrucción se definió con el fin de adaptarse a la presencia de potenciales singularidades. Consiste en una modificación ingeniosa de la interpolación centrada de cuarto orden de Lagrange a trozos. Para implementar la adaptación, la reconstrucción se realiza localmente en un intervalo [xj ; xj+1] usando los valores disponibles de la función en las cuatro abscisas centradas fxjð€€€1; xj ; xj+1; xj+2g; y teniendo en cuenta dos aspectos principales. El primer aspecto es que la modificación en un área donde la función subyacente es suave debe hacerse de tal manera que las cantidades alteradas no cambien significativamente, de modo que la modificación siga siendo O(h4); donde h representa el espaciado del mallado. El segundo aspecto es que, en los intervalos adyacentes a una singularidad, pero que no la contienen, la reconstrucción conserve cierto orden de aproximación, de hecho O(h2); al contrario de lo que ocurre con su homólogo lineal que pierde completamente el orden de aproximación. Esta tesis se dedica principalmente al estudio del operador de reconstrucción no lineal PPH en mallados no uniformes. En algunos casos y para demostrar determinados resultados teóricos haremos uso de mallados σ cuasi uniformes, que no son otra cosa que un tipo de mallados no uniformes que aparecen en casi todas las aplicaciones prácticas. La definición exacta se da más adelante.

[ENG] This doctoral dissertation has been presented in the form of thesis by publication. Subdivision and multiresolution schemes have been used in the last few decades in many ap- plications that require from geometrical design. These applications are numerous in industry, for example for car and ship manufacturing, and also in the film industry in order to generate different shapes as much in 2D as in 3D. Subdivision schemes are based on a process of successive refine- ment of a given initial discrete data set. A new denser set of data is generated according to some specific rules. In turn, this new set will be further refined. A bunch of important mathematical questions arise at this point, and range from ensuring the convergence of the schemes, studying the smoothness of the limit function, the stability of the subdivision schemes and the order of approxi- mation and the necessary requirements for their applicability in real life problems. In particular, it is important the analysis of the preservation capabilities of the schemes for some crucial properties which might be present in the initial set of data such as it could be the convexity. Subdivision schemes generate fast algorithms to the easy construction of curves and surfaces [26], [29]. All these qualities make them an interesting tool for several industrial applications. Also, their close relation to multiresolution schemes opens the door to more applications in the fields of data and signal processing. Compression and denoising processes are easy to implement by using multiresolution schemes and they have been tested to be quite efficient. See for example [35], [5], [2]. A chief issue in choosing an adequate subdivision scheme is the property of convexity preser- vation, because many application require it. Many efforts have been done in this sense, see for example [27], [32], [33], [37]. Stability is also a main issue in real life applications, since the final designs are generated through the refinement of an initial set of points which usually is affected by some error. Therefore, keeping track of the error and maintaining it under a prescribed tolerance is essential. Some recommended references about stability of subdivision and multiresolution schemes can be consulted in [24], [9], [11], [1], [3], [15]. Harten derived a theory which closely connects reconstruction operators with subdivision and multiresolution schemes [35], [5]. Nonlinear reconstructions appear as a good option to minimize the adverse effects of potential singularities and to improve the adaptation to the given data. This theory is not as easy to study as for the linear case. Nonlinear reconstruction operators give rise to nonlinear subdivision and multiresolution schemes. In order to let clear the kind of difficulties to be encountered, we mention for example the case of stability analysis. In what stability issues regards, all linear subdivision and multiresolution schemes are proved to be stable, while a particular analysis is needed for each particular nonlinear scheme. Multiresolution schemes are deeply connected with subdivision schemes and they inherit many of their properties. For more information about these useful schemes one can consult [5] as a first reference. In [6] a nonlinear reconstruction called PPH was introduced, and the associated subdivision scheme was studied. This reconstruction was built in order to get adapted to the presence of potential singularities. It consist on a witty modification of the centered fourth order piecewise Lagrange interpolation. In order to implement the adaptation, the reconstruction is built also locally using a stencil of four centered data, but keeping in mind two main concerns. The first concern is that the modification in an area where the underlying function is smooth must be done in such a way that the modified quantities are not significatively changed, so that the modification remains O(h4), where h stands for the grid size. The second concern is that in the intervals adjacent to a singularity, but not containing it, the reconstruction retains some order of approximation, in fact O(h2), on the contrary to what happens with its linear counterpart that loses completely the approximation order. [ENG] Subdivision and multiresolution schemes have been used in the last few decades in many ap- plications that require from geometrical design. These applications are numerous in industry, for example for car and ship manufacturing, and also in the film industry in order to generate different shapes as much in 2D as in 3D. Subdivision schemes are based on a process of successive refinement of a given initial discrete data set. A new denser set of data is generated according to some specific rules. In turn, this new set will be further refined. A bunch of important mathematical questions arise at this point, and range from ensuring the convergence of the schemes, studying the smoothness of the limit function, the stability of the subdivision schemes and the order of approximation and the necessary requirements for their applicability in real life problems. In particular, it is important the analysis of the preservation capabilities of the schemes for some crucial properties which might be present in the initial set of data such as it could be the convexity. Subdivision schemes generate fast algorithms to the easy construction of curves and surfaces [26], [29]. All these qualities make them an interesting tool for several industrial applications. Also, their close relation to multiresolution schemes opens the door to more applications in the fields of data and signal processing. Compression and denoising processes are easy to implement by using multiresolution schemes and they have been tested to be quite efficient. See for example [35], [5], [2]. A chief issue in choosing an adequate subdivision scheme is the property of convexity preservation, because many application require it. Many efforts have been done in this sense, see for example [27], [32], [33], [37]. Stability is also a main issue in real life applications, since the final designs are generated through the refinement of an initial set of points which usually is affected by some error. Therefore, keeping track of the error and maintaining it under a prescribed tolerance is essential. Some recommended references about stability of subdivision and multiresolution schemes can be consulted in [24], [9], [11], [1], [3], [15]. Harten derived a theory which closely connects reconstruction operators with subdivision and multiresolution schemes [35], [5]. Nonlinear reconstructions appear as a good option to minimize the adverse effects of potential singularities and to improve the adaptation to the given data. This theory is not as easy to study as for the linear case. Nonlinear reconstruction operators give rise to nonlinear subdivision and multiresolution schemes. In order to let clear the kind of difficulties to be encountered, we mention for example the case of stability analysis. In what stability issues regards, all linear subdivision and multiresolution schemes are proved to be stable, while a particular analysis is needed for each particular nonlinear scheme. Multiresolution schemes are deeply connected with subdivision schemes and they inherit many of their properties. For more information about these useful schemes one can consult [5] as a first reference. In [6] a nonlinear reconstruction called PPH was introduced, and the associated subdivision scheme was studied. This reconstruction was built in order to get adapted to the presence of potential singularities. It consists on a witty modification of the centered fourth order piecewise Lagrange interpolation. In order to implement the adaptation, the reconstruction is built also locally using a stencil of four centered data but keeping in mind two main concerns. The first concern is that the modification in an area where the underlying function is smooth must be done in such a way that the modified quantities are not significatively changed, so that the modification remains O(h4), where h stands for the grid size. The second concern is that in the intervals adjacent to a singularity, but not containing it, the reconstruction retains some order of approximation, in fact O(h2), on the contrary to what happens with its linear counterpart that loses completely the approximation order.