THE CALCULUS OF FINITE DIFFERENCES
THE CALCULUS
OF
FINITE DIFFERENCES
BY
L. M. MILNE-THOMSON, C.B.E.
PROFESSOR OF MATHEMATICS IN THE UNIVERSITY OF ARIZONA EMERITUS PROFESSOR OF MATHEMATICS IN THE ROYAL NAVAL COLLEGE GREENWICH
LONDON,
MACMILLAN & CO LTD
NEW YORK ■ ST MARTIn’s PRESS 1965
This book is copy fight ifi all countries which arc signatories to the JBeme Convention
First Edition - - . ^933 Reprinted xg6o, xg6s
MACMII-LA.3Sr AND COM PAN V" LIMITED
St Martin’s Street London IV C 2 also Sombay Oalcutta M adras M elhonrne
THE MACMILLAN COMPANY OF CANADA LIMITED
70 JBond street 'Toronto 2
SX martin's press INC
jr 75 Fifth A.ven'ue ISfevo 'York xooxo MY
PJRlISrTKD IN GRKAX BRIXAIN BV AIORRXSON AND OZBB X,IMITEI>, X.ONDON AND BDINBUROBl
PREFACE
Thk <»r t.liis hook is i-o jirovide a sinijyk' cUid (‘onnootrd aocoimt
of t.h(' sid)joot. of Finite Differences and to present the theory in a forni which ca,n l)e readily applied.
Two distinct reasons impelled me to undertake this work. Finst, in ni\' lectures at Greenwich to junior members of the Royal Corps of Na.val Constructors I have occasion to treat certain aspects of differ(‘n(U‘ equations ; secondly, the calculation of tables of elliptic functions and integrals, on which I have been recently engaged, ga,\u‘ rise to st‘veral int(‘.resting practical difficulties which had to he overcome. For both these causes my attention has been (lir(‘et(‘d towards the subject and the lack of a suitable text-book upon which to draw was brought to my notice. The only com- prehensive Elnglish treatise, namely Boole’s Finite Difference's, is long since out of print, and in most respects out of date. My tirstr idea, was to revise Boole’s book, but on looking into the matter it appeared that such a course would be unsatisfactory, if not impracticable. 1 therefore decided to write a completelj^ new work ill which not only the useful material of Boole should find a place, but in which room should also be found for the more modern developments of the finite calculus.
My aim throughout has been to keep in mind the needs of the beginner, so that the book may be regarded as suitable for a first course as well as for more advanced reading. I do not, however, believe that the needs of the beginner in a mathematical subject a, re best served by eschewing all but the most elementary math(‘.- matical apparatus. Rather, his interest in the subject may well form an adequati‘. o])portunity for enlarging liis outlook on the science of ruatheniatics, so that he may the better be enabled to distinguish and appreciate' the connection of the whole system a,nd the relative dependency of its several parts. Consequently 1 have not hesitated to use the mathematical process or terminology which has appeared to me most appropriate to the immediate object in view. On the other hand whenever this course seems to
PREFACE
vi
lead beyond tbe elementary matters, with which all who embark on the reading of a mathematical book must be presumed to be acquainted, I have included the necessary definitions or proofs as part of the text or have given accessible references to treatises which can ordinarily be found in any mathematical library. In this way it has been possible to treat the subject in a simple yet rigorous manner.
The subject-matter falls naturally into two main divisions which may be subsumed under the headings Interpolation and Difference Equations. The pioneer in interpolation was undoubtedly Briggs, whose work was largely of an arithmetical character. Newton was the originator of the systematic theory and his divided difference formula is really the fundamental basis of all the usual metliods of polynomial interpolation. Gregory was probably an independent discoverer in the same field.*
The present work therefore starts with divided differences in Chapter I ; and in a general sense Chapters III, IV and VII may be regarded as elaborations of Newton’s work. Chapter V on reciprocal differences, describes a method of interpolation, due to Thiele, by means of rational functions, which is more general than polynomial interpolation, and which will possibly be new to many Enghsh readers. Chapter VI introduces the generalisations, due to Norlund, of Bernoulli’s polynomials, but here they are treated by a symbohe method, which seemed to me to be as effi- cacious and in many ways more suitable than Norland’s method, which is founded upon a different principle. By means of these generalisations the subject of numerical differentiation and integra- tion assumes a unified aspect which hardly seems to be attainable without them. Chapters I to VII therefore form a suitable intro- ductory course and will make very little demand on the reader’s previous mathematical knowledge. I have tried to meet the requirements of those who wish to make numerical applications by giving the formulae in a manner suited to direct use with a table of data. The numerical illustrations scattered through these chapters are mainly of a simple kind which can be easily worked, for it is not my purpose to obscure principles by unnecessary arith- metic. The subject-matter of some of these examples is perhaps
* See H. W. TumbuU, p. 101, footnote.
PREFACE
vii
of an unusual nature, but this is intentional in order to lend variety to the applications. In the chapters on Interpolation I have followed Steffensen’s excellent example in lapng much stress on the remainder term, which measures the error committed in using an interpo- lation formula. Indeed, no formula has been given which is unaccompanied by a means of estimating the remainder.
The part of the book which deals with difference equations begins with Chapter VIII, which expounds Norlund’s method of treating the summation problem. Chapter IX applies these methods to elaborating the theory of the Gamma function. In Chapter X, I have attempted to give a consecutive account of the salient properties of factorial series, which, I hope, wiU prove interesting in itself. The object of this chapter is to develop the properties of the series in which the solutions of difference equations find their natural expression. Chapter XI discusses the difference equation of the first order ; the hnear case is completely elucidated, and certain amenable non-linear forms are treated. This chapter includes an investigation of the exact difference equation of the first order. The methods of this, and of succeeding chapters, are illustrated by simple worked examples in the text. Chapter XII considers the properties of the general linear equation, including the application of generalised continued fractions treated by matrix methods. Chapter XIII deals with the important case of constant coefficients. Here the theory is complete, in the sense that the solution can be explicitly obtained. I have dealt with this equation at some length both by Boole’s method and by a method of my own, which seems well adapted to applications of a geometrical or physical nature, and which is analogous to Heaviside’s method for differential equations. The linear equation with constant coefficients has recently come into prominence in connection with various physical and mechanical problems ; for example in the theory of Structures. Chapters XIV and XVI develop the solution of linear difference equations with variable coefficients by means of Boole’s operators, which I have generalised in order to render the treatment more complete. Chapter XV gives an alternative treatment founded on Norland’s use of Laplace’s transformation. Chapter XVII gives two fundamental theorems of Poincar4 and Perron on the asymptotic properties of the solutions of a certain type of linear difference equation. The proof of Perron’s theorem
PREFACE
viii
is made to depend upon the properties of a certain class of simul- taneous linear equations in infinitely many unknowns. The theory is so interesting and so closely connected with finite differences that it has seemed worth while to give Perron’s treatment in extenso.
Operational and symbolic methods have been freely used through- out the book, and it is hoped that the manner of presentation here given will be found free from the objections often associated with their use. Indeed it has always seemed to me that symbolic methods constitute the essence of the finite calculus. My choice of notations has therefore been made with a view to facilitating the statement and application of operational methods, and to stressing the analogies with the infinitesimal calculus.
In stating theorems I have as far as possible associated the name of the discoverer as sufficient indication of the origin, but it must not be assumed that the method of presentation is in every case that in which the theorem was originally given. Indeed in the case of the work of the older analysts it would be easy, but un- profitable, to point out defects and lack of rigour in many of their proofs.
My labour in correcting the proof sheets has been greatly lightened by Professor H. W. Turnbull, F.R.S., who has read the first proof and made many valuable suggestions both mathematical and historical ; and by Dr. A. G. Aitken, F.R.S.E., who has performed the same kindly office, has supplied many original examples, and has verified the numerical work. To both these friends I wish to express my lively thanks for assistance which has helped me to remove many imperfections both of expression and demonstration. For any blemishes which may remain I am solely responsible, but I am led to express the hope that the work will be found to be free from important errors. I take this opportunity of expressing my thanks to the officials of the Glasgow University Press for the ready way in which they have met my somewhat exacting require- ments.
L. M. MILNE-THOMSON.
Mathematics Department,
Royal Naval Colleoe,
Greenwich,
Jvlif 1933.
CONTENTS
PAGE
Introduction xxi
Notations xxii
CHAPTER I
DIVIDED DIFFERENCES
1*0. Definitions 1
M . Newton’s interpolation formula with divided differences - - 2
M5. Rolle’s Theorem 4
1*2. Remainder term in Newton’s formula 5
1*3. Divided differences are symmetric functions of the arguments 7
1*31. Divided differences of 7
1-4. Lagrange’s interpolation formula 8
1-5. Expression of divided differences by means of determinants • 9
1- 6. Divided differences expressed by definite integrals - - - 10
1*7. Divided differences expressed by contour integrals - - - 11
1*8. Divided differences with repeated arguments - - - - 12
1*9. Interpolation polynomials 14
Examples I 17
CHAPTER II
DIFFERENCE OPERATORS
2*0. Difference notation 20
2- OL Central difference notation . , - - 22
2*1. Difference quotients 23
2*105. Partial difference quotients - - - - 24
2*11. Difference quotients of factorial expressions - 25
2*12. Expansion of a polynomial in factorials - - 27
2*13. Successive difference quotients of a polynomial 28
2*14, Difference quotients of - - - - 29
2*2. Properties of the operator A - - - - 30
u»
2*3. The operator y 31
(M OJ
X
CONTENTS
24. The operator E“
241. Herschel’s Theorem
242.
243. <55>(E“)a®w(.'r)=a«=</)(a"E“)?^(^) - - - •
2*5, Relations between A, E^s
ta
2*51. The analogue of Leibniz’ Theorem - - - -
2*52. Difference quotients of
2*53. Difference quotients of zero
2*54. Difference quotients in terms of derivates
2*6. The summation operator p”^
2*61. A theorem on the value of -
2*62. Relation between sums and functional values -
2*63. Moments
2*64. Partial summation
2*7. Summation of finite series
2*71. Summation of factorial expressions of the form xW
•72. Polynomials - - -
•73. Factorial expressions of the form -
2‘74. A certain type of rational function - . - .
2*75. The form a® a polynomial
2*76. The form (re), <^(x) a polynomial
2*77. Unclassified forms
Examples II
CHAPTER III INTERPOLATION
3*0. Divided differences for equidistant arguments - 3*1. Newton’s interpolation formula (forward differences) 3*11. Nevijon’s interpolation formula (backward differences) 3*12. The remainder term
3*2. Interpolation formulae of Gauss - . . .
3*3. Stirling’s interpolation formula - - . _
3*4. Bessel’s interpolation formula - - - - _
3*41. Modified Bessel’s formula - - - - .
3*5. Everett’s interpolation formula - -
3*6. Steffensen’s interpolation formula - - _ .
3*7. Interpolation without differences - - - _
3*81. Aitken’s linear process of interpolation by iteration
3*82. Aitken’s quadratic process
3*83. Neville’s process of iteration
Examples III
PAGE
31
32 32
32
33
34
35
36
37 37 39
39
40
41
42
42
43
44
45
46 46
48
49
56
57 59 61 63
67
68
71
72
74
75
76 78 81 84
lO lO
CONTENTS
CHAPTEE IV
NUMERICAL APPLICATIONS OF DIFFERENCES
PAGE
4*0. Diilerences when the interval is subdivided . - . • 87
4*1. Differences of a numerical table 88
4*2. Subtabulation 91
4*3. Inverse interpolation 95
4*4. Inverse interpolation by divided differences - . - ■ 96
4*5. Inverse interpolation by iterated linear interpolation - 97
4*6. Inverse interpolation by successive approximation - - • 99
4*7. Inverse interpolation by reversal of series - - - -100
Examples IV 101
CHAPTER V
RECIPROCAL DIFFERENCES
5*1. Definition of reciprocal differences - - - 104
5*2. Thiele’s interpolation formula - - - - 106
5*3. Matrix notation for continued fractions - - 108
5*4. Reciprocal differences expressed by determinants 110
5*5. Reciprocal differences of a quotient - - - 112
5*6. Some properties of reciprocal differences - 114
5*7. The remainder in Thiele’s formula - - - 116
•8. Reciprocal derivates ; the confluent case - - 117
•9. Thiele’s Theorem 119
Examples V 122
CHAPTER VI
THE POLYNOMIALS OF BERNOULLI AND EULER
6*0. The <f) polynomials 124
6*01. The (3 polynomials 126
6*1 Definition of Bernoulli’s polynomials 126
6*11. Fundamental properties of Bernoulli’s polynomials - - - 127
6*2. Complementary argument theorem 128
6*3. Relation between polynomials of successive orders - - - 129
6*4. Relation of Bernoulli’s polynomials to factorials - - - 129
6*401. The integral of the factorial 131
6*41. Expansion of xW in powers of a: 133
6*42. Expansion of x'' in factorials 133
6*43. Generating functions of Bernoulli’s numbers - - - - 134
CONTJi:Nl’fc5
xii
PAGE
6*5. Bernoulli’s polynomials of tlic first ord(‘r - 136
6-501. Sum of the vtii powers of the first n integers 137
6-51. Bernoulli’s numbers of the first order - - 137
6-511. Euler-Haclaurin Theorem for polynomials - 139
6-52. Multiplication Theorem 141
6-53. Bernoulli’s polynomials in the interval (0, 1) - 141
6-6. The 7] polynomials 142
6-7. Definition of Euler’s polynomials . - - 143
6-71. Fundamental j^roperties of Euler’s polynomials 144
6*72. Complementary argument theorem . ~ 145
6-73. Euler’s polynomials of successive orders - 145
6-8. Euler’s polynomials of the first order - - 146
6-81. Euler’s numbers of the first order - - - 147
6-82. Boole’s Theorem for polynomials . - - 149
Examples \T 150
CHAPTER VII
NUMERICAL DIFFERENTIATION AND INTEGRATION
7-0. The first order derivate 154
7*01. Derivates of higher order . - . . 155
7-02. Markoff’s formula 157
7*03. Derivates from Stirling’s formula - - - 159
7-04. Derivates from Bessel’s formula ... 161
7-05. Differences in terms of derivates ... 162
7-1. Numerical integration 162
7-101. Mean Value Theorem 163
7*11. Integration by Lagrange’s interpolation formula 164
7*12. Equidistant arguments 165
7*13. Remainder term, n odd 166
7-14. Remainder term, even - . - - - 167
7*2. Cotes’ formulae 168
7-21. Trapezoidal rule 170
7*22. Simpson’s rule 171
7*23. Formulae of G. F. Hardy and AVcddle ... 171
7*3. Quadrature formulae of the open tyq:)e ... 172
7*31. Method of Gauss 172
7*33. Method of Tschebyscheff . . . _ . 177
7*4. Quadrature formulae involving differences - . 180
7*41. Laplace’s formula 181
7*42. Laplace’s formula applied to differential equations ■ 183
7*43. Central difference formulae - - - . . 184
CONTENTS xiii
PAQK
7’5. Euler- Maclaurin formula - 1^7
7*51. Apx^lioation to finite summation 191
7-6. Gregory’s formula - - - 191
7-7. Summation formula of Lubbock 193
Examples VII - - - 196
CHAPTER VIII THE SroiMATION PROBLEM
8*0. Definition of the principal solution or sum .... 201
8*1. Properties of the sum 204
8T1. Sum of a polynomial 208
8*12. Repeated summation 208
8*15. Proof of the existence of the principal solution (real variable) - 209
8*16. Bernoulli’s polynomials iL (a* I CO ) 213
8*2. Differentiation of the sum 213
8*21. Asymptotic behaviour of the sum for large values of a - - 214
8*22. Asymptotic behaviour of the sum for small v^alues of co - - 216
8*3. Fourier series for the sum 218
8*4. Complex variable. Notation. Residue Theorem - - - 220
8*41 . Application of Cauchy’s residue theorem .... 222
8*5. Extension of the theory 226
8*53. The sum of the exponential function - - - - - 231
8*6. Functions with only one singular point 232
8*7. An expression for F{x* I - CO ) 238
Examples VUI 238
CHAPTER IX
THE PSI FUNCTION AND THE GAMMA FUNCTION
9*0. The function 'T' (a* j co) 241
9*01. Differentiation of the Psi function 241
9*03. Partial and repeated summation 243
9*1. Asymptotic behaviour for large vahic‘S of a* . . . . 244
9*11. Partial fraction development of 'P (a: 1 CO ) _ . . . 245
9*2. Multiplication theorem for the Psi function . - . - 246
9*22. Fourier series for "P (a;) 247
9*3. Gauss’ integral for 'P (a*) 247
9*32. Poisson’s integral 248
9*4. Complementary argument theorem for the Psi function - - 249
9*5. The Gamma function 249
|
xiv |
CONTEISTTS |
PAGE |
|
9*52. |
Schlomilch’s infinite product for r(a; + 1) |
250 |
|
9*53. |
Infinite products expressed by means of F (a;) |
251 |
|
9-54. |
Complementary argument theorem for F (a:) - |
251 |
|
9-55. |
The residues of F (a:) - |
262 |
|
9-56. |
Determination of the constant c - |
262 |
|
9-6. |
Stirling’s series for log F (a; + |
253 |
|
9-61. |
An important limit - . . . - |
254 |
|
9-66. |
Generalised Gamma function F(a: | co) - |
255 |
|
9-67. |
Some definite integrals |
266 |
|
9-68. |
Multiplication theorem of the Gamma function |
257 |
|
9-7. |
Euler’s integral for F (a;) |
257 |
|
9-72. |
Complementary Gamma function Fi(a;) - |
258 |
|
9-8. |
H3q)ergeometric series and function F {a, b ; c ; x) |
260 |
|
9-82. |
H3q)ergeometrie function when a; = 1 |
261 |
|
9-84. |
The Beta function B{x, y) - |
262 |
|
9-86. |
Definite integral for the hypergeometric function |
264 |
|
9-88. |
Single loop integral for the Beta function |
265 |
|
9-89. |
Double loop integral for the Beta function |
266 |
|
Exasiples IX |
267 |
CHAPTER X
EACTORIAL SERIES
10*0. Associated factorial series . 272
10-02. Convergence of factorial series 273
10-04. Region of convergence 275
10*06. Region of absolute convergence ------ 276
10-07. Abel’s identities 276
10-08. The upper limit of a sequence 277
10-09. Abscissa of convergence. Landau’s Theorem - - - 279
10-091. Majorant inverse factorial series 283
10-1. Series of inverse factorials 284
10-11. Uniform convergence of inverse factorial series - - - 284
10-13. The poles of (rr) 287
10*15. Theorem of unique development 288
10-2. Application of Laplace’s integral ; generating function - » 288
10*22. Order of singularity and the convergence abscissa - - - 292
10-3. The transformation (ar, a: +m) 293
10*32. The transformation {x, xjcxi) 294
10*4. Addition and multiplication of inverse factorial series - - 295
10*42. Differentiation of inverse factorial series - - - - 297
10*43. An asymptotic formula 298
CONTENTS
PAGE
10*44. Integration of inverse factorial series - - 299
10*5. Finite difference and sum of factorial series - 300
10*6. Newton’s factorial series - - - - 302
10*61. Uniform convergence of Newton’s series - - 302
10*63. Null series 304
10*64. Unique development 305
10*65. Expansion in Newton’s series ; reduced series - 306
10*67. Abscissa of convergence of Newton’s series - 309
10*7. Majorant properties 310
10*8. Euler’s transformation of series . - . 311
10*82. Generating function 312
10*83. Laplace’s integral and Newton’s series - - 314
10*85. Expansion of the Psi function in Newton’s series 315
10*9. Application to the hypergeometric function - 316
Examples X 317
CHAPTER XI
THE DIFFERENCE EQUATION OF THE FIRST ORDER
11*0. Genesis of difference equations 322
11*01. The linear difference equation of the first order - - - 324
11*1. The homogeneous linear equation 324
1 1 *2- Solution by means of the Gamma function. Itational coeflicients 327 11*3. Complete linear equation of the first order . . - . 328
11*31. The case of constant coefficients 329
11*32. Application of ascending continued fractions - - - . 330
11*33. Incomplete Gamma functions 331
11*34. Application of Prym’s functions 332
11*4. The exact difference equation of the first order - - - 334
11*41. Multipliers 339
11*42. Multipliers independent of a: 339
11*43. Multipliers independent oi u 340
11*5. Independent variable absent. Haldane’s method - - - 341
11*51. Boole’s iterative method 343
11*6. Solution by differencing. Clairaut’s form . _ . . 344
11*7. Equations homogeneous in w 346
11*8. Riccati’s form 346
11*9. Miscellaneous forms 347
Examples XI 348
XVI
CONTENTS
CHAPTEE XII
GEXEEAL PEOPEETIES OF THE LINEAE BIFFEEENCE EQUATION
PAGE
12*0. The homogeneous linear difference equation - - - - 351
12*01. Existence of solutions 352
12*1. Fundamental system of solutions 353
12*11. Casoratfs Theorem 354
12*12. Heymann’s Theorem 357
12*14. Relations between two fundamental systems - . . . 359
12*16. A criterion for Hnear independence 360
12*2. Symbolic highest common factor 361
12*22. Symbolic lowest common multiple 363
12*24. Reducible equations 366
12*3. Reduction of order wFen a solution is known - - - - 367
12*4. Functional derivates 369
12*5. Multiple solutions of a difference equation - - - . 379
12*6. Multipliers. Adjoint equation 372
12*7. The complete linear equation. Variation of parameters - - 374
12*72. Polynomial coefficients 377
12*8. Solution by means of continued fractions - . . - 373
Examples XII 381
CHAPTER XIII
THE LINEAR DIFFERENCE EQUATION WITH CONSTANT COEFFICIENTS
13*0. Homogeneous equations 3g4
13*02. Boole’s symbolic method 387
13*1. Complete equation 333
13*2. Boole’s operational method 392
13*21. Case I, <j){x) = x'^ . 39^
13*22. Case II, <j:i{x) = - - - . . . , _ _ gqg
13*23. Casein, (^{x) = a^M{x) 393
13*24. The general case
13*25. Broggi’s method for the particular solution - - - - 401
13*26. Solution by undetennined coefficients 493
13*3. Particular solution by contour integrals - - - - - 494
13*32. Laplace’s integral
13*4. Equations reducible to equations with constant coefficients - 408
CONTENTS xvii
PAGE
13*5. Milne-Thomson’s operational method 410
13*51. Operations on unity 411
13*52. Operations on a given function X 412
13*53. Application to linear equations with constant coefficients - 413
13*54. Simultaneous equations 415
13*55. Applications of the method 415
13*6. Simultaneous equations 420
13*7. Sylvester’s non-linear equations 420
13*8. Partial difference equations with constant coefficients - - 423
13*81. Alternative method 425
13*82. Equations resolvable into first order equations - - - 426
13*83. Laplace’s method 427
Examples XIII 429
CHAPTER XIV
THE LINEAR DIFFERENCE EQUATION WITH RATIONAL COEFFICIENTS. OPERATIONAL METHODS
14*0. The operator p 434
14*01. The operator tt 436
14*02. Inverse operations with tt ----- - 437
14*03. The operators tti, pi 439
14*1. Theorem I 439
14*11. Theorem II 440
14*12. Theorem HI 440
14*13. Theorem IV 442
14*14. Theorem V 443
14*2. Formal solution in series 445
14*21. Solution in Newton’s series 448
14*22. Exceptional cases 451
14*3. Asymptotic forms of the solutions 457
14*31. Solutions convergent in a half-plane on the left - - 459
14*4. The complete equation 460
14*5. Monomial difference equations 461
14*6. Binomial equations 465
14*7. Transformation of equations. Theorems VI, VII, VIII - 467
14*71. Equation with linear coefficients 469
14*73. The equa^tion {ax^ -{-hx+c)u{x) +{ejc +f)ii{X’-l) -{■gu{x -2) = 0 472
14*75. The equation {ax^ +hx +c)Au-\- {ex +f)Au+gu‘- 0 474
14*8. Bronwin’s method 475
14*9. Linear partial difference equations - - 475
CONTENTS
PAGE
476
477
xviii
14-91. Laplace’s method for partial equations Examples XIV . - - -
CHAPTER XV
THE LINEAR DIFFERENCE EQUATION WITH RATIONAL COEFFICIENTS. LAPLACE’S TRANSFORMATION
15*0. Laplace’s transformation - - - 478
15*1. Canonical systems of solutions - - - 482
15*2. Factorial series for the canonical solutions 485
15*3. Asymptotic properties - - - . 487
15-31. Casorati’s determinant . , » - 488
15*4. Partial fraction series . . . . 490
15-5. Laplace’s difference equation - - - 491
15-51. Reducible cases 493
15-52. Hypergeometric solutions - - - 494
15-53. Partial fraction series - . . . 495
15-54. Relations between the canonical systems - 496
15-55. The case aj =^2 498
15-6. Equations not of normal form - - - 500
Examples XV 501
CHAPTER XVI
EQUATIONS WHOSE COEFFICIENTS ARE EXPRESSIBLE BY FACTORIAL SERIES
16-0. Theorem IX 504
16-01. Theorem X 505
16-1. First normal form 5O8
16-2. Operational solution of an equation of the first normal form - 509
16-3. Convergence of the formal solution 511
16-4. Example of solution 510
16-5. Second normal form 5I8
16-6. Note on the normal forms - - - . . . - 519
Examples XVI
CHAPTER XVII
THE THEOREMS OP POINCARE AND PERRON
1 / *0. Tlie linear ei^uation witli constant coefficients - 523
17-1. Poincare’s Theorem
CONTENTS
xix
PAGE
17-2. Continued fraction solution of the second order equation - - 532
17-3. Sum equations - 534
17*4. Homogeneous sum equations with constant coefficients.
Theorem I 537
17*5. A second transformation of sum equations . . - . 539
17*6. General solution of sum equations. Theorem II - - - 542
17*7. Dilference equations of Poincare’s type. Perron’s Theorerq - 548
Examples XVII 550
Index 553
INTRODUCTION
Let /(a:) be a given function of the variable x. The Differential Calculus is concerned with the properties of
f{x) - Dm = lim
W-^0 ^
which is still a function of the single variable x. On the other hand the Calculus of Differences is concerned with the properties of
w a)
which is a function of the two variables x and co.
More generally, in contrast with the Infinitesimal Calculus, the Finite Calculus is concerned with the values of a function at a set of isolated points and with such properties as may be derivable there- from.
Suppose then that we are given the numbers/(:r^),/(a^2)?/(%)5 ••• ? and an argument x different from 0:3, ... . Among the subjects of enquiry which naturally present themselves are the following.
(i) The determination of /(a;) from the given functional values. This is the Interpolation problem.
(ii) The determination of
^ a
These are the problems of Numerical Differentiation and Integration.
Extending our enquiries in another direction we are led to con- sider the properties of the functions J[x) defined by the equation
CO
where g{x) is a given function. This constitutes the Summation problem, which is analogous to the problem of integration in the Integral Calculus.
xxii INTKODUCTION
On the theory of summation we are able to found in a satisfactor}^ manner the theory of the Gamma function which plays such an important part in the Calculus of Differences.
Consideration of more general relations between/(a?), /(a? -f co), . . . , /(x-f noj) brings us to the study of difference equations, which are analogous to the differential equations of the Infinitesimal Calculus.
NOTATIONS
The following list, which is intended only for reference, contains the s}Tnbols, operators, and functions which occur most frequently in this book. The numbers refer to the sections where explanations are given.
Symbols
'm\ __ m(m-l) ... {m-7i + l) nJ ~ n!
lim /(a*), the limit of f(x) when X tends to a,
lim sup a;„. Upper limit, 10*08.
n-^x
fix) ~ g{x), 8-22.
==, symbolic equivalence, 2*4:1. R{x), the real part of x, 8*4.
Rn{^), Remainder Terms,
M, 7*11.
|x|, arg X, 8*4.
C7, Arbitrary Periodic Punction, IM.
... Divided Difference, 1*0.
= x(x-o)){x-2(x>) ...{x-moi + oi), 2*11.
~ (r+co)-i(a;H-2co)~h.. (r+mco)~\ 2*11.
n
A Difference Quotient of Zero, 2-53.
Bernoulli's Numbers of order n, 6T.
Euler's Numbers of order n, 6*7.
Bv, Bernoulli's Numbers, 6*5.
Ey, Euler's Numbers, 6-8.
OK), 9*8.
NOTATIONS
Operators
Difference Operator, 2-0.
S, [jlS, Central Difference Oper- ators, 2*01.
Difference Quotient Oper- " ator, 2*1.
D, Differentiation Operator, 2*1.
Partial Difference Quotient, “ 2-105.
V, 2*3.
E“, 2-4,
P~^, Summation Operator, 2-6. p, p„, Eeciprocal Difference, 5-1. T, Reciprocal Derivate, 5-8.
Sum Operator, 8-0.
Tc, p, 14-01, 14-0.
TTi, pp 14-03.
Functions
exp X, Exponential Function. Bernoulli's Polynomial of order n, 6-1.
B^{x\ co). Generalised Bernoulli’s Polynomial, 8-16.
Euler’s Polynomial of order n, 6-7,
By{x), Bernoulli’s Polynomial,
6-5.
E^{x), Euler’s Polynomial, 6-8.
Periodic Bernoulli Func- tion, 7-5.
B(ir, y), Beta Function, 9*84. r(a::). Gamma Function, 9*5. Viix), Complementary Gamma Function, 9-72.
r(x|6)), Generalised Gamma Function, 9-66. co), Psi Function, 9-0. 'F(x), Psi Function, 9-0.
F{x \ co). Sum Function, 8-0. F(a,b;c;x), Hypergeometric Function, 9-8.
Q(a;), Factorial Series Sum Function, 10-1.
CHAPTER I
DIVIDED DIFFERENCES
1-0. Definitions. Consider a function /(a;) whose values are given for the values of the variable x. These latter
values we suppose to be all different.
The divided difference oif[x) for the arguments Xq, x-^ is denoted by and is defined by the relation
1 /(^o) fi^i) _„/(%)“/(^o) _ T
Xi-Xn
Sinularly we define the divided difierence of arguments 2:25 ag by [=<=1^2] =
and so on.
Two divided differences of two arguments having a common argument can be used to define a divided difference of three argu- ments. Thus the divided difference [xqX-^x,^ of the three arguments ^0, x-^, is defined by
[XqX-^x^ = [^0^1] ~ [^1^2] _ [^o%] ~ [^2^1]
^0 ~ ^2 ^0 ““ ^2
Proceeding in this way we can form divided differences of ti+l arguments when we have defined the divided differences of n argu- ments. Thus
\x X r 1 — “* "" ••• ^n]
Jy(\ —
* Other notations are ^"(vi ... x„), d”f{x), x^ x„). It wiU be
proved in 1*3 that divided differences are symmetric functions of their arguments so that the order of symbols within the bracket is immaterial.
[1-0
DIVIDED DIEEERENCES
These results may be exhibited in, a scheme of divided differences as
|
follows : |
||||
|
Xq |
fi^a) |
[XqX^] |
[^0%^2] |
|
|
1 — 1 1 |
||||
|
X2 |
f3) |
1 — 1 1 C9 1 1 |
{x^x^x^ |
|
|
[XjX^^i] |
||||
|
/fe) |
[^3^4] |
1 1 ■«# 4 |
||
|
^4 |
||||
|
• |
1 — 1 |
|||
|
/w |
1-1. Newton’s Interpolation Formula with Differences. Writing % for we have by definition
. . . a:„] = - ^
^ 2 X-Xn 'T.-rr.
X-Xn
X-X,
n-l
Divided
[xxi ... cr„_J = - .
[ afi— B-aJ x-x„_s ‘ x-x„_2
[xx-
^ *•* x-x, X — Xi’
Mm XJ //• _ O* 'T* _
o/ ~ JU'Y Jj
By repeatedly substituting for the second member on the right of each identity its value as given by the succeeding identity, we have
[Zia^ — iCn] [x^Xz — x^-^ x-x^ {x-x„){x-Xn_-^
[XjX^ ... x„_^ [x^
[ax5ia:2...a:„] = -^
{x-x„){x-x„_^{x-x„_^) (x-x„){x-x„_j)...(x-xzj
M) /(^)
(X-X^ ... {X-X2)(x-Xi) '^{X-X^) ... (X-Xj)
M]
or
DIVIDED DIFPEKENCES
f{x) = f (xi) + (a; - Xj) [x^x^ +{x- aj^) (a: - x^) [x^x^x^] +...
+ (a; - aji) {x-x^)...(x- x,_j} [x^x^, . . . a;J + . . .
+ (a; - a^i) (a: - aja) . . . (aj - a;„_i) [x^x^ ■ • • a3„]
+ (a: - aji) {x-x^...{x- x„) [xx^x^ • • • a;„], or
n- 1
(1) f{x) =f{x-i)+'^{x-Xi){x-Xi) ... {x-x,)[x^x^ ... a;,J + .R„(a;),
S-1
(2) wliere jR„ (a;) = (x - Xj) (x - Xg) . . . (x - x„) [xx^Xg . . . x„].
This is Newton’s general interpolation formula with the remainder term i2n(x). The formula is of course a pure identity and is therefore true without any restriction on the form of /(x).
By means of this formula the evaluation of a function /(x) whose value is known for the values x^, Xg, , x^ of the variable is reduced to the problem of evaluating the remainder term (x). Should this term be known or negligible, the required value/(x) can be calculated from Newton’s formula.
It should be observed that no particular rule is laid down for the sequence of the arguments x, Xj, Xg, ... , x^, which need not be in ascending or descending order of magnitude.
If /(x) be a polynomial of degree n-1 in x, then
[KKi] =
/W-/K)
x-x^
is of degree - 2 in x. Hence the operation of taking the divided difference of a polynomial lowers the degree by unity. Conse- quently the divided difference of the (n- l)th order of a polynomial of degree n-1 is constant, and therefore the divided difference of the nth order is zero, that is, [xx^ ... x„] = 0.
In this case i2„(x) = 0, so that the value of f(x) given by the formula
n— 1
(3) f{x)= f{Xj) +'^{x-xj)...{x~x,) . . . x,+^}
is exact.
If/(x) be not a polynomial, we see that
Rn{x) = 0, for X = X^, Xg, ... , Xn,
DIVIDED DIFFERENCES [i-1
SO that the right-hand member of (3) yields the polynomial of degree n~l whose value coincides with the value of /(cc) for
X = Xj, Xo, ... , Xn-
Example. Find approximately the real root of the equation ^3 _ 2y -5 = 0.
Let X = ]f-2y-6.
This relation defines a function y=f(x). We want the value of /(O). Attributing suitable values to we obtain the following ta])le of divided differences.
|
X |
m |
|||
|
- 1-941 |
1-9 |
+ -10627 |
||
|
- 1-000 |
2-0 |
+•09425 |
- -0060 |
+ -0005 |
|
+ 0-061 |
2-1 |
+ -08425 |
-•0044 |
+•0003 |
|
+ 1-248 |
2-2 |
+ -07582 |
- -0034 |
|
|
+ 2-567 |
2-3 |
Thus approximately, using (3) above, w^e have 2/ = 2-0 -t- 1 X *09425 + 1 x *061 x *0044 + 1 x *061 x 1*248 x *0003 = 2*09454.
The corresponding value of x is -0*00013 and the above value of y is in error by about one unit in the last digit.
1 *16. Rollers Theorem. In order to discuss the form of the remainder term in hiewton’s formula we need the following theorem known as Eolle’s theorem.
If the functioyi f{x) be continuous and differentiable in the interval a:^x:^b, where a, h are two roots of the equation f{x) = 0, then the equation f^ {x) = 0 has at least one root interior to the interval (a, b).
Proof If f{x) have the constant value zero, the theorem is evident. If/(a;) be not constantly zero, it will take positive values or negative values. Suppose that f{x) takes positive values. Then
DIVIDED DIFFERENCES
M5]
f{x) being continuous will attain a maximum value M for some point 5 such, that a <^<h. Thus, if h be positive,
M+h)-M)
h
is negative or zero and hence the limit when A-;-0, namely cannot be a positive number, that is,
Similarly, by considering the ratio we prove that
Thus we have /'(5) = 0 and the theorem is proved. In the same way we prove the theorem for the case when f{x) takes negative values.
1 *2. The Remainder Term. From M (2), we have Rni^) =f{x)-Pn-i{x)
n — 1
where Pn-M = ...{x-x,)[x.^x^...x,^^l
so that is a polynomial of degree n-1, and its (w-l)th
derivate is
(1) Ptl^\x)^{n-l)nx,x^...x^].
Hitherto / {x) has been unrestricted. We now suppose that in the interval {a, b) bounded by the greatest and least of x, x^, x^, ...,x„ the function /(i) of the real variable t, and its first n—1 derivates are finite and continuous and that/(")(«) exists.
Then since R„{t) vanishes when t = 3^,x^,..., x„, by Rolle’s theorem it follows that X(t) vanishes at n--l points of (a, b) and therefore by a second application of the theorem that E'n {t) vanishes at n-2 points of {a, h). Proceeding in this way we see that = 0 where 7] is some point of (a, 6).
Thus =
0 DIVIDED DIFFERENCES 1^='^
SO that
(2) [^1^2 ••• ^n] = - rjr ’
wliich is a formula expressing the divided difference of order n-1 in terms of the (w-l)th derivate of f{x) at some point of {a, b). Hence we have
[xXjX^ ...X„] = ,
where ^ is some point of (a, b). We have therefore
(3) B„{x) = {x-Xt){x-x^ ... {x-x„) where ^ is some point of {a, b).
This important result enables ns to find an upper limit to the error committed in omitting the remainder term, provided that we can find an upper limit for the ^th derivate of/(0 in the interval bounded by the greatest and least of x, x^j x^^ ••• >
Exam'ple. Find an approximate value of logio 4*01 from the following table :
••• a-nj — ’
|
X |
logic ^ |
||
|
4-0002 |
0-6020 817 |
+•108431 |
|
|
4-0104 |
-6031 877 |
+ •108116 |
-•0136 |
|
4-0233 |
-6045 824 |
+ -107869 |
- -0130 |
|
4-0294 |
-6052 404 |
The 'divided differences are as shewn. Thus approximately log 4-01 = -6020817 + -0098 x -108431 + -0098 x -0004 x -0136 = -6031444,
which is correct to seven places.
The error due to the remainder term is of order
-0098 X -0004 X -0133 x -4343 x 2 cc3x3!
DIVIDED DIFFERENCES
7
1-2]
where x varies between 4-0002 and 4*0294, which is less than 2 in the 10th decimal place. The above value could therefore be affected only by errors of rounding in the seventh place.
1*3. The Divided Differences are Symmetric Functions of the Arguments. By definition
[1=1,]=®-+/^),
1- XJ Of* ry* <7*
Jj U/j Jj
SO that we obtain without difficulty
\xxx^= I I .
It is now very easily proved by induction that (1) [xx^x^.-.x^]
/W ^ .
' {x-oi>j){x-x^) ... {x-x„) {Xj^-x)(xj^-X2) ... (a%-a;„)
^ fi^n)
{x„-x) {x„ -Xj)...{x„- a!„_i) •
Clearly the interchange of any two of the arguments does not alter the value of the divided difference, which is therefore a symmetric function of its n arguments.
For example [^^1^2! ~
Again [x^x^x^ . . . x„_jX„x„+i] = [x^x^x^ . . . x„.^jXjX„+j] ,
SO that
{x^x^x^...x.^'\-ix^...
^n^w+l]
V^) -
*^1
— [^n^2^3 *•* ~ [^2^3 ***
^n+1
~ [^1^2^3 * • * ^w-l^n+l]
1*31. The divided differences of x" can be obtained as follows : from 1*3 (1),
p^i
[Xj^ . . . x„+j] - (x, - a^) (a;^ -x^) ... (x, - '
DIVIDED DIFFERENCES
[1-31
This last is the coefficient of in the expansion of
t {x, - a^i) . . . {x, - (1 - xj) {x, - x,^^) ...{x,-- x^^^) *
But this expression is evidently the result of putting into partial fractions the function
(1 -- - x<^t)-'^ ... (1 -
and hence the coefficient of is the sum of the homogeneous products of degree n-f of ^25 •** ’ ^p+V Thus [x^x^ . . . J = S Xi' ^
where the summation is extended to all positive integers including zero which satisfy the relation % + a2+ ... ~ n-f.
For the divided differences of - we have
X
1
Hi i^s - a^i) . . • {^S - ^s-l) - ^s+l) • • •
and this is the value when ^ = 0 of
- y t
Hi i^s - ^^l) - ^s) {^S “ ^s+l) • •
which is obtained by putting into partial fractions
-1
i)’
so that
r 1 (-1)^
X^X^ , . . Xpj^-^
1*4. Lagrange's Interpolation Formula.
From 1-3 (1)
we have (1)
where
f(T\ =z fir \ 3:2) (x x^...{x — x^
.rz-vX (X!-Xj){x-Xs)...{x-X„) ,
R„ {x) = {x-Xj){x-x^) ... {x- x„) [xoojX^ . . . a:„]. ''G. Chiystal, Algebra, 2nd edition, (London, 1919), 205.
1-4]
DIVIDED DIFFERENCES
This is Lagrange’s Interpolation Formula with the remainder term Comparing with 1*1 (2) we see that this remainder
term is the same as the remainder term in JSTewton’s Formula. It follows that Lagrange’s Formula has exactly the same range of application as Newton’s and yields identical results. .
The formula may also be written in a slightly different form. Write
(2)
(3) Then
^{x) = {x^x^){x-x>^) ... {x-x^).
/w
t^xX-x, (f)'(x,)
1 *5. Expression of Divided Differences by means of Determi nants. By a well-known theorem in determinants origin- ally due to Vandermonde and generalised by Cauchy, we have
(1)
1 1 1
^3
^1^ ^2^
1
n— 1
= n - «=■)>
j>i
where the product expression has \n{n~\) factors. This import- ant determinant is usually called an alternant.
Now from 1*3 (1),
[XjX^s - = 2
fi^,)
=1 - ^i) (a;^ - {x, - x,+^) ...{x^-x^)
S=1 j i j>i
where YV - x^ means that the value s is not to be ascribed to the suffixes % j. Now
2(-l)"-'/(x.)n'(a:,-x,)
|
/(^) |
/(^2) • |
• fi^n) |
|
1 |
1 |
1 |
|
X2 . |
||
|
/y. n-2 '^2 |
/y ra— S |
as is evident when the determinant is expanded by its top row.
10 DIVIDED DIFPEKENCES [1-5
Hence rearranging the order of the rows and thereby removing the factor ( - we get
(2)
|
li^l) |
/(*«) |
. n~l |
, n— 1 |
n—l n |
|
|
^ n-2 |
^^n-2 |
^ n—2 •^2 |
n—2 n |
||
|
rp n-3 |
^^n-3 |
/yt fl — 3 Xg, |
rf fl— 3 |
||
|
% |
X2 |
||||
|
1 |
1 |
1 |
1 |
1 |
1 |
1-6. Divided Differences expressed by Definite Inte- grals. We shall prove by induction the following formula, which is due to Hermite :
1*1 fii f'„_2
(1) [xjX^ ... a:„] = dii dt^ ...
Jq Jq Jq
where U„ = (1 — ifj) — ^2) ^2 (^n-2 ~~ ^n—i) ^n-l ^n-i^hf
and ^1, ••• ^ ^n-1 3.re to be treated as (n- 1) independent variables,
which of course disappear when the repeated definite integral is evaluated.
Froqf. When w = 2, the right-hand member of (1) becomes
f / '{(1 - ih) % + .
Jo *^2 ”
so that the formula is true when n~ 2. We assume it to be true for n arguments, and proceed to employ a new x^j^i and a further parameter Now
j* 1) ((f ~ ^x) ~b ♦ — 4- (^n-2 ~~ ^w-i) ^n-X + ^n-l^n)
0 ^n~~~ ^n+1
_ ^1+ - ‘ + (^w-2“" ^w~l) ^n-i +
Hence f dt^ f
•Jo -J n
_ [XjX^ ... x„] - [x^x^...
1-6]
DIVIDED DIFFERENCES
11
_ \PA ... - [^^2^3 ... ^n^n+l] ^2)
^1 ^71+1
= ••• >
SO that the result follows by induction from the case n = 2.
1*7. Divided Differences expressed by Contour Inte- grals. Consider a simple closed contour 0 enclosing a simply connected region of the complex variable t in which are situated the points Then by Cauchy’s Eesidue Theorem,* if
/(i) be holomorphic * throughout this region and on the contour C,
Again, the residue — of the function
, /W is
— — ... {t — Zn) (2s~%.) ••• i^s~^s-l){^s~^s+l)
Hence t
(1) Jl- f -/(Q- V'
[^1^2 **• ^n]} ^y (1)5
which is the required expression by a contour integral of the divided difference of order n-1 of f(z}.
We can use this result to obtain another proof of Newton’s general interpolation formula, but with the remainder term now expressed as a contour integral. We have
1 1 Z-Zj^ 1
t-z t-z-^ t-z^t-z^
^ I
t-z t-z^ t-z^t-z'
* See 84 and Whittaker and Watson, Modern Analysis, 4th edition, (Cambridge, 1927), 5-2, 6*1, 5-12. This work will be cited in later footnotes as Modern Analysis.
tThe notation S' means that the factor is excluded from the
denominator for ^ = 1, 2, , n.
12
DIVIDED DIFFERENCES
[1-7
SO that by repeated substitution for
— ^ we set the identity t-z ^
L = i- + — — I- + - J— + . . .
4. J
(i-z{j[t-z^) ..."(t-z^y t-z’
so that .
;^-2: 2’:ziJot~-z^ ^ ^ 27zi J c (t - (t ~ Zq)
fity
{t-Zn){t-z]
that is
(2) f{z) = f{Zi) + (3 - %) [%Z2] + (z - Si) (2-22) [212223] + • • •
+ (2 - Sj) (2 - 22) ... (s - 2„_i) [2i22 . . . Z„] + i?„ (z),
where
(3) R.M = (»-'.) 2^ j„ (r-i,)'®‘V-^j f-.'
which is again IsTewton’s general formula. But it should be observed that, while in 1-1 (2) f{x) is unrestricted, in the present case f{t) is an analytic function holomorphic in a certain simply connected region.
1*8. Divided Differences with Repeated Arguments: the Confluent Case. The identities yrhich define the divided differences in 1-0 become indeterminate if two of the arguments coincide. By 1-2 (2) we have
(1)
(W-I)l
where 7] Kes in the interval bounded by the greatest and least of ccj, a’2, ... , Xn. If all these variables coincide with we take, as the definition of ••• 2*1], the value of the right-hand member, so that for 71 coincident arguments x-^
[x^x,...x^]
(71-1)1 •
(2)
1-8]
DIVIDED DIFFERENCES
13
The limiting value of a divided difference, which arises when two or more of the arguments coincide, may, with propriety, be called a confluent divided difference arising from the confluence of the arguments in question.*
Provided that we write the difference scheme in such a way that all the arguments coincident with a given value occur in a single group, we can form a complete scheme of divided differences by the use of (2) above and the definitions of 1*0 without encountering indeterminate forms. Thus
|
Xi |
M) |
U"(x^) |
||
|
f (*i) |
U'A^i) |
|||
|
x^ |
/(*i) |
|||
|
Z'K) |
[X^X^X^X2] |
|||
|
fi^i) |
[x^x-ip:^ |
|||
|
[^V^z] |
||||
|
A^z) |
[xjxa^ |
|||
|
f'i^z) |
[XjX.2X.^X^] |
|||
|
A^z) |
W’i^z) |
|||
|
f'i^z) |
||||
|
A^z) |
||||
|
[a'^a's] |
||||
|
A^z) |
In this scheme, for example, which is perfectly determinate.
In the case where all the arguments coincide .with
Newton’s formula 1*1 (1) yields Taylor’s expansion, namely,
J{x) + /"(^i)+-
"■‘'cf. Modern Analysis. 10*5.
14
DIVIDED DIFFERENCES
[1-8
R^{X) =
nl
where ? lies in the interval (x, Xj).
It should be noted that confluent divided differences can only be formed if /(a?) possess the necessary derivates.
To obtain a formula for when arguments are equal
to Xj, % arguments are equal to arguments are equal to
Xj,, we use 1*7 (1), which gives the interpretation
= 3^ I =
1 1 1 r f{t)dt
(«1- 1)! (Wg- 1)! "■(«„- 1)! Jc
__ 1 1 1 0»i+W2 + ...-fnp-37 ^
^ ’ ~ K-l)! (Wg-l)! ■■■ K-1)! dxj^i-K..dx^”P-^
If all the n arguments coincide with x^, we have
in agreement with (2) above.
m
it =
(w-l)!
1-9. Interpolation Polynomials. A polynomial of degree ra - 1 at most, whose values at the points a^, ajg, , a;„ are the same as the values of given function/(a;) at these points is called an inter- polation polynomial of /(a:). If I^^{x) denote such a polynomial, we have at once from Lagrange’s interpolation formula 1-4 (3),
(1)
where
In-Ax) = y] -iM. _ y
M x-x, cl>'{x,) ^^x-x,j>'{x,)
4>{x) = (x-Xj)...(x-Xn).
It is clear from this result that the degree of (x) is at most n - 1 .
Only one such poljnomial with given agreement can exist, for if Jn-iix) denote a second polynomial with the same agreement, the polynomial I„-Ax)-J„_Ax}, which is of degree w-1 at most, has n zeros x^, x^,...,Xn and therefore must vanish identically.
To recover the interpolation formula from which (1) wa^ derived we have sunply to add the remainder term
Rn {x) — [X X^ (X-X^) ...(X- X„) [XX^X^ X„].
DIVIDED DIFFERENCES
15
1-9]
Thus we have
/(») +
Since Ifewton’s interpolation formula has the same remainder term as the formula of Lagrange, we have, from 1*1 (1), the alter- native expression
n-l
(2) 1 „_i (a:) = f{x^) + 2 (a: - Xj) {x-x^)...{x- x,) [x^x^ . . . x,+j].
S=1
For example, if n = 3,
h (^) = A^i) + (^-^) [xjx^] + (x-xi)(x- x^ [XjX^x^l
It should be observed that an interpolation polynomial, being fized by the values of the function at the given points, does not depend on the order in which these- points are considered. Thus if we take the four points x_j^, Xg, x^, x^ in turn in the orders
^o> ®-a> ^2 a.nd x^, Xg, x^, x_^
we have the two expressions
hip) =J{^q) + (35 - aJo) [a:oail+ {x - Xg) {x - x^ [a:oa;ia:-i]
+ {x- Xg) (x -X^){x- a:_i) [x^x_.^X2l
h (^) = /K) + (» - IPi^olt + (a: - »i) {x - Xg) [x^XgX^]
+ (x-x^){x- Xg) (x - Xz) J.
Adding these expressions and dividing by 2, we have
(3) I a {x) = i {/ (a^o) +/(ai) } + (a? - Jxj - ^Xj) \Xfp{\
+ {x — Xg) (x — Xj) { ix^jXgfXjJ + [Xga^Xg] }
•+ (x - Xg) (x - Xi) (x - ^x_i - Jxa) [x_iXoXiX2] ,
which employs the divided differences shown in the scheme
x_i
^0
[XoXj]
Xz
fi^o)
fi^)
[x_iXoXj
[XoXiXa]
[x_iXoXiX2]
16 DIVIDED DIFFERENCES [1-0
From I^ix) we could obtain an interpolation formula by adding the remainder term
Ri {x) = (x- a:_i) (a: - Xg) (x -x{){x- x^) [xx_jX^jX^].
Again by taking five points x_^, x_^, Xq, Xj^, x^ in each of the orders Xq, x^^, x^, x^^, and x^, x^, x_i, Xj, x_2 we obtain two expressions for I^ix) whose arithmetic mean gives
(4) h(x:)= fi^o) + (a: - a^o) H [a^-ia^o] + [a^o%] }
+ {x — sIq) {x —
+ (® - a;_i) {x - Xo) {x-xj}i{ [a:_2a:_ia:oa=i] + [a5-ia:oa:ia;2] }
+ {x- X_i) {x - Xo) {x - Xi) (x - |-X_2 - Jxj) [x_2X_iXoXiX2] , which employs the divided differences in the scheme
|
a;_2 |
||
|
a:-i |
• |
|
|
1 — 1 0 V |
||
|
a^o /(a=o) |
||
|
[XflXi] |
1 1 0 |
|
|
Xj |
||
|
X2 |
||
|
From I^^ix) we |
could obtain an interpolation formula by adding |
X'JLUULL A 4.
Bs(x).
The above results, (3) and (4), are also due to Newton. They can easily be extended to include divided differences of any order, the form (3) being taken if n be even and the form (4) if n be odd.
Eeturning to (2), if two or more of the arguments coincide we obtain a confluent interpolation polynomial. Thus if ^ = 4, with the arguments x-^, ^2, x^, we obtain
h{^)=f (%) + {x-Xj) [XiXj + (x - Xj)^ [XjP^X^]
+ (x — Xj)^ (x — X2) [Xj^X2X2X3]
=/(ah) + (a: - a^) /' (x^) + (x - x^)®
+ (x — Xj^)2 (x - Xg) [XjXjXg] ,
i.9] DIVIDED DIFFEBENCES 17
SO thatj in this case,
Iq{Xj) 1 2, =/
It is easily seen, in the same way, that if v arguments coincide with then
(5) f"’’ {x^) = (Ki), s = 0, 1 , . . . , V - 1,
and the polynomial may be said to have agreement of order v with the function f[x) at the point x-^. In this way we can construct polynomials having arbitrarily assigned orders of agreement with the function at given points. Thus the confluent interpolation polynomial of degree 4, which has agreement of order 3 at and of order 2 at is
^4 (®) = fi^i) + (2: - aji) [xjxj + (x- Xj}^ [aJiaJA]
-h(x- X^f [^iX2XiX2] + (x- (x - X2)
= /(%) + i^- ^1) fi^i) + 2^
1 92 19®
+ i^- ^1)^ m 9“2 [^1^2] +{^- ^1? - 3^2) 2 1 ^2-9^
That this polynomial has agreement of order 3 at is obvious. That the agreement is of order 2 at Xg is equally obvious if we observe that the polynomial could have been written down in an alternative form with the arguments taken in the order X2X2XjX^Xi .
EXAMPLES I
1. Shew that the divided differences of f{,x)-{-<f){x) are the sums of the corresponding divided differences off(x) and of (j>{x).
2. Shew that the divided differences of cf{x) where c is a constant are c times the corresponding divided differences otf{x),
3. If the arguments be each multiplied by the same constant c, while the tabular values remain unchanged, shew that the divided difference [x^X2 ... x^^^J is multiplied by c~”.
4. Shew that the divided differences of f{x) are unaltered if the arguments be each increased by the same constant c, while the corresponding tabular values are left unchanged.
jg DIVIDED DIFFEBENCES [ex, ]
5. Form the divided differences of the polynomial
+ ... +a„.
6. Prove that
. . . 2^«] = I . . • + ^2^2 + • • • + ^n^n) • dt^ ,
where the integration is extended to all positive values, including zero, which satisfy i5i + ^2+ ... = 1. [Genocchi.]
7. With the notation of 1*8 (3) shew that
where
[x^x^.,.x^x^~\- f dk r dk... [
Jq Jq Jq
2/ — (1 — ij) a^+ ig) ^2 + . . . + (fj,_2 ip-i) >
, .. (1 - «ir~' ih - hr~' - fe-2 - cv '
K-l)!(n2-l)!...K-l)!
8. If
L M = (g - a;i) (a - jgg) . . ■ (a; - a;,_i) (x - x,+^) ...(x-x„)
{^r~ ^l) {^r - ajg) - {^r “ " ^^r+l) • • • i^r “ ^n) ’
r = 1, 2, ... , n,
prove that
L^(x)-\-L2{x) + ...+Ln{x) = 1,
ixi-xYL^{x) + (x^-xyLs{x) + ... + (x„-xyL„(x) = 0,
V = 1, 2, 3, ... , n-1.
9. Prove that the function
t-g {t-a){t-b) a-b {a-b){a-c)
becomes unity when t = a, and zero when t = b, c, .
Hence with the notation of example 8, prove that
x^-x^ ix^-x^){x^-xs) (a:i-x„)’
witli similar expressions for L^ix), Lg{x), ....
10. Deduce Lagrange’s form of the interpolation polynomial from tke rule for resolving
fM
(x-a^)(a;-a;2)...(x-x„)
into partial fractions.
DIVIDED DIFFERENCES
19
EX. 1]
11. Find the polynomial of the lowest possible degree which assumes the values 3, 12, 15, - 21 when x has the values 3, 2, 1, - 1 respectively.
12. Three observations u^, of a quantity are taken near
a maximum or minimum. Shew that the value of x at the maximum or minimum is approximately
(62 - c2) Ua + (c^ - a^) Ui, + (a^ - b^) 2{{b-~c)Ua-\-{c-a)Uf,-{-(a-b)Uc} ‘
13. The values of a function at m + n points are given. Prove
that a rational function, whose numerator is of degree m-l and whose denominator is of degree n, may be found, which assumes the m + n given values at the given points. [Cauchy.]
14. If m = 2, ^ = 1, prove that the rational function of example 13, which assumes the values u^, at the points a, 6, c, is
~ UjUc (6 -c){x-a)- u^Ug (c -a){x-b}- UgU^ {a-b){x-~ c)
Ua (6 -c){x-a) + (c - a) (a: - 6) + {a -h){x-c)
15. If the function
(a;) = ^ 0 + cos x + sin cc) + . . . + (^ „ cos nx + sin nx) assume the values Wg, , W2n+i when x = x^, Xg, ... , a?2n+i5 prove that
^ sin i(x- x^) sin ^(x-x^)... sin jjx- ^
^ S = ] sin J (x, - a;i) sin ^ (x, - Xg) ... sin (a;, - ® ’
the factor which becomes indeterminate when x = Xg being omitted in each term of the sum. [Gauss.]
16. By means of 1*5 (2) express the confluent divided difference [aabc\ in the form
m f{a) m f{c) 3a2 6^
2a 62 ^2 a2 2a
d 1 b c ’ a \ b 0
10 11 10 11
17. Express the confluent divided difference [aaa66c] as the quotient of two six row determinants.
18. From the confluence of the n arguments in 1*5 (2) deduce the formula 1*8 (2).
CHAPTEK II
DIFFERENCE OPERATORS
2‘0. Difference Notation. Let J a; be an increment of the variable x. The corresponding increment of a function* u{x) is then given by
J u{x) = u{x+^ x)-u{x).
This increment ^u{x) is called the jSrsi difference of u{x) with respect to the increment /\x. The most important case arises when the increment J a; is constant. Denoting this constant by w we have for the first difference of m(x)
(1) m(x) = w(x+o))-u(x).
The result of performing the operation denoted by the operator J is still a function of x on which the operation may be repeated. We thus obtain the second difference
/^u{x) = /i[/iu{x)] = ['i4(x+2cd)-w(x+co)]-[w(x+c!)) — w(x)]
(2) J^'ii{x) = «(x-f2a))-2M(x+a))+w(x).
Proceeding in this way we can form the third, fourth, nth differences, namely,
A^u{x), #m(x),..., by means of the relation
A'uix)=A[A^-'^u{x)].
We find, for example, that
A ^ = +
zj^a;3 = 6x0)2 +60)3, z13x3 = 6o)3,
A^x^ = 0.
*\]e shall denote a function of a: by u(z) or by according to convenience.
20
2-0] DIFFEKENCE OPERATORS 21
The successive differences of a tabulated function are easily formed by simple subtraction. Thus for the function we have
|
X |
A |
A^ |
A^ A* |
|
|
0 |
0 |
1 |
||
|
1 |
1 |
7 |
6 |
6 |
|
2 |
8 |
12 |
0 |
|
|
19 |
6 |
|||
|
3 |
27 |
18 |
0 |
|
|
37 |
6 |
|||
|
4 |
64 |
61 |
24 |
|
|
125 |
||||
|
More generally, if we denote the functional value + by |
||||
|
we have the scheme |
||||
|
Argument |
Function |
|||
|
3 I |
W_2 |
A “-2 |
||
|
a - 0) |
U_i |
zJw-i |
||
|
a |
Uq |
A^u-i |
Zl*^-2 |
|
|
A ^0 |
||||
|
(X -f* G> |
tq |
Zl" Wp |
||
|
zl% |
Zl^Wo |
|||
|
^2 |
A ^2 |
A^^i |
||
|
G H“ 3g) |
||||
|
where each entry in a |
vertical difference colunin is obtained by |
subtracting the upper entry immediately to the left from the lower entry immediately to the left.
By adjoining further functional values we can extend the scheme as far as desired. Inspection of the scheme shews that to form a fifth difference six consecutive tabular entries are required. Simi- larly, to form a difference of the ^'ith order, n + 1 consecutive
DIFPEBENCB OPERATOBS
[2-0
tabular entries are necessary. In the above scheme the differences ■which lie on a line sloping diagonally downwards from Mq, are called descending, or forward, differences of Ug. The differences /j u_^, ••• , which he on a line sloping
diagonally upwards from Ug are called ascending, or backward, differences of Ug.
2*01. Central Difference Notation. If we introduce the operator S defined by
the difference scheme of the last section becomes
|
3 1 |
U^9 |
|
|
a-co |
Su_^ |
|
|
Su^ |
||
|
CJ + O) |
% |
Su.2 |
|
^2 |
Sus |
|
|
a+3co |
Bhig
S%o
ss
The operator * S is the central difference operator and the differ- ences in the above table are known as central differences. It should be carefully observed that the numbers in the above difference scheme are the same as the numbers in the corresponding positions in the scheme of 2-0. The two schemes differ only in the notations. It will be seen that Bu^ = v^-Ug, = and so on.
The differences in the same horizontal line with are labelled ■with the s'ufiix h. Those on the horizontal line between Mj, and Wi+i are labelled with the sufiSx A+J. The notation of central differences is useful for the compact description of certain inter- polation and other formulae. The arithmetic mean of successive
* This notation is due to 'VV. F. Sheppard, Proc. Land. Math. Soc. 31 (1899),
DIFFERENCE OPERATORS
23
2-01]
differences in the same vertical column is denoted by and is labelled with the arithmetic mean of the suffixes of the entries from which this expression arises.
Thus
|(8X+SX) ==
When these are entered in the difference table the lines a, a + o, and the line between, will have the following appearance.
|
Mfl |
S%o |
sx |
||
|
Swi |
||||
where denotes +
Another notation, originally due to Gauss, for central differences is (m, n) where m denotes the row, and n the order, thus
§2^0 = (O3 % = (i 5)-
2’1. Difference Quotients. The notations of differences ex- plained in the preceding sections, while of the greatest practical utility, do not sufficiently unmask the close analogy between the finite and the infinitesimal calculus. We now introduce Norlund’s operator A? which is defined by the relation
(1)
We call which is evidently a divided difference, t]xe first
it)
difference quotient of u{x). This symbol has the advantage that (2) lim A^(^) = Du{x),
(O — >-0 0)
where D denotes the operator of differentiation, in this case djdx. The operation can be repeated, thus
, ^u{x + o)}- /^u{x)
Ku{x) = A[Au{x)] = ^
(t) it) (t) CJ
u{x-{-2(ii)-%u{x + ui) + u{x}
(3)
24
DIFFEBENCE OPERATOBS
[2*1
and generally for the ?^tli difference quotient
n
A «(;»)= A A •
a> w L_ 0) —
From this we infer the useful relation
n n + l n
AM(a; + Co) = 6) A w(a!)+ A
CO <ti a>
We have also
n
(4) lim Aw(a:) = D"M(a:).
CO“->0 CO
From the definitions it is clear that the operators /J and are related by the formula
(5)
CO
and in the special case where ca = 1 the two operators have precisely the same meaning.
If 6) = 1, we shall write A instead of A*
1
2*105. Partial Difference Quotients. Consider/(a;, w) where X and u are regarded as independent variables. Let x be given the increment o>, and u the increment A. We then define ‘partial differ- ence quotients with respect to x and u by
Axj{^3 w) = [/(aj+co, u)-f[x, u)]j CO,
An fix, u) = [f(x, u + h) -fix, U)] I h.
The difference of f{x, u) is defined by Af{:x, u) =/(a;+co, u-\-h)-f{x, u)
—fix+o}, ^ + u + h)+f{x, u + h) -fix, u)
=f{x+o), u+Ji)^fix-\ro>, w)+/(a;+co, u) -f{x, u). Thus we have the two equivalent relations 0-) Af{x,u)=:c^ Ax fix, + h Aufix, u),
w h
(2) AM ^) = CO Affix, U) + hAuf{x + 0,, u).
2-105]
DIFFERENCE OPERATORS
25
Again
Aa/(a^> “) = [A«/(a:+«> w)- A«/(a:, «)]/«
= [/(a:+<d, m + A) -/(a;+6),M) -f{x,u+'h)-{-f{x, u)] /
The symmetry of this result ia h and to shews that
(3) Ax Auf{x, u) = A« Ax/(aJ> «)•
u) h h ui
2*11. The Difference Quotients of Factorial Expres- sions. Products of the forms
(1) u(x) . u{x-Ci)) . ^^(a;~2ca) ... w(^^-mco4-co),
(2) w(a? + 6)) . 'i^(a;+2a>) . ^(a; + 3co) ... u{xi-m(x))y
where mis a positive integer, are called expressions, the first being a descending factorial, the second an ascending factorial ex- pression.
Of expressions of these t3rpes the two simplest and also the two most important are
(3) = rr(ir-co)(a;-2co) ... (ic-mo-f co),
(4) = (a;-f-(o)-i(cr+2o))-i(a; + 3co)-i ... +
If m = 0 we interpret each of these expressions as unity, that is
and if 6) 0, we have also
lim = x^,
(u — )- 0
lim ~ x~'^.
To form the diiSference quotients of we have
_ (a; + co-a;+mo>-co) x{x~<x) ... (a: - ?nco + 2co),
Hence, if n^m,
n
_ m(m-l) ... (m-w+1)
26 DIFFERENCE OPERATORS [2.11
which can also be written, after dividing by m !, in the form
(5)
A-
7?i! (m-n)!'
If 71 = m, we Iiave
n:<m.
m ^(ma>)
while if n>m the result is zero. If 0) = 1, we have
7n! m!
=(*)
\m/
in the usual notation for Binomial coeflicients, so that (5) yields the important formula
(6)
A ^
^ Vm/ \m ~ nJ
n^m.
Again from (5), if m ^0, we have by 2*1 (4)
m! (7n-7i)\‘
These results shew the analogy between in the finite calculus and in the infinitesimal calculus.
For the difference quotients of we have
a;+6)-a;-ma)-co
a, (^+o))(a;-f 2co) ... (a;+m<o + co) ’
j^X^~ = — 77lX^ ~m(o- to))^
ti)
so that
n
(^) Ak (“‘^■“1) ... (“-971 — ~
which can be written
n
w ^
When 6) O5 we have
D^{m-l)lx~‘^ = (- + 1)!
DIFFERENCE OPERATORS
27
2-11]
For more general forms of the types (1) and (2), we easily obtain
CO /\ • • • 'li/g -moi+bi
Oi
“ ^X+bi ~~ "^X - wto+w) '^X '^X - <0 • • • '^X ~ J»a)+2a>
1 ^x-i-b) '^x-hmcit+co
oi ^x-{-b>^x-\-Zb3 •*• ^ic+7Ww ^x~h(o^x-j-2(t} •*•
In particular for Ua, = ax + by we can write
(8) Ux'^x—bi *•• '^x-'m(o+o> ~ (ci2/ + 6)
(9) : (aa;+ 6)
^a:+oii'^a;H-2to • •• '^x+moi
and we have
(10) A
(11) +
2*12. Expansion of a Polynomial in Factorials. Let <l> (x) be a given polynomial of degree m. Assume that
2j(to) aj(2w) 2j(rrta>)
(1) ^(x)^ao+«i-Yr+®2'2r + - + ®™ 1^’
which is evidently a legitimate assumption since the right-hand member is a pol3aiomial of degree m with m+ 1 arbitrary coefficients. Forming the successive difference quotients, we have by 2*11 (5),
aj(Wa»~aj)
Afi^) = % + (m~ ij! '
= 02+^3 -Yr + - + °”» (m-2)!'’
m
l^4>{x) =a^.
(j3
If in these results we put x — 0, we have expressions for the coefficients in the form
A<i>{% 5 = 0, 1, 2, ... , m.
bi
28
DIFFERENCE! OPERATORS
[2-12
Thus
/y.(w) 3j(2to) 2
(2) ^(a:) = ^i(0) + -Ty A'^(0)+-9rA^i(0)+-” +
i- • tu ^ ‘ (O
Q^iniui) m
ml
, A^6(0).
The coefficients in this expansion can be obtained by writing down the values of <f>(x] for a: =: 0, w, 2w, , mco and then forming the
successive difference quotients. Thus for
<j)(x) = + + to®,
we have
|
X |
<f>{x) |
/^<j>{x) |
A4>{^) |
|
0 |
£0® |
||
|
46)3 |
|||
|
0) |
5co* |
10o)2 |
6co |
|
2a> |
15u)S |
226)3 |
12ca |
|
3co |
376)3 |
so that
3
A<f>(^)
6
3cii^ x+co^ = a>^ + 4co^x^"^ + 3ca +
Another method follows from observing that the coefficients
ttQ, ... , are the successive remainders when we divide cl>{x)
by X, the quotient of this division by (x-co), the new quotient by (x-2a>), and so on.
Thus with ^(x) = x^ + 3a>^x4-co^ we have
X j X^-r3co^X + CO’^
X - oj X- + 3co^ remainder co^
X - 2co X + o) remainder 4a)^
remainder So)
which gives the same expression for (f>{x) as that obtained by the first method.
2-13. The Successive Difference Quotients of a Poly- nomial. To obtain the successive difference quotients we can express the polynomial in factorials by the method of the preceding
2-13]
DIFFERENCE OPERATORS
29
paragraph and then apply 2' 11 (5). Since each application of the operator A a polynomial lowers the degree by unity we have the
following important theorem :
The mth difference quotients, and also the mth differences, of a 'poly- nomial of degree m are constant. The differences of order higher than the mth are zero.
Thus with the polynomial
we have
/S.(f>{x) = 60)33^*“) + 4oa^ = -h 3cox + 4co^5
2
(ti
= 6,
CO
A<i>{x) = 0.
G — (1 “i"
we have
(2) A(l + M" = ^”(l + &co)"
Since
X
lim {l + 6o>)" =
co-»0
we have as a limiting case of (2)
X
Thus in the finite calculus (l+co)^^ plays the part of e*.
DIFFEKENCE OPEKATORS
30
2*2. Properties of the Operator A-
[2-2
From the definition
it is evident that ^ obeys the following three laws :
(i) The distributive law
(ii) The index law
mrn ~| w+w n r m “■
A - A «(:») = A Aw(a:) ,
— * <i) 10^0) —
where m and n are positive integers.
(iii) The commutative law with regard to constants l^cu{x) = c l^u{x),
(t) 0)
where c is independent of z. This result is also true if c be replaced where &{x) is a periodic function of x with period co ; for
(oA®(a:)w(a:) = m[x+oi)u{x+a)- ■b3{x)u{x)
(1)
= m{x)u(x-ho^)-rn{x)u{x)
= o^VLf(x) J\u{x).
to
If then ^(X) = + be a polynomial in X whose
coeflhcients are independent of z, we can associate with an operator ^i(A)j such that
to
= aoAu{x) + a^”^ u{x) + ...+a„u{x).
^ to (jj
If (l>2{k) = + be a second polynomial, and if
we expand their product in the form
(h) <l>2 W = ^ ^
we have, on account of the above laws,
<k{A)<f>2{A)u{x) = 42{A)MA)u(z)
m+n «if n - 1
= CoA^(aj) + Ci A +
DIFFERENCE OPERATORS
31
2-2]
We may also note that the above results are still true if the coefficients of the poljmomials be replaced by periodic functions of X with period co.
2*3. The Operator V- The definition of this operator is given
CO
by
S] u{x) = -J [u{x)^u{x-\-(^)],
CO
which may be compared with the definition of the central difference averaging operator [x of 2-01.
Repeating the operation, we have 2
y u{x) = I [u{x) + 2u{x+(^)-{-u{x-\-2c^)] ,
CO
and generally, as is easily proved by induction,
Y»w = r,
+...
As an example,
u{x) + (^^'ju{x+(j:)) + {2) +
+ (^)w(a:+«w)]-
ya® = |a®(a"4-l),
Va* = ^a^(a“+1)"-
2*4. The Operator E". This operator is defined by the relation
(1) = u{x + o>).
The operation may be repeated any number of times. Thus
The operator E“ clearly obeys the same laws of combination as A-
60
In particular, if <f>2Q^) be the poljmomials of section 2*2
above, we have
^i(El9^2(E“)^(^) = <I>2{E-)ME^Mx)
= CoE U (x) + u{x}+... + c„+„u(x)
= CQu{xi- m(x> fuo) + CjU{x+mo) + no> - o^) + ... +c„j+„w(a;).
32
DIFFERENCE OPERATORS
[2’41
2-41. Herschel’s Theorem. If f(X) be a 'polynomial 'with constant coefficients and if ~ then
He-*) = Hi)+tHE“)o+^^,HE-)o^+... ,
or symbolically
cl>{e-^)^<f>{E^)e^-K
The sign = is used to denote symbolic equivalence.
We have (^(e“*) = and it is therefore sufficient to prove
the theorem for <f>{e-t) = e«“<, for the result will then follow by addition of constant multiples of terms of this type. Now
gix+nu,)t _ l+i;(a:+wco) + ~(a: + Moi)2+...
= l + iE"“a: + 5^ E"“a:N-... .
Putting cc = 0, we have
f2
gn^t _ l + iE«"0 + |^ E""0’*+... which proves the theorem.
2-42. From the definition of E“, we have
E"“ a® = = a* . a”".
Thus if <f,{X) = be a polynomial in X, we have
^(E“)a®= = a^f{a'“).
More generally, if the power series
9^(X) =
w=0
be convergent for X = a", we have
9^(E“) a® = o®^(a").
2-43. Theorem If f(X) ig a polynomial ■whose coefficients are independent of x, then
<i>{E'‘)a==u{x) = a=‘<j>{a''‘E“)u{x).
9^(E")w(a;) = a“,J(a“E“)a-®w(a;).
Let 9S(X) = SM„X”.
2-43]
DIFFERENCE OPERATORS
33
Then
u{x) = 0'^u{x)
~ w(a3 + noo)
= a^^(a‘“E‘^)^(3?),
which proves (1), and (2) follows by replacing u{x) by a'~^u{x).
2 ‘5. The Relations between E" D. We have from the definitions
E“«(a:) = M(a;+co) = M(a:) + 6)
Thus
E“ = l+e)A,
coA=E”-r.
As deductions from these relations, we have Gregory's Theorem, namely,
(1) u{x^n(j^) = = (1 + 0)
ui
= u{x) + (^o^ ^u{x) + (^(^^ l^u{x) + ...
+ l^u{x) ,
n being a positive integer. This formula expresses u{xi-no^) in terms of u (x) and its successive differences.
Again, we have
(2) o^^^u{x) = (E'^-^^uix)
(U
= u{x+no^)-'(^u{x-j-n-lo^) + (^u{x + n-2c^)-
which expresses the nth difference in terms of functional values.
Again, assuming that u{x-\~<h) can be expanded by Taylor’s Theorem, we have
z= 'u(cc+6)) = ^^(^r) + coD w(a5) + ^D2t^(ii?)+ ... ize^^u{x).
34 DIFFERENCE OPERATORS
Thus we have the relations of operational equivalence
l+0!)A = e"^,
so that
n
A “ («) = (e"-® - 1)« M (x).
2»51. The Analogue of Leibniz’ Theorem. The theorem of Leibniz in the differential calculus, namely,
D^{m) = (D«m) v+(^{B^--i-u)Bv+Q{D^-Zu)I^v+ ... ,
where D denotes the operation of differentiation, has an analogue in the finite calculus, which we proceed to obtain. We have
(1)
= {(EEi)“-1}m«u*,
where the operator E acts upon m* alone and the operator E, acts upon alone. Thus we have
(1) «"A = {{E Ei)“ - 1}» .
In the ezpressions of E and Ei let us suppose that A acts on u* alone, while Ai acts on u* alone, so that
E" = 1 + coA, Ei“ = 1 + 0)Ai.
Then we have
(EEi) ^ ).
Thus " « u.
A(M,«.) = fA+E“Aa)»M
" « «
2-51] DIFFERENCE OPERATORS 35
Bemembering that A and E operate only on we may drop the
to
suffix and write
(2) A {Ux%) = (a %) + ( i) ( A «*+„) A %
which is the required theorem. Since
s
lim
w <*»
we see that Leibniz’ theorem may be regarded as a limiting case of this result.
The theorem may be expressed in other forms. If in (1) we expand the right-hand member directly, we have
(^) ^aj+nar^a;+n(«> ^ ^aj+{n— l)w^aj+(n--l)a»
which is in fact a case of 2*5 (2).
If the expansion be required in difference quotients of Ug. and we write
(EEi)”*-! =w A+wAi+“® AAi,
<lt Ui
so that
= (A+Ai+“ AAi)”K^’x)-
(il w a> ut w
The expansion of the right-hand member gives the required result, but it is hardly worth while to write down the general expansion.
2‘52. The Difference Quotients of a’' v^. By 2*14: we have
A = ^aj+sw
h =
where
36 DIFFERENCE OPERATORS [2.5
If then in (2) of 2-51 we put = a* we obtain
= «*[— ^+“"Aj ‘»z‘
Thus if <j>[l) be a polynomial, we have the operational theorem
94(A) a^i'x = a* 94 (a"A+ u, .
<0
If next we put a“ = 1 + aco, we obtain
K X
^ [A] (1 + «<o)“ V* = (1 + aw)“ 94 [( 1 + aco) A + a]
If we now let w 0, we obtain the corresponding theorem for the operator!), namely
94 (D) = e«’^94(D + a) v
2-53. The Difference Quotients of Zero. The value of A
when a: = 0 is written A O'" and is called a difference quotient of zero. Clearly
(^) AO”* = 0 if ?i >m, A0” = n!.
If in 2-51 (2) we put = x^-^, = x, we have
A»” = a:Aa;'"-i + w"A\a;+co)'"-i
w
= X ^ ^ [w ^ _j_ A ^771-11
Putting a; = 0, we have the recurrence relation
/0\ ^ ^ W — 1
i-7 ^0^“^ + n j\
which in conjunction with (1) enables these numbers successively. Thus
to be calculated
AO = 1,
AO^ = &jA0=co,
2-53] DIFFERENCE OPERATORS 37
A0^ = 2!,
A0» = coA0“ = 0)3,
u) a>
A03 = 2a)A0H2A02 = Ga),
A03 = 3!,
and so on. Expressions for these numbers will be obtained in Chapter VI in terms of Bernoulli's numbers.
2*54. Expression of Difference Quotients in terms of Derivates. By Herschel’s Theorem, 241, we have
{e-t- 1)« = f(E“-l)«0+^ (E“-1)”03 + ... .
Since E"-l=r^AjWe obtain
C^-n(e„e_l)n ^^o+,f,A02+... ,
where
AO» = [Aajlr=o,
which is equal to zero if s < w, and to w ! if s = w.
Thus
/n+1 n /n+2 n
CO-"(e“‘-l)’‘ = «" + /-rXTr. A0”+l + 7r-FAT,A0'‘+3+... .
Now from 2-5 we have
A = «-”(e“-0-l)'\
Thus
A0”+^
A0«+3
[See also 7*05.]
2'6. The Summation Operator P“i. If oj be a positive integer variable, capable of taking the values 0, 1, 2, 3, ..., we write
x-l
P (^) ~ ^x~X ”!■ '^a;-2 '^x-Z ~b • • • + *^^0 = ^ ,
(1)
38
DIPFEREN'CE OPERATORS
[2-6
where the notation p-^ is introduced for formal reasons f and indicates the inverse nature of the operation. Indeed it follows at once, if Uf be independent of x, that
APw P(all)M« - P^Uf
= ('U^ + Uig-i+ ... + Uq) ~ ('*^*-1 + Wa,_2 + ... + Mo)
so that the operator A neutralises the operator p-i, which is in this sense an operation inverse to A- With the above notation we have for example, ’
Pt.n-m+D'^t+m = “« + %-!+••• + Pn + 1 - P('^Wj. When there is no risk of ambiguity we may conveniently write P~^ w* = u^i + m*_2 + . . . + Mp.
These notations may be compared with
rx
u^dt and u^dx.
Jo Jo
We have at once from (1),
P(n«« = Mo. P(oN« = 0.
If, by affixing an asterisk, we now define a function u* bv the properties ^
if 27 ^ 0, = 0 if a? <; 0,
we have
= (E-^+ E"H ... + E"^~H ...)«*
The operation can be repeated any number of times, thus
Pw «*= Pw [(E = (E
= ^x-z+2u^s + 3u^_^+... + (x-1)uo, and this result is seen to be in agreement with (1) and (3).
r L. M. Milae-Thoiason, Proa. Oarrd>. PUl. Soc., xxvii (1931), 26-36.
2-6]
DIFFERENCE OPERATORS
39
More generally we have
P(x^ = (E “ 1)“^ 2 + •••
(6) = P(;l:„+1)
which expresses n successive operations with P”^ in terms of a single operation. Also, if he independent of x, we have
(7) APf.r = APw [P(7)”+' = P(7r''
2*61. Theorem. JJ f{^) be a function of the positive integral variable x such that A /(^) = '^x ? 6e independent of x, then
L Jq
We have
A {P w -/{*)} = M* - «x = 0.
Hence
Pw = constant = -/(O) ,
since P(0)^ = 0. This is the required theorem.
2*62. The following table exhibits the relations between the sums and the functional values Uq, u^, ... .
|
P-^Ml |
A Mo |
0 |
||||
|
p-^Wj |
Ml |
A Mo |
3 |
|||
|
P"®«3 |
P~^M2 |
A Ml |
2 |
A Mo |
||
|
P-^MJ |
AMi |
|||||
|
P“®W4 |
P-^«3 |
A M2 |
2 |
a A Ml |
||
|
p-^u^ |
Ms |
A M2 |
3 |
|||
|
P-^MJ |
P-^M4 |
A Ms |
2 |
A Ms |
||
|
p-^u. |
M4 |
A % |
||||
|
P-®«6 |
p-^Wg |
P-^% |
Ms |
AM4 |
||
|
P-^«6 |
40
DIFFERENCE OPERATORS
[2-62
Each sum is formed by adding the members of the column on the right, beginning with the member immediately above the required sum. Thus
We note also that each column can be formed by differencing the column immediately to the left. It will also be noticed that if we change the origin, that is, label another entry with the sujSEix 0, the resulting sum table will have each of its members altered in value while the differences will be unaffected. Lastly, we note that all entries labelled with the same suffix lie on a diagonal line.
Obviously in analogy with central differences we could also form central sums ’’ by a mere change of notation.
2*63. Moments. Given a set of x tabular values, say,
Uq, U2, ^x-l}
their nth moment * about the point a; - 1 is defined by
sc-l
(1) M„=J^{t-x+l)”Ut= p^-l{t-x + l)'^u,.
If we express (x-t-l)”’ in factorials by tbe method of 2-12 we obtain
^=() \ b /
where
(2) c» = A0",
a difference of zero (see 2*53). ' Thus
x-l n
i=0 8=0 n x-~s-l
Sv-A X—t—1
Zj
8=0 t=0
Since \ vanishes when t ^ x — s —1.
* See for example W. Palin Elderton, Frequency Curves ayid Correlation^ (London, 1927), chap. iii.
2-63]
DIFFEREN*CE OPERATORS
41
Hence from 2*6 (6) we have
(3) ( - 1)”M„ = ^ C, Ui='^c, p-»-i .
s~Q fi==0
Using the differences of zero given in 2-53 and noting that Cq = 0, we have
My= - P-^M^,
M^= p-^u^+2p-^u^,
M^= -p-^u,-Qp-^u,-Qp-^u,,
and so on. The terms P~‘u^ (which are also called factorial moments) can be obtained directly from the sum table of 2-62. If the moments be required about another point, say y, we have
X-1
t=0
^=:0
which expresses the moment Mn, y in terms of the moments . 2*64. Partial Summation. We have
u^A'Vx = - ■»®+i A ■
Operating with we obtain
Pw A - Pw A •
Example. To calculate P^)Xa^,
We have /X a^= (a - 1) a®, and hence
PMxa‘‘{a-l) = \xa^ -Pwa‘'+^.
L. Jn
Now
P(-;/a*+i = a’‘+o«-i+...+a = ,
so that
P(„Ja;a*
w a” - a. (a- 1)2 ■
42
BIFFEREl^-CE OPERATOBS
[2-64
The analogy of the formula for partial summation with the formula for integration by parts should be noted. In fact if^ taking to be an integer, we make the extended definition
P(n)i ^ + • • • + J
the formula for summation by parts becomes
J P (n)ai A ^a: j
wticli wken co — > 0 becomes
2*7. The Summation of Finite Series. If we denote by tbe xth term of a series, tbe sum of the first n terms is
P(ft) ^x+l ” +
To evaluate this sum we see, from tbe theorem of 2-61, that it is sufficient to find a function /(tc) such that
A /(a;) = M*+i.
The general problem of solving this equation constitutes the summation problem, which will be treated in Chapter VIII. For the present purpose we require only a particular solution, and we ■shall now shew how such a solution can be obtained for certain special forms of .
2*71. Factorial Expressions of the form By211(5) Thus, by 2*61,
Tor example.
L m+l J(, m+1
1 . 2 .3+2 . 3 . 4+... + (re-2)(n-l) w = l{n-2){n-l)n{n+l). Also
m(m+l)(m + 2) + (m+l)(m + 2)(m+3) + ... + (M-2)(w-l)n = P(-/(a;+l)(3) - P(-Vi)(a:+l)W
= i(n-2)(n-l)n(n+l)-^(m-l)m(m+l){m + 2).
2-71] DIFFERENCE OPERATORS
Again, from 2*11 (10), we have
43
whence we get
‘ a(m+l)
= (ax + bY^\
in)
a(m + l)
Example. Sum to n terms the series
3.5.7 + 5,7.9 + 7.9.11 + ....
The icth term is (2x+5)(2x+3)(2cc+l) = (2a; + 5)<^> and the required sum is therefore
'(ft)
(2x+7)(3) z=
L y
= M2w+7)(2M+5)(2n+3)(2n+l)-
J 01.
8 *
2*72. Polynomials. If the irth term be a polynomial in a;, we could use the method of 2*71, having first expressed in factorials by the method of 2-12. But from 2*12 (2) we have
4>{n) = ^(0) + nA^4(0)+?i^) A^i(0) + ... .
Putting (f){n) — P(n)^Wa.^.i, we obtain
^(0)==o, A^(0) = A^i,.-.,
so that we get the formula
Pin) ~ A — gr A ^1+ • • ■ •
Since u^. is a polynomial, the terms on the right vanish after a finite number of differences have been formed.
Example (i). Bind the sum of n terms of the series
12 + 22+32+.. . .
2
Here = a;2, A^a: = 2a;+l, A^a = 2 and the required sum is
, 3n(n-l) 9^(9^-l)(n-2) _ n(n+l)(29^ + l) n+ ~ + g .
44 DIPFEREN-CE OPERATORS [2-72
Example (ii). Find the sum of n terms of the series whose nth term is n^+7n.
We form the following table of dilFerences :
|
«1 |
U2 |
Ms |
M4 |
|
|
8 |
22 |
48 |
92 |
|
|
14 |
12 |
26 |
18 |
44 |
6
Hence the required sum is
I , 12n(n-l)(n - 2) 6w(m - 1) (n - 2) (n - 3)
2 ■ 6 ^ 24 =in(re + l){n®+n+14).
Another method of summing series of this type by means of the Polynomials of Bernoulli will be explained in 6-501.
2-73. Factorial Expressions of the form xf-"™). 2-11 (7) and (9), we have
2;(-in+l)
A TT = 2^“”^ ■
-m+l
(aj-f l)(a!-f 2) ... (x+m)’
. (ax+bY~^-^^^
From
Thus
[a (a; -f 1 1 -f 6] [a (a; + 2) + 6 j . . . [a (a; + ti^T] '
Pw(a:+ !)(-’”> =
L- -a(w-l) Jj'
Example. Find the sum of n terms of the series
_i._ , 1 , 1
i-4.7'^4.7.io'^n:oj+- •
Here the xth. term is
1
2-73]
DIFFERENCE OPERATORS
45
Thus the required sum is
P(-;/[3(a;+l)-5](-3) = ^(3 . 1 -5)(-2)-H3(n+ 1)-5]<-2)
1 1 24 6(3w+1)(3m+4)’
These results are analogous to the formula {"(ax + 61 - dx -
J^(axHr6) dx- a{m+l)‘
2*74. A certain type of Rational Function. If
where ax +b
and if (f>{x) be a polynomial of degree lower by at least two unities than the degree of the denominator, then we can sum the series to n terms. We begin by expressing <f>{x) in the form
<j>{x) = ao + «l'^'’x^-a2■y*u*+l+...+a„_l^)xVx+l^>x+2■••'yx+m-2•
This can be done by an obvious extension of the methods of 2-12, or indeed by equating coefficients. It then follows that
so that the sum can be obtained by the method of 2*73.
Again, supposing the numerator of a rational fraction to be of degree less by at least two unities than the degree of the denomi- nator but intermediate factors alone to be wanting in the denomi- nator to give it the factorial character described above, then, these factors being supplied to both numerator and denominator, we can obtain the sum. Thus, for example,
^£C+2 '^SC+S
^«^a+l'^a5+2'^ar-{-3
Example. Find the sum of n terms of the series
i.3.4'^2.4.'5'^3.5.6'
46
DIFFEBENCE OPEBATORS
[2*74
Here
x+1 _
" x{x+2){x+3) " x{x+l){x+2){x-\-Zy = (a;+2)(-2) + (a;+l)(-3> + a;<-«
Pw “»+i = - (»+2)(-« - i (w+ 1)(->*> - 1 n(-3
_1 , 1 , 1 1
“3 12 18 n+3 2(w+2)(to+3) 3(w+1)(w+2)(m+3) ’
2’75. The form a^(f>{x}, ^(x) a Polynomial. We have Aa“i)» = a®(«-l+aA)«'» = “®(«-l)(l + ^A) ‘Vx, where 6 = a/(a-l).
If ^{x) be a polynomial of degree v, put
Vx = ^{^-bA+b^k-- + {-irb^A]<f>i^)-
Then
j\a’‘v„= a*{l + (-l)‘'h‘'+^ A
We have therefore (1) p^J;a-^^j>{x+l)
fin-rl 2 V
= -ji [1 - & A+&' A- - + ( - 1)- A] <^(n+ 1)
-„^[i-6A+&'A-- + (-i)‘&’'A]<^(i).
Example. Find the sum to n terms of the series
12. 2+22. 22+32. 23+42. 2«+... .
Here «, = 2® and the required sum is
2«+i{l _ 2A + 4A} (m+ 1)2 - 2 {1 - 2A + 4A} 12 = 2»+H(n+l)2-2(2n+3)+8}-2{l-6 + 8},
= 2»+i(n2-2n+3)-6.
2-76. The form v^<f>{x), <f>{x) a Polynomial. Let ^{x) he a polynomial of degree v. Consider the expression
f(x) = (p-^v^)<f>{x-l) - (p-2 v^) A<f>{x-2)
2
+ (P-® ®x) A 3) - ... + ( - 1)- (P—I A (a; - V - 1).
2-76]
DIFFERENCE OPERATORS
47
Since A («» Q = Wi A «* + s* A ,
we bave
A/(a:) = 'o^<i>{x) + {P-'^v^)
+ ( - 1)-- [( p- A - v) + (P--1 1,^) aV (a: - V - 1)]
= v^,f>{x) + {-iy ( p-‘-i v^) "a <j>(x-v-l)=v^<j> (x),
v+1
since A v- 1) = 0.
Thus, by 2-61,
(1) P(l) + = { P(l) ^x+i) ^ (^) - ( P(n)V:,+i) A ^ - 1)
+ (P(«f^x+i) A^(^-"2)- ... ,
Since P(n/ = 0 when n = 0.
This result enables us to sum the series whose xth term is v^(l>(x), where ^ (x) is a polynomial of degree v, provided that we can form the repeated sums
P(n)'^£C4-l> 5 = 1, 2, 3, ... , v + l.
Example. Sum to n terms the series whose nth term is (n-c) sin {2an4-6).
Here <j>{x) ^ x-c, = sm.{2ax+b), and the required sum is P(«)^ (ic + 1 - c) sin (2ax + 2a + 6)
= (n-c) P(^)^sm(2aa;+2a+&)- P(;;fsin(2a£i?+2a+i). Now* A sin (2aa; + 6) = sin {2ax + 2a + 6) - sin {2ax + 6)
= 2sinasinf 2aa5+6H-a + ^y .
*It is interesting to note that, if we form the difference table for sin(aa; + 6) or more generally for the terms in the same horizontal line are in Geometrical Progression. This fact was employed by Briggs and by Gregory.
48
DIFFERENCE OPERATORS
[2-76
Hus
P(;?sin(2aa;H-2a + 6) = ^ • ?— ( sin r2aa:+2a + &- a -
M SlIX -JQ
= j^sin (2an + b+a-^ + QOB{a + h)^ ,
P(;fsin(2aa; + 2a + 6) = +
” ncos{a + b) 2 sin a
Hence, after reduction, the required sum is
-csiana sin (na+a+b) n cos {2an + a + 6) sin na cos (an + b) sin a 2 sin a 2 sin%
The repeated sums required for the method of this section can always be formed for the t3rpes (ax+b)^^\ 4>{^), a^(j>(x), where <l>(x) is a polynomial, since the operation with P”^ in each case leads to a function of the same form. Repeated sums for {ax + b)^^^'> can be formed, provided that the number of repetitions be not great enough to lead to the necessity of evaluating + for which no
compact form exists in terms of the elementary functions here con- sidered.
2*77. When the nth term of a series proposed for summation cannot be referred to any of the preceding forms it is often possible to conjecture the form of the sum from a general knowledge of the effects of the operator and hence to determine the sum by trial. For example, if (f>{x) be a rational function, then
i!^a^<f>(x) = a®
where is likewise a rational function. Similarly A tan-^ <l> (x) = tan*”^ ^ (x), where ^(cc) is rational if <f>{x) be rational.
Example. To sum to n terms, when possible, the series P . X . X2 32 . X3 2.3 3.4 ■^"4.5
The rcth term is given by
2*77]
DIFFERENCE OPERATORS
40
Here we should evidently assume that
P(n) ^0^+1= constant.
Operating with Aj we have
(n + l)^X^+^ _ 1 ({a(n-{-l) + 6) X _ an +-61
(n + 2)(n + 3) ~~ n4-3 n + 2 j
Equating coefficients, we must have (X-l)a = 1, 3a(X~l) + 6(X~l) = 2, 2(a + fc)X-36 = 1, From the first two, (X-l)(a-f 6) = 0, whence from the third h=z so that a = X = 4.
Thus the series can be summed if X = 4, and we have for the sum
r(x~i)4*+n«_ 2
_ 3{x+2) Jo“ 3(w + 2) ■*'3‘
This example is due to Boole, who explains the peculiarity as follows :
= X"-
4X^ X^
^ + 2*^^+ 1 ’
\n
SO that unless X = 4, in which case the term :r destroys the corre-
n+l
-4X^
spending term ^n-i> we should require the sum of a series
whose nth term is
_X" n + 1*
Such a sum cannot be obtained in terms
of the elementary functions considered here (but see Chapter IX).
EXAMPLES II
1. Prove that
(i) A log U (x) = log (l + ;
u
(ii) A log (% %_! . . . Mx-m+l) = log
^ar-m+l
2. Prove that
Asin(^J^-f-6) = (2 sin^a)^sin{a3J+6-f|n(a+Tc) } ,
n
Acos(ax + &) = (2sm|a)” cos{aa;-f 6H--|n(a4-7r) } .
n
Obtain corresponding results for the operator A? deduce the results for the operator D^. “
50
BIFEEREJSrCE OPERATORS
[ex, n
3. Prove that
tan ax =
sin a
cosaa3Cosa(aj-i- 1) '
A tan-'^ ax = tan”^ ^
4. Evaluate
5. Find the first differences of
2*smp, taii|;, cot (a. 2*).
6. Shew that
A™ =
<u 'Oo^
7. Prove that
8. If cj) (X) be a polynomial, shew that
9^(E)0-=Ef(E)0-\
and deduce 2-53 (2).
9. From HerscheFs Theorem, or otherwise, deduce the secondary form of Maclaurin's Theorem, namely,
^(«) = ^(0) + ^(D)0+^^6(D)02+^'^(i3)03+... ,
where ^4(D)0* is the value when t = 0 oi (f>{D)t>.
10. If E”0® denote n®, prove that
^(E«) 0“ = re®^(E)0®.
11. Shew that the differences of zero
AO”, A0"+^ A0”+^ ...
form a recurring series and find the scale of relation.
12. If C” = i A 0“, shew that
ib !
Cl = Clz\+n(Jl_-^.
DIFFERENCE OPERATORS
51
EX. Il]
13. Shew that
Uq^u^x+-~ +... = e® + ^ A'^^'o + 2! A^o+--- | , where is a polynomial.
14. If Sn = T“ +07 ^ . + ... + -~“-v , shew that, if m > 2,
1 . 71 2{n-~l) n . 1
(SiA-^2A+...)o- = o.
71
15. Express A ^ series of terms, proceeding by powers of x, by means of the differences of zero.
Find a finite expression for the infinite series
l’” .a; - 3”*.^ + S”*. ,
where m is a positive integer. If m = 4, shew that the result is {x - 6x^) cos x~{7x^- x^) sin x.
16. Prove that
f{x^){xE = {xE )”‘f(x^ + m)u^.
17. Find Un from the relation
^i”Un =
71-0
1 - 71 - 4«2
18. If t’^u„ = /(e‘), prove that
n~0
W„ =-^^^^0".
n\
19. Find a symbolical expression for the nth difference of the product of any number of functions in terms of the differences of the separate functions, and deduce Leibniz’ Theorem therefrom.
20. If the operator A on n alone, prove that
TjCl+l TT-
m being a positive integer greater than a and the even integer next greater than a + 1.
52
DIFFERENCE OPERATORS
(KX. II
21. Shew that
"a*9. = AL"-'-i+ a'i” n+i
22. Prove that
A 1*’+^ = (w+ i)A i^+n a'i”,
and apply the formula to constructing a table of cliffercncoa of powers of unity up to the fifth power.
23. Prove that
( - l)«/(a:+ ww) = /(*) - 2 ( j) + 2= g) Vf(x) - .
24. Prove that
A V/(®) = Am
ui ti* 2«>
A V/(^) = A/(x).
25. Sum to n terms the following series (i) 1.3. 5. 7+3. 5. 7. 9 + ....
(ii)
1.3. 5. 7^0. 7.9
+ ... .
(iii) 1.3.5.10+3.5.7.12 + 5.7.9.14 + ....
(iv)
_10 , 12 , 14 1.3.5 077 ■^079'^
(v) 1.3.5cos0+3.5.7cos2e+5.7.9cos3O + ... .
(vi) l + 2acos0+3a2cos20 + 4o®co8 30 +
26. The successive orders of figurate numbers arc defined by tbs; that the ajth term of any order is equal to the sum of
nAhfft ! preceding, while the terms
of the &st order are each equal to unity. Shew that the xth ti>rm 01 tile nth order is
EX, ll]
DIFFERENCE OPERATORS
53
27. Prove that where /(./) is equal
to the expression
. m ...v - . m .
sin (2x "> 1 ) cos {2x)
• /*> -t %
sm-^(2a;+l)
T"
cos-H-(2a:+2) sin ^ (2a; + 3)
/„ A-?i(3;) + ... .
(2sm^j 2sm2j
28. Prove that
Pw
= (JlV” + (^“i)'A^(a=)-...}
4-CQ + (7jir'f...4-
and determine the constants Cq, Cj, ... ,
29. Use the result of Ex. 28 to discuss the summation of the
'^1 - ^2 + % *^4 + * • •
to n terms. Consider the forms of given in sections 2-71-2-70.
30. Prove that to n terms
(i) — -v; H~ + -t — + . . . = cot ^0 — cot 2”"'^0 ;
^ ' sin 0 sin 20 sm 40 ^
.... ^ ^ _ 2sinn0
cos 6 cos 2 0 cos 20 cos 30 “ "" cos {n + 1)0 sin 20 *
31, Shew that cot'‘^(y + 5f + ra;2) can be evaluated in finite
terms if == 4(j)r-~ 1). Calculate :
P<») iTT7:^-i iT^ ’ P(«)
1 log tan 2“a 2® (x - 1)
) 2^ ’ i^i+iy
rw l + a:(a;-l)X>‘’ 2* ’
32. It, is always possible to assign such real or imaginary values to s that P~’-/(a5) can be evaluated in jSinite terms, where
f( ) — («+P^+Y^^+--- + '^^")
a, j3> , V being any constants, and u^. = ax +b, (Herschel.
54
DIFFERENCE OPERATORS
fMX-. II
33. Shew that M„+% cos 26 + M2 cos 40-1- ...
= — -
4 sin^0 8 sin^0
4^sine + ,-A-®w
16 sin‘'0
cos 20 •
32 sitr'’’0 '
34. If (^(x) = Vg + ViX+v.,x~+... , yhew that
Mq«0 + “1 V + + • • •
= Mo,^(a;) + 3:f (a:)AMo + ^|f'WA'«u I -- •
and if ^ (x) = ■!;(, -t- VjX -h H- . . . , then
UgVg + UjVlX 4- +•••
= Ug(l>{x)+x^(j>{x-l) . i^Ug+Q^(l,(x-2) . ^Ug \ ... .
((iiideriiiaiui.)
35. If Sn — and p = ?«.(■;« t- 1), shew that
Sn = P^f(p) or (2?jn-l)y)/(;ii), according as n is odd or even,/(j)) being a jiolynomial.
36. Prove that the number of ways in which an integer which i.s the product of m prime numbers can be e.xpressed us a product of factors relatively prime to each other is
m r
r=0
Prove also that 8^ satisfies the recurrence relation
37. Prove that
and that, if m is a prime number, - 2 is divisible by tn.
CHAPTER III
INTERPOLATION
In the practical applications of the finite calculus the problem of interpolation is the following : given the values of a function for a finite set of arguments, to determine the value of the function for some intermediate argument.
In the absence of further knowledge as to the nature of the function this problem is, in the general case, indeterminate, since the values for arguments other than those given can obviously be assigned arbitrarily.
If, however, certain analytic properties of the function be given, it is often possible to assign limits to the error committed in calcu- lating the function from values given for a limited set of arguments. For example, when the function is known to be representable by a polynomial of degree n, the value for any argument is completely deterininate when the values for n+ 1 distinct arguments are given. In the present chapter we propose to obtain certain formulae based on the successive differences of the function for the given arguments and to investigate the remainder term, the knowledge of which will enable us to decide as to what further information is necessary to ascertain limits within which the interpolated value represents the value sought. In actual calculations there is, of course, another source of error due to the fact that the known values are usually approximations obtained by curtailing at, let us say, the fifth figure a number which contains more than five figures. For an investigation of this error see papers by W. F. Sheppard.*
The basis of the interpolation formulae about to be obtained is the general formula of Newton for interpolation with divided differences.
* Proc, London Math. Soc. (2), 4 (1907), p. 320 ; 10 (1912), p. 139.
55
INTERPOLATION
56
[a-0
This formula with its remainder term has aln^atly been gi\'eiL The formulae of Gauss, Stirling and Bessid were knovvui to Ni'wton, and if for brevity we do not attach his name to them, it dtH\s not detract from his credit in discovering them.
3*0. Divided Differences for Equidistant Arguments. If in the formula T3 (1), we put
5 = 1,2, 3, ... , /a
we obtain for the divided difference the expression
/(a?+ w) n\ CO”
/(a;4-(^-l)co) /(:r i {n 2) c.>)
(^-1)! ifco” ■(//■■ 2)! 2! c.>“ ■■
= ^ A/(i^) from 2-f) (2).
Since the arguments in a divided difference can written in any order we have thus proved the following theorem.
If the arguments x^, X2, taken in a certain order form an arithmetical progression whose first term is x, and whose amimon difference is <0, the divided difference of f{x) formed with these argu- ments is given by the relations
(1) [W3 ... a;„ J = i A/(a;,) - A'‘fO.)-
Again by 1-2 (2), we have
K^2-^n+i] = 2 /(«)(5),
where 5 lies in the interval (x^, x,+no).
Thus we have
(2) Af(x.} =/<">(?),
ui
where ? is some point of the interval (»„ x, +nw).
In the notation of differences this result can be written, usini; 2-1 (5), ^
(3) /(«)(^) =
Ms result shows that the Mth column of differences formed from a table of functional values for equidistant arguments places before us a specimen set of values of the nth derivate of the function, each
INTERPOLATION
3«0]
57
such derivate being multiplied by which is a constant for the column in question.
3*1. Newton’s Interpolation Formula (Forward Differ- ences). Consider the following table of functional values and differences.
|
Argument |
Function |
|||
|
a |
/(“) |
Alia) |
||
|
(X + CO |
/(a+w) |
Zl/(a + «) |
A^fia) |
A^fia) |
|
a + 2(0 |
f{a + 2(j>) |
Af{a + 2a) |
ZlV(« + «) |
Z|3/(a + «) |
|
a + 3co |
/(a + 3w) |
JV(« + 2co) |
If in Newton’s general interpolation formula with divided differ- ences, 1-1 (1), we write
X, — a~h(s-l)oi, 5 = 1, 2, 3, ... , w, we have by 3*0 and 1-2 (3)
[^1^2 - a:,+i] = ^ /!“/{«).
[OTj ... x„] = ,
so that the formula gives
(1) /(^) = f{a) + {x-a) <o-M/(«) + ~ W + -
+
(x-a){x-a-oi) ... (a; - a - nco -f 2co)
W"+M"~V(«) + (»)>
where
(2) R.ix) = /«(E),
i
and ^ lies somewhere in the interval bounded by the greatest and least of X, a, a + nca - CO.
This is Newton’s Interpolation formula with forward differences. The diJBEerences employed with this formula lie on a line sloping downwards from / (a). The formula gives the value of f{x) in
58
INTERPOLATION
[•M
terms of f{a) and the differences of /(a) provi(i(‘«i I ha,t \v<‘ can calculate the remainder term Tlu‘. formula assuiucs a
simpler form if we introduce the fhase 'p, wlua‘(‘
(3) p=:{x-a)jo},
which represents the ratio of the distance betwi'cn t he '' ])oint s ” X and a to the tabular interval of the argument. We t hen ohlaiii
(4) /(iK)=/(a)+j)/j/(a) + (|jaV(0 + (3j/1VV') i
which is the most convenient form of Newton’s formula, wit li forward differences, the value of p being given l)y (r>).
If in (4) we omit the remainder term, we ol)tain Newtoirs lnt(‘r~ polation polynomial (see 1-9)
(5) /«-!(») =/(ffl)+pa/(«)+(2)av(a)'i ij-'i” ‘/(«).
which assumes the values of/(a;) at the points a, a + co, ... , I) cr).
It follows that neglect of the remainder term is equivahait to replacing /(a?) by this interpolation polynomial. drgrtM‘ of
approximation attained by this process of polynomial itdorpolat ion of course depends on the magnitude of the m^glecdcd r<*ma,in<li‘r term. This will be discussed in section 3-12.
We may here observe that the interpolation polynomial (d) eati he written symbolically in the form
(6) ^»-iW = (i+a)f„ ..,)/{«),
where the su&x 7i~\ indicates thut the cxpcinsioii of t<ht* operiif or by the binomial theorem is to cease after th(j term in , | ‘ bus hoen
obtained.
Newton s formula, or rather the series which arises from it when thennmher oftermsisnnhmited, is of great theon'tical importance, as will be seen in Chapter X. For practical mimerical interpolation the central difference formulae to be obtained latter are preferred. Near the beginning of a table, however, when (jcntral differeticeH are not given, Newton’s forward formula is available.
3-1]
INTERPOLATION
59
In the above work we have written ^ewtoii’s formula in the notation of differences, the form best suited to numerical applica- tions. We can, however, use difference quotients. Using 2*1 (5), we see at once that (1) can be written
(7) fi^) + + A /(«) + ■••
iU ^ * oj
{x-a){x-a-i>i) ...(a:-a-ww + 2c5) r, ^ , -o , \
+ ' IV-IT! ^ A/(a) + -K«(a:).
Or in the factorial notation,
(8) / {x) = f{a) -I- (x - a) A /(a) + A /(«) + -
When 0) -> 0 we obtaiii Taylor’s Theorem, namely, fix) = f{a) + ix- a)f' (a) + f" {a) f .. .
(H-1)!
where ^ lies in the interval {a, x).
The formula of this section is often referred to as the Gregory- Newton formula, since it was actually discovered by James Gregory in 1670.*
3*11. Newton's Interpolation Formula (Backward Differences). Here we consider the table
|
a -See |
/(a-3co) |
|
a - 2co |
/(a-2m) |
|
a-6) |
fia-oi) |
|
a |
/(a) |
J/(a-3o))
J/(a-2co)
zlV(a-4w)
/f^f{a-Z(^)
A^fia-2a)
A^fia-^)
ZlV(«-3o>)
* The actual MS. letter from Gregory to Collins which gives this formula is dated 23 November 1670, and is preserved among other of its contemporary documents in the library of the Royal Society.
60
INTERPOLATION
If in M (1) we write
= a-{s~ l)co, 5^1, 2, ... , n, we have by the theorem of 3*0
[^1^2 * • • ^5+l] ~ ^ [ A^f(^ •
Thus we have
[:mi
f(x) =/(a) + (a;-a)«-M/(ffl-<o) (x-a) (x-g + o)
2!
o>~^A~f{a - 2a>) f
or introducing again the phase p = (x-a)l u, this Ix'comea
/(s;) =/(fl)+i)Zl/(a-«)+^^!-i^ J“/(a--2w) f ... , which can be written
(1) /(®) =/W+^’Zl/(a-w) + ^^2 + ...
+ w - 1 + C' ’* * j (?),
where | lies in the interval bounded by the greatest and least of X, a, a - (w - l)u. This result could also be obtained by writing the tabular values in the reversed order, difierencing, and’ tiien apply- mg the forward formula.
The differences employed with this formula lie on a line sloping upwards from f {a). The corresponding interpolation polynomial obtamed by omittmg the remainder term may be written syml)oli- cally in the form
d'n-iCa:) = +
/(«)
where the suffix again indicates the index of the last term of the bmomial expansion which is to be retained.
nnkt^^ ^ fcaoiward formula has its practical application to inter-
pdation near the end of a table, when central differences are not given.
3-12]
INTERPOLATION
61
3*12. The Remainder Term. The process of interpolation applied to the values in a given table cannot of course give an accuracy greater than that of the values in the table, which are in themselves usually approximations. In attempting to attain the utmost accuracy which the table permits, when a given interpolation formula is used, it is common practice to omit from the interpolation formula the first term which ceases to influence the result obtained. The question then arises as to how far the result so obtained repre- sents the desired approximation.
The error in the approximation arises from two sources : (i) errors of rounding, inherent in the tabular matter and the subse- quent calculations ; (ii) errors due to neglect of the remainder term. With regard to errors of the first category we shall content ourselves with the observation that, in so far as they arise from subsequent calculations, these errors can be minimised by using one or two extra figures which are subsequently discarded. As to the errors arising from (ii) we shall make some observations, with particular reference to Newton’s forward formula, but which are of general application.
(а) In numerical work we naturally take x between a and a + co, so that the phase p is positive and less than unity. Consequently
and opposite sign.
(б) If we can conveniently calculate (a;) we can generally state
upper and lower bounds to the value of this derivate in the interval (a, l)<d) and thus delimit the error due to neglect of the
remainder term.
(c) If {x) have a fixed sign in the interval {a, a+ (n - 1) co) and f(n-¥i) (x) have the same fixed sign in the interval (a, a-h-nco), then the inclusion of an extra term in the interpolation formula gives
Since, by (a), and opposite signs, so also have
lt„(x) and ; and consequently
Unix) (j)zl"/(«)
02 INTEBPOLATION i;i-12
that is, R^{x) is less than the first term omitted from the formula and has the same sign. This result is called l)y St(‘iren.s.‘n the. Error Test.* The test depends essentially on and A’„n(:r) having
opposite signs.
(d) If nothing be known about the value or sign of/'">(^'). «'(> can only regard the results of interpolation as a working hypotlie.sis. This in particular would be the case if the tabular malt.er were empirical. In such cases we might bo incliiu’-d to (“stimate flu? value o£ fM(x), on the grormds of the last part of section .'J-O, by an examination of the nth column of differences. That smdi Gonj(“cture may be fallacious is seen from the following table ;
We have
X
0
1
2
3
0
1
4
9
V -fi
/(0-5) = 0 + -5xl--^ x2
■5 X -5x1 -5 G
4*
= 0-25 + ,V
Tte third difference is zero, so that an estimate of tin*, error term would be zero and we would conclude that /(0-5) ()*2r>.
This is correct iif{x) = x^. If, however,
f(x) = x^ + sin Tzx, (x) = “ 7V^ cos nx ,
the maximum value of which is tt®, and the actual error is I .
It might be contended that the instance is extremcily art illeial To this we answer that a satisfactory mathematical th(K>ry auist not exclude possibilities of such a nature, and, secondly, that if talmlar matter be collected from observations .made at equal intervids (say of time), a periodic term might quite well be masked in this mmimr.
* J. F. SteiBfensen, Interpolation^ London {1927).
INTElil^OLATlON
63
3*12]
Example, From the following values * calculate sm0*lG04, cos 0*1616.
|
X |
sin X |
A |
cos X |
A |
|
|
0*160 |
0-15931 820G6 |
9871475 |
0-98722 72834 |
1598118 |
|
|
*161 |
■16030 53511 |
1604 |
•98706 74716 |
9871 |
|
|
9869871 |
1607989 |
||||
|
162 |
•16129 23112 |
•98690 66727 |
Using Newton’s forward formula, we have for the sine
The coefliclent of the second dijfference is |x*4x -*6= -*12, while, since o = •{)()], the coefficient of the remainder term is
X *4 X - •() X - 1*6 X (-001)^ = 6*4 x IQ-^i.
Since -cosx, the remainder term contributes
- 6*1 X 10-11 X *99,
that is, 6 in the eleventh decimal place. We have then, treating the tabular values as integers,
sin-1604 = 1593182066 + 3948590*04- 192*5- *6 = 0*1597130848.
For the cosine, using Newton’s backward formula, we have^ = ~ -4 and the coefficients ~ *12, - 6*4 x 10~ii.
Here = sinx, so that the remainder term contributes
- 6*4 X 10-11 X *16= - lxlO"ii.
Thus •
cos *1616 = 9869066727 + 643195*6+ 1184*5 -*1 = 0*9869711107.
In these values the only errors which can be present are those due to rounding.
3*2. The Interpolation Formulae of Gauss. These are obtained from Newton’s general divided difference formula, 1*1 (1), by means of a special distribution of the arguments
* C. E. van Orstrand, Nat, Academy of Sciences, xiv, (1921), Part 5.
64
INTERPOLATION
It is again convenient to introduce the phase
(1) j) = (x-a)lo>,
and to write
fix) =/(a-f^?6>) = u^.
With the central difference notation of 2-0 1 we tlien have the table
(2)
a + co %
If we put
(3) a?! = a, X2, = a + 5co, a'2,,4,1 - (i-
the theorem of 3-0 gives
^•“2s
[a^iTg . . . Kjs+i] = j.2jy| ~ ~ ( 2,v ) ! '
while
(X-Xj) {X-X2)...{X-X2,)
= i^- %-i) (» - a:2s_3) ...{x-X3){x-Xi){x- a-,) {x - .r,j) ... (a: -
= (p + s-l)(p + s-2) ...{p+l)p{f~l){p-2) ... (p-.s)oj“’
Thus
(a:-Xi)(a;-X2) ... (x-x,Xx^x^...z^„,] = MS‘* w„,
and similarly we can shew that
(X-Xj)(x-X2) - ix>-X^^^)[x^X^... 07.2,, .J .-= (.£,J,y S’*"' Mj.
If then we make in 1-1 (1) the substitutions given I)y (3), we obtain
f{x) = U^ = Uo+i^)^Ui+ (I) S^Mo -I- J ^ j §3 « J
'^'2] INTEHrOLATION O5
Ihis is Gauss forward formula, and is used in conjunction with the zig-zag scheme of differences shewn in (2).
If n = 2m, we liave
^^2rn ““ - 2^2) • • • - ^*2 (?) / (2w) !
and Gauss’ forward formula becomes
(1) /(-G
v.’So*—
where ^ lies in the interval (a — - 1) w, a + mco), when x lies in this
interval.
If fi = 2m -4- 1, we have
(5, /w = - 1 i” -- *)
where 5 hes in the interval (a~ mw, a4- mca), when x lies in this interval.
Gauss’ backward formula is used in conjunction with the table
a - 0)
(6) Sw„S 8^u_^
To obtain the formula we write
= a, = a- s<j>, = a + so>
in the formula 1-1 (1). We then obtain hj the method described above
{x - Xi) (x - Xa) .. . (x - Xj.) = Mo ,
(x - Xj) (x - Xa) . . . (x - X25+1) = (is + 1) ’
66
so that
INTERPOL ATI OK
f{pc) — Wj, __ ^ | , ^/ ^ J ’^a
which is the required formula.
If n = 2m, we have
■y.;.
(7) /w = », = «.+ s'(0*“"'”-i ' K
-er)“=-/-=-(a
where a: lie in the interval (a-m), « i (wi |)fo). whih fo: n = 2m+l,
where a: lie in the interval {a-mca, a + 7tm).
It shonld be noted that if in (5) and (8) we omit t he .vnuiinder terms, the corresponding interpolation poIynomiiiLs terminate ;it Mie, same difference and therefore both agrees with f{x) iit t he s'une points, and consequently coincide. Thus (lauss’ forward f.^rmuhi ha.s the same remainder term as the backward formula if t;h(' la.st, dilTer-
ence used m each be of the same even order, and both formulae give tJie same result. ”
Again, since
V 2s y 26-
we see that, in-the forward formula the sign of p hi* (dumged, the coefficients of the even order difterences coimude with the com-
in sim to +1, ^ differences are equal in niagnitmle but, oppo.site m sign to the corresponding coefficients in the backward formula.
lOTERPOLATION
3-3]
67
3-3. Stirling’s Interpolation Formula. Stirling’s formula is obtained by taking tlio arithmetic mean of Gauss’ forward and backward formulae.
We have
i V 'i ^ ' .S') (p H- 3 - 1 )...(??+] ) f {f- 1 ) „ . (p - s)
2s i- i/ ' (2s f l)!
(2.V+1)!
(P ^ ’ i , ('P ^-•'>•'^_2p(p + s-l)...(p-s+l)
V 2s / \ 2s / “ (25)1
_ 2f (p2 - P) {f - 22) . . . (p2 - s - P) “ (2s)l
Taking the arithmetic mean of 3-2 (5) and (8), we obtain
(1) m - «„ -
.f-o (2s+l)!
V p2(p2-P)(p^-22)... (p2_7ri2)
+
« I
where, as ht^fore,
(2.)!
p(p2„ p) _
(2/M-fl)!
Uq
S2»Mo 0)3“+l/(2™+l)(^),
p (:r - a) / co, Uj, =^f{a+jm) =f{x).
This is Stirling’s formula. The dilferences employed lie on a horizontal line through thus :
(2) a Uq g.S'Wo ^"*^0 —
Stirling’s formula is completely symmetrical about = 0 and can therefore be vrsed for either positive or negative values of p. In the form (1), which terminates with a difference of even order, the re- mainder term is the same as in the formulae of Gauss which termi- nate at the same difference. Hence from the point of view of numerical calculation the formula of Gauss is superior in that there is no necessity to form mean differences.
By taking tlie mean of 3-2 (4) and (7) we can obtain the remainder term of Stirling’s formula when the last difference used is of odd order. It will be seen that this is not of a very simple form.
68
INTERPOL.ri’ION
[3%3
Stirling’s formula written in full for rn ™ 2 is (3) f{x) = U„ = + +
+ “ii
where x lie in the interval (a 2o>, a-f- 2o)).
The corresponding interpolation })o]ynornial o!)taine(l hy omitting the remainder term in (3) agrees with \-i) (•!), whi<di may he n‘ganiecl as a generalisation of Stirling’s fornuila for unequal intervals of the argument.
Example, Calculate exp (-0075) from tlui following : *
|
X e® |
zl |
A~ |
|
0-006 1-00601 80361 |
100652] 2 |
|
|
-007 1-00702 45573 |
10075282 |
10070 |
|
•008 1-00803 20855 |
||
|
p = -5. |
The coejficient of the second difference is -125, and since 6> •001
the remainder term is - *0625 x (-OOlf 6'"^ - 6 x io approxi-
mately.
Thus, using Stirling’s formula, we have exp (-0075) = 10070245573
+ l (10065212+ 10075282) f J (I(K)70) - -6 = 1*0075281955.
3-4. Bessel’s Interpolation Formula. BeHscl’s formula is obtained by taking the arithmetic mean of Giuih.h’ forward formula with initial argument a and the corresponding backward formula with initial argument a + w. We choose the forms which terminate with a difference of odd order, that is to say ;b2 (4) iimi (7).
* C. E. van Orstrand, loc, cit p. 63.
3-4]
INTERPOLATION
09
With 'p I io, w(‘. Iuiv(^
/(x) Uo-
.’v /
52-’+%j+ ^
fi 0 ^ ^.s* + 1 /
V fp-\-s-l
p \~ ni- I
The second of thes(.‘ has been obtained by writing p-l for p in 3-2 (7) since the initia] argument is here a-f co. The remainder term is the same in both since each terminates with the same difference, namely Taking the arithmetic mean, we obtain
where x are in tlu‘ interval (a~(m-])co, ft + mo)).
This is Bessel’s formula. There is symmetry about the argument a + |a), for writing - p + i for p - i-, we have fp + s-u^fs-p-.
so that the coefiicients of the differences of even order are unaltered, while the other coefficients mendy change sign.
It is convenient to replace ^ + (jo - 1) by UQ+pSu^, The first summation above is then from 5 = lt0 5 = m~l. Written in full for five dififerences, we have
+ (j?+i)?^(p-|)(p-i)(y-2) g5 4- (P + 2)(p+l)p(p-l)(y-2)(y-3)
70
INTERPOLATION
[3-4
The differences used with Bessel’s formula are shewn in the scheme
a Uq
The formula may be compared with 1-9 (3), which shows the more general form for arguments which are not equidistant.
If the last difference used be of even order the remainder term is not so simple.
Example. From the following table * of the Complete Elliptic Integral K, find the value of K when m = 0-032 whore ni{ = /c^) is the squared modulus.
|
m |
E |
A |
A^ |
A^ |
A |
|
0-01 |
1-5747 45562 |
3994351 |
|||
|
•02 |
1-5787 39913 |
4040429 |
4G078 |
999 |
|
|
•03 |
1-5827 80342 |
'4087506 |
47077 |
1022 |
23 |
|
•04 |
1-5868 67848 |
4135605 |
48099 |
1064 |
42 |
|
•05 |
1-5910 03453 |
4184768 |
49163 |
||
|
•06 |
1-5951 88221 |
Using Bessel’s formula, the required value (p = -2) is 1682780342 + -2 x 4087506 - -08 x 47588 -f -008 X 1022 + remainder.
In the absence of a convenient formula for the fourth order derivate we make the hypothesis that this is approximately represented by gin^e ce = -01 we have for the remainder the
hypothetical value + IQ-® x -0144 x 33 = 5 x 10"“ Thus we obtain K = 1-583594045.
* L. M. Milne-Thomson, Proc. London Math. Soc., (2), 33 (1932), p. 162.
INTERPOLATION
71
3-41]
3' 41. Modified Bessel’s Formula- Neglecting the remainder term, BesseFs formula correct to differences of the sixth order can be written in the form
j{x) = UQ+f 8ui + [J.82 Ui + [S* Mj - A; S® m j]
(p + l)p(p-l)(p-2)
4!
- 1 fjiS® u^] + A-\- B,
where
A =
pIIT
sf
_A+l(p+l)(?5-2)]s5Mi,
B
_ (y + l)y(ff-l)(y-2) 4!
[^+^0(?> + 2)(j5-3)][xS«Mj. The mean value of A over the interval _p = 0 to is
and the mean value of B over the interval 0 to 1 is
1 rili 191
'2520 J'
These mean values vanish if we take
(J,8® Mj.
13
191
Putting
V “i = ~ iii “i’
we have the modified form of Bessel’s formula, namely,
m = ^„,+£(£r|(Ezi) v„,
+(?±2K£+liE(£^)^..„„
4!
which includes the effect of sixth order differences. The coefficients of the differences in A and B in the interval 0 ^ ^ 1 are of the orders
0*00002 and 0*00003 respectively, so that, if S® % and do not exceed 10,000, the maximum errors which would arise from the
72
INTERPOLATION
[3-41
neglect of A and B would not exceed 0*2, 0*3 units of the last digit respectively. Actually we use rounded values so that the error may be greater.
The above method of modified differences can of course be extended to diff“erences of higher order and to other interpolation formulae.
Example. Consider the following table* of where
^3(01 t) is the value of the theta function %(x\ t), when a; = 0, arranged according to values of m, the squared moduhis.
|
m |
V^(0|t) |
A |
A^ |
A’^ |
A* |
A^ |
Zl« |
|
0-70 |
0-76687 78205 |
54346488 |
1161883 |
68293 |
5889 |
788 |
109 |
|
•71 |
•76144 31717 |
55576664 |
1230176 |
74970 |
6677 |
933 |
145 |
|
•72 |
•74588 55053 |
1305146 |
7610 |
166 |
Forming the reduced differences we have the following
table for use with Bessehs modified formula.
|
m |
V^OIt) |
||||
|
0-70 |
0-75687 78205 |
54346488 |
1196030 |
68208 |
6257 |
|
•71 |
•75144 31717 |
55576664 |
1267661 |
74869 |
7111 |
|
-72 |
•74588 65053 |
Calculating the function for m = *706, either by using all the differences or by usii^ the modified formula, we get 0-7536313968.
3*5. Everett’s Interpolation Formula. This formula uses even differences only on horizontal lines through Uq and as in the scheme
a Wft
a + oy
* L. M. Milne-Thomson, loc. cit. p. 70.
3*5]
INTERPOLATION
73
Gauss’ forward formula ending with an odd difference can be
written
f{x) = Uo+j>Bui+
S
+
.•li
p + m-l
’Mn +
p+s 2s + l
§2s+l
2 m
^ C02™/(2«)(^).
The term in curled brackets is equal to
Now
_l) |(2s + l)S2*M„ + (p + s)S2»+%i} .
(25 + 1)!
(25+l)S2»Mo + (i3 + s)S^“+^Wi = (25+l)S2»M(, + (p + s)(S2“Ml-a2»Mo)
= (jJ + 5)S‘^‘'Ml-(p-S-l)S2sWo. Hence we have one form of Everett’s formula, namely,
m = u,+pSu, + ’f
A more symmetrical way of writing the formula is obtained by observing that
V 2s + l / ~ V 2s + l /’
Mo+J)Smj = Ug(l-p)+ptii.
Hence introducing the complementary phase p', where p' = 1-p z= (a+o)-x) 1 00, we have the symmetrical form
f[x] = pu, + (£+ u,
+P'^o + "t (t+ 0
where x lie in the interval (a - (m~ l)o), a+ wco).
Everett’s formula is useful when employing tables which provide even differences only, a practice which saves space and printing cost but which offers little advantage to the user of the tables.
74 INTERPOLATION [3-5
For numerical values of the coefficients in Everett’s formula as well as the formula of Gauss the reader is referred to E. Chappell, A Table to facilitate Interpolation by the Formulae of Gauss, Bessel and Everett (1929). (Printed and published by the author, 41 West- combe Park Road, London, S.E. 3.) The coefficients are given at interval 0-001 for the phase p and for differences up to the sixth order, and are so arranged that the coefficients in Everett’s formula for p and the complementary phase p' each appear on the same page. Another table (of Everett’s coefficients only) is that by A. J. Thompson, Tracts for Computers No. F, 1921, Cambridge Univer- sity Press. The latter book gives many numerical examples of interpolation.
3*6. StefFensen’s Interpolation Formula. Gauss’ forward formula ending with an even order difference, 3-2 (5), can be written
|
m f{x) = Mo+ D 5 = 1 |
j- + R^m+l (^) |
|
|
The term in brackets is equal to |
||
|
1 + 2sl 2s-l , |
) |(j9 + s) -{p-s) |
u |
|
Now so that we have |
/p + s-1 -p + s \ 25 25 |
|
|
II o 1 |
||
which is Steffensen’s formula. The formula employs odd differences only according to the scheme
a -CO u_
INTERPOLATION
75
3*7]
3*7. Interpolation without Differences. The problem of interpolation without the use of differences is solved in principle by Lagrange’s formula 14 (3), which gives
(1)
m
(x,)
(x-Xj)(x~Xo) ... (x-x,^).
From this we can obtain a formula equivalent to Gauss’ formula by substituting the proper distribution of arguments. Thus to obtain a formula completely equivalent to 3-2 (4), we put ^2s-i ~ a - {s ~l) CO, “ a + .vco, s ~ 1, 2, 3, ... , m.
Introducing the phase p = {x - a) j co, we have
<j) (x) = (p-h m "f m - 2) ... (p - m) co^
= (m-s)! (mH-s- 1) ! (- ^'(3?2s) = (m + 5-1)! (m~6-)! (- so that (1) gives
f(x] = V (p + ”'t-I)...(p-m) jf(a- ,S(0 CO ) _ /(a + «o) 1
s=i (m + s - ] ) ! {m - s) ! ^ 1. ^5 + .s - 1 ji~~s j
+ remainder.
This can be written in the simpler form
X «) _ /(« + 1 + 1 ^ f(3™) (1)
t ^ + 5-1 p-s J V 2'm /
Other formulae of this nature can be obtained by varying the distribution of the arguments. The practical objection to the use of the Lagrangian formulae lies in the excessive labour of numerical calculation involved. In using interpolation formulae founded on differences the order of magnitude of the terms becomes progressively less. Moreover, if it be found desirable to include further differences it is only necessary to add more terms. In Lagrange’s formula every term is of equal importance and when another functional value has to be included the calculation must be started de novo.
The first attempt to avoid forming differences when interpolating in a table not provided with them, and at the same time to escape
76 INTERPOLATION [3.7
the labour of Lagrange’s formula, was due to C. Jordan,* who formed certain linear interpolates and operated upon these. We shall not describe Jordan’s process, since an essential improvement thereon has been made by A. C. Aitken,t who reahsed that the practical advantage lay in the process of linear interpolation, and devised a method of interpolation by iterating this process.
3-81. Aitken’s Linear Process of Interpolation by Iteration. Let u^, u„ ..., denote the values of a function corresponding to the arguments a, b, 0, ... .
We denote as usual the divided differences by [ah], [abc],
Let /(a;; a, 6, c), for example, denote the interpolation polynomial which coincides in value with at the points a, h, c. Then by 1-9 (2)
a, h) = + (a; — a) [ah] ,
f{x] a, h, c) = Ua + (®-a)[ah] + (a:- a) (a; - h) [ahc],
/(a:; a, h, c, d) = Ua+{x-a)[ah'] + (x-a){x-b)\abc]
+ (a; - a) (a; - h) {x - c) [abed] , and so on. We have then, for example,
/(a:; a,b, c,d) =f[x; <^,b, c) + {x~a)(x — b){x-c)[abcd].
Since the order of the arguments is immaterial we have also fix; a,h,c,d)=/(a;; a, h, d) + (a; - a) (a; - h) (a; - d) [ahed]. Eliminating [abed] we obtain
(1) fix ; a, h, c, d) = (x,b,c)~ic-x) fixj^, b, d)
id-x)-io-x)
^ fix; a, h, c) c-x I . , , ,
fix; a, h, d) d-x | ‘
^ Thus /(a; ; a, h, c, d) is obtained by the ordinary rule of propor- tional parts from the values of fix ; a, h, y) for y = c, w = d. This argument is clearly general.
(1) AUi del Congrmo Internaz. dei Matematici, JBologna, (1928), vi, p 157 (u) Metron, vii (1928), p. 47. wi.
t A. C. Aitken, Proc. JEdinhurgh Math JSoc. (2), iii (1932), p. 56.
mTERPOLATION
3-811
Applying this rule we can now write down
77
the following scheme :
Argument Function (1) (2)
a Ua
h Ms a,b)
c j{x ; a, c) f{x ; a, b, c)
d Ug, f{x ; a, d) f{x ; a, b, d)
(3) ... Parts
a-x h-x c-x
f{x, a, b,c,d) d-x
Each entry is formed by cross-multiplication and division, with the numbers in their actual positions, thus
f{x; a, 6)=
I %
f{x\ a, c) = ““
a-x
b-x
(b-a),
a-x
c-x
~ (c-a),
a-x
d-x
{d-a),
f(x ; a, 6, c) ••
f{x ; a, b) b-x f{x; a,c) c-x
(c-6),
and so on.
The above scheme constitutes Aitken’s process.
The members of column (1) are linear interpolation polynomials, those of column (2) quadratic interpolation polynomials, those of column (3) cubic interpolation polynomials, and so on. If a numerical value be substituted for a;, each member of the rth column is the value of an interpolation polynomial which coincides with u^. at r-i- 1 points and gives the value of within a degree of approxi- mation measured by the remainder term at this stage. The process is therefore completely equivalent to interpolation with Newton’s general divided difference formula. Thus, for example,
=/(cc; a, 6, c, d)+ {x-a){x-h){x-c)[x-d)uf^^ j 4:\ ,
where 5 lies in the smallest interval containing a, 6, c, d, x. If then interpolation by Newton’s formula be practicable, the numbers in later columns will tend to equality as the work proceeds. This leads to a simplification, since in the linear interpolation those figures at the beginning which are common to all the members of a column can
78
INTEBPOLATION
[3-81
be dropped. Tte process terminates when further interpolation would cease to influence the result. With regard to the column headed Parts/' we may replace the entries by any numbers pro- portional to them, as is obvious from (1). In particular, if the argu- ments be equidistant, we may divide each entry in this column by the argument interval co. Moreover, when the arguments are equi- distant, this division by ce will make them differ by integers. The method is eminently suited to use with an arithmometer and is independent of tables of interpolation coefficients. The process can also be used at the beginning or end of a table.
Example. From the given values of the elliptic function sn (ir | 0*2), find by interpolation the value of sn(0*3 | 0*2).
|
z |
sn {z 1 0-2) |
(1) |
(2) |
(3) |
(4) |
(5) Parts |
|
0-0 |
0-00000 |
-3 |
||||
|
•1 |
•09980 |
29940 |
- 2 |
|||
|
•2 |
•19841 |
29761-5 |
29583 |
-1 |
||
|
•4 |
•38752 |
29064 |
29356 |
..469-5 |
+ 1 |
|
|
•5 |
•47595 |
28657 |
29248-5 |
..471-5 . |
.. 467-5 |
+ 2 |
|
•6 |
•55912 |
27956 |
29146-4 |
..473-85 . |
..467-3 . |
..7*9 +3 |
Here the parts ” are - *3, - *2, - *1, -{- *1, -h *2, + *3, which we replace by integers. We also treat the tabular numbers as integers and carry extra figures as a guard. After column (2) we can drop the figures 29. We could likewise treat the entries of column (3) as 9*5, 11*5, 13*86. The following are examples shewing how the numbers are obtained.
|
29940 = |
0 9980 |
-3 -2 |
-1, |
29064 = |
0 38752 |
-3 + 1 • |
|
469-5 = |
583 356 |
-1 + 1 |
^2, |
7-9 = |
7-5 7-3 |
■1. |
The result is 0*29468, which is correct * to five places.
3*82. Aitken’s Quadratic Process. Suppose given an even number of symmetrically placed data such as
* Milne-Tbomson, Die elUptischen Funktionen von Jacobi, Berlin (1931).
INTERPOLATION
79
The expression
[y+x)u,j + {y-x) u^y ^ . ^2^
is an even function of y, since it remains unaltered when -i/ is written for y. This justifies the notation. Also/(x ; x^) = % . With the given data we can form., by means of (1), the values off{x ; a^), f{x\ b^),f{x; c^). If we apply the linear process of the last section to these new data, taking as variables a^, b^, we thereby obtain an interpolated value for/(cc; x^) or u^. Thus we can form by 3-81 (1)
(2) -(‘’-O').
f, 2 ;■> fix; a\b^) b^-x^
/(x;»> J-,o-)= ^ ^
and so on until the data are exhausted.
Thus we form from (1)
f{x; b^, c^)
{b^-a%
~ (c2-62),
f{x; a^)
(2a), etc.,
and form by means of (2) the scheme f(x; a^)
fix ; ¥) f{x ; a2, b^)
fix; c2) fix; a^c2) /{x; a\b\c^)
which is essentially the same as that of the last section, but with squared variables.
Since we are in fact using 2, 4, 6, ... values of the function in successive columns, we are progressively taking account of the first, third, fifth, ... differences in an ordinary interpolation formula. If then 2n values be used, the remainder term is
B,,ix) = (x^-a^) ix^-b^) ...
This process can also be worked at the end or beginning of a table.
In applying this method to equidistant data we first subtract from each argument the middle argument m about which they are
80
INTERPOLATION
[3-82
symmetrical. After division by the interval w the arguments become ± ± ±2|, ... and x is replaced by the phase
p = {x-m) j ci>. The “parts” then become
-which are of the form 0, 2 + 0, 6 + 0, 12 + 0, 20 + 0, 30+6,..., where 0 = (|')®-p®. The advantage of this will be apparent from the following example.
Example. Prom the following values of Jacobi’s Zcta function Z{x \ 0'6), calculate by interpolation Z(0-11 | 0-6).
|
X |
Z(a:|0-6) |
(a) |
(i) |
|
0-00 |
0-0000 000 |
-2-5 |
2-75 |
|
-04 |
-0133 469 |
-1-5 |
1-75 |
|
•08 |
•0266 172 |
-0-5 |
0-75 |
|
■12 |
•0397 350 |
+ 0-5 |
o 1 |
|
•16 |
•0526 262 |
+ 1-5 |
-1-25 |
|
•20 |
•0652 186 |
+ 2-5 |
-2-25 |
Here the middle argument is OTO, column (a) shows the prepared arguments obtained by subtracting OTO and dividing by « = 0-04. The phase is (OTl - OTO) +- O-Oi = 0-25.
Column (6) gives the numbers x-a, x+a, etc. for formula (1). Thus we have (treating the tabular values as integers),
364 655'50 OT875
362 598-25 3647 38-99 2-1875
358 702-30 3647 38-41 ...9-31 6-1875
The first column is formed by formula (1) thus, for example.
364 555-50 =
397 350 266 172
After this we use (2) thus.
--25
•75
-+1.
364 73841=®’“““-“ 6
358 702-30 6-1875 , '
Finally we obtain Z (0-11 1 0-6) = 0-0364 739, which is correct to 7 places.*
M Zeta Function of Jacobi, Proc. Roy. Soc., Edinburgh,
(iyo2), p. 2So.
INTERPOLATIOlSr
81
3-82]
If the number of data be odd but symmetrical, Aitken has devised several methods founded on iteration, but it is actually simpler to retain one method and annex an extra tabular value. For details the reader is referred to Aitken’s paper.*
3-83. Neville’s Process of Iteration. A somewhat different technique has been developed by Neville,*!* which has the advantage of finding a place in the iteration scheme for those derivates of the function of which the values may be known.
The essential point of the process consists in interpolation between consecutive entries in the columns, beginning at the centre and working outwards, new functional values being adjoined as required. The clustering of the interpolates round a central value leads to greater equality between the members of a column as the work progresses and avoids the necessity of any preliminary estimate of the number of tabular values required.
With the notation of 3-81 the process is indicated by the following scheme :
Argu- Funo-
raent Parts tion
a X- a
|
fix ; a, h) |
||||
|
h |
x-b |
a, 6, c) |
||
|
fix ; b, c) |
fix ; a, b, c, d) |
|||
|
c |
x-c |
u. |
/(*; |
bjCjd) /{x; a,b,c,d,e) |
|
fix ; c, d) |
fix ; b, c, d, e) |
|||
|
d |
x-d |
fi^l |
c, d, e) |
|
|
fix ; d, e) |
||||
|
e |
x-c |
(1)
Here it is convenient to write 3*81 (1) in the form x-a f(x ; b)
f{x ; a, h, c)
x-c f{x; b, c)
(c-a)
* he. cit. p. 76.
t E. H. Neville, in a paper read at the International Congress of Mathe- maticians, Zurich, 1932. This paper will be published in a commemoration volume of the Journal of the Indian Mathematical Society. Prof. Neville has kindly allowed me to use his MS. and upon this the present section is based.
INTERPOLATION
82
[3*83
in order that the '' parts ” may be identified as lying at the base of a triangle of which the interpolate is the vertex.
The process of course leads to the same interpolation polynomial as Aitken’s process when founded on the same arguments.
In the case of equal intervals the parts may be most conveniently treated by division with the tabular interval co.
Example. Find sin 0*25 from the values given below.
|
0-1 |
1-5 |
0-0998 |
2481-5 |
|
0-2 |
■1987 |
...73-6 2471 4-1 |
|
|
0-3 |
-•5 |
■2955 |
... 74-G 2485-5 |
|
04 |
-1-5 |
■3894 |
|
|
Here x = |
0-25, (0 = |
0-1; the |
parts are given in tlie second column. |
|
2471 |
•5 |
1987 |
.K 71 74-6 = |
|
-•5 |
2955 |
-1-5 85-5 |
sin 0*25 = 0*2474.
In order to introduce derivates into the scheme, we first notice that the interpolation polynomial /(a;; a, b) is given by
f{x; a, 6) = +
where [ah] is the divided difference of .
If a = 6, we have [aa] = Ua (see 1*8 (2) ) , and we can write
(2) f(x; a, a) Ua-b{x-a)Ua = f(x; a^) say.
Similarly, ita—b — c, we have
(3) f{x; a, a, a) = f{x ; a^) + (a; - af [aaa]
= f{x; a^) + (x-a)^ u'a = f{x ; a^) say.
These values can be calculated and introduced into Neville’s scheme in the appropriate columns. Suppose, for example, that we
3-83]
INTEBPOLATION
83
are given u^,, u'^. The scheme becomes, by repeating
the arguments,
a x-a
f(x; B?)
a x-a f(x; a^)
f(x; a2) J{x-,a?,h)
a x~a Ua f{x;a\b) f{x;a^,b,c)
fix; a, b) f{x ; a% b, c) f(x ; a*, b, c^)
b x-b u, f{x;a,b,c) f{x;a\h,d^)
fi^->b,c) f{x;a,b,c^)
c x-c
f(x; c2)
C x-c Uf.
The entries in heavy type are calculated from (2) and (3) and the interpolation proceeds by formula (1). Thus, for example,
fix; a?, b) =
x — a x-b
fix; a^) fix; a^, b)
~ib-a).
f{x ; a, b, c2) =
X-a
x~c
fix; a, b, c) fix; b, c2)
d- (c-a).
Example. Find sin 0-25 from the following table :
X sin X cos X
0-2 0-1987 0-9801
0-3 -2955 0-9553
We form /(0-25 ; 0-2^) = 2477-05, /(0-25; O-S^) = 2477-35, then 0-2 -5 1987
2477-05
•2 -5 1987 ...4.0
2471
•3 --5 2965 ...4.2
2477-35
- -5 2955
sin 0-25=0-2474.
-3
84
INTERPOLATION
[KX', III
EXAMPLES III
1. Find approxiniatelj the value of antilog 0-9763 452 given the table :
|
X |
antilog X |
|
0-95 |
8^9r2 509 |
|
•96 |
9^120 108 |
|
■97 |
9^3:i2 543 |
|
■98 |
9^549 926 |
|
■99 |
9^772 372 |
and discuss the limits of error. Calculate also antilog 0*9532 64 1 , and antilog 0-9873 256 (a) by Newton's formula, (b) by Aitkon's process.
2. The logarithms in Tables of n decimal places dilfer from
the true values by i 5 x at most. Hence shew that the
errors of logarithms of ^places obtained from the Tabh‘-s by interpolating to first and second differences cannot exceed ± 10“”+ c, and ± 10“” x (9/ 8) + e' respectively, e and e/ l)eing the errors due exclusively to interpolation.
[Smith's Prize.]
3. From the table
|
X |
Jx |
|
|
530^1 |
23-02 |
3901 |
|
540-1 |
23-24 |
0052 |
|
550-1 |
23-45 |
4211 |
|
560-1 |
23-66 |
6432 |
form a scheme of differences and calculate 7^^0-67459, 7040*67459, 7550-67469, in each case determining the limits of error.
4. If f{a) = Uq, /((X + co) = tij, prove the following formula for interpolation in the middle, or to halves ",
/(a + l-co) = [xwj - g ™ j
- + fat (^) ■
Obtain tbe general form of this result when the last difference used is
KX. Ill I
INTRRrOLA'l'rONr
5. Supply the values correspoading to x = O-iOi, -103, -105 in the following table :
X sin X
0*100 0*09983 3417
‘102 -10182 3224
•104 -10381 2624
•iOG *10580 1609
6. The following table gives values of the complete elliptic integral * E corresponding to values of m ( = F) :
|
m |
E |
|
0*00 |
1-5707 96327 |
|
*02 |
1-5629 12645 |
|
*04 |
1-5549 68546 |
|
•06 |
1-5469 62456 |
|
•08 |
1-5388 92730 |
Insert the values corresponding to m = 0*01, -03, *05, *07 and construct a corresponding table of E for k = 0*00, *01, *02, , *08.
7. Find expressions for the remainder term in Stirling’s formula when terminated with a difference of odd order, and in Bessel’s formula when terminated with a difference of even order.
8. Taking o) = 1, prove the central difference interpolation formula t
/(^)=/(0)+ v^(
s i ^ ^
X /"x-h ln- 1
} X fx+ ^s ~ 1 ^-1
s>/(0)
X fx+^n-^
9. Taking co = 1, prove the equivalence of the following opera- tions :
i>.u, = l(E^ + E
* L. M. Milne-Thomson, Proc, London Math. Soc. (2), 33 (1932), p. 163. t Steffenson, Interpolation^ p. 32.
86
INTEEPOLATION
iKX'. HI
10. Use tlie result of the last example to prove tliat the to'rms of the central difference formula of example 8 are obtained by expanding in ascending powers of S the exprovssiou
/l8+(l+iii=)*}'’/(0).
11. Find from the following data an approximate' value of log 212 :
log 210=2-322 2193 log 213 = 2-328 37‘K)
log 211=2-324 2825 log 214 = 2-330 -Ib’nS
and discuss the error term.
|
12. From the following table mately log F (|) : |
of logr(w.), |
d(‘t(‘nniiu’ |
|
|
n |
logr(n) |
n |
log r(«.) |
|
2 12 |
0-74556 |
iii |
0-18432 |
|
y 1"2 |
-55938 |
M 1 ‘J. |
-13165 |
|
i 1'2 |
-42796 |
\) 1 2 |
-08828 |
|
y‘-j |
-32788 |
1 0 |
-0526 1 |
13. If n radii vectores (n being an odd inti-ger) be drawn from the pole dividing the four right angles into equal parts, shew that an approximate value of a radius vector «<,, which makes an angle 0 with the initial line is
_ 1 ,^sin|n(G-a) n2j sin -1(0 -a)
where a, , are the angles which the n radii vectores make with the initial line.
CHAPTER IV
NUMERICAL APPLICATIONS OF DIFFERENCES
In this chapter we consider a few important applications of differences a-iid iifferpolation formulae, mostly of a numerical nature.
4*0. Differences when the Interval is Subdivided. Suppose that we ha,ve the difference scheme
|
§•« Mo |
||
|
and that we wisli to form the table u . j, u . o, ^l . jj, subdivided into ]() equal scheme will t>he.n read |
tlie central differences corresponding to , ti, 0, where the interval has been ])arts. The first two lines of the new |
|
|
Uq |
a- Mo |
d^UQ |
|
5«-05 |
05 |
|
|
M-l |
U .jL |
9“^ u .j |
|
We have du .05 = tc,i - u |
0, SO that from Bessel’s formula |
|
|
(1) . 05 = i\> u <1 ») |
\ 0 0 0 + KooU P-S |
The remaining first differences can be found in the same way. To form the second differences we have
87
88 NUMERICAL AURLICATIONS OE 1)1 FEKRENCES [-H)
Using Stirling’s formula., this gives
(2) rJoS^Mo- 4«¥..« S^«o+--
Similarly from
u -05
we obtain
u .Q5
and in a like manner
9^ Uq = i 0 0 "*^0 ”" * * * •
It will be noticed that division of the interval by 10 has the general effect of reducing the order of magnitude of tlie first, second,
third, differences in the ratios 10“-^
More generally, if we subdivide* the interval into a ])arts, we shall reduce the differences approximately in the ratios
4*1 . The Differences of a Numerical Table. The succ(‘ss of interpolation by the formulae of Chapter III in a numerical table of a function tabulated for equidistant values of the argument depends upon the remainder term becoming insignificant to the order of accuracy required. Since the remainder terra is proportional to a value of the derivate of a certain order of the funcf.ion, and the differences of this order are also proportional to values of this derivate, the practical conclusion is that the effect of the differences of a certain order shall become negligible. In the case of a poly- nomial of degree n, the (n-f-l)th order differences are zero ; in the case of other functions, or even in the case of a polynomial wlum the values are curtailed to a fewer number of figures than the full value for the arguments, the differences never attain the constant value f a* table in which it is proposed to interpolate
by differences it is therefore first requisite to ascertain at what stage
= w .2 - 3^0 ~ ,j,
“ 1 0^0 0 ii 0 0 00 — ... ,
application of the differences of the subdivided interval to ra'Cf oU Brituh
4-1] NUMERICAL APPLICATIONS OP DIFFERENCES 89
the effect of the differences become negligible, which can be done by actually forming the differences in question. Consider, for example, the following table of Jx.
|
X Jx |
A A^ |
X Jx |
A |
A^ A^ |
|
1000 31-02 2777 |
1010 31-780497 |
-8 |
||
|
10807 |
15729 |
0 |
||
|
1001 31-G3 8584 |
-7 |
1011 31-79 6226 |
-8 |
|
|
15800 -2 |
15*721 |
-tl |
||
|
1002 31-65 4384 |
-9 |
1012 31-81 1947 |
-7 |
|
|
15791 -f2 |
15714 |
-1 |
||
|
1003 31-67 0175 |
-7 |
1013 31-82 7661 |
-8 |
|
|
15784 - 1 |
15706 |
0 |
||
|
1004 31-68 5959 |
-8 |
1014 31-843367 |
-8 |
|
|
15776 0 |
15698 |
0 |
||
|
1005 31-70 1735 |
-8 |
1015 31-85 9065 |
-8 |
|
|
15768 0 |
15690 |
0 |
||
|
1006 31-71 7503 |
-8 |
1016 31-87 4755 |
-8 |
|
|
15760 + 1 |
15682 |
-fl |
||
|
1007 31-73 3263 |
-7 |
1017 31-89 0437 |
-7 |
|
|
15753 -2 |
15675 |
-1 |
||
|
1008 31-74 9016 |
-9 |
1018 31-906112 |
-8 |
|
|
15744 -f2 |
15667 |
-fl |
||
|
1009 31-764760 |
-7 |
1019 31-921779 |
-7 |
|
|
15737 - 1 |
15660 |
|||
|
1010 31-780497 |
-8 |
1020 31-93 7439 |
Here we see that the differences A ® do not vary much, while alternates in sign. Since the third order derivate of Jx has a positive sign, the fluctuation in sign of A ^ ni’ist be attributed to the fact that the values here given are only approximations to Jx. This suggests that we should investigate the nature of the fluctua- tions which will be introduced into the differences by an error in the tabulated functioE.
90 KUMERICAL APPLICATIONS OF DiFFFHFNCFS f.M
The effect of a single error x in an otherwises correct i ahhs is shewn in the following scheme :
|
Error |
/j |
.cC |
.1^ |
|||
|
0 |
X |
X |
||||
|
0 |
X |
X |
- Gx |
Gx |
||
|
0 |
X |
X |
-Zx |
- 4x* |
r KU |
j lar |
|
X |
-x |
■~-2x |
H~ 3ir |
+ Gx |
- lOu; |
- 2{Kr |
|
0 |
X |
-X |
— *1.7; |
-i r>x |
1 i5.r |
|
|
0 |
X |
- Gx |
0 a:
It will be noticed that the coeiBficients of th(‘ (‘rrors in Hie eoluiuu /I ” are the coefficients in binomial expansion of ( I ■ as is indetsl obvious from 2*5 (2).
If we replace the zeros in the above sclunuc b}^ ;/’j, j\>, j\,, x^,
we have for the sixth order difference opposite, to x t he expression
~ iCj- 6^2 + 153^3-- 2();r -1- Ibrj
In a table of approximations correct to a giv(*n nninber of figures the maximum error in a single tabular valiui is fO-b, the ta[)ular values being regarded as integers. The corresponding rnaxiinuni error in the sixth difference arises when the toTors a, re alt ernatidy + 0*5 and -0-5, the result then being Wdnui the
differences fluctuate in a way which cannot be aetamnied for by tliese considerations the presumption is that the t;al, Hilar values contain an error, the probable position of which is indicated approximab.dy as that entry which stands on the horizontal line opjiosite to the largest anomalous difference of even order.
Returning to the above table of Jx, we see tliat a knowledge of all the values in the column /J of the first entry in column /j and
+•1] NUMRRTUAL APPLICA'I'IONS OF DIFFERENCES 91
the eight-iigure value of KKMl, would enable us to reconstruct the table, by first (completing the column ^ and then the column Jx. Moreover, a knowledge of the last digit in the column Jx enables us to infer the valines in the column thus :
v'^ A
7
7
4 -7 0
•1 -9
1
5
provided tliat we subtract in the a-ppropriate directions and have prior knowItHlge of the a])])roxiinat(‘ magnitude of the numbers This ftict is oiten ustdul in d(‘t(‘rniining whether a printed table contains errors otluu- than thos(‘ in the hist digit. For we can rapidly form the difhu’cncfhs j “ (or a higher ord(n’,if necessary) by differencing the end digits in tlu^ maniK^r (h'seribed. We can then build up the table again, prtdhraiily on a,n adding machine, and compare the result with the original tabh\
4*2. Subtabulation. T1h‘ principle enunciated at the end of 4-1 can b(i (»m]>loyml in subta,hulation. Suppose a function to have been calculated at ccjual inbu'vals of the argument and let it be required to re< luee tlu* int(M-val to 1/10 of the original interval. The proljlem here is to obtain new values of the function for the phases
•], '2, dl, -4, *5, -6, 7, *8, -9.
Taking Besstd’s formula, in, t)m modified form if necessary (see 3*41), we have
ip + 1 ) P (p - 1) (p - 2) Mj,
where the phase p lias the above values and the remainder term is neglected. The formula has been written with the mean differences
14*2
92 NUMERICAL APPLICATIONS OF DIFFERENCES
doubled in order to avoid divisions by 2, The values of cotdii- cients of the differences are shewn in the following table :
|
T |
ipb-1) |
Uv+i)Hp-i) |
|
|
•1 |
- -0225 |
+ ■006 |
+ •0039 1875 |
|
•2 |
- -0400 |
+ •008 |
+ •0072 0000 |
|
•3 |
-•0525 |
+ •007 |
+ ■0096 6875 |
|
•4 |
- -0600 |
+ ^004 |
+ •0112 0000 |
|
•5 |
- -0625 |
•000 |
+ ■0117 1875 |
|
■6 |
- -0600 |
-•004 |
+ •0112 0000 |
|
•7 |
- -0525 |
-•007 |
+ •0096 6875 |
|
•8 |
- -0400 |
-•008 |
+ •0072 0000 |
|
•9 |
- -0225 |
-•006 |
+ •0039 1875 |
As we only want the last digit of each interpolate wc need only write down the two relevant figures of the products in (1), keeping one decimal as a guard. Those products which are negative can be made positive by the addition of 10*0. If wc add the resulting products for each value of p, keeping only the last two figures in the sum and then round off, we get the required end digits of the interpolates. The differences can then be formed and the 9 inter- polates built up by summation as described in 4*1, the initial first difference being obtained from 4*0 (1).
We shall illustrate the method by constructing the t.able of ^ given in 4-1 from the following data :
|
X |
A |
A^ |
A '' |
||
|
■Uq |
1000 |
31-62 2777 |
-792 |
||
|
157720 |
-1570 |
4-14 |
|||
|
% |
1010 |
31-78 0497 |
-778 |
||
|
156942 |
- 1546 |
+ 10 |
|||
|
“2 |
1020 |
31-93 7439 |
-768 |
From (1) we have for the first interpolate, regarded as an integer,
(2) 3162 277 7-0+1577 2-0 + 3 5-3 + 0-1
= 3163 858 4-4 = 3163 858 4.
4-2] NUMERICAL APPLICATIONS OP DIFFERENCES 93
Writing down only the figures in large type we have the following scheme in which the figures just obtained are in the horizontal line opposite the argument 1001.
|
EAA^ |
||||
|
1000 a b c d s |
7 |
1010 Cl s 7 -8 |
||
|
9 |
||||
|
1 7-0 2-0 5-3 0-1 i-i |
4 |
-7 |
1 7-0 4-2 4-8 0-1 6-1 6 -8 |
|
|
0 |
||||
|
2 7-0 4 0 2-8 0-1 3-9 |
4 |
-9 |
2 7-0 8-4 1-8 0-1 7-3 7 -7 |
|
|
1 |
4 |
|||
|
3 7-0 6-0 2-4 0-1 5-5 |
5 |
-7 |
3 7-0 2-6 1-2 0-1 0-9 1 -8 |
|
|
6 |
||||
|
4 7-0 8-0 4-2 0-1 9'3 |
9 |
-8 |
4 7-0 6-8 2-8 0-0 6-6 7 -8 |
|
|
6 |
8 |
|||
|
5 7-0 0-0 8-1 0-0 5-1 |
5 |
-8 |
5 7-0 1-0 6-6 0-0 4-6 5 -8 |
|
|
0 |
||||
|
6 7-0 2-0 4-2 9-9 3-1 |
3 |
-8 |
6 7-0 5-2 2-8 0-0 5-0 5 -8 |
|
|
0 |
2 |
|||
|
7 7-0 4-0 2-4 9-9 3-3 |
3 |
-7 |
7 7-0 9-4 1-2 9-9 7-5 7 -7 |
|
|
3 |
5 |
|||
|
8 7-0 6-0 2-8 9-9 5-7 |
G |
-9 |
8 7-0 3-6 1-8 9-9 2-3 2 -8 |
|
|
4 |
7 |
|||
|
9 7-0 8-0 5-3 9-9 0-2 |
0 |
-7 |
9 7'0 7-8 4-8 9-9 9-5 9 -7 |
|
|
7 |
0 |
|||
|
1010 |
7 |
-8 |
1020 9 |
In the above scheme the numbers in the columns a, b, c, d repre- sent the contributions of to the last figure of
the interpolate. The numbers under s are the sums of these contri- butions, two figures only, and the column E represents the rounded value of s. The columns refer in the same way to the
initial value We then form the differences as shewn. To form the leading first difference we have, from 4*0 (1),
3^.05 = 15807-4 = 15807.
We can therefore complete the required table in the manner described in 4*1. The theoretical value of the second difference
NUMERICAL APPLICATIONS OF BlFFI^RENi'KS [4.2
opposite the argument 1010 is by 4*0 (2) equal to - 7-78 or 8, which agrees with the value in the scheme and serves as a elu^ck. ft will be observed that the above process, if correctly |)eri\)rme.(i, nuist reproduce the exact value of
If we had continually to reproduce cahnilations of the typr^ (2) above, little would be gained by this procedure. It, is, how(‘ver, a simple matter to construct, once for all, tallies wliitdi give th(‘ two- figure numbers used in this process, for all values of tlu^ di ITt‘nuic(‘s which can arise. Such tables, with examples of their usi% are t o bo found in the Nautical Almanac, 1931. We may renmrk that in practice it is more convenient to arrange woi-k so that the additions, here shewn horizontally for conveuiencti of (‘X|)osition, are performed vertically.* The decimal points an% of cours«^, un- necessary, as in similar work of this kind.
Another method of subtabulation which lias been widely used consists in calculating by the formulae of 4*0 tlu‘ theon*tieal valiuxs of the differences of the interpolates in that differeiu‘.e column wlu^re the differences are small or constant. The practical object ion to tliis method is that small errors in a high order diifi'nuH'e ra{>idly a<‘(,‘umU“ late large errors in the functional values, so that a large number of useless figures have to be carried tlirough th(:‘ work and subse- quently discarded. If, however, the contribution of tln^ 1 bird crdcu’ difference in the original table be negligible, it is quite pra(‘ti(‘al to assume a constant value for the second ditT<u’eru‘v and rtqtaq tlui decimal figures of the interpolates, treating tlu^ original valu(\s as integers.
Thus in the example just considered for Jx, st-arf ing with a; = 1000, we have with the notations of 1*0, n(‘glecting tliird differences entirely,
(3) , , a.05 = 15807*325,
and if we take the constant value
(4) a'l = ri-o = 7'850,
we can build up by summation the values already obtaiiuni. The
* For an example of extensive interpolation in t.liia way, sec L. M. Milno- ThoiMoi^ 8tandmd Table of Square Roots (1929). This table woa iirsl formed as a ten-ngure table and was afterwards reduced to eight figures.
4*2] NITMEKICAL APPLICATIONS OP DIFFERENCES 95
value for ^ 1 010 will be reproduced exactly, since the value obtained
with the above differences is
Wq + 10 (-IS - -045 fxS- u^) + 45 x *01(rS = Uq+Su^ = u^.
We can then proceed to calculate and start again.
The work can, however, be made continuous by using a suitable second difference opposite %. Consider the scheme
-9 9.1
9.05 + 9 95
'ih ^
^ro5
which shews the end of the first calculation, to and the beginning of the next, to ^/o. If for x we put d\ we shall not in general produce the correct value of as given by the above method, for
9i.o5 - *1 - -045 = *1 - 4-5 dh,
d.Qr, *1 Stq ~ *045 yiS'^u^ = -1 - 4-5 9?^ .
But if w(^ put
X = 9i .05 — d.Qr^ — 9 9ri = i (95 + 9pi ) + ^\J { — 100 x -I (95 + di-i) } , we obtain the corr(‘ct value of 9i.o5 and the work can then proceed with the second constant 9i.i until we reach when the second difference opposite to u.y is again adjusted. The decimal figures introduced in this way are discarded when the tabulation is completed.
4*3. Inverse Interpolation. The problem of interpolation briefly stated consists of finding, from a table of the function, the value of the function which corresponds to a given argument. The problem of inverse interpolation is that of finding from the same table the argument corresponding to a given value of the function. Thus if y be a function of the argument x, given the table
Argmuent Function
Vi
^2 ^2
96 NUMERICAL APPLICATIONS OF DiPFKHKNCKS [4.3
we require the argument x corresponding to a given functional value y. A numerical table b)’' its nature determines a single- valued function of the argument but the inverse function may very well be many-valued.
ThuS; for example, a table of the function y h3 takes
the form
cc 0 1 2 3 4
y 3 0-1 0 3
and there are two arguments corresponding to y 0 (and in fact to every value of y). This simple example shows that care is needed in formulating a problem of the inverse ty])e which nuiy only Ixjcome determinate when the range of variation of tlic argument is in some way restricted.
A practical way of obtaining such n^striction is to form a rough estimate of the required result and to confine tlu^ argumcmts of the table to values in the neighbourhood of this estimate. Assuming then that a determinate problem has been formulated, we proetHnl to consider methods of obtaining the solution.
4'4. Inverse Interpolation by Divided Differences. The given table, by interchanging the roles of the argunuuit x and the
|
function y, becomes |
||
|
Argument |
Function |
|
|
2/1 |
||
|
[M2] |
||
|
2/2 |
lUi'Mh] |
|
|
yz |
1.72.73 1 ^3 |
where we have formed the divided differences
(?/, -■ 2^2), etc.
We then obtain
a: - *1 + (2/ - 2/i) [M2] + {y~ Vi) {y - y^ -f- ■ • • .
4*4] NUMEEICAL APPLICATIONS OP DIFFERENCES 97
where, if we stop at the divided difference the remainder
term is
iy-Vi) {y-Vi) — {y-y„) lyy-iy^ — y^-
This is a complete theoretical solution of the problem provided that we have some means of evaluating the remainder term or, in other words, of calculating the nth derivate of y with respect to x, or an equivalent process. In practice this may present difficulties. We can, however, estimate the suitability of the value of x by inter- polating the original table and seeing how far the result agrees with the given value of y.
Example. Calculate
dx
J.37 V (1 — x^) (^-f r
from the following table * of cn {u | |) .
|
cn(w| |
u |
|||
|
0-44122 |
1-2 |
-1-34048 |
||
|
•36662 |
1-3 |
-1-32066 |
-•132 |
--18 |
|
•29090 |
1-4 |
-1-30685 |
-•091 |
-•16 |
|
•21438 |
1-5 |
-1-29836 |
•055 |
|
|
•13736 |
1-6 |
The required integral is the inverse function cn"’^(*37 1 1). The divided differences regarding the left-hand column as the argument are shewn. We have, therefore, the value
1-2 + *07122 X 1*34048 + *07122 x *00338 x *132 + *07122 X *00338 x *07910 x *18 = 1*29550.
4*6. Inverse Interpolation by Iterated Linear Inter- polation. The iterative methods described in the last chapter
‘ Mhne-Thomson, Die elUptUohen FunJetionen von Jacohi, Berlin (1931).
98
NUMERICAL APPLICATIONS OF I>IFFEHENCKkS
[4-r,
(3-81, 3*83) are very well adapted to iriv<‘ns(? inter|)olatioii when several orders of differences have to taktni into account.. These methods do not depend on the argiimtu.it proca'eding by e(|ual steps, and hence we may interchange argument and fumdion in the same way as before and so arrive at t!ie requirtui result by the general (linear) iterative process.
IsTeville * has shewn that known derivates, at Ituist of tht‘ first two orders, can be conveniently employed by means of tlie formulae
dx ^ I dy d^x d-y / /dy y^
dy'^ / dx' dy^ dx^ / W/:r/ ’
We give the following example as worked by Aitkcn. |
Example. Find the positive root of the equation a;'7+28x^-480=:^0.
From a graph of y = 480 it is easily stuui that tlu^ root
is slightly beyond T9. We form the table given below and seek the value of X corresponding to y = 0.
|
y |
z |
||
|
-25-7140261 |
1-90 |
||
|
-14-6254167 |
1-91 |
2 3189586 |
|
|
- 3-3074639 |
1-92 |
2952228 |
28 82864 |
|
+ 8-2439435 |
1-93 |
2716929 |
87312 84138 |
|
+20-0329830 |
1-94 |
2483678 |
91702 17 5 |
Since y = 0 the left-hand column contains the the process. Thus
^*9^ -2571402(51
23189586 = .i. i K
1*91 - 146254107 ’
and so on. We obtain
oj = 1*922884153, which is correct to ten figures.
us(Hi in
KtSSOOlM,
* loo. ciU p. 81.
due to W. B. DavfcH, Kducatwnal Ti»M, (1924) 61 ' Wliittaker and Kobinson, Calculus of ObaervativKa,
4-6] NUMERICAL APPLICATIONS OP DIFFERENCES 99
4-6. Inverse Interpolation by Successive Approxima- tion. This widely employed method proceeds as follows. By linear interpolation a few figures of the argument are found, and the values of the function for this and one or two adjacent arguments are calculated. Using these functional values we find some more figures of the arg\imcnt, and then repeat the process until it ceases to yield figures different from those already obtained.
Exanifle. Find the value of m corresponding to j = 0-01 from the following table,* which gives values of the nome 5 as a function of the squared modulus lc“ = m.
|
m |
A A^ |
A^ |
A^ |
|
|
0-12 |
0-00798 89058 |
71 40944 |
||
|
•13 |
•00870 30002 |
82195 |
||
|
72 23139 |
1887 |
|||
|
•14 |
•00942 53141 |
84082 |
68 |
|
|
73 07221 |
1955 |
|||
|
•15 |
•01015 60362 |
86037 |
67 |
|
|
73 93258 |
2022 |
|||
|
•16 |
•01089 53620 |
88509 |
||
|
74 81317 |
||||
|
•17 |
•01164 34937 |
|||
|
As a first approximation |
||||
|
Using Gauss’ formula, we |
find |
|||
|
m |
||||
|
-14787 |
•00999 96780 |
|||
|
1 00 00 |
-01000 04112 |
The interval is now .1 / 1000 of the original interval, so that by
♦ L. M. Milne-TLomson, Journ, London Math* Soc*, 5, (1930), p. 148.
100 NUMERICAL APPLICATIONS OP DIFFERENCES [4-0
4-0 the second difference is negligible and we have, dividing 3220 by the new first difference 7332,
m = -14787 4392.
4‘7. Inverse Interpolation by Reversal of Series. The relation between the function y and the argument x, wliich is obtained from an interpolation formula by neglect of the remainder term, can be written in the form
y-2/i = + + «3 ?'■■’+ +«»?’”.
where j) = (x-x^) j is the phase.
This (finite) power series can be reversed in the form
where *
h — ^ h — /) — ■“
Q. — ^ .
Thus we have
y-yi “2 (y - Vi? ^ iW - «i«3) iy ~ yi?
Taking for example BesseFs formula and neglecting fourth order differences, we have
y-yi-p hi + \ if' - p) gS® yi + 1 (p® - 'ip^ -t- Ip) S® yi , and we therefore take
ai = (8-^-gS2+V.,S=>) 2/:., etj = (-|gS2 - .^S®) y. , = J,S» y, ,
and we then obtain p from (1).
The method is of limited application since the (^onvcu'geiu't* is often slow.
* For the first 12 coefficients, see C. .E. van Orntrand, Phil, Mag,, May 1908. A simple determinantal expression for the general coefficient in givt‘ri by M. Ward, Rendiconii di Palermo, liv (1930), p. 42, fSee also G. J. Lidstone,
51 (1918), p, 43. » .
4-7]
NUMERICAL APPLICATIONS OF DIFFERENCES 101
Example. Find an approximate value of cotliO-6 from tke following table.*
|
X |
coth~^ X |
A |
A^ |
A^ |
|
1*85 |
0-6049 190 |
-40908 |
||
|
1*86 |
•6008 222 |
- 40352 |
"F 616 |
-16 |
|
1*87 |
•5967 870 |
OQ7 rco |
+ 600 |
|
|
1*88 |
•5928 118 |
~ 6v 1 |
Taking = *6008 222, we have
2/ - yi = - 8222, - 40657, ag = 308, ag = - 2*7.
Substituting in (1), we get p = *20254.
Since co = *01 , we have therefore the approximation
coth0*6 = 1*862025.
EXAMPLES IV
If =/(^’-bI)“/(a:^), Zl/W =/(^’+ l0)-/(ic), shew
that
{i+Aiy^f(x) = (i+A)f{x),
and by means of this formula express the forward differences! off (x) for unit intervals in terms of the forward differences for interval 10.
2. Obtain corresponding formulae connecting the differences for intervals o) and wco, where m is a positive integer.
3. Obtain the central differences corresponding to one-fifth of the tabular interval in terms of the central differences for the whole interval
* L. M. Milne-Thomson, Atti del Cong, Iniernaz, d. Matematici, Bologna^ (1928), t. 2. p. 357.
fThis is essentially the problem of Briggs. See H. W. Turnbull, James Gregory ”, Proo, Edinburgh Math, Soc,y (2) 3 (1933), p. 166.
102
NUMERICAL APPLICATIONS OF DIFFERENCES [kx. iv
4. Obtain the table of Jx in 4-1 from the vahu\s of Jx at interval 10 by first halving the interval and tlum intcn'polatiiig to fifths.
|
5. Taking logarithms |
to seven figures |
at interval 10 in the |
|
neighbourliood of 350, find the logarithms |
at unit intervals from |
|
|
350 to 370. |
||
|
6. Find cosech 3-63 from the table of inverst^ values : |
||
|
X |
cosecn—u; |
. J“ |
|
0-052 |
3-6503341 |
3704 |
|
•053 |
3-6313121 |
3r)r»r) |
|
•054 |
3-6126467 |
3135 |
|
7. From the following table of inverse s(‘eaiits ealeulate |
||
|
sec 0-17856 : |
||
|
X |
sec“^a; |
.p |
|
1-015 |
0-1721329 |
1 962 |
|
1-016 |
0-1777050 |
1782 |
|
1-017 |
0-1830989 |
1 629 |
|
8. Calculate cosec 1-3957 from the following table of inverse |
||
|
cosecants : |
||
|
X |
coaccr^x |
.1^ |
|
1-016 |
1-3986634 |
19()3 |
|
1-016 |
1-3930913 |
1 TS1> |
|
1-017 |
1-3876974 |
1 0)29 |
|
1-018 |
1-3824664 |
1497 |
|
9. Check the value of i |
oo.sec~^ 1-016 ill (8) |
from the table : |
|
X |
cosec X |
|
|
1-393 |
1-0160 16(56 |
109 |
|
1-394 |
1-0158 3463 |
108 |
|
10. Check the value of t |
3ec-i 1-016 in (7) by means of the table : |
|
|
X |
sec® |
.p |
|
0-177 |
1-0158 7162 |
108 |
|
0-178 |
1-0160 5387 |
108 |
EX. iv] NUMEKICAL APPLICATIONS OF DIFFERENCES 11. Calculate cot~^ 2-9883 from tlie table :
|
X |
cot X |
|
0-320 |
3-0175980 |
|
-322 |
2-9975074 |
|
-323 |
2-9875522 |
|
-326 |
2-9580402 |
12. Prove that if the linear iterative process of 3-81 (p. 76) be applied to the divided differences
^’‘a-3
a-h ’ a-c ’ a-d ’ ’
the multipliers being b,c,d,..., the sequences obtained tend to the derivate u' (a). Investigate the remainder after n steps.
[Aitken.]
13. Prove that if the quadratic process of 3-82 (p. 78) be applied to the central divided differences
2a. ' 20 ’ 'Ac
the multipliers being a^ 6“, ..., the sequences tend to w'(0), and
that if Wj, be a polynomial of degree 2n+2 the value obtained in n steps is exact. [Aitken.]
14. Prove that if the multipliers used in Example 13 be 6^-0)^ c^-co“, the sequences tend to the subtabulated central divided difference {«„ - u_^) / 2o.
15. By means of the methods of Examples 12 and 13 above com-
pute the derivates at a: = 0-00, 0-10, of the function Z{x 1 0-6) from the tabular values given on p. 80. [Aitken.]
CHAPTER V
RECIPROCAL DIFFERENCES
5*0. The interpolation methods hitherto considered are founded on the approximate representation of the function to be inttupolated by a polynomial and the use of divided dilfercnces or the ecjuivahint formula of Lagrange. Reciprocal differences, introduced by Thiele,* lead to the approximate representation of a function by a rational function and consequently to a more general method of interpolation. In this chapter we shall consider a few of the most important pro- perties of Thiele^s reciprocal differences.
5'1. Definition of Reciprocal Differences. Let the values of a function f(x) be given for the values Xq, ... , of the
argument x. We shall for the present suppose that no two of these arguments are equal. The reciprocal difference of f{x), of arguments Xq, cCj, is defined by f
(1)
pK^i)
which is the reciprocal of the divided difference The re- ciprocal difference of three arguments thrflned by
(2)
P2 (^0^1^2)
. ... ''o +/(:, ).
p(xoa:i)-p(cr^a:.)
*T. N. Thiele, Inter'polationsrechmmg, Leipzig, 1900. 8ee also N. E. Nor- land, Differenzeyirechnung, Berlin, 1924.
fThe order of the arguments within the brtujkots is immatt^rial, for it will be shewn in 54 that reciprocal differences, like divided diih’imwm, are symmetrical in all their arguments.
104
KECIPROCAL DIFFERENCES
105
5*1]
We have here denoted the order by a suffix, since P2(^o%^2) is not formed by a repetition of the operation denoted by p. The operator p does not obey the index law, neither is the operator distributive, that is to say, the reciprocal difference off{x)-^g(x) is not equal to the sum of the reciprocal differences otf(x) and g{x).
Proceeding to reciprocal differences of four arguments we define
(3)
P3(^0^1^2^3)
P2 (^o%^2) P2 (%^2^3)
+ 9(x^x^)
and generally when we have defined reciprocal differences of n argu- ments we define reciprocal differences of n+1 arguments by the relation
(4)
Pn-l (^0^1 • * • ^n-l) ■“ P«-i {^1^2 * * • ^n)
+ pn-2(^1^2 *•'
Comparing this with (1), we see that
(5) Pn (^0^1^2 * • * ^rt) ~ 9 Pn~l (^0^1 * * * ^n-l) + Pn-2 {^1^2 * * ’
Reciprocal differences may be exhibited in a difference scheme as follows :
|
^0 |
/(S^o) |
p(2?0^l) |
||
|
/(a^i) |
p (XjX^) |
P2 (^0^1^2) |
P3 (XQX2X2X2) |
|
|
P2i^^2^z) |
||||
|
P (^2%) |
P3 (^1^2^3^4) |
|||
|
/(a%) |
P2 (^2^3^4) |
• |
RECIPBOCAL DIFFERENCES
106
[5-1
As aa example, the following table shews reciprocal differences of 1/(1 + a;^) :
X
i
1 + x^
0 1
1 i
2 i
3 tV
4 jV
5
P
-2
-10
4 4 2 0'
P2 P3 p4
-1
0
— 1
lor
40
140
— 1 Iff-
0
0
This table exemplifies the fact that the reciprocal (lifferences of a certain order of any rational function are constant. In this case the differences of the fourth order have the constant value zero.
5*2. Thiele’s Interpolation Formula. If in the formulae of the last section we write x for Xq, we have successively,
^{xx^ = ^{XiX^) +
X — X^
^i[xXiX^) -f(x])'
(?^{xXiX^ = I?^{x^x^^ +
x-x^
g^{xx^x^^)-
x-x^
P^{XX^X^^X^) - ^z{:XyX.^X.i) ’
^^{XXiX^X^i) = +
x-x.
P5(^^l*2*3*4®5) P3(^1^2*3^4)
TiiTis we have fox f{x) the continued fraction
RECIPROCAL DIFPE: INCES
07
<Nr
* O. Perron, Die, LeJire von den Kettenbriichen, Leipzig, 1929, § 42.
108
RECIPROCAL DIFFERENCES
[5‘2
we obtain a rational function, expressed in the form of a partial fraction, which agrees in value with f{x) at the points a?!, x^, x^, Xq.
It- folio TO that Thiele’s formula gives us a method of obtaining a rational function which agrees in value with a given function at any finite number of prescribed points.
Example. Determine tan 1-5685 from the following table * :
|
X |
tan X |
Pi |
P2 |
|
1-566 |
208-49128 |
0-000018208313 |
|
|
1-567 |
263-41125 |
10615733 |
- 0-00382 |
|
1-568 |
357-61106 |
05023108 |
•00276 |
|
1-569 |
556-69098 |
01430462 |
•00178 |
|
1-570 |
1255-76559 |
The required value is
357-61106+
-000005023108 +
=357-61106 +