numerical_recipes

nr3”-2007/5/1—20:53—pageI一#1 NUMERICAL RECIPES TheArtofscientificcomputing Thirdedition nr3”-2007/5/1—20:53—pagell-#2 n3-2007/5/1-20:53-Pageill-#3 NUⅣERICAL RECIPES TheArtofScientificComputing Thirdedlition WIlliamhpress RaymerChairinComputerSciencesandIntegrativeBiology TheUniversityofTexasatAustin SaulA.Teukolsky sA.BetheProfessorofPhysicsandAstrophysics CornellUniversity WilliamTVetterling ResearchFellowandDirectorofImageScience ZINKImaging,LLC Brianpflanne Science,StrategyandProgramsManager ExxonMobilCorporation CAMBRIDGE UNIVERSITYPRESS CAMBRIDGEUNTVERSITYPRESS Cambridge,NewYork,Melbourne,Madrid,CapeTown,Singapore,SaoPaulo CambridgeUniversityPress TheedinburghBuilding,CambridgeCB28RU,UK PublishedintheUnitedStatesofAmericabyCambridgeUniversityPress,NewYork www.cambridge.org Informationonthistitlewww.cambridge.org/9780521880688 oCambridgeUniversityPress1988,1992,2002,2007exceptfor13.10,whichisplacedinto thepublicdomain,andexceptforallothercomputerprogramsandprocedures,whichare Thispublicationisincopyright.Subjecttostatutoryexceptionandtotheprovisionof relevantcollectivelicensingagreements,noreproductionofanypartmaytakeplace withoutthewrittenpermissionofCambridgeUniversityPress. Firstpublishedinprintformat2007 ISBN-13978-0-511-33555-6eBook(Netlibrary) ISBN-100-511-33555-5eBook(NetLibrary ISBN-13978-0-521-88068-8hardback ISBN-100-521-88068-8hardback ambridgeUniversityPresshasnoresponsibilityforthepersistenceoraccuracyofurls forexternalorthird-partyinternetwebsitesreferredtointhispublication,anddoesnot guaranteethatanycontentonsuchwebsitesis,orwillremain,accurateorappropriate Withoutanadditionallicensetousethecontainedsoftware,thisbookisintendedasatext andreferencebook,forreadingandstudypurposesonly.However,arestricted,limited freelicenseforuseofthesoftwarebytheindividualownerofacopyofthisbookwho personallykeyboardsoneormoreroutinesintoasinglecomputerisgrantedunderterms describedonp.xix.Seethesection"LicenseandLegalInformation"(ppxixxxi)for informationonobtainingmoregenerallicenses.Machine-readablemediacontainingthe g softwareinthisbook,withincludedlicenseforusebyasingleindividual,areavailable fromCambridgeUniversityPress.Thesoftwaremayalsobedownloaded,withimmediate purchaseofalicensealsopossiblefromtheNumericalRecipesSoftwareWebsite(http //www.nr.com).UnlicensedtransferofnUmericalRecipesprogramstoanyotherformat ortoanycomputerexceptonethatisspecificallylicensed,isstrictlyprohibited.Technical questions,corrections,andrequestsforinformationshouldbeaddressedtoNumerical RecipesSoftware,PO.Box380243,Cambridge,MA02238-0243(USA),emailinfo@nr com,orfax781-863-1739 2007/5/1 20:53 pagev—#5 Contents PrefacetotheThirdEdition(2007) PrefacetotheSecondEdition(1992) PrefacetotheFirstEdition(1985) XV LicenseandLegalInformation XIX 1Preliminaries 1.0Introduction 1.1Error,Accuracy,andstability 8 1.2CFamilySyntax 12 1.3Objects,Classes,andInheritance 17 1.4VectorandMatrixObjects 24 1.5SomeFurtherConventionsandcapabilities .30 2SolutionofLincarAlgcbraicEquations 37 2.0Introduction 37 2.1Gauss-Jordanelimination 41 2.2Gaussianeliminationwithbacksubstitution 46 2.3LUDecompositionandItsApplications 48 2.4TridiagonalandBand-DiagonalSystemsofequations 56 2.5IterativeImprovementofasolutiontolinearequations 61 2.6SingularvalueDecomposition 65 2.7SparseLinearsystems 75 2.8VandermondematricesandToeplitzmatrices 93 2.9CholeskyDecomposition 2.10ORDecomposition 102 2.11IsMatrixInversionann3Process? 106 3InterpolationandExtrapolation 110 3.0Introduction l10 3.1Preliminaries:ScarchinganOrderedTable 114 3.2PolynomialInterpolationandExtrapolation.............118 3.3CubicSplineInterpolation 120 3.4RationalFunctionInterpolationandExtrapolation........124 n3”-2007/5/1-20:53-PagevI一# Contents 3.5CoefficientsoftheInterpolatingPolynomial 129 3.6InterpolationonagridinMultidimensions .132 3.7InterpolationonScattereddatainmultidimensions 29 3.8LaplaceInterpolation 150 4IntcgrationofFunctions 155 4.0Introduction 155 4.1ClassicalFormulasforEquallySpacedAbscissas 156 4.2ElementaryAlgorithms 4.3RombergIntegration .166 4.4ImproperIntegrals 4.5QuadraturebyVariableTransformation 172 4.6GaussianQuadraturesandOrthogonalPolynomials ....,179 4.7AdaptiveQuadrature ...194 4.8Multidimensionalintegrals 196 5Evaluationoffunctions 201 5.0Introduction 201 5.1PolynomialsandRationalFunctions 201 5.2EvaluationofContinuedfractions 206 5.3SeriesandTheirConvergence 209 5.4RecurrencerelationsandClenshawsRecurrenceformula 219 5.5Complexarithmetic 225 5.6QuadraticandCubicequations .227 5.7NumericalDerivatives .229 5.8ChebyshevApproximation 233 5.9DerivativesorIntegralsofaChebyshev-ApproximatedFunction..240 5.10PolynomialApproximationfromChebyshevCoefficients 241 5.11Economizationofpowerseries .243 5.12PadeApproximants 245 5.13RationalChebyshevApproximation .247 5.14EvaluationofFunctionsbyPathIntegration 251 6SpecialFunctions 255 6.0Introduction 255 6.1GammaFunction.BetaFunctionFactorials.BinomialCoefficients256 6.2IncompleteGammaFunctionandErrorFunction 59 6.3ExponentialIntegral 266 6.4IncompletebetaFunction 270 6.6BesselFunctionsofFractionalOrder,AiryFunctions,Spherical.274 6.5BesselFunctionsofIntegerOrder Besselfunctions 283 6.7Sphericalharmonics 292 6.8FresnelIntegrals,Cosineandsineintegrals 297 6.9Dawson’sIntegral 302 6.10GeneralizedFermi-DiracIntegrals 304 6.11InverseoftheFunctionxlog(x) 307 6.12EllipticIntegralsandJacobianEllipticFunctions 309 nr3”-2007/5/1-20:53—pagevil-#7 Contents 6.13HypergeometricFunctions .318 6.14Statisticalfunctions 7RandomNumbers 340 7.0Introductio 340 7.1UniformDeviates 341 7.2CompletelyHashingaLargearray 358 7.3DeviatesfromOtherdistributions 361 7.4Multivariatenormaldeviates .378 7.5LinearFeedbackShiftRegisters ..380 7.6HashTablesandHashmemories 386 7.8Quasi-(thatis.Sub-)RandomSequencer 7.7SimplemonteCarloIntegration 397 403 7.9AdaptiveandRecursiveMonteCarloMethods 410 8SortingandSelection 419 8.0Introduction 419 8.1StraightInsertionandshell'smethod 420 8.2Quicksort 423 8.3H 426 8.4IndexingandRankin 428 8.5SelectingtheMth 431 8.6DeterminationofEquivalenceClasses 439 9RootFindingandNonlinearsetsofEquations 442 9.0Introduction 442 9.1BracketingandBisection 445 9.2Secantmethod.falsepositionmethod.andriddersmethod 449 9.3VanWijngaarden-Dekker-BrentMethod 454 9.4Newton-RaphsonMethodUsingDerivative 456 9.5Rootsofpc 463 9.6Newton-RaphsonMethodforNonlinearSystemsofequations 473 9.7GloballyConvergentMethodsforNonlinearSystemsofEquations477 10Minimizationormaximizationoffunctions 487 10.0Introduction 487 10.1InitiallyBracketingaMinimum 490 10.2GoldenSectionSearchinOnedimension 492 10.3ParabolicInterpolationandBrentsmethodinOnedimension...496 10.4One-Dimensionalsearchwithfirstderivatives 4 10.5DownhillSimplexMethodinMultidimensions 502 10.6Linemethodsinmultidimensions 507 10.7DirectionSet(Powells)MethodsinMultidimensions 509 10.8ConjugateGradientMethodsinMultidimensions 515 10.9Quasi-NewtonorVariableMetricMethodsinMultidimensions 521 10.10LinearProgramming:TheSimplexMethod 526 10.11LinearProgramming:Interior-PointMethods 537 10.12SimulatedAnnealingmethods 549 10.13DynamicProgramming .555 nr3”-2007/5/1-20:53—pa Contents 11Eigensystems 563 11.0Introduction ..563 11.1JacobiTransformationsofaSymmetricMatrix 570 11.2Realsymmetricmatrices 576 11.3ReductionofaSymmetricMatrixtoTridiagonalForm:Givens andhouseholderreductions .,,..578 11.4EigenvaluesandEigenvectorsofaTridiagonalmatrix 583 11.5Hermitianmatrices .590 11.6RealNonsymmetricMatrices 590 11.7TheORAlgorithmforRealHessenbergMatrices .596 11.8ImprovingEigenvaluesand/orFindingEigenvectorsbyInverse Iteratio 597 12FastFourierTransform 600 12.0Introducti 600 12.1FourierTransformofDiscretelySampledData 605 12.2Fasth 608 12.3FFTofRealFunctions .617 12.4Fastsineandcosinetransforms 620 12.5FFTinTwoormoredimensions 6 7 12.6FourierTransformsofRealdatainTwoandThreedimensions.631 12.7ExternalStorageorMemory-LocalFFTs .637 13FourierandSpectralApplications 640 13.0Introduction 640 13.1ConvolutionandDeconvolutionUsingtheFFt .641 13.2Correlationandautocorrelationusingthefft 648 13.3Optimal(Wiener)FilteringwiththeFFT 649 13.4PowerSpectrumestimationUsingtheFFt 652 13.5DigitalfilteringintheTimedomain 667 13.6LinearPredictionandLinearPredictiveCoding .673 13.7PowerSpectrumEstimationbytheMaximumEntropy(All-poles Method 681 13.8SpectralanalysisofUnevenlySampleddata 685 13.9ComputingFourierIntegralsUsingtheFFt .692 13.10WaveletTransforms 699 13.11NumericalUseoftheSamplingTheorem 717 14StatisticalDescriptionofData 720 14.0Introduction 720 14.1Momentsofadistribution:Mean.VarianceSkewnessandsoforth721 14.2DoTwoDistributionshavethesamemeansorvariances? 726 14.3AreTwoDistributionsDifferent? 730 14.4ContingencyTableAnalysisofTwoDistributions 741 14.5Linearcorrelation 745 14.6NonparametricorRankCorrelation 748 14.7Information-TheoreticPropertiesofDistributions 754 14.8DoTwo-DimensionalDistributionsDiffer?......,......762