Đăng ký Đăng nhập
Trang chủ Công nghệ thông tin Kỹ thuật lập trình Numericalmethodsalgorithmsandtoolsincsharp...

Tài liệu Numericalmethodsalgorithmsandtoolsincsharp

.PDF
583
310
99

Mô tả:

C#
Numerical Methods, Algorithms and Tools in C# © 2010 by Taylor and Francis Group, LLC Numerical Methods, Algorithms and Tools in C# Waldemar Dos Passos Boca Raton London New York CRC Press is an imprint of the Taylor & Francis Group, an informa business © 2010 by Taylor and Francis Group, LLC All the source codes for the material contained in this book can be downloaded directly from the publisher’s website: http://www.crcpress.com/product/isbn/9780849374791 followed by selecting the option for “Downloads & Updates.” CRC Press Taylor & Francis Group 6000 Broken Sound Parkway NW, Suite 300 Boca Raton, FL 33487-2742 © 2010 by Taylor and Francis Group, LLC CRC Press is an imprint of Taylor & Francis Group, an Informa business No claim to original U.S. Government works Printed in the United States of America on acid-free paper 10 9 8 7 6 5 4 3 2 1 International Standard Book Number: 978-0-8493-7479-1 (Hardback) 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 validity 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 utilized in any form by any electronic, mechanical, or other means, now known or hereafter invented, including photocopying, 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. Library of Congress Cataloging‑in‑Publication Data Dos Passos, Waldemar. Numerical methods, algorithms, and tools in C# / Waldemar Dos Passos. p. cm. Includes bibliographical references and index. ISBN 978-0-8493-7479-1 (hardcover : alk. paper) 1. Numerical analysis--Data processing. 2. Algorithms. 3. C# (Computer program language) I. Title. QA297.D684 2010 518.0285’5133--dc22 Visit the Taylor & Francis Web site at http://www.taylorandfrancis.com and the CRC Press Web site at http://www.crcpress.com © 2010 by Taylor and Francis Group, LLC 2009031461 Preface Today, more than at any other time in the history of mankind, computers are increasingly and successfully being exploited to gain a better understanding of our physical world and as a result, also deepen our appreciation and reverence for God’s Creation. Consequently, as computers evolve, so must the means to control them through advancements not just in hardware but also in software. In order to satisfy this demand for better software, Microsoft released an entirely new programming language called C# that incorporates the best features of all the other existing popular programming languages such as Java, C/C++, and Visual Basic. In spite of considerable resistance by some people who persist on clinging on to the past and continue to program computers the hard way, C# has now firmly established itself worldwide as arguably the preferred language for software application development. Although many excellent books on the topic of general programming in C# have been written, there is still a considerable lack of published material on the topic of numerical methods in C#. Accordingly, Numerical Methods, Algorithms and Tools in C# is a book containing a large collection of very useful ready-to-use mathematical routines, algorithms and other computational tools aimed at programmers, mathematicians, statisticians, scientists, engineers and anyone else interested in developing mathematically oriented computer applications in the relatively new and easy-to-learn object-oriented C# programming language from Microsoft. With a heavy emphasis on using well established numerical methods, object-oriented techniques and the latest state-ofthe-art Microsoft .NET programming environment, this book provides readers with working C# code including practical examples that can be easily customized and implemented to solve complex engineering and scientific problems typically found in real-world applications. For the benefit of those readers who are not yet familiar with C#, Chapter 1 provides a brief outline of the .NET Framework, the C# programming language and the basic concepts of Object Oriented Programming (OOP). Special attention is given to topics that illustrate how to best utilize these and other tools to develop accurate and robust numerical methods in C#. Chapter 2 is entirely focused on the .NET Framework Math Class Library which already comes built into Microsoft’s Visual Studio software development system. Additional material is introduced where appropriate in order to supplement, complete or otherwise enhance the features already available with this library. Chapter 3 introduces data structures along with their associated functions that are particularly useful for programming and working with vectors and matrices. These iii © 2010 by Taylor and Francis Group, LLC iv Numerical Methods, Algorithms and Tools in C# routines are often used in more advanced applications in later chapters. Chapter 4 is entirely dedicated to the topic of complex numbers. Since timing issues can sometimes pose a substantial problem when doing numerical calculations, complex number functions are presented using both elegant state-of-the-art objectoriented methods which, although slick, can at times carry some overhead and the old fashioned but proven methods which at times have been found to actually run faster on some computers. In addition, important overflow and underflow issues are also discussed and alternative solutions to avoid those problems are proposed. Chapter 5 is devoted solely to sorting and searching algorithms. Computers are often required to perform various types of data sorting for which many different algorithms exist. Consequently, choosing the most efficient sorting algorithm is a very important decision that developers frequently have to make. In this chapter, readers are provided with both a wide selection of sorting and searching algorithms from which to choose along with a brief explanation of how each algorithm works. Chapter 6 is centered on the topic of bit manipulation which is typically used in a variety of programming applications ranging anywhere from computer interfacing to image processing. Chapter 7 is focused on interpolation methods. Equations that cannot be solved analytically often need to be solved using some kind of interpolation scheme, and this chapter has plenty of practical examples to illustrate how one might handle this kind of problem. Chapter 8 centers on the numerical manipulation of linear algebraic equations. This is actually a huge topic by itself and quite worthy of its own book. Nevertheless, a substantial amount of useful information can be readily obtained from just a handful of these powerful tools. Chapter 9 is focused on numerical methods for calculating approximate solutions to nonlinear equations which often appear naturally in various branches of science and engineering. Chapter 10 is devoted exclusively to the topic of random numbers. Although C# comes with its own internal random number generator function, it is not regarded to be sufficiently robust for use in advanced secured applications or in computer simulations that require thousands and sometimes even millions of random numbers in order to produce reliable and accurate results. Alternate ways to obtain both computer generated pseudo-random numbers and real random numbers obtained from naturally occurring physical phenomena are also discussed. In addition, routines are also provided for generating random numbers that follow a particular probability distribution function. Chapter 11 describes various methods for approximating numerical differentiation of functions. This is a very tricky and controversial topic whose approximations can give fairly good to atrociously bad results. Nevertheless, numerical methods do exist for calculating these types of functions. The trick is really in learning to recognize the difference between good and bad results and in choosing the best available method for use in a particular situation. Chapter 12 centers on developing numerical methods for approximating integrals of specific functions as well as from collections of raw data points. Other more exotic © 2010 by Taylor and Francis Group, LLC Preface v ways of calculating integrals, such as by using Monte Carlo methods, are also briefly discussed. Chapter 13 contains a considerable number of routines for use in performing statistical analysis of data. Chapter 14 is devoted to developing numerical methods for approximating special functions which are typically found in various branches of mathematics, physics and engineering. Chapter 15 is focused on least squares and numerical curve fitting methods that are frequently used in analyzing experimental data. A brief discussion of the χ 2 goodness-of-fit test is also included. Chapter 16 centers on developing routines to find numerical solutions to ordinary differential equations. Although this is really a huge topic, there are some basic numerical methods which can be used successfully to solve a lot of these types of equations in many real-world applications. Chapter 17 introduces some numerical methods for solving partial differential equations. Although this is also a huge topic by itself and quite deserving of its own book, there are some standard types of partial differential equations that arise naturally in many areas of science and engineering, and whose solutions can be approximated by well established numerical methods. Chapter 18 focuses on optimization methods which are primarily aimed at the minimization or maximization of functions and thus have many practical scientific and engineering applications. Since this is still a very active area of ongoing research, the examples presented here are more narrowly focused on just a few established topics with the explicit purpose of illustrating how such methods may be individually customized and then applied towards solving more advanced problems. Lastly, I would like to point out that most of the numerical methods described in this book have actually been around in one form or another for years, and sometimes even for centuries, and it is only their computer implementation in C# that makes this book uniquely different from some other book on the topic of numerical analysis. Accordingly, I have made every effort to track down and give proper credit to original sources whenever possible as the size of this book’s reference section can easily attest. In addition, I have also made every effort to provide my readers with accurate, reliable information to help them in their efforts to successfully complete their programming projects. Unfortunately, unwanted mistakes including typographical errors may inadvertently creep up somewhere in this book. As a result, I would greatly appreciate if my readers would be so kind as to bring to my attention if such errors are ever found so that I may promptly have the problem corrected for any future editions of this book. Also, as with just about everything we do in life, there is always room for improvement. Accordingly, I would also very much welcome any constructive criticism that my readers may have regarding this book so that I can perhaps make appropriate changes. Finally, there is an old saying that states, “an author never finishes a book, but merely abandons it.” I have certainly come to appreciate that observation after working on this project for so long and making countless revisions. Nevertheless, this has certainly been a very enjoyable project where just about every word was carefully chosen and every topic was meticulously researched and © 2010 by Taylor and Francis Group, LLC vi Numerical Methods, Algorithms and Tools in C# documented. Therefore, if it is indeed true that I have willingly chosen to abandon writing this book, it is only with the modest hope that it may be useful to my readers in spite of any possible shortcomings. Waldemar Dos Passos, Ph.D. Concord, California e-mail: [email protected] website: www.waldemardospassos.com Acknowledgements It gives me great pleasure to thank the many people who made this book possible. First, I would very much like to thank my publisher, Nora Konopka, for not only accepting this book for publication but also for her exceptional patience as I underwent a series of unforeseen tumultuous events in my life during the course of writing this book which unfortunately led to some regrettable delays in its original publication target date. I would also like to particularly thank both my project director, Theresa Delforn, and my editor, Amy Rodriguez, for their excellent expert guidance in various aspects of this project. I would also like to thank Dawn Snider for her excellent artistic skills in designing the cover for this book. Many thanks to Ashley Gasque for guiding me through the necessary bureaucratic paperwork and to Shashi Kumar for some expert LATEX tips he gave me. I would also like to thank all those other wonderful people at Taylor & Francis who have worked tirelessly behind the scenes to make this project a success but whose exact names I may likely never come to know. I am also very grateful for the support I received from the H.E. Martin Foundation under grant 13011938. Without their most kind and extraordinary generous financial assistance, the writing of this book would not have been possible. I am especially grateful to my third grade teacher, Miss Daly, for all her help, patience, kindness, and enthusiasm which ultimately sparked my interest in mathematics and eventually, physics. Looking back over all these years that have elapsed since I was a student in her class, I can now say unequivocally that Miss Daly was by far the very best and most caring teacher, professor, or instructor I ever had. Lastly, I would also like to express my deepest and most heartfelt thanks to my parents, Helenice and Waldemar Dos Passos (Sr.) © 2010 by Taylor and Francis Group, LLC This book is dedicated with all my love and care to my parents, Helenice and Waldemar Dos Passos (Sr.) for all their hard work, genuine love, and selfless sacrifices made on my behalf throughout my entire life. “In this life we cannot do great things; only small things with great love.” Mother Teresa Ad Majorem Dei Gloriam © 2010 by Taylor and Francis Group, LLC Contents 1 Introduction 1.1 C# and the .NET Framework . . . . . . . . . . . . . . . . 1.2 Installing C# and the .NET Framework . . . . . . . . . . . 1.3 Overview of Object-Oriented Programming (OOP) . . . . 1.4 Your First C# Program . . . . . . . . . . . . . . . . . . . 1.5 Overview of the IDE Debugger . . . . . . . . . . . . . . . 1.6 Overview of the C# Language . . . . . . . . . . . . . . . 1.6.1 Data Types . . . . . . . . . . . . . . . . . . . . . 1.6.2 Value Types . . . . . . . . . . . . . . . . . . . . . 1.6.3 Reference Types . . . . . . . . . . . . . . . . . . 1.6.4 Type-Parameter Types . . . . . . . . . . . . . . . 1.6.5 Pointer Types . . . . . . . . . . . . . . . . . . . . 1.6.6 Variable Declaration . . . . . . . . . . . . . . . . 1.6.7 Constant Declaration . . . . . . . . . . . . . . . . 1.6.8 Nullable Types . . . . . . . . . . . . . . . . . . . 1.6.9 Scope . . . . . . . . . . . . . . . . . . . . . . . . 1.6.10 Characters . . . . . . . . . . . . . . . . . . . . . . 1.6.11 Strings . . . . . . . . . . . . . . . . . . . . . . . 1.6.12 Formatting of Output Data . . . . . . . . . . . . . 1.6.13 Type Conversion . . . . . . . . . . . . . . . . . . 1.6.14 Reading Keyboard Input Data . . . . . . . . . . . 1.6.15 Basic Expressions and Operators . . . . . . . . . . 1.6.16 Program Flow Mechanisms . . . . . . . . . . . . . 1.6.17 Jump Statements . . . . . . . . . . . . . . . . . . 1.6.18 Arrays . . . . . . . . . . . . . . . . . . . . . . . . 1.6.19 Enumerations . . . . . . . . . . . . . . . . . . . . 1.6.20 Structures . . . . . . . . . . . . . . . . . . . . . . 1.6.21 Exceptions . . . . . . . . . . . . . . . . . . . . . 1.6.22 Classes . . . . . . . . . . . . . . . . . . . . . . . Constructors and Destructors . . . . . . . . . . . . . Properties . . . . . . . . . . . . . . . . . . . . . . . Methods . . . . . . . . . . . . . . . . . . . . . . . 1.6.23 Indexers . . . . . . . . . . . . . . . . . . . . . . . 1.6.24 Overloading Methods, Constructors and Operators 1.6.25 Delegates . . . . . . . . . . . . . . . . . . . . . . 1.6.26 Events . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1 3 3 4 9 11 12 13 14 16 17 17 18 18 18 18 19 19 20 23 24 27 29 30 32 32 33 34 37 38 38 42 42 43 46 ix © 2010 by Taylor and Francis Group, LLC x Numerical Methods, Algorithms and Tools in C# 1.6.27 Collections . . . . . . . . . . . . . . . . . . . . . . . . . 1.6.28 File Input/Output . . . . . . . . . . . . . . . . . . . . . . 1.6.29 Output Reliability, Accuracy and Precision . . . . . . . . 2 The .NET Framework Math Class Library 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 The .NET Framework Math Class - Fields . . . . . . . . . . . . 2.2.1 The Math.PI and Math.E Fields . . . . . . . . . . . . . 2.3 The .NET Framework Math Class - Methods . . . . . . . . . . . 2.3.1 The Minimum and Maximum Methods . . . . . . . . . 2.3.2 The Power, Exponential and Logarithmic Methods . . . 2.3.3 Special Multiplication, Division and Remainder Methods 2.3.4 The Absolute Value Method . . . . . . . . . . . . . . . 2.3.5 The Sign Method . . . . . . . . . . . . . . . . . . . . . 2.3.6 Angular Units of Measurement . . . . . . . . . . . . . . 2.3.7 The Trigonometric Functions . . . . . . . . . . . . . . . 2.3.8 The Inverse Trigonometric Functions . . . . . . . . . . 2.3.9 The Hyperbolic Functions . . . . . . . . . . . . . . . . 2.3.10 The Inverse Hyperbolic Functions . . . . . . . . . . . . 2.3.11 Rounding Off Numeric Data . . . . . . . . . . . . . . . The Ceiling Method . . . . . . . . . . . . . . . . . . . . The Floor Method . . . . . . . . . . . . . . . . . . . . . The Truncation Method . . . . . . . . . . . . . . . . . . The Round Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 60 65 73 73 73 73 74 74 74 76 77 78 78 81 82 86 88 89 89 90 90 91 3 Vectors and Matrices 97 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 3.2 A Real Number Vector Library in C# . . . . . . . . . . . . . . . . 98 3.3 A Real Number Matrix Library in C# . . . . . . . . . . . . . . . . 106 4 Complex Numbers 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Fundamental Concepts . . . . . . . . . . . . . . . . . . 4.3 Complex Number Arithmetic . . . . . . . . . . . . . . . 4.4 Elementary Functions of a Complex Number . . . . . . . 4.4.1 Exponentials . . . . . . . . . . . . . . . . . . . 4.4.2 Logarithms . . . . . . . . . . . . . . . . . . . . 4.4.3 Powers and Roots . . . . . . . . . . . . . . . . . 4.4.4 Trigonometric and Hyperbolic Functions . . . . 4.4.5 Inverse Trigonometric and Hyperbolic Functions 4.5 A Complex Number Library in C# . . . . . . . . . . . . 4.6 A Complex Number Vector Library in C# . . . . . . . . 4.7 A Complex Number Matrix Library in C# . . . . . . . . 4.8 Generic vs. Non-Generic Coding . . . . . . . . . . . . . © 2010 by Taylor and Francis Group, LLC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 121 121 123 125 125 125 127 128 130 132 151 158 168 Table of Contents 5 6 7 xi Sorting and Searching Algorithms 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Sorting Algorithms . . . . . . . . . . . . . . . . . . . . . . . 5.3 Comparison Sorts . . . . . . . . . . . . . . . . . . . . . . . . 5.3.1 Bubble Sort . . . . . . . . . . . . . . . . . . . . . . . 5.3.2 Cocktail Sort . . . . . . . . . . . . . . . . . . . . . . 5.3.3 Odd-Even Sort . . . . . . . . . . . . . . . . . . . . . 5.3.4 Comb Sort . . . . . . . . . . . . . . . . . . . . . . . 5.3.5 Gnome Sort . . . . . . . . . . . . . . . . . . . . . . . 5.3.6 Quicksort . . . . . . . . . . . . . . . . . . . . . . . . 5.3.7 Insertion Sort . . . . . . . . . . . . . . . . . . . . . . 5.3.8 Shell Sort . . . . . . . . . . . . . . . . . . . . . . . . 5.3.9 Selection Sort . . . . . . . . . . . . . . . . . . . . . . 5.3.10 Merge Sort . . . . . . . . . . . . . . . . . . . . . . . 5.3.11 Bucket Sort . . . . . . . . . . . . . . . . . . . . . . . 5.3.12 Heap Sort . . . . . . . . . . . . . . . . . . . . . . . . 5.4 Count Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5 Radix Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.6 Search Algorithms . . . . . . . . . . . . . . . . . . . . . . . . 5.6.1 Linear Search . . . . . . . . . . . . . . . . . . . . . . 5.6.2 Binary Search . . . . . . . . . . . . . . . . . . . . . . 5.6.3 Interpolation Search . . . . . . . . . . . . . . . . . . 5.6.4 Searching for the Maximum and Minimum Values . . 5.6.5 Searching for the N-th Largest or M-th Smallest Value 5.6.6 Some Useful Utilities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 171 172 175 175 178 178 179 180 181 182 183 184 185 186 187 188 189 191 192 193 193 194 195 196 Bits and Bytes 6.1 Introduction . . . . . . . . . . . . . . . 6.2 Numeric Systems . . . . . . . . . . . . 6.3 Bit Manipulation and Bitwise Operators 6.4 Assorted Bits and Bytes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199 199 199 202 223 Interpolation 7.1 Introduction . . . . . . . . . . . . . . . . . . . . . 7.2 Linear Interpolation . . . . . . . . . . . . . . . . . 7.3 Bilinear Interpolation . . . . . . . . . . . . . . . . 7.4 Polynomial Interpolation . . . . . . . . . . . . . . 7.4.1 Lagrange Interpolation . . . . . . . . . . . 7.4.2 Barycentric Interpolation . . . . . . . . . . 7.4.3 Newton’s Divided Differences Interpolation 7.5 Cubic Spline Interpolation . . . . . . . . . . . . . 7.5.1 Natural Cubic Splines . . . . . . . . . . . 7.5.2 Clamped Cubic Splines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229 229 230 231 234 234 236 238 242 244 247 © 2010 by Taylor and Francis Group, LLC . . . . . . . . . . . . . . . . . . . . xii 8 Numerical Methods, Algorithms and Tools in C# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251 251 253 254 256 259 259 261 264 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271 271 272 274 276 277 279 280 10 Random Numbers 10.1 Introduction . . . . . . . . . . . . . . . . . 10.2 The C# Built-In Random Number Generator 10.3 Other Random Number Generators . . . . . 10.4 True Random Number Generators . . . . . 10.5 Random Variate Generation Methods . . . . 10.6 Histograms . . . . . . . . . . . . . . . . . 10.7 Random Variate Generation . . . . . . . . . 10.7.1 Discrete Distributions . . . . . . . . Bernoulli Distribution . . . . . . . . Binomial Distribution . . . . . . . . Geometric Distribution . . . . . . . . Negative Binomial Distribution . . . Poisson Distribution . . . . . . . . . Uniform Distribution (discrete) . . . 10.7.2 Continuous Distributions . . . . . . Beta Distribution . . . . . . . . . . . Beta Prime Distribution . . . . . . . Cauchy Distribution . . . . . . . . . Chi Distribution . . . . . . . . . . . Chi-Square Distribution . . . . . . . Erlang Distribution . . . . . . . . . . Exponential Distribution . . . . . . . Extreme Value Distribution . . . . . . Gamma Distribution . . . . . . . . . Laplace Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283 283 284 290 295 299 309 312 312 312 315 317 320 322 326 328 328 330 332 334 337 340 343 345 347 349 9 Linear Equations 8.1 Introduction . . . . . . . . . . . . 8.2 Gaussian Elimination . . . . . . . 8.3 Gauss-Jordan Elimination . . . . . 8.4 LU Decomposition . . . . . . . . 8.5 Iteration Methods . . . . . . . . . 8.5.1 Gauss-Jacobi Iteration . . 8.5.2 Gauss-Seidel Iteration . . 8.6 Eigenvalues and Jacobi’s Algorithm Nonlinear Equations 9.1 Introduction . . . . . . . . 9.2 Linear Incremental Method 9.3 Bisection Method . . . . . 9.4 The Secant Method . . . . 9.5 False Positioning Method . 9.6 Fixed Point Iteration . . . . 9.7 Newton-Raphson Method . © 2010 by Taylor and Francis Group, LLC . . . . . . . . . . . . . . . . . . . . . . . . . . . . Table of Contents xiii Logistic Distribution . . . . . . . Lognormal Distribution . . . . . Normal Distribution . . . . . . . Pareto Distribution . . . . . . . . Rayleigh Distribution . . . . . . . Student-t Distribution . . . . . . . Triangular Distribution . . . . . . Uniform Distribution (continuous) Weibull Distribution . . . . . . . 10.8 Shuffling Algorithms . . . . . . . . . . 10.9 Adding Random Noise to Data . . . . . 10.10 Removing Random Noise from Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352 354 356 359 361 363 365 368 370 372 376 379 11 Numerical Differentiation 11.1 Introduction . . . . . . . . . . . . . . . . . . 11.2 Finite Difference Formulas . . . . . . . . . . 11.2.1 Forward Difference Method . . . . . 11.2.2 Backward Difference Method . . . . 11.2.3 Central Difference Method . . . . . . 11.2.4 Improved Central Difference Method 11.3 Richardson Extrapolation . . . . . . . . . . . 11.4 Derivatives by Polynomial Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383 383 383 385 387 390 392 395 401 12 Numerical Integration 12.1 Introduction . . . . . . . . . . . . . . 12.2 Newton-Cotes Formulas . . . . . . . . 12.2.1 Rectangle Method . . . . . . 12.2.2 Midpoint Method . . . . . . . 12.2.3 Trapezoidal Method . . . . . 12.2.4 Simpson’s Method . . . . . . Simpson’s 1/3 Method . . . . . Simpson’s 3/8 Method . . . . . 12.3 Romberg Integration . . . . . . . . . 12.4 Gaussian Quadrature Methods . . . . 12.4.1 Gauss-Legendre Integration . 12.4.2 Gauss-Hermite Integration . . 12.4.3 Gauss-Leguerre Integration . . 12.4.4 Gauss-Chebyshev Integration 12.5 Multiple Integration . . . . . . . . . . 12.6 Monte Carlo Methods . . . . . . . . . 12.6.1 Monte Carlo Integration . . . 12.6.2 The Metropolis Algorithm . . 12.7 Convolution Integrals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405 405 406 406 408 409 411 411 412 414 416 417 419 421 423 424 426 427 428 431 © 2010 by Taylor and Francis Group, LLC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiv Numerical Methods, Algorithms and Tools in C# 13 Statistical Functions 13.1 Introduction . . . . . . . . . . . . . . . . . . . . 13.2 Some Useful Tools . . . . . . . . . . . . . . . . 13.3 Basic Statistical Functions . . . . . . . . . . . . 13.3.1 Mean and Weighted Mean . . . . . . . . 13.3.2 Geometric and Weighted Geometric Mean 13.3.3 Harmonic and Weighted Harmonic Mean 13.3.4 Truncated Mean . . . . . . . . . . . . . . 13.3.5 Root Mean Square . . . . . . . . . . . . 13.3.6 Median, Range and Mode . . . . . . . . 13.3.7 Mean Deviation . . . . . . . . . . . . . . 13.3.8 Mean Deviation of the Mean . . . . . . . 13.3.9 Mean Deviation of the Median . . . . . . 13.3.10 Variance and Standard Deviation . . . . . 13.3.11 Moments About the Mean . . . . . . . . 13.3.12 Skewness . . . . . . . . . . . . . . . . . 13.3.13 Kurtosis . . . . . . . . . . . . . . . . . . 13.3.14 Covariance and Correlation . . . . . . . . 13.3.15 Miscellaneous Utilities . . . . . . . . . . 13.3.16 Percentiles and Rank . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 435 435 435 438 438 439 440 441 441 442 444 444 445 445 447 448 449 451 453 456 14 Special Functions 14.1 Introduction . . . . . . . . . . . . 14.2 Factorials . . . . . . . . . . . . . 14.3 Combinations and Permutations . 14.3.1 Combinations . . . . . . . 14.3.2 Permutations . . . . . . . 14.4 Gamma Function . . . . . . . . . 14.5 Beta Function . . . . . . . . . . . 14.6 Error Function . . . . . . . . . . . 14.7 Sine and Cosine Integral Functions 14.8 Laguerre Polynomials . . . . . . . 14.9 Hermite Polynomials . . . . . . . 14.10 Chebyshev Polynomials . . . . . . 14.11 Legendre Polynomials . . . . . . . 14.12 Bessel Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 461 461 461 464 464 467 470 472 472 474 475 476 477 479 480 15 Curve Fitting Methods 15.1 Introduction . . . . . . . . . . . . 15.2 Least Squares Fit . . . . . . . . . 15.2.1 Straight-Line Fit . . . . . 15.3 Weighted Least Squares Fit . . . . 15.3.1 Weighted Straight-Line Fit 15.4 Linear Regression . . . . . . . . . 15.4.1 Polynomial Fit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 483 483 484 485 488 488 492 496 © 2010 by Taylor and Francis Group, LLC Table of Contents xv 15.4.2 Exponential Fit . . . . . . . . . . . . . . . . . . . . . . . 497 15.5 The χ 2 Test for Goodness of Fit . . . . . . . . . . . . . . . . . . 499 16 Ordinary Differential Equations 16.1 Introduction . . . . . . . . . . . . . . . . . 16.2 Euler Method . . . . . . . . . . . . . . . . 16.3 Runge-Kutta Methods . . . . . . . . . . . . 16.3.1 Second-Order Runge-Kutta Method 16.3.2 Fourth-Order Runge-Kutta Method 16.3.3 Runge-Kutta-Fehlberg Method . . . 16.4 Coupled Differential Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 503 503 505 506 507 508 510 513 17 Partial Differential Equations 17.1 Introduction . . . . . . . . . . . . . . . 17.2 The Finite Difference Method . . . . . . 17.3 Parabolic Partial Differential Equations . 17.3.1 The Crank-Nicolson Method . . 17.4 Hyperbolic Partial Differential Equations 17.5 Elliptic Partial Differential Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 517 517 520 521 525 527 532 18 Optimization Methods 18.1 Introduction . . . . . . . . . . . . . . 18.2 Gradient Descent Method . . . . . . . 18.3 Linear Programming . . . . . . . . . 18.3.1 The Revised Simplex Method 18.4 Simulated Annealing Method . . . . . 18.5 Genetic Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 539 539 541 544 546 550 555 References © 2010 by Taylor and Francis Group, LLC . . . . . . 571 1 Introduction The main objective of this first chapter is to provide my readers with a brief outline of the .NET Framework, the C# programming language and the basic concepts of Object Oriented Programming (OOP). Special attention will be given to materials that illustrate how to best utilize these tools to develop accurate and robust numerical methods in C# primarily for use in scientific and engineering applications. 1.1 C# and the .NET Framework In the late 1990s, Microsoft embarked on a project to update and improve its flagship software application development system, more commonly known as Visual Studio, and as a result of this effort, an entirely new programming language named C# emerged that, among other things, essentially incorporates the best features of all the other popular programming languages of the time such as Java, C/C++ and Visual Basic. Consequently, since its first release in July of 2000, C# has quickly established itself worldwide as perhaps the preferred language for software application development. Besides being a very powerful general purpose, object-oriented programming language, C# enjoys the full advantage and benefits of being fully integrated with the Microsoft .NET Framework system. The Microsoft .NET Framework is a fundamental Windows operating system component that supports building and running both software applications as well as Web services. It consists of a large set of class libraries of pre-coded solutions to common programming problems and also provides a new environment for building applications that can be deployed and executed across multiple architectures and operating systems. The .NET Framework was designed to be installed on top of the Windows operating system and is divided into two key components: a runtime environment called the Common Language Runtime (CLR), which provides the runtime services to manage and execute applications originally written in any one of the .NET programming languages, and a large library of pre-coded object oriented classes called the Framework Class Library (FCL) which provides the required services for developing .NET applications. Conceptually, .NET applications reside above the .NET Framework architecture and can be illustrated abstractly as shown in Table 1.1. The C# language specification [1] has been standardized by ECMA International, 1 © 2010 by Taylor and Francis Group, LLC 2 Numerical Methods, Algorithms and Tools in C# TABLE 1.1 Outline of the .NET Framework Architecture Visual Basic .NET Applications Visual C# Visual C++ .NET Framework Class Library (FCL) Common Language Runtime (CLR) Operating System which is an industry association dedicated to the standardization of information and communication systems. As a result, consumers can now choose to buy their C# compilers from among several different manufacturers such as Microsoft [2], SharpDevelop [3], DotGNU [4] and Mono [5]. However, the most popular C# compiler on the market today comes bundled with Microsoft’s Visual Studio software development system which, in addition to having a C# compiler, also provides a full featured integrated development environment (IDE) that standardizes support for many of the other popular programming languages like Visual Basic and Visual C++. Accordingly, all the code and examples contained in this book were written and tested using the latest version of Microsoft Visual Studio. As part of the natural evolution of programming languages, C# has incorporated and exploited familiar features from C/C++ and Java that already had a proven record of success. In addition, C# also has a number of unique new features that make it a very attractive programming language. For example, C# controls access to hardware and memory resources and, by default, does not allow for the explicit usage and manipulation of pointers as C and C++ do except for sections of code that have been specifically designated as unsafe. This feature, along with the support of a more powerful garbage collector that automatically manages all aspects of memory allocation and de-allocation during runtime, has now made frustrating memory leaks and dangling pointers, often hard to find and debug in C/C++ programs, a thing of the past. In addition, improvements made in exception handling provide a well structured and extensible approach to error detection and recovery. C# is also designed with type-safe features that make it impossible to have non-initialized variables, to index arrays beyond their bounds, or to perform unchecked type casts. The C# language also supports more advanced features such as multi-threading and Just-in-Time (JIT) compilation from byte code to native code to name a few. © 2010 by Taylor and Francis Group, LLC Introduction 3 1.2 Installing C# and the .NET Framework You can buy Visual C# either by itself or as part of the Visual Studio IDE, which also includes, in addition to Visual C#, support for other programming languages such as Visual Basic and Visual C++. Visual C# comes in several editions. If you want Visual C# all by itself, you have only one choice: the Express edition. However, if you buy Visual C# as part of the Visual Studio package, you have three choices: Standard, Professional and Team editions to accommodate every budget, work environment and skill level. There is also the Academic version of the Professional edition which is available at a substantial discount for students and teachers. The key differences between these various editions center primarily on the number of development environment features available to the programmer. If you do computer programming as a hobby, the Express edition should work just fine for most of the applications described in this book. However, if you do a significant amount of software development in various languages and platforms, then you will likely derive most benefit from the multipurpose Professional edition. The Visual C# installation kit may consist of one or more CDs depending on the edition chosen. The installation itself is relatively easy and is simply a matter of following the directions displayed on the screen. If you do not have the required .NET Framework already installed on your system, the installation program will perform that task automatically for you prior to doing anything else. Due to the huge size of the program, it may take some time to install. But patience is a virtue in programming and it begins with the installation of Microsoft Visual Studio. Installing the latest version of the MSDN reference libraries directly on your computer is also highly recommended so that help files can be retrieved and promptly consulted as needed. 1.3 Overview of Object-Oriented Programming (OOP) There are primarily two methods of programming in use today: procedural and object-oriented. Procedural programming has its roots in the earliest forms of programming languages and essentially involves creating and naming computer memory locations that can hold data which can then be changed and manipulated through a series of sequential steps. The named computer memory locations are called variables because they hold values that might vary at some point during the life of the program. Sometimes a finite number of these sequential steps used in computer programs can be grouped into smaller logical units called procedures. Hence the objective of procedural programming is to focus on the creation of procedures to operate and potentially alter data. If, at some later point in time, the program’s original © 2010 by Taylor and Francis Group, LLC 4 Numerical Methods, Algorithms and Tools in C# specifications somehow change significantly enough to warrant a corresponding fundamental change in the program’s original data structure then the original code must also be changed and rewritten to accept the new data format. Unfortunately, such changes often result in additional work for programmers and this may ultimately lead to potential project release delays, higher production costs and perhaps most importantly, can also increase the chances for unwanted bugs to appear in the code. Object-oriented programming can be thought of as a major significant improvement of procedural programming. Whereas procedural programming is focused on creating procedures to manipulate data, object-oriented programming centers on creating abstract, self-contained software entities called objects that contain both attributes and methods, previously also known as data and procedures. The attributes of an object provide information about its characteristics whereas the methods of an object provide information about how to manipulate those attributes. More formally, an object is said to be an instance of a class and a class is said to be a template or a blueprint for describing how an object is created and how it behaves at runtime. Hence, a class defines behavior, properties and other attributes of an object that is an instance, or example, of that class. Object-oriented programs have attributes and methods that are said to be encapsulated into objects. Encapsulation is the object oriented principle associated with hiding the internal structural details of an object from the outside world so that programmers can only use a well defined interface to interact with an object’s internal structure. This feature is intended to prevent programmers from easily and perhaps even recklessly altering an object’s internal structure or behavior. Polymorphism is the object-oriented programming principle that allows the creation of methods that act appropriately depending on the context within which a particular task is carried out. Inheritance is an object oriented principle relating to how one class, called the derived or child class, can share the characteristics and behavior from another class, called the base or parent class. In addition to its own new and unique attributes and methods, the derived class is said to inherit and thus contain nearly all the attributes and methods of the existing base class. Therefore, besides retaining all the familiar and well established concepts of data (i.e. attributes) and procedures (i.e. methods), object-oriented programming also contains six additional unique features that are called: objects, classes, encapsulation, interfaces, polymorphism, and inheritance. 1.4 Your First C# Program There are at least four general types of applications that can be created with C#: Console applications, Windows Form applications, Web Services and ASP.NET applications. Console applications run from the command line and are the most fundamental and easiest applications to understand. Consequently, console applications © 2010 by Taylor and Francis Group, LLC
- Xem thêm -

Tài liệu liên quan