Introduction to numerical programming a practical guide for scientists and engineers using Python and CC++ (Titus A. Beu) (z-library.sk, 1lib.sk, z-lib.sk)

K16451 SERIES IN COMPUTATIONAL PHYSICS Steven A. Gottlieb and Rubin H. Landau, Series Editors IN TRO DUC TIO N TO N UM ERIC A L PRO G RA M M IN G Beu “Your journey will be a real pleasure since the book focuses on thorough explanations, hands-on code examples, and graphical representations.” —Professor Dr. Alexander K. Hartmann, Institute for Physics, University of Oldenburg “… an invaluable resource for aspects that are often not sufficiently emphasised, despite their importance for reliable calculations. I strongly recommend it for everyone’s bookshelf.” —Professor Joan Adler, Technion, Israel Institute of Technology “… a comprehensive introduction to classical numerical methods… via clear and simple codes in Python and C/++. … I will recommend it to my students.” —Professor Mike Wheatland, The University of Sydney Makes Numerical Programming More Accessible to a Wider Audience Bearing in mind the evolution of modern programming, most specifically emergent program- ming languages that reflect modern practice, Numerical Programming: A Practical Guide for Scientists and Engineers Using Python and C/C++ utilizes the author’s many years of practi- cal research and teaching experience to offer a systematic approach to relevant programming concepts. Adopting a practical, broad appeal, this user-friendly book offers guidance to anyone interested in using numerical programming to solve science and engineering problems. Empha- sizing methods generally used in physics and engineering—from elementary methods to com- plex algorithms—it gradually incorporates algorithmic elements with increasing complexity. Develop a Combination of Theoretical Knowledge, Efficient Analysis Skills, and Code Design Know-How The book encourages algorithmic thinking, which is essential to numerical analysis. Establish- ing the fundamental numerical methods, application numerical behavior and graphical output needed to foster algorithmic reasoning, coding dexterity, and a scientific programming style, it enables readers to successfully navigate relevant algorithms, understand coding design, and de- velop efficient programming skills. The book incorporates real code and includes examples and problem sets to assist in hands-on learning. This text introduces platform-independent numerical programming using Python and C/C++ and appeals to advanced undergraduate and graduate students in natural sciences and engineering, researchers involved in scientific computing, and engineers carrying out applicative calculations. Computer Science/Scientific Programming K16451_cover.indd 1 7/16/14 11:03 AM

INTRODUCTION TO NUMERICAL PROGRAMMING

Steven A. Gottlieb and Rubin H. Landau Series Editors Parallel Science and Engineering Applications: The Charm++ Approach Sanjay Kale and Abhinav Bhatele, Eds. Introduction to Numerical Programming: A Practical Guide for Scientists and Engineers Using Python and C/C++ Titus Adrian Beu Forthcoming Visualization in Computational Physics and Materials Science Joan Adler Introduction to Classical Dynamics: A Computational View Kelly Roos and Joseph Driscoll SERIES IN COMPUTATIONAL PHYSICS

SERIES IN COMPUTATIONAL PHYSICS Steven A. Gottlieb and Rubin H. Landau, Series Editors INTRODUCTION TO NUMERICAL PROGRAMMING A Practical Guide for Scientists and Engineers Using Python and C/C++ Titus Adrien Beu Babeș-Bolyai University Faculty of Physics Cluj-Napoca, Romania

CRC Press Taylor & Francis Group 6000 Broken Sound Parkway NW, Suite 300 Boca Raton, FL 33487-2742 © 2015 by Taylor & Francis Group, LLC CRC Press is an imprint of Taylor & Francis Group, an Informa business No claim to original U.S. Government works Version Date: 20140716 International Standard Book Number-13: 978-1-4665-6968-3 (eBook - PDF) This book contains information obtained from authentic and highly regarded sources. Reasonable efforts have been made to publish reliable data and information, but the author and publisher cannot assume responsibility for the valid- ity of all materials or the consequences of their use. The authors and publishers have attempted to trace the copyright holders of all material reproduced in this publication and apologize to copyright holders if permission to publish in this form has not been obtained. If any copyright material has not been acknowledged please write and let us know so we may rectify in any future reprint. Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced, transmitted, or uti- lized in any form by any electronic, mechanical, or other means, now known or hereafter invented, including photocopy- ing, microfilming, and recording, or in any information storage or retrieval system, without written permission from the publishers. For permission to photocopy or use material electronically from this work, please access www.copyright.com (http:// www.copyright.com/) or contact the Copyright Clearance Center, Inc. (CCC), 222 Rosewood Drive, Danvers, MA 01923, 978-750-8400. CCC is a not-for-profit organization that provides licenses and registration for a variety of users. For organizations that have been granted a photocopy license by the CCC, a separate system of payment has been arranged. Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used only for identification and explanation without intent to infringe. Visit the Taylor & Francis Web site at http://www.taylorandfrancis.com and the CRC Press Web site at http://www.crcpress.com

To Mihaela and Victor

Contents Series Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiii Author . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvii Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xix 1 Approximate Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Sources of Errors in Numerical Calculations . . . . . . . . . . . . . . . . 1 1.2 Absolute and Relative Errors . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Representation of Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4 Significant Digits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.5 Errors of Elementary Operations . . . . . . . . . . . . . . . . . . . . . . . 7 References and Suggested Further Reading . . . . . . . . . . . . . . . . . . . . 10 2 Basic Programming Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.1 Programming Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2 Functions and Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.3 Passing Arguments to Python Functions . . . . . . . . . . . . . . . . . . 15 2.4 Passing Arguments to C/C++ Functions . . . . . . . . . . . . . . . . . . 17 2.5 Arrays in Python . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.6 Dynamic Array Allocation in C/C++ . . . . . . . . . . . . . . . . . . . . 19 2.7 Basic Matrix Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 References and Suggested Further Reading . . . . . . . . . . . . . . . . . . . . 30 3 Elements of Scientific Graphics . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.1 The Tkinter Package . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.2 The Canvas Widget . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.3 Simple Tkinter Applications . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.4 Plotting Functions of One Variable . . . . . . . . . . . . . . . . . . . . . 39 3.5 Graphics Library graphlib.py . . . . . . . . . . . . . . . . . . . . . . 44 3.6 Creating Plots in C++ Using the Library graphlib.py . . . . . . . . 57 References and Suggested Further Reading . . . . . . . . . . . . . . . . . . . . 61 4 Sorting and Indexing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 4.2 Bubble Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 4.3 Insertion Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 vii

viii Contents 4.4 Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 4.5 Indexing and Ranking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 4.6 Implementations in C/C++ . . . . . . . . . . . . . . . . . . . . . . . . . . 75 4.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 References and Suggested Further Reading . . . . . . . . . . . . . . . . . . . . 84 5 Evaluation of Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 5.1 Evaluation of Polynomials by Horner’s Scheme . . . . . . . . . . . . . . 85 5.2 Evaluation of Analytic Functions . . . . . . . . . . . . . . . . . . . . . . . 88 5.3 Continued Fractions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 5.4 Orthogonal Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 5.5 Spherical Harmonics—Associated Legendre Functions . . . . . . . . . . 98 5.6 Spherical Bessel Functions . . . . . . . . . . . . . . . . . . . . . . . . . . 102 5.7 Implementations in C/C++ . . . . . . . . . . . . . . . . . . . . . . . . . . 105 5.8 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 References and Suggested Further Reading . . . . . . . . . . . . . . . . . . . . 125 6 Algebraic and Transcendental Equations . . . . . . . . . . . . . . . . . . . . . . 127 6.1 Root Separation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 6.2 Bisection Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 6.3 Method of False Position . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 6.4 Method of Successive Approximations . . . . . . . . . . . . . . . . . . . 134 6.5 Newton’s Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 6.6 Secant Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 6.7 Birge–Vieta Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 6.8 Newton’s Method for Systems of Nonlinear Equations . . . . . . . . . . 147 6.9 Implementations in C/C++ . . . . . . . . . . . . . . . . . . . . . . . . . . 151 6.10 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 References and Suggested Further Reading . . . . . . . . . . . . . . . . . . . . 168 7 Systems of Linear Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169 7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169 7.2 Gaussian Elimination with Backward Substitution . . . . . . . . . . . . 169 7.3 Gauss–Jordan Elimination . . . . . . . . . . . . . . . . . . . . . . . . . . 179 7.4 LU Factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187 7.5 Inversion of Triangular Matrices . . . . . . . . . . . . . . . . . . . . . . . 195 7.6 Cholesky Factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197 7.7 Tridiagonal Systems of Linear Equations . . . . . . . . . . . . . . . . . . 203 7.8 Block Tridiagonal Systems of Linear Equations . . . . . . . . . . . . . . 207 7.9 Complex Matrix Equations . . . . . . . . . . . . . . . . . . . . . . . . . . 208 7.10 Jacobi and Gauss–Seidel Iterative Methods . . . . . . . . . . . . . . . . . 209 7.11 Implementations in C/C++ . . . . . . . . . . . . . . . . . . . . . . . . . . 213 7.12 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223 References and Suggested Further Reading . . . . . . . . . . . . . . . . . . . . 231 8 Eigenvalue Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233 8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233 8.2 Diagonalization of Matrices by Similarity Transformations . . . . . . . 234 8.3 Jacobi Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235 8.4 Generalized Eigenvalue Problems for Symmetric Matrices . . . . . . . . 243 8.5 Implementations in C/C++ . . . . . . . . . . . . . . . . . . . . . . . . . . 246

Contents ix 8.6 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249 References and Suggested Further Reading . . . . . . . . . . . . . . . . . . . . 264 9 Modeling of Tabulated Functions . . . . . . . . . . . . . . . . . . . . . . . . . . 265 9.1 Interpolation and Regression . . . . . . . . . . . . . . . . . . . . . . . . . 265 9.2 Lagrange Interpolation Polynomial . . . . . . . . . . . . . . . . . . . . . 268 9.3 Neville’s Interpolation Method . . . . . . . . . . . . . . . . . . . . . . . . 273 9.4 Cubic Spline Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . 276 9.5 Linear Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283 9.6 Multilinear Regression Models . . . . . . . . . . . . . . . . . . . . . . . . 287 9.7 Nonlinear Regression: The Levenberg–Marquardt Method . . . . . . . 293 9.8 Implementations in C/C++ . . . . . . . . . . . . . . . . . . . . . . . . . . 301 9.9 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309 References and Suggested Further Reading . . . . . . . . . . . . . . . . . . . . 331 10 Integration of Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333 10.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333 10.2 Trapezoidal Rule; A Heuristic Approach . . . . . . . . . . . . . . . . . . 333 10.3 The Newton–Cotes Quadrature Formulas . . . . . . . . . . . . . . . . . 335 10.4 Trapezoidal Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337 10.5 Simpson’s Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339 10.6 Adaptive Quadrature Methods . . . . . . . . . . . . . . . . . . . . . . . . 341 10.7 Romberg’s Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344 10.8 Improper Integrals: Open Formulas . . . . . . . . . . . . . . . . . . . . . 348 10.9 Midpoint Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352 10.10 Gaussian Quadratures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354 10.11 Multidimensional Integration . . . . . . . . . . . . . . . . . . . . . . . . 361 10.12 Adaptive Multidimensional Integration . . . . . . . . . . . . . . . . . . . 369 10.13 Implementations in C/C++ . . . . . . . . . . . . . . . . . . . . . . . . . . 372 10.14 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 384 References and Suggested Further Reading . . . . . . . . . . . . . . . . . . . . 393 11 Monte Carlo Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395 11.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395 11.2 Integration of Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 396 11.3 Importance Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 399 11.4 Multidimensional Integrals . . . . . . . . . . . . . . . . . . . . . . . . . . 402 11.5 Generation of Random Numbers . . . . . . . . . . . . . . . . . . . . . . 408 11.6 Implementations in C/C++ . . . . . . . . . . . . . . . . . . . . . . . . . . 415 11.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 417 References and Suggested Further Reading . . . . . . . . . . . . . . . . . . . . 426 12 Ordinary Differential Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . 427 12.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 427 12.2 Taylor Series Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 429 12.3 Euler’s Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 431 12.4 Runge–Kutta Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434 12.5 Adaptive Step Size Control . . . . . . . . . . . . . . . . . . . . . . . . . . 440 12.6 Methods for Second-Order ODEs . . . . . . . . . . . . . . . . . . . . . . 447 12.7 Numerov’s Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 454 12.8 Shooting Methods for Two-Point Problems . . . . . . . . . . . . . . . . 457

x Contents 12.9 Finite-Difference Methods for Linear Two-Point Problems . . . . . . . 466 12.10 Implementations in C/C++ . . . . . . . . . . . . . . . . . . . . . . . . . . 471 12.11 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 481 References and Suggested Further Reading . . . . . . . . . . . . . . . . . . . . 507 13 Partial Differential Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 509 13.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 509 13.2 Boundary-Value Problems for Elliptic Differential Equations . . . . . . 511 13.3 Initial-Value Problems for Parabolic Differential Equations . . . . . . . 525 13.4 Time-Dependent Schrödinger Equation . . . . . . . . . . . . . . . . . . 542 13.5 Initial-Value Problems for Hyperbolic Differential Equations . . . . . . 553 13.6 Implementations in C/C++ . . . . . . . . . . . . . . . . . . . . . . . . . . 559 13.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 567 References and Suggested Further Reading . . . . . . . . . . . . . . . . . . . . 585 Appendix A: Dynamic Array Allocation in C/C++ . . . . . . . . . . . . . . . . . . 587 Appendix B: Basic Operations with Vectors and Matrices . . . . . . . . . . . . . 591 Appendix C: Embedding Python in C/C++ . . . . . . . . . . . . . . . . . . . . . . 599 Appendix D: The Numerical Libraries numxlib.py and numxlib.h . . . . . 605 Appendix E: The Graphics Library graphlib.py Based on Tkinter . . . . . . 611 Appendix F: The C++ Interface to the Graphics Library graphlib.py . . . . 627 Appendix G: List of Programs by Chapter . . . . . . . . . . . . . . . . . . . . . . . 637 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 641

Series Preface There can be little argument that computation has become an essential element in all areas of physics, be it via simulation, symbolic manipulations, data manipulations, equipment interfacing, or something with which we are not yet familiar. Nevertheless, even though the style of teaching and organization of sub- jects being taught by physics departments has changed in recent times, the actual content of the courses has been slow to incorporate the new-found importance of computation. Yes, there are now speciality courses and many textbooks in Computational Physics, but that is not the same thing as incorporating computation into the very heart of a modern physics curriculum so that the physics being taught today more closely resembles the physics being done today. Not only will such integration provide valuable pro- fessional skills to students, but it will also help keep physics alive by permitting new areas to be studied and old problems to be solved. This series is intended to provide undergraduate and graduate level textbooks for a modern physics curriculum in which computation is incorporated within the traditional subjects of physics, or in which there are new, multidisciplinary subjects in which physics and computation are combined as a “compu- tational science.” The level of presentation will allow for their use as primary or secondary textbooks for courses that wish to emphasize the importance of numerical methods and computational tools in sci- ence. They will offer essential foundational materials for students and instructors in the physical sciences as well as academic and industry professionals in physics, engineering, computer science, applied math, and biology. Titles in the series are targeted to specific disciplines that currently lack a textbook with a compu- tational physics approach. Among these subject areas are condensed matter physics, materials science, particle physics, astrophysics, mathematical methods of computational physics, quantum mechanics, plasma physics, fluid dynamics, statistical physics, optics, biophysics, electricity and magnetism, grav- ity, cosmology, and high-performance computing in physics. We aim for a presentation that is concise and practical, often including solved problems and examples. The books are meant for teaching, although researchers may find them useful as well. In select cases, we have allowed more advanced, edited works to be included when they share the spirit of the series—to contribute to wider application of computational tools in the classroom as well as research settings. Although the series editors had been all-too-willing to express the need for change in the physics curriculum, the actual idea for this series came from the series manager, Luna Han of Taylor & Francis Publishers. We wish to thank her sincerely for that, as well as for encouragement and direction throughout the project. Steve Gottlieb Bloomington Rubin H. Landau Corvallis Series Editors xi

Preface This book is devoted to the general field of numerical programming, with emphasis on methods specific to computational physics and engineering. While tremendous advances of computer performances have been achieved in recent years, numeri- cal methods still remain virtually inexhaustible resources for extending the range of challenging real-life problems made tractable. Along these lines, the book sets as its primordial goal to contribute to fos- tering interest in numerical programming by making computations accessible and appealing to broader categories of scientists and engineers. I have written this book for advanced undergraduate and graduate students in natural sciences and engineering, with the aim of being suited as curriculum material for a one- or two-semester course in numerical programming based on Python or C/C++. The book may also be used for independent study or as a reference material beyond academic studies. It may be useful, for instance, as an introductory text for researchers preparing to engage in scientific computing, or engineers needing effective numerical tools for applicative calculations. I have placed emphasis on the rigorous, yet accessible presentation of the fundamental numerical methods, which are complemented with implementations and applications, highlighting specific numer- ical behavior and often featuring graphical output. Although the material requires basic knowledge of calculus, linear algebra, and differential equations, it does not assume previous acquaintance with numerical techniques, leading the reader all the way from elementary algorithms to elaborate methods of relevance for modern numerical programming. Notably, there is a steady increase of complexity of the methods which are dealt with, both within each chapter and along the sequence of chapters. In essence, the book aims at assisting the reader in developing their capacity of algorithmic reasoning, a specific coding dexterity, and an efficient scientific programming style, which are essential prerequisites for subsequent involvement in comprehensive programming projects. Relation to reference works. The literature abounds in excellent books on numerical programming. To mention just two works that have set milestones in the field, the book makes frequent reference to Numer- ical Analysis by R.L. Burden and J.D. Faires, and to Numerical Recipes by W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery. Some reference texts excel in the rigorous presentation of the math- ematical foundations and algorithms, yet with generic implementations and limited justifications of the concretely employed coding solutions. Other works highlight the subtleties and performance of concrete implementations, being mainly addressed to experienced users. The goal of this book is to bridge the two mentioned options, providing the reader with an adequate level of proficiency by following a route which develops a well-balanced combination of basic theoreti- cal knowledge, as well as code design and efficiency analysis skills. Along the way, constant emphasis is laid on the fact that good programming is neither barely a mechanistic translation of mathematical for- mulas into a programming language, nor should effective implementations be complicated by principle. xiii

xiv Preface In all respects, the book follows as a guiding principle the “beauty of simplicity” with a view to achiev- ing effectiveness and long-lasting usability of numerical applications. As a distinctive feature, the book also attaches particular importance to graphical representations, as a means of synthetic assessment of numerical behavior, the material deliberately being highly visual and brimming with graphs. Programming languages. In terms of programming languages, the book relies on standard Python (version 3.3) and ANSI C/C++, not making use of any additional packages. On the one hand, the choice is motivated by their modern “minimalism,” which enables the systematic presentation of programming concepts with relatively simple means, and on the other, by their ubiquity, which ensures the cross- platform portability of the applications, as well as the potential mobility of the users to other fields of applied programming. As for Python, it proves its virtues ever more increasingly, not only as an easy-to-use teaching language, but also in high-performance computing for creating complementary scripts and graphical user interfaces in conjunction with compiled languages, or for building stand-alone applications in various fields of present-day science and technology. With this in mind, the book addresses both the effectiveness of the compiled C/C++ code and the ease-of-use and portable graphical features of the interpreter-based Python applications. Starting from the fact that code indentation is compulsory in Python, but optional in C/C++ (being merely a means of enhancing code readability), throughout the book we employ a unified code format- ting style for Python and C/C++, implying an indentation size of three spaces for marking consecutive subordination levels. Numerical methods. The numerical methods are presented in detail, although avoiding an excess of purely mathematical aspects. The implementations are designed so as to highlight the specificity of scientific programming, and, for the sake of creating a consistent programming style, they assume a compromise between clarity and performance. In certain cases, without sacrificing the execution speed, less efficient memory usage but more elegant and illustrative implementations are preferred. The routines are richly commented in order to clarify the role of the various parameters, variables, and code sequences. The comments on individual code lines are generally right aligned in order not to disperse the executable sequences and to save on source file size. Addition of delicate algorithmic elements is carried out in a gradual manner, through successive ver- sions of the routines of increasing complexity. The routines are complemented with numerical examples, designed to elucidate the data input/output and to highlight specific numerical behavior of the solutions. The material also emphasizes the cross-disciplinary usability of numerical methods originally devel- oped for specific fields of computational physics or engineering. As a concrete example, the Verlet propagator, which is a well-established method for solving equations of motion in molecular dynam- ics simulations, can additionally be applied successfully to study the motion of celestial systems. The text also points repeatedly to the fact that mastering numerical methods implies to a large extent the in-depth understanding and control of errors. Python versions of the developed routines are listed separately in each chapter, alongside the relevant theoretical and algorithmic aspects, while C/C++ versions are listed jointly as header files in separate sections, generically titled “Implementations in C/C++.” In perfect symmetry, the Python routines are also grouped in modules corresponding to each of the treated chapters. In fact, the book brings forward two similar Python and C/C++ numerical libraries, numxlib.py and numxlib.h, which include the partial libraries developed in the separate chapters (see Appendix D for a description). Even though the applications illustrating the various numerical methods exposed in the book employ the partial numerical libraries (as, for instance, ode.py or ode.h is included for solving ordinary differential equations), the overall library numxlib can well be used in their place, and this is actually the recommended option, once the numerical methods presented in the book have been mastered. Graphics. Bearing in mind that in modern research the amount of output data quite often exceeds the user’s capacity to analyze individual figures, as already mentioned, the book places importance on

Preface xv graphical representation methods, which are able to reveal global trends, otherwise difficult to extract from numeric sequences. The graphics is based on the remarkable capabilities of Python’s Tkinter package, not in the least taking advantage of its wide-ranging portability. In Chapter 3, the book puts forward a versatile Python graphics library, graphlib.py (see also Appendix E), which is used throughout the material to produce runtime graphics both from Python and C/C++. In particular, the C/C++ applications gain access to graphlib.py via a dedicated interface file, graphlib.h (see Appendix F). The persistent use of graphical presentation methods is meant to stimulate the development of abilities for building large-scale scientific applications with graphical user interfaces. Exercise problems. The applications in each chapter complementing theoretical aspects and imple- mented routines mainly address illustrative topics from undergraduate-level courses, such as Mechanics, Electricity, Optics, and Quantum Physics. More complex topics, involving concepts beyond the under- graduate curriculum, are typically presented in the final sections of the chapters, being mainly intended to highlight the full potential of the basic numerical methods and to provide instructors and researchers with additional material. The input to the problems is deliberately kept simple, often merely as bare assignments to the problem parameters, in order to allow the reader to focus on the essential aspects. The hands-on style of presenting the material, with trial-and-error routes, with emphasis on advantages and pitfalls, encourages the reader to develop skills by experimenting. As a rule, the C/C++ versions of the programs are not included in the “Problems” section of the chap- ters. Instead, along with their Python counterparts, they are to be found as supplementary material on the book’s website. Also as a general rule, all the routines, libraries, and programs come in pairs of Python and C/C++ files having identical names and appropriate extensions. Book structure. The book is divided into 13 chapters. Following this introduction, Chapter 1 deals with the main aspects of approximate numbers and propagation of associated errors. Without giving a systematic presentation of the Python and C languages, Chapter 2 reviews the language elements of interest to coding the numerical methods developed in later chapters. Chapter 3 is devoted to introducing elements of graphic functionality in Python and C/C++ applications. In Chapter 4 basic sorting and indexing methods are presented. Chapter 5 describes prototypical techniques of function evaluation (in particular, for special func- tions). Chapter 6 describes methods for solving algebraic and transcendental equations, while Chapter 7 is devoted to describing the most important methods for solving systems of linear equations. Chap- ter 8 deals with eigenvalue problems, in particular, for symmetric matrices. Chapter 9 is concerned with approximating tabulated functions, specifically by interpolation (including by spline functions) and regression (including nonlinear regression). Chapter 10 describes methods of integrating one- and multi-dimensional functions by classical and Gaussian quadratures, while Chapter 11 is devoted to Monte Carlo integration techniques and generation of random variables with various distributions. In Chapter 12 methods for solving ordinary differential equations are presented, ranging from Runge–Kutta to Numerov’s method, and Chapter 13 discusses the most important discretization methods for elliptic, parabolic, and hyperbolic partial differential equations, familiarizing the reader with the stability analysis. Supplementary material and the book’s website. The book is complemented with material provided on the book’s website, http://www.crcpress.com/product/isbn/9781466569676/ The material is organized by chapters in a simple folder structure, each chapter folder containing routine libraries, example programs, and sample graphical output. The root folder is /INP/ (from “Introduction to Numerical Programming”) and the chapter folders are named Chnn, with nn representing the two- digit chapter number.

xvi Preface The file names associated with the application programs contain the complete information on their location. The general format is Pnn-name.py or Pnn-name.cpp, whereby nn indicates, as before, the chapter folder /INP/Chnn/, and the file’s extension indicates the respective subfolder /INP/Chnn/Python/ or /INP/Chnn/C/. To locate the file corresponding to a particular program listing from the text, the reader is advised to use the cross-reference list provided in Appendix G, “List of Programs by Chapter.” All the general Python libraries (*.py) developed in the book are to be found in the folder /INP/modules/, while the corresponding C/C++ header files (*.h) reside in the folder /INP/include/. Access to the libraries numxlib and graphlib. Accessing the libraries on a particular com- puter is a technical problem. It basically boils down to adding the folders /INP/modules/ and /INP/include/ to the search paths of the respective programming environments. For Python in particular, this operation requires certain knowledge of operating systems and there are several methods in use. For reasons of simplicity, two cross-platform methods are recommended. The first method of gaining access to the developed modules is to simply copy them from the distribution folder /INP/modules/ into the standard folder of the Python 3.3 installation, /Python33/Lib/site-packages/ which is the environment implied by the applications developed in the book. The second method relies on Python’s ability to dynamically redefine search paths by invoking the sys.path.append method. Assuming the folder structure presented above and the script to be exe- cuted located in /INP/Ch14/Python/, gaining access to numxlib.pymight be achieved by adding to an executable Python script: import sys sys.path.append("/INP/modules/") from numxlib import * It is important, however, to append the path up to and including the root folder for both the libraries and the executable script (/INP/, in this case). An essential aspect to be noted is that the use of the graphics library graphlib.py also requires access to the utilities file utils.py. Failure to find utils.py in Python’s search path results in graphlib.py aborting. However, performing graphics with graphlib from C/C++ requires the interface file graphlib.h to have access to the basic Python library graphlib.py.

Author Titus Adrian Beu, professor of theoretical and computational physics at the University “Babeş-Bolyai” from Cluj-Napoca, Romania, has been active in the broader field of computational physics for more than 30 years, both in research and academia. His research has been theoretical and computational in nature, covering a multitude of subjects. His research topics have evolved from Tokamak plasma and nuclear reactor calculations in the 1980s, collision theory and molecular cluster spectroscopy in the 1990s, to fullerenes and nanofluidics simulations in recent years. Development of ample computer codes has permanently been at the core of all research projects the author has conducted. In parallel, he has deliv- ered lectures on general programming techniques and advanced numerical methods, general simulation methods, and advanced molecular dynamics. The material covered by the book stems jointly from the author’s research experience and the com- putational physics courses taught at the university. The basic material has undergone a continuous process of distillation and reformulation over the years, following the evolution of modern programming concepts and technologies. xvii

Acknowledgments Special thanks are due to Professor Rubin Landau, for having had the idea of the project in the first place, and for providing feedback on subtle aspects during the elaboration of the material. The author wishes to express his gratitude to Luna Han, for the encouragement and forthcoming support throughout the realization of the book. The author wishes to acknowledge Professor Manuel José Páez of Universidad de Antioquia for his contribution to the preparation of some problems in Chapters 5, 6, 7, 9, and 10 during the early stages of manuscript development. Special thanks are also due to Dr. Octavian More for proofreading the final manuscript. xix