. eo 587? I S Meshfree Approximation Methods with MATLAB 1 « INTERDISCIPLINARY MATHEMATICAL SCIENCES Series Editor: Jinqiao Duan (Illinois Inst, of Tech., USA) Editorial Board: Ludwig Arnold, Roberto Camassa, Peter Constantin, Charles Doering, Paul Fischer, Andrei V. Fursikov, Fred R. McMorris, Daniel Schertzer, Bjorn Schmalfuss, Xiangdong Ye, and Jerzy Zabczyk Published Vol. 1: Global Attractors of Nonautonomous Dissipative Dynamical Systems David N. Cheban Vol. 2: Stochastic Differential Equations: Theory and Applications A Volume in Honor of Professor Boris L. Rozovskii eds. Peter H. Baxendale & Sergey V. Lototsky Vol. 3: Amplitude Equations for Stochastic Partial Differential Equations Dirk Blomker Vol. 4: Mathematical Theory of Adaptive Control Vladimir G. Sragovich Vol. 5: The Hilbert-Huang Transform and Its Applications Norden E. Huang & Samuel S. P. Shen Vol. 6: Meshfree Approximation Methods with MATLAB Gregory E. Fasshauer Meshfree Approximation Methods with M A T L AB G r e g o ry E. F a s s h a u er _ r s Illinois Institute of Technology, USA - ^ W r i f l rl ^ H o n t i f in . lb. /• Published by fif-?, Y~ W o r ld Scientific Publishing Co. Pte. Ltd. 5 Toh Tuck Link, Singapore 596224 / t£>&^~ U SA °^ce: 27 W a r r en Street, Suite 401-402, Hackensack, NJ 07601 /] UK office: 57 Shelton Street, Covent Garden, London WC2H 9HE British Library Cataloguing-in-Publication Data A catalogue record for this book is available from the British Library. MESHFREE APPROXIMATION METHODS WITH MATLAB (With CD-ROM) Interdisciplinary Mathematical Sciences — Vol. 6 Copyright © 2007 by World Scientific Publishing Co. Pte. Ltd. All rights reserved. This book, or parts thereof, may not be reproduced in any form or by any means, electronic or mechanical, including photocopying, recording or any information storage and retrieval system now known or to be invented, without written permission from the Publisher. For photocopying of material in this volume, please pay a copying fee through the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, USA. In this case permission to photocopy is not required from the publisher. ISBN-13 978-981-270-633-1 ISBN-10 981-270-633-X ISBN-13 978-981-270-634-8 (pbk) ISBN-10 981-270-634-8 (pbk) Printed by Mainland Press Pte Ltd This book is dedicated to Inge, Conny, Marc and Patrick. Preface 34 Traditional numerical methods, such as finite element, finite difference, or finite vol ume methods, were motivated mostly by early one- and two-dimensional simulations of engineering problems via partial differential equations (PDEs). The discretiza tion involved in all of these methods requires some sort of underlying computational mesh, e.g., a triangulation of the region of interest. Creation of these meshes (and possible re-meshing) becomes a rather difficult task in three dimensions, and virtu ally impossible for higher-dimensional problems. This is where meshfree methods enter the picture. Meshfree methods are often — but by no means have to be — radially symmetric in nature. This is achieved by composing some univariate basic function with a (Euclidean) norm, and therefore turning a problem involving many space dimensions into one that is virtually one-dimensional. Such radial basis func tions are at the heart of this book. Some people have argued that there are three "big technologies" for the numerical solution of PDEs, namely finite difference, fi nite element, and spectral methods. While these technologies came into their own right in successive decades, namely finite difference methods in the 1950s, finite el ement methods in the 1960s, and spectral methods in the 1970s, meshfree methods started to appear in the mathematics literature in the 1980s, and they are now on their way to becoming "big technology" number four. In fact, we will demonstrate in later parts of this book how different types of meshfree methods can be viewed as generalizations of the traditional "big three". Multivariate meshfree approximation methods are being studied by many re searchers. They exist in many flavors and are known under many names, e.g., diffuse element method, element-free Galerkin method, generalized finite element method, /ip-clouds, meshless local Petrov-Galerkin method, moving least squares method, partition of unity finite element method, radial basis function method, reproducing kernel particle method, smooth particle hydrodynamics method. In this book we are concerned mostly with the moving least squares (MLS) and radial basis function (RBF) methods. We will consider all different kinds of aspects of these meshfree approximation methods: How to construct them? Are these constructions mathematically justifiable? How accurate are they? Are theEg~wavs to implement them efficiently with standard mathematical software-packages such vii viii Meshfree Approximation Methods with MATLAB as MATLAB? HOW do they compare with traditional methods? How do the various flavors of meshfree methods differ from one another, and how are they similar to one another? Is there a general framework that captures all of these methods? What sort of applications are they especially well suited for? While we do present much of the underlying theory for RBF and MLS ap proximation methods, the emphasis in this book is not on proofs. For read ers who are interested in all the mathematical details and intricacies of the theory we recommend the two excellent recent monographs [Buhmann (2003); Wendland (2005a)]. Instead, our objective is to make the theory accessible to a wide audience that includes graduate students and practitioners in all sorts of sci ence and engineering fields. We want to put the mathematical theory in the context of applications and provide MATLAB implementations which give the reader an easy entry into meshfree approximation methods. The skilled reader should then easily be able to modify the programs provided here for his/her specific purposes. In a certain sense the present book was inspired by the beautiful little book [Tre- fethen (2000)]. While the present book is much more expansive (filling more than five hundred pages with forty-seven MATLAB1 programs, one Maple 2 program, one hundred figures, more than fifty tables, and more than five hundred references), it is our aim to provide the reader with relatively simple MATLAB code that illustrates just about every aspect discussed in the book. All MATLAB programs printed in the text (as well as a few modifications dis cussed) are also included on the enclosed CD. The folder MATLAB contains M-files and data files of type M AT that have been written and tested with MATLAB 7. For those readers who do not have access to MATLAB 7, the folder MATLAB6 contains versions of these files that are compatible with the older MATLAB release. The main difference between the two versions is the use of anonymous functions in the MATLAB 7 code as compared to inline functions in the MATLAB 6 version. Two packages from the MATLAB Central File Exchange [MCFE] are used throughout the book: the function haltonseq written by Daniel Dougherty and used to generate sequences of Halton points; the /cd-tree library (given as a set of MATLAB MEX-files) written by Guy Shechter and used to generate the kd-tvee data structure underlying our sparse matrices based on compactly supported basis functions. Both of these packages are discussed in Appendix A and need to be downloaded separately. The folder Maple on the CD contains the one Maple file mentioned above. The manuscript for this book and some of its earlier incarnations have been used in graduate level courses and seminars at Northwestern University, Vanderbilt University, and the Illinois Institute of Technology. Special thanks are due to Jon 1 MATLAB® is a trademark of The MathWorks, Inc. and is used with permission. The Math- Works does not warrant the accuracy of the text or exercises in this book. This book's use or discussion of MATLAB software or related products does not constitute endorsement or sponsor ship by The MathWorks of a particular pedagogical approach or particular use of the MATLAB software. 2Maple™ is a registered trademark of Waterloo Maple Inc. Preface ix Cherrie, John Erickson, Paritosh Mokhasi, Larry Schumaker, and Jack Zhang for reading various portions of the manuscript and/or MATLAB code and providing helpful feedback. Finally, thanks are due to all the people at World Scientific Publishing Co. who helped make this project a success: Rajesh Babu, Ying Oi Chiew, Linda Kwan, Rok Ting Tan, and Yubing Zhai. Greg Fasshauer Chicago, IL, January 2007