Mercurial > hg > thesis
changeset 0:d2ada4dc47dc
First commit
author | Jordi Gutiérrez Hermoso <jordigh@gmail.com> |
---|---|
date | Sun, 06 Jul 2008 15:18:09 -0500 |
parents | |
children | 3ecb46831106 |
files | apology.tex code.tex preamble.tex rbf-ddm.tex thesis.bib thesis.tex |
diffstat | 6 files changed, 472 insertions(+), 0 deletions(-) [+] |
line wrap: on
line diff
new file mode 100644 --- /dev/null +++ b/apology.tex @@ -0,0 +1,147 @@ +\chapter{Apolog\'ia} + +Quiero empezar ofreciendo unos pensamientos del manual en espa\~nol de +\TeX{}macs\footnote{\TeX{}macs es un editor principalmente de textos + matem\'aticos que usa \TeX para formatear el texto y una interfase + tipo GNU Emacs para la edici\'on. Naturalmente, \TeX{}macs tambi\'en + es software libre.} acerca del software libre y su relaci\'on con +las matem\'aticas: + +\begin{quote} +Como un matem\'atico, estoy profundamente convencido que s\'olo los +programas libres son aceptables desde un punto de vista cient\'ifico. +Veo dos razones principales para esto: + +\begin{itemize} + \item Un resultado computado por un sistema ``matem\'atico'', cuyo + c\'odigo fuente no es p\'ublico, no puede ser aceptado como parte de + una prueba matem\'atica. + + \item As\'i como a un matem\'atico deber\'ia ser capaz de construir + sobre teoremas encima de otros teoremas, deber\'ia ser posible + modificar y liberar algoritmos de software matem\'atico libremente. +\end{itemize} + +Sin embargo, es extra\~no, y una verg\"uenza, que los principales +programas matem\'aticos que est\'an siendo usados actualmente sean +privativos. La principal raz\'on para esto es que los matem\'aticos +muchas veces no consideran la programaci\'on como una actividad +cient\'ifica completa. Consecuentemente, el desarrollo de software +\'util es delegado a ``ingenieros'' y los programas resultantes son +usados como cajas negras. + +Esta subdivision de la actividad cient\'ifica es muy artificial: con +frecuencia es muy importante desde un punto de vista cient\'ifico +saber que est\'a dentro de la caja negra. Rec\'iprocamente, un +profundo conocimiento cient\'ifico usualmente conduce a la +producci\'on de mejor software. Consecuentemente, pienso que los +cient\'ificos deber\'ian abogar por el desarrollo de software como una +actividad cient\'ifica total, comparable a la escritura de +art\'iculos. Entonces es claro tambi\'en que tal software deber\'ia +ser difundido en una forma que sea compatible con los requirimientos +de la ciencia: disponibilidad p\'ublica, reproductibilidad y +usabilidad libre. +\end{quote} + +Esta tesis de maestr\'ia es software libre, distribuida bajo los +t\'erminos de la GNU\footnote{GNU quiere decir ``GNU's not Unix'', un + proyecto de mediados de los 80 del siglo pasado para crear un + sistema operativo completamente libre y compatible con Unix. En la + actualidad, el proyecto GNU junto con el n\'ucleo Linux han + alcanzado esta meta dando a luz el sistema operativo GNU/Linux.} +GPL\footnote{General Public License, la licencia bajo la cual se + distribuye casi todo el software GNU y aproximadamente el 60\%-70\% + de la totalidad del software libre. Es una licencia tipo copyleft. + Es decir, exige que cualquier obra derivada de otra obra cubierta + por la GPL tambi\'en sea GPL y por lo tanto libre.} versi\'on 3 u +opcionalmente cualquier versi\'on posterior. Adem\'as de la +justificaci\'on dada por Joris van der Hoeven, el autor de \TeX{}macs +y el texto que acabo de citar, quisiera agregar algunas palabras. + +En cierta forma, me veo legalmente obligado a liberar el c\'odigo de +mi tesis bajo la GPL, pero la obligaci\'on en realidad es m\'as bien +moral que legal. Explicar\'e por qu\'e. En la elaboraci\'on de esta +tesis he usado +\begin{itemize} + \item \emph{GNU Emacs} como editor y entorno integral de desarrollo, + \item \emph{gcc} como compilador, + \item \emph{kdbg} como interfase gr\'afica al depurador \emph{gdb}, + \item La \emph{GNU Scientific Library} como biblioteca para + operaciones num\'ericas b\'asicas, + \item La biblioteca \emph{Boost} para suplementar algunas funciones + b\'asicas de C++ que se espera sean parte del pr\'oximo est\'andar + de C++ disponible en 2009, + \item La biblioteca \emph{Qt} para generar una interfase gr\'afica + para mi tesis, + \item \emph{GNU Octave} para depurar brevemente algunas ideas + num\'ericas antes de programarlas en C++, + \item \emph{Octaviz} para visualizar junto con Octave los resultados + de los c\'alculos que a su vez usa la biblioteca \emph{VTK} para + generar gr\'aficas mediante \emph{OpenGL}, + \item \emph{te\TeX{}} y \emph{\TeX{}live} como distribuciones \TeX{} + para formatear el texto de mi tesis, +\end{itemize} +entre otros. Todo este software est\'a bajo la GPL excepto VTK y Boost +que est\'an bajo una licencia libre tipo BSD, no copyleft, y \TeX{} +que tambi\'en tiene su propia licencia, pero como he enlazado mi +c\'odigo con software GPL, las cl\'ausulas copyleft de la GPL me +obligan a que mi mismo c\'odigo tambi\'en se distribuya bajo los mismo +t\'erminos que la GPL. + +Hay tambi\'en mucho m\'as software que aqu\'i no menciono +expl\'icitamente que he usado en la elaboraci\'on de esta tesis, pero +todo el software que he usado, desde los editores y compiladores hasta +el mismo n\'ucleo del sistema operativo en el que he trabajado es +software libre. No hay absolutamente nada oculto en lo que he hecho, +ni una sola l\'inea de c\'odigo en ning\'un nivel que no est\'e +disponible para el escrutinio de cualquier p\'ublico. Como van der +Hoeven, creo que esto es sumamente importante para el desarrollo de +software relevante para las matem\'aticas. + +Aunque mi obligaci\'on legal de liberar esta tesis bajo la GPL +es por haber enlazado mi c\'odigo con bibliotecas GPL como Qt y la +GSL, siento que mi obligaci\'on moral es mucho mayor por la deuda +k\'armica que le tengo a todos los autores de software libre que +generan software matem\'atico adecuado para muchos usos. Tengo la +esperanza de que esta tesis demuestre que el software libre no es +idealismo vacuo, sino una realidad factible y una alternativa al +desarrollo de software que esconde el c\'odigo fuente e intenta +limitar legalmente la cooperaci\'on entre matem\'aticos, cient\'ificos +e ingenieros. El software privativo es anticiencia, antimatem\'aticas +y anticooperaci\'on. No hay ninguna raz\'on para tolerarlo. + +Tampoco no hay ninguna raz\'on para suponer que software matem\'atico +como Mathematica, Maple o Mathematica s\'olo se puede desarrollar bajo +el modelo del software privativo. Tenemos muchos ejemplos de software +libre especializado como \emph{GAP} para teor\'ia de grupos. +\emph{Pari/GP} para teor\'ia de n\'umeros y \emph{Singular} para +\'algebra conmutativa y geometr\'ia algebraica que demuestran la +posibilidad de crear software matem\'atico de calidad, pero sobre +todo, libre. Tambi\'en en a\~nos m\'as recientes empezamos a ver +software para prop\'ositos generales como \emph{Maxima} o \emph{SAGE} +que quiz\'as alg\'un d\'ia logren suplantar la verg\"uenza que van der +Hoeven isin\'ua son las tres grandes M's. + +Cierto es que en ingenier\'ia y an\'alisis num\'erico el software +libre tiene un poco menos de difusi\'on y no dudo que esto pueda ser +el resultado de que los ingenieros est\'an m\'as acostumbrados que los +matem\'aticos y cient\'ificos a trabajar en grandes corporaciones +donde las patentes, los secretos industriales y los acuerdos de no +divulgaci\'on son muy comunes. No obstante, no creo que el software +num\'erico o ingenieril se deba someter a ning\'un est\'andar +diferente al de cualquier otro software matem\'atico y que por lo +tanto, tambi\'en deber\'ia de ser libre. + +As\'i pues, esta tesis es software libre, incluyendo el texto de la +misma. Esto significa que hasta la misma fuente \LaTeX{} que estoy ahora +escribiendo estar\'a disponible para cualquiera en la direcci\'on +web \url{http://www.cimat.mx/~jordi/thesis}, o en el mismo sitio donde +se encontr\'o el texto formateado, para ser analizada, distribuida y +de ser necesario, modificada. Los t\'erminos exactos bajo los cuales +esto es posible se dan en el ap\'endice. + +Suficiente filosof\'ia. Demos ahora lugar a las matem\'aticas. +%%% Local Variables: +%%% mode: latex +%%% TeX-master: "thesis" +%%% End:
new file mode 100644 --- /dev/null +++ b/code.tex @@ -0,0 +1,82 @@ +\chapter{Estructura del c\'odigo y algoritmos} + +\section{Introducci\'on} + +Hemos decidido programar casi todo en C++, por varios motivos. +Primeramente, porque C++ es un lenguaje compilado muy cerca del +c\'odigo m\'aquina y por lo tanto muy eficiente. Segundo, porque hay +muchas bibliotecas de C y C++ que nos ayudaron en la elaboraci\'on de +nuestros algoritmos, entre las cuales destaca en particular la +biblioteca est\'andar de C++ (tambi\'en conocida a veces como la +\emph{Standard Template Library}, biblioteca est\'andar de +plantillas), de la cual hacemos amplio uso sin ning\'un +escr\'upulo. Tambi\'en usamos la \emph{GNU Scientific Library} (GSL) y +algunas funciones de \emph{Boost} para mayor funcionalidad. + +La \'ultima raz\'on puede llegar a ser m\'as contenciosa, sobre todo +entre numeristas donde C++ no tiene una tradici\'on tan extensa como C +o Fortran. Estoy hablando sobre la programaci\'on orientada a objetos +y algunas otras cualidades m\'as avanzadas de C++, como excepciones, +plantillas, manejo autom\'atico de memoria, espacios nominales +(\emph{namespaces} en ingl\'es) y otras abstracciones que en mi +opini\'on facilitan el desarrollo de software. Justificar\'e +brevemente la elecci\'on de haber usado algunas de estas cualidades de +C++, pues he visto que todas ellas hayan sido criticadas por +numeristas. + +\begin{description} + \item[La bilblioteca est\'andar:] La biblioteca est\'andar de C++ es + un software sumamente desarrollado y probado. Los algoritmos que se + encuentran ah\'i son el producto de muchos a\~nos de trabajo de + excelentes programadores de todo el mundo. La implementaci\'on + particular de GCC que yo he usado es una derivaci\'on de una + implementaci\'on libre iniciada por Hewlett Packard. + + \item[Excepciones:] Las excepciones son un m\'etodo alterno para + manejar condiciones de error en el programa. La GSL tiene + predeterminadamente un manejo de error algo fr\'agil, donde + cualquier error por peque\~no que sea para en seco la ejecuci\'on + del programa, pero nos pareci\'o m\'as c\'omodo reemplazar este + mecanismo por excepciones. Una ventaja en particular de las + excepciones es que permiten separar el c\'odigo principal del manejo + de condiciones de error. + + \item[Espacios nominales:] El uso de espacios nominales es una + alternativa a ponerle prefijos a los nombres de todas las + variables. En cierto sentido, simplemente son prefijos que + opcionalmente se pueden hacer invisibles dentro de ciertos contextos + y no complican en nada la elaboraci\'on del c\'odigo. +\end{description} + +\'Estos detalles no son tan importantes sobre la implementaci\'on. La +elecci\'on de programar con orientaci\'on a objetos es m\'as peculiar +y requiere una justificaci\'on y explicaci\'on m\'as plena. + +\section{Programaci\'on orientada a objetos} + +En c\'odigo num\'erico no es muy com\'un ver programaci\'on orientada +a objetos, pero sostengo que no hay raz\'on para ello. Las mismas +abstracciones que son \'utiles para otros motivos son \'utiles para +las matem\'aticos y el software num\'erico. Por ejemplo, en mi +c\'odigo hay clases para dominios, operadores diferenciales, +funciones, interpoladores y funciones base radiales, con subclases y +relaciones entre s\'i que modelan las mismas relaciones que tienen los +objetos matem\'aticos correspondientes. Se dice que usar clases reduce +la eficiencia del c\'odigo final, pero yo he comprobado que el +desperdicio de recursos con clases es absolutamente despreciable si es +que existe. En efecto, a menudo las optimizaciones que el mismo +compilador hace producen c\'odigo objeto que no difiere del mismo +c\'odigo sin clases. Por contraparte, el ahorro de tiempo que +programar con clases ofrece durante el proceso de desarrollo y +depuraci\'on del software da contrapeso a cualquier deficiencia real o +imaginaria que pudiera haber en el desempe\~no del programa durante su +ejecuci\'on. + +Un punto muy importante de la programaci\'on orientada a objetos es la +reusabilidad del c\'odigo, que fue para nosotros una meta clave en la +elaboraci\'on de este software. + +%%% Local Variables: +%%% mode: latex +%%% TeX-master: "thesis" +%%% End:
new file mode 100644 --- /dev/null +++ b/preamble.tex @@ -0,0 +1,47 @@ +\documentclass{book} +\usepackage{amsmath, amsthm, amssymb} +\usepackage{fancybox, url} +\usepackage{syntonly} +\usepackage[spanish]{babel} +\spanishdecimal{.} + + +\theoremstyle{plain} +\newtheorem*{teo}{Teorema} +\newtheorem*{lema}{Lema} +\newtheorem{cor}{Corolario} +\newtheorem*{eg}{Ejemplo} +\newtheorem*{prop}{Proposici\'on} +\newtheorem{ej}{Ejercicio} + +\theoremstyle{definition} +\newtheorem*{defn}{Definici\'on} +\newtheorem*{com}{Comentario} +\newtheorem*{notn}{Notaci\'on} +\newtheorem*{obs}{Observaci\'on} + +\newcommand{\CC}{\mathbb{C}} +\newcommand{\RR}{\mathbb{R}} +\newcommand{\QQ}{\mathbb{Q}} +\newcommand{\ZZ}{\mathbb{Z}} +\newcommand{\NN}{\mathbb{N}} + +\newcommand{\leftbb}{\left[ \! \left[} +\newcommand{\rightbb}{\right] \! \right]} +\newcommand{\bracket}[2]{\left<{#1} \middle|{#2}\right>} +\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor} +\newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil} +\newcommand{\del}{\partial} + +\renewcommand{\ker}{\operatorname{k\acute{e}r}} + +\author{Jordi Guti\'errez Hermoso \\ Asesores de tesis: Miguel \'Angel + Moreles V\'asquez y Pedro Gonz\'alez Casanova} \date{\today} + +\title{Funciones base radiales y ecuaciones diferenciales parciales} + + +%%% Local Variables: +%%% mode: latex +%%% TeX-master: "thesis" +%%% End:
new file mode 100644 --- /dev/null +++ b/rbf-ddm.tex @@ -0,0 +1,147 @@ +\chapter[FBR y MDD]{Funciones base radiales y descomposici\'on de dominios} +\section{Introducci\'on} +Empecemos con una definici\'on clave. +\begin{defn} + \label{rbf-def} + Una funci\'on $\phi : \RR^n \to \RR$ es \emph{radial} si existe + alg\'un punto $c \in \RR^n$ y una funci\'on $\tilde{\phi} : \RR \to +\RR$ tal que $\phi(x) = \tilde{\phi}(|x - c|)$. +\end{defn} +Brevemente, una funci\'on radial depende solamente de la distancia +desde alg\'un punto en $\RR^n$. Pronto daremos ejemplos relevantes de +funciones radiales. Antes, consid\'erese de manera general el problema +de valor en la frontera (PVF) +\begin{equation} + \label{thebvp} + \begin{cases} + \mathcal{L}u &= f \quad \text{en } \Omega, \\ + \mathcal{B}u &= g \quad \text{en } \del\Omega, + \end{cases} +\end{equation} +donde $\mathcal{L}$ y $\mathcal{B}$ son operadores diferenciales +lineales, $\Omega$ es un dominio abierto y conexo como todos los +dominios considerados en esta obra, y $f$ y $g$ son funciones reales +en $\RR^n$ sin ninguna suposici\'on adicional. El operador +$\mathcal{B}$ puede representar condiciones de Dirichlet, Neumann, +Robin o alguna mezcla de \'estas en diferentes puntos de la frontera. + +La idea de \emph{funciones base radiales} (FBR) es en principio muy +sencilla. Escogemos algunos puntos $\Xi_I \subset \Omega$ y $\Xi_F +\subset \del\Omega$. En el m\'etodo de colocaci\'on asim\'etrico, el +\'unico que consideramos en esta obra y el m\'as sencillo de plantear, +centramos una FBR $\phi_p$ en cada $p \in \Xi := \Xi_I \cup \Xi_F$ y +proponemos la aproximaci\'on +\begin{equation} + \label{theinterp} + \tilde{u} := \sum_{p \in \Xi} u_p \phi_p, +\end{equation} +donde las $u_p$ son constantes. Al introducir la aproximaci\'on +propuesta \eqref{theinterp} en el PVF \eqref{thebvp} y evaluar en cada +punto de $\Xi$, obtenemos el sistema lineal +\begin{align*} + \sum_{p \in \Xi} u_p \mathcal{L}\tilde{\phi}(q) &= f(q) \quad + \text{para cada } q \in \Xi_I, \\ + \sum_{p \in \Xi} u_p \mathcal{B}\tilde{\phi}(q) &= g(q) \quad + \text{para cada } q \in \Xi_F, +\end{align*} +o en forma matricial, +\[ +\left[ + \begin{array}{c|c} + \mathcal{L}\phi_I & \mathcal{L}\phi_F \\ + \hline + \mathcal{B}\phi_I & \mathcal{B}\phi_F + \end{array} +\right] +\begin{bmatrix} + u_I \\ + u_F \\ +\end{bmatrix} += +\begin{bmatrix} + f(\Xi_I)\\ + g(\Xi_F) +\end{bmatrix}, +\] +donde los sub\'indices $I$ y $F$ indican FBRs, coeficientes, o puntos +del interior y de la frontera respectivamente. Abreviemos este sistema +lineal por medio de $M\vec{u} = \vec{f}$. Entonces basta invertir $M$ +para obtener una soluci\'on a \eqref{thebvp}. Observemos que si +tomamos el PVF trivial con $\mathcal{L}$ igual al operador identidad +$I$ y usamos $\Xi_F = \emptyset$, entonces obtenemos un simple +problema de interpolaci\'on. Las propiedades de las FBRs para +problemas de interpolaci\'on han sido m\'as estudiadas como base +te\'orica para su uso en resolver PVFs y ecuaciones diferenciales +parciales. + +Obs\'ervese que este m\'etodo recuerda vagamente al m\'etodo de +elementos finitos (MEF), salvo que no hay uso de ninguna malla. En vez +de malla, s\'olo se escogen algunos puntos de colocaci\'on que no +tienen por qu\'e tener ninguna estructura en particular. Tambi\'en +n\'otese que la dimensionalidad de $\Omega$ es irrelevante en toda +esta formulaci\'on. Como evaluar una FBR no se vuelve m\'as complicado +conforme el n\'umero de dimensiones de $\Omega$ aumenta, no hace falta +ninguna modificaci\'on al m\'etodo general en dimensiones superiores. + +Por supuesto que el m\'etodo no es panacea, como no lo es ning\'un +otro. A cambio de ahorrarnos los mallados complicados del MEF, nos +vemos obligados a invertir una matriz $M$ que a priori no tiene por +qu\'e tener ninguna propiedad agradable; en efecto, hemos observado ya +que $M$ tiende a ser una matriz grande, llena, no sim\'etrica y mal +condicionada, la pesadilla de todo numerista. + +Veremos c\'omo se puede aliviar un poco este problema usando +descomposici\'on de dominios. La idea es sencilla, y nos concentramos +solamente en el llamado \emph{m\'etodo aditivo de Schwarz}. +Brevemente, la idea en los m\'etodos de Schwarz (hay tambi\'en uno +llamado \emph{multiplicativo} que es muy similar), es descomponer el +dominio $\Omega = \cup_{i=1}^k \Omega_i$ donde cada $\Omega_i$ se +traslapa con otra $\Omega_j$ y resolver el PVF resultante en cada +$\Omega_i$, donde en cada frontera artificial interior (es decir, +donde $\del \Omega_i \cap \del \Omega = \emptyset$) imponemos +condiciones de Dirichlet iterativamente seg\'un donde dicha frontera +artificial se traslape con otro subdominio $\Omega_j$. Se mide +entonces la convergencia con respecto a estas fronteras artificiales. + +Los m\'etodos de descomposici\'on de dominios (MDD) ofrecen entonces +matrices m\'as peque\~nas y ligeramente mejor condicionadas, aunque +habr\'a m\'as matrices que invertir. Con suficientes subdominios +escogidos juiciosamente, est\'a claro que el trueque entre una matriz +grande y mal condicionada y muchas peque\~nas pero ligeramente mejor +condicionadas es conveniente. Veremos tambi\'en que las iteraciones +sobre las fronteras artificiales pueden ser muy r\'apidas sin +necesidad de hacer demasiadas factorizaciones $LU$ de las matrices. + +\section{Funciones base radiales} + +Para efectos de esta obra, nos enfocaremos en s\'olo seis tipos de +funciones base radiales. Sea $\tilde{\phi}$ seg\'un la definici\'on +\eqref{rbf-def}. En el cuadro \ref{the-rbfs} vemos algunas +posibilidades para $\tilde{\phi}(r)$ que dan lugar a FBRs distintas. +\begin{table}[h] + \begin{center} + \ovalbox{ + \begin{tabular}{r|l} + \text{Polinomial seccional o c\'onica} & $r^n,$ \text{$n$ impar} \\ + \text{Trazador (\emph{spline}) de capa delgada} & $r^n \log r,$ + \text{$n$ par}\\ + \text{Multicu\'adrica} & $\sqrt{1 + (\epsilon r)^2}$ \\ + \text{Multicu\'adrica inversa} & $(1 + (\epsilon r)^2)^{-1/2}$ \\ + \text{Cuadr\'atica inversa} & $(1 + (\epsilon r)^2)^{-1}$ \\ + \text{Gaussiana} & $e^{-\epsilon r^2}$ + \end{tabular} + } + \end{center} + \caption{Algunas funciones base radiales} + \label{the-rbfs} +\end{table} + +De estas FBRs, las \'ultimas cuatro con par\'ametro $\epsilon$ son +$C^\infty$ y las primeras dos con par\'ametro $n$ tan s\'olo son +seccionalmente suaves \cite{Larsson/Fornberg:2003}. + + +%%% Local Variables: +%%% mode: latex +%%% TeX-master: "thesis" +%%% End:
new file mode 100644 --- /dev/null +++ b/thesis.bib @@ -0,0 +1,24 @@ +@Article{Larsson/Fornberg:2003, +author = {Larsson, E. and Fornberg, B.}, +title = {A Numerical Study of Some Radial Basis Function Based Methods + for Elliptic {PDE}s}, +journal = {Computers and Mathematics with Applications}, +year = 2003, +volume = 45, +pages = {891--902} +} + +@Article{, + author = {}, + title = {}, + journal = {}, + year = {}, + volume = {}, + number = {}, + pages = {}, + month = {}, + note = {}, + annote = {} +} + +
new file mode 100644 --- /dev/null +++ b/thesis.tex @@ -0,0 +1,25 @@ +\include{preamble} +%\syntaxonly +\includeonly{apology, rbf-ddm, code} + +\begin{document} +\bibliographystyle{acm} + +\frontmatter +\maketitle +\tableofcontents + +\include{apology} + +\mainmatter +\include{rbf-ddm} +\include{code} + +\appendix + +\addcontentsline{toc}{chapter}{Bibliograf\'ia} +\bibliography{thesis} + +\backmatter + +\end{document}