Object-Oriented Implementation of Numerical Methods An Introduction with Smalltalk

41w2hhtecul-_sx373_bo1204203200_

Contents

1 Introduction 1

1.1 Object-oriented paradigm and mathematical objects . . . . . . . 2

1.2 Object-oriented concepts in a nutshell . . . . . . . . . . . . . . . 3

1.3 Dealing with numerical data . . . . . . . . . . . . . . . . . . . . . 4

1.3.1 Floating point representation . . . . . . . . . . . . . . . . 4

1.3.2 Rounding errors . . . . . . . . . . . . . . . . . . . . . . . 5

1.3.3 Real example of rounding error . . . . . . . . . . . . . . . 7

1.3.4 Outsmarting rounding errors . . . . . . . . . . . . . . . . 8

1.3.5 Wisdom from the past . . . . . . . . . . . . . . . . . . . . 9

1.4 Finding the numerical precision of a computer . . . . . . . . . . . 10

1.4.1 Computer numerical precision . . . . . . . . . . . . . . . . 12

1.5 Comparing

oating point numbers . . . . . . . . . . . . . . . . . 15

1.6 Speed consideration (to be revisited) . . . . . . . . . . . . . . . . 16

1.6.1 Smalltalk particular . . . . . . . . . . . . . . . . . . . . . 17

1.7 Conventions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

1.7.1 Class diagrams . . . . . . . . . . . . . . . . . . . . . . . . 18

1.7.2 Smalltalk code . . . . . . . . . . . . . . . . . . . . . . . . 19

1.8 Road map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2 Function evaluation 23

2.1 Function { Smalltalk implementation . . . . . . . . . . . . . . . . 24

2.2 Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.2.1 Mathematical denitions . . . . . . . . . . . . . . . . . . . 25

2.2.2 Polynomial | Smalltalk implementation . . . . . . . . . . 27

2.3 Error function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

2.3.1 Mathematical denitions . . . . . . . . . . . . . . . . . . . 34

2.3.2 Error function | Smalltalk implementation . . . . . . . . 35

2.4 Gamma function . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

2.4.1 Mathematical denitions . . . . . . . . . . . . . . . . . . . 38

2.4.2 Gamma function | Smalltalk implementation . . . . . . 39

2.5 Beta function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

2.5.1 Mathematical denitions . . . . . . . . . . . . . . . . . . . 42

2.5.2 Beta function | Smalltalk implementation . . . . . . . . 42

3 Interpolation 43

3.1 General remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

3.2 Lagrange interpolation . . . . . . . . . . . . . . . . . . . . . . . . 49

3.2.1 Lagrange interpolation | Smalltalk implementation . . . 50

3.3 Newton interpolation . . . . . . . . . . . . . . . . . . . . . . . . . 53

3.3.1 Newton interpolation | General implementation . . . . . 53

3.3.2 Newton interpolation | Smalltalk implementation . . . . 54

3.4 Neville interpolation . . . . . . . . . . . . . . . . . . . . . . . . . 55

3.4.1 Neville interpolation | General implementation . . . . . 56

3.4.2 Neville interpolation | Smalltalk implementation . . . . 57

3.5 Bulirsch-Stoer interpolation . . . . . . . . . . . . . . . . . . . . . 59

3.5.1 Bulirsch-Stoer interpolation | General implementation . 60

3.5.2 Bulirsch-Stoer interpolation | Smalltalk implementation 60

3.6 Cubic spline interpolation . . . . . . . . . . . . . . . . . . . . . . 61

3.6.1 Cubic spline interpolation | General implementation . . 63

3.6.2 Cubic spline interpolation | Smalltalk implementation . 63

3.7 Which method to choose? . . . . . . . . . . . . . . . . . . . . . . 66

4 Iterative algorithms 69

4.1 Successive approximations . . . . . . . . . . . . . . . . . . . . . . 69

4.1.1 Iterative process | Smalltalk implementation . . . . . . . 73

4.2 Evaluation with relative precision . . . . . . . . . . . . . . . . . . 77

4.2.1 Relative precision | Smalltalk implementation . . . . . . 78

4.3 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

5 Finding the zero of a function 81

5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

5.2 Finding the zeroes of a function | Bisection method . . . . . . . 82

5.2.1 Bisection algorithm | General implementation . . . . . . 84

5.2.2 Bisection algorithm | Smalltalk implementation . . . . . 84

5.3 Finding the zero of a function | Newton’s method . . . . . . . . 86

5.3.1 Newton’s method | Smalltalk implementation . . . . . . 87

5.4 Example of zero-nding | Roots of polynomials . . . . . . . . . 90

5.4.1 Roots of polynomials | Smalltalk implementation . . . . 90

5.5 Which method to choose . . . . . . . . . . . . . . . . . . . . . . . 92

6 Integration of functions 93

6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

6.2 General framework | Trapeze integration method . . . . . . . . 94

6.2.1 Trapeze integration | General implementation . . . . . . 97

6.2.2 Trapeze integration | Smalltalk implementation . . . . . 97

6.3 Simpson integration algorithm . . . . . . . . . . . . . . . . . . . 99

6.3.1 Simpson integration | General implementation . . . . . . 100

6.3.2 Simpson integration | Smalltalk implementation . . . . . 100

6.4 Romberg integration algorithm . . . . . . . . . . . . . . . . . . . 101

6.4.1 Romberg integration | General implementation . . . . . 102

6.4.2 Romberg integration | Smalltalk implementation . . . . 103

6.5 Evaluation of open integrals . . . . . . . . . . . . . . . . . . . . . 104

6.6 Which method to chose? . . . . . . . . . . . . . . . . . . . . . . . 105

6.6.1 Smalltalk comparison . . . . . . . . . . . . . . . . . . . . 106

7 Series 107

7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

7.2 Innite series . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

7.2.1 Innite series | Smalltalk implementation . . . . . . . . 109

7.3 Continued fractions . . . . . . . . . . . . . . . . . . . . . . . . . . 110

7.3.1 Continued fractions | Smalltalk implementation . . . . . 111

7.4 Incomplete Gamma function . . . . . . . . . . . . . . . . . . . . . 112

7.4.1 Mathematical denitions . . . . . . . . . . . . . . . . . . . 113

7.4.2 Incomplete Gamma function | Smalltalk implementation 114

7.5 Incomplete Beta function . . . . . . . . . . . . . . . . . . . . . . 117

7.5.1 Mathematical denitions . . . . . . . . . . . . . . . . . . . 117

7.5.2 Incomplete Beta function | Smalltalk implementation . . 118

8 Linear algebra 123

8.1 Vectors and matrices . . . . . . . . . . . . . . . . . . . . . . . . . 123

8.1.1 Vector and matrix implementation . . . . . . . . . . . . . 127

8.2 Linear equations . . . . . . . . . . . . . . . . . . . . . . . . . . . 137

8.2.1 Linear equations | General implementation . . . . . . . 140

8.2.2 Linear equation implementation . . . . . . . . . . . . . . 140

8.3 LUP decomposition . . . . . . . . . . . . . . . . . . . . . . . . . 144

8.3.1 LUP decomposition | General implementation . . . . . . 146

8.3.2 LUP decomposition . . . . . . . . . . . . . . . . . . . . . 147

8.4 Computing the determinant of a matrix . . . . . . . . . . . . . . 151

8.5 Matrix inversion . . . . . . . . . . . . . . . . . . . . . . . . . . . 153

8.5.1 Matrix inversion implementation . . . . . . . . . . . . . . 155

8.5.2 Matrix inversion | Rounding problems . . . . . . . . . . 158

8.6 Matrix eigenvalues and eigenvectors of a non-symmetric matrix . 158

8.6.1 Finding the largest eigenvalue | General implementation 160

8.6.2 Finding the largest eigenvalue implementation . . . . . . 161

8.7 Matrix eigenvalues and eigenvectors of a symmetric matrix . . . 163

8.7.1 Jacobi’s algorithm | General implementation . . . . . . 166

8.7.2 Jacobi’s algorithm implementation . . . . . . . . . . . . . 167

9 Elements of statistics 173

9.1 Statistical moments . . . . . . . . . . . . . . . . . . . . . . . . . 173

9.1.1 Statistical moments | General implementation . . . . . . 176

9.1.2 Statistical moments | Smalltalk implementation . . . . . 176

9.2 Robust implementation of statistical moments . . . . . . . . . . . 178

9.2.1 Robust central moments | General implementation . . . 180

9.2.2 Robust central moments | Smalltalk implementation . . 180

9.3 Histograms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184

9.3.1 Histograms | General implementation . . . . . . . . . . 185

9.3.2 Histograms | Smalltalk implementation . . . . . . . . . . 186

9.4 Random number generator . . . . . . . . . . . . . . . . . . . . . 195

9.4.1 Random number generator | Smalltalk implementation . 197

9.5 Probability distributions . . . . . . . . . . . . . . . . . . . . . . . 203

9.5.1 Probability distributions | Smalltalk implementation . . 205

9.6 Normal distribution . . . . . . . . . . . . . . . . . . . . . . . . . 210

9.6.1 Normal distribution | Smalltalk implementation . . . . . 210

9.6.2 Gamma distribution | Smalltalk implementation . . . . 213

9.7 Experimental distribution . . . . . . . . . . . . . . . . . . . . . . 216

9.7.1 Experimental distribution | General implementation . . 217

9.7.2 Experimental distribution | Smalltalk implementation . 217

10 Statistical analysis 221

10.1 F-test and the Fisher-Snedecor distribution . . . . . . . . . . . . 222

10.1.1 Fisher-Snedecor distribution | Smalltalk implementation 224

10.2 t-test and the Student distribution . . . . . . . . . . . . . . . . . 229

10.2.1 Student distribution | Smalltalk implementation . . . . 231

10.3 2-test and 2 distribution . . . . . . . . . . . . . . . . . . . . . 236

10.3.1 2 distribution | Smalltalk implementation . . . . . . . 238

10.3.2 Weighted point implementation . . . . . . . . . . . . . . . 239

10.4 2-test on histograms . . . . . . . . . . . . . . . . . . . . . . . . 242

10.4.1 2-test on histograms | Smalltalk implementation . . . . 243

10.5 Denition of estimation . . . . . . . . . . . . . . . . . . . . . . . 246

10.5.1 Maximum likelihood estimation . . . . . . . . . . . . . . . 246

10.5.2 Least square estimation . . . . . . . . . . . . . . . . . . . 247

10.6 Least square t with linear dependence . . . . . . . . . . . . . . . 249

10.7 Linear regression . . . . . . . . . . . . . . . . . . . . . . . . . . . 250

10.7.1 Linear regression | General implementation . . . . . . . 251

10.7.2 Linear regression | Smalltalk implementation . . . . . . 252

10.8 Least square t with polynomials . . . . . . . . . . . . . . . . . . 255

10.8.1 Polynomial least square ts | Smalltalk implementation 257

10.9 Least square t with non-linear dependence . . . . . . . . . . . . 261

10.9.1 Non-linear t | General implementation . . . . . . . . . 263

10.9.2 Non-linear t | Smalltalk implementation . . . . . . . . 263

10.10Maximum likelihood t of a probability density function . . . . . 267

10.10.1Maximum likelihood t | General implementation . . . . 270

10.10.2Maximum likelihood t | Smalltalk implementation . . . 271

11 Optimization 275

11.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276

11.2 Extended Newton algorithms . . . . . . . . . . . . . . . . . . . . 277

11.3 Hill climbing algorithms . . . . . . . . . . . . . . . . . . . . . . . 278

11.3.1 Optimizing | General implementation . . . . . . . . . . . 279

11.3.2 Common optimizing classes | Smalltalk implementation 280

11.4 Optimizing in one dimension . . . . . . . . . . . . . . . . . . . . 286

11.4.1 Optimizing in one dimension | Smalltalk implementation 286

11.5 Bracketing the optimum in one dimension . . . . . . . . . . . . . 289

11.5.1 Bracketing the optimum | Smalltalk implementation . . 289

11.6 Powell’s algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 290

11.6.1 Powell’s algorithm | General implementation . . . . . . 291

11.6.2 Powell’s algorithm | Smalltalk implementation . . . . . . 292

11.7 Simplex algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 294

11.7.1 Simplex algorithm | General implementation . . . . . . 296

11.7.2 Simplex algorithm | Smalltalk implementation . . . . . . 296

11.8 Genetic algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 299

11.8.1 Genetic algorithm | General implementation . . . . . . . 302

11.8.2 Genetic algorithm | Smalltalk implementation . . . . . . 304

11.9 Multiple strategy approach . . . . . . . . . . . . . . . . . . . . . 309

11.9.1 Multiple strategy approach | General implementation . . 310

12 Data mining 313

12.1 Data server . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314

12.1.1 Data server | Smalltalk implementation . . . . . . . . . 315

12.2 Covariance and covariance matrix . . . . . . . . . . . . . . . . . . 317

12.2.1 Covariance matrix | General implementation . . . . . . 319

12.2.2 Covariance matrix | Smalltalk implementation . . . . . . 319

12.3 Multidimensional probability distribution . . . . . . . . . . . . . 322

12.4 Covariance data reduction . . . . . . . . . . . . . . . . . . . . . . 322

12.5 Mahalanobis distance . . . . . . . . . . . . . . . . . . . . . . . . 323

12.5.1 Mahalanobis distance | General implementation . . . . . 325

12.5.2 Mahalanobis distance | Smalltalk implementation . . . . 326

12.6 Cluster analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328

12.6.1 Cluster analysis | General implementation . . . . . . . . 330

12.6.2 Cluster analysis | Smalltalk implementation . . . . . . . 332

12.7 Covariance clusters . . . . . . . . . . . . . . . . . . . . . . . . . . 336

A Decimal oating-point simulation 339

B Smalltalk primer for Java programmers 343

B.1 Syntax in a nutshell . . . . . . . . . . . . . . . . . . . . . . . . . 343

B.1.1 Smalltalk expressions . . . . . . . . . . . . . . . . . . . . 343

B.1.2 Precedence . . . . . . . . . . . . . . . . . . . . . . . . . . 344

B.1.3 Assignment, equality and identity . . . . . . . . . . . . . 345

B.2 Class and methods . . . . . . . . . . . . . . . . . . . . . . . . . . 345

B.2.1 Instance methods . . . . . . . . . . . . . . . . . . . . . . . 345

B.2.2 Class methods . . . . . . . . . . . . . . . . . . . . . . . . 347

B.2.3 Block . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348

B.3 Iterator methods . . . . . . . . . . . . . . . . . . . . . . . . . . . 348

B.3.1 do: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349

B.3.2 collect: . . . . . . . . . . . . . . . . . . . . . . . . . . . 349

B.3.3 inject:into: . . . . . . . . . . . . . . . . . . . . . . . . 349

B.4 Double dispatching . . . . . . . . . . . . . . . . . . . . . . . . . . 349

B.5 Multiple dispatching . . . . . . . . . . . . . . . . . . . . . . . . . 351

C Additional probability distributions 353

C.1 Beta distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . 353

C.1.1 Beta distribution | Smalltalk implementation . . . . . . 353

C.2 Cauchy distribution . . . . . . . . . . . . . . . . . . . . . . . . . 357

C.2.1 Cauchy distribution | Smalltalk implementation . . . . . 358

C.3 Exponential distribution . . . . . . . . . . . . . . . . . . . . . . . 360

C.3.1 Exponential distribution | Smalltalk implementation . . 360

C.4 Fisher-Tippett distribution . . . . . . . . . . . . . . . . . . . . . 363

C.4.1 Fisher-Tippett distribution | Smalltalk implementation . 364

C.5 Laplace distribution . . . . . . . . . . . . . . . . . . . . . . . . . 367

C.5.1 Laplace distribution | Smalltalk implementation . . . . . 367

C.6 Log normal distribution . . . . . . . . . . . . . . . . . . . . . . . 370

C.6.1 Log normal distribution | Smalltalk implementation . . 370

C.7 Triangular distribution . . . . . . . . . . . . . . . . . . . . . . . . 374

C.7.1 Triangular distribution | Smalltalk implementation . . . 374

C.8 Uniform distribution . . . . . . . . . . . . . . . . . . . . . . . . . 377

C.8.1 Uniform distribution | Smalltalk implementation . . . . 377

C.9 Weibull distribution . . . . . . . . . . . . . . . . . . . . . . . . . 380

C.9.1 Weibull distribution | Smalltalk implementation . . . . . 381

D Accurate accumulation of expectation values 385

D.1 Accurate accumulation of central moments . . . . . . . . . . . . 385

D.2 Accurate accumulation of the covariance . . . . . . . . . . . . . . 387

Object-Oriented Implementation of Numerical Methods An Introduction with Smalltalk

Anúncios

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s