Menu
Introduction
Author's Description
Publisher
Table of Contents
Index
Discussion Area
Acknowledgements
Resources
Links

Updated Table of Contents


Download in PDF Format



1 FOUNDATIONS OF COMPUTATION 1
1.1 Introduction 1
1.2 Representations of Numbers 2
1.2.1 Integers 3
1.2.2 Rational Numbers and Real Numbers 14
1.2.3 Representations of Numbers as Text 17
1.2.4 Exercises for Section 1.2 20
1.3 Finite Floating-point Representations 21
1.3.1 Simple Cases 21
1.3.2 Practical Floating-point Representations 25
1.3.3 Approaching Zero or In.nity Gracefully 28
1.3.4 Exercises for Section 1.3 30
1.4 Floating-point Computation 31
1.4.1 Relative Error; Machine Epsilon 31
1.4.2 Rounding 32
1.4.3 Floating-point Addition and Subtraction 35
1.4.4 Exercises for Section 1.4 36
1.5 Propagation of Errors 37
1.5.1 General Formulas 37
1.5.2 Examples of Error Propagation 39
1.5.3 Estimates of the Mean and Variance 41
1.5.4 Exercises for Section 1.5 43
1.6 Bibliography and Endnotes 45
1.6.1 Bibliography 45
1.6.2 Endnotes 46

2 SETS AND MAPPINGS 47
2.1 Introduction 47
2.2 Basic De.nitions 49
2.2.1 Sets 49
2.2.2 Mappings 53
2.2.3 Axiom of Choice 62
2.2.4 Cartesian Products 62
2.2.5 Equivalence and Equivalence Classes 65
2.2.6 Exercises for Section 2.2 67
2.3 Union, Intersection and Complement 68
2.3.1 Unions of Sets 68
2.3.2 Intersections of Sets 69
2.3.3 The Relative Complement 70
2.3.4 De Morganís Laws 71
2.3.5 Exercises for Section 2.3 71
2.4 In.nite Sets 72
2.4.1 Basic Properties of In.nite Sets 72
2.4.2 Induction and Recursion 73
2.4.3 Countable Sets 76
2.4.4 Countable Unions and Intersections 77
2.4.5 Uncountable Sets 78
2.4.6 Exercises for Section 2.4 80
2.5 Ordered and Partially Ordered Sets 82
2.5.1 Partial Orderings 82
2.5.2 Orderings; Upper and Lower Bounds 83
2.5.3 Maximal Chains 84
2.5.4 Exercises for Section 2.5 84
2.6 Bibliography 85

3 EVALUATION OF FUNCTIONS 86
3.1 Introduction 86
3.2 Sensitivity and Condition Number 86
3.2.1 De.nitions 86
3.2.2 Evaluation of Polynomials 87
3.2.3 Multiple Roots of Polynomials 89
3.2.4 Exercises for Section 3.2 91
3.3 Recursion and Iteration 92
3.3.1 Finding Roots by Bisection 92
3.3.2 The Newton-Raphson Method 92
3.3.3 Evaluation of Series 95
3.3.4 Exercises for Section 3.3 97
3.4 Introduction to Numerical Integration 99
3.4.1 Rectangle Rules 101
3.4.2 Trapezoidal Rule 102
3.4.3 Local and Global Errors 102
3.4.4 Exercises for Section 3.4 105
3.5 Solution of Di.erential Equations 106

3 CONTENTS
3.5.1 Eulerís Method 107
3.5.2 Truncation Error of Eulerís Method 109
3.5.3 Stability Analysis of Eulerís Method 111
3.5.4 Selected Finite-Di.erence Methods 112
3.5.5 Exercises for Section 3.5 118
3.6 Bibliography 120

4 GROUPS, RINGS AND FIELDS 121
4.1 Introduction 121
4.2 Groups 122
4.2.1 Axioms 122
4.2.2 Two-Element Group 127
4.2.3 Orbits and Cosets 130
4.2.4 Cyclic Groups 136
4.2.5 Dihedral Groups 141
4.2.6 Cubic Groups 143
4.2.7 Continuous Groups 143
4.2.8 Classes of Conjugate Elements 147
4.2.9 Exercises for Section 4.2 149
4.3 Group Homomorphisms 152
4.3.1 De.nitions and Basic Properties 152
4.3.2 Normal Subgroups 158
4.3.3 Direct Product Groups 162
4.3.4 Exercises for Section 4.3 164
4.4 *Symmetric Groups 165
4.4.1 Permutations 165
4.4.2 Cayleyís Theorem 167
4.4.3 Cyclic Permutations 169
4.4.4 Even and Odd Permutations 171
4.4.5 Exercises for Section 4.4 173
4.5 Rings and Integral Domains 175
4.5.1 Axioms and Examples 175
4.5.2 Basic Properties of Rings 179
4.5.3 Rational Numbers 180
4.5.4 *Ring Homomorphisms 181
4.5.5 Exercises for Section 4.5 184
4.6 Fields 184
4.6.1 Axioms and Examples 184
4.6.2 *Galois Fields 186
4.6.3 Exercises for Section 4.6 189
4.7 Bibliography 189

5 VECTOR SPACES 191
5.1 Introduction 191
5.2 Basic De.nitions and Examples 193
5.2.1 Axioms for a Vector Space 193
5.2.2 Selected Realizations of the Vector-Space Axioms 194
5.2.3 Vector Subspaces 201
5.2.4 *Comments on Vector-Space Axioms 205
5.2.5 Exercises for Section 5.2 208
5.3 Linear Independence and Linear Dependence 211
5.3.1 De.nitions 211
5.3.2 Basic results on Linear Dependence 212
5.3.3 Examples of Linear Independence 216
5.3.4 Exercises for Section 5.3 219
5.4 Bases and Dimension 221
5.4.1 Dimension of a Vector Space 221
5.4.2 Selected Realizations of Vector-Space Bases 225
5.4.3 Vector-Space Isomorphisms 228
5.4.4 Gaussian Elimination and Linear Dependence 232
5.4.5 Exercises for Section 5.4 237
5.5 Complementary Subspaces 239
5.5.1 Vector Complements and Direct Sums 239
5.5.2 De.nition of Complementary Subspaces 240
5.5.3 Dimensions of Complementary Subspaces 241
5.5.4 Direct Sums of Vector Spaces 242
5.5.5 Bases of Complementary Subspaces 243
5.5.6 Examples of Direct Sums of Vector Spaces 244
5.5.7 Exercises for Section 5.5 245
5.6 Bibliography and Endnotes 246
5.6.1 Bibliography 246
5.6.2 Endnotes 246

6 LINEAR MAPPINGS I 248
6.1 Linear Mappings and their Matrices 248
6.1.1 Basic Properties 248
6.1.2 Matrix of a Linear Mapping 250
6.1.3 Computation of Matrix Products 261
6.1.4 Invariant Subspaces and Direct Sums 263
6.1.5 Other examples of Linear Mappings 265
6.1.6 Exercises for Section 6.1 268
6.2 Nonsingular Linear Mappings 271
6.2.1 De.nitions and Basic Properties 271
6.2.2 Change of Basis 275
6.2.3 Permutation Matrices 277
6.2.4 General Linear Group of a Vector Space 278
6.2.5 Exercises for Section 6.2 278
6.3 Singular Linear Mappings 281
6.3.1 Singularity and Linear Dependence 281
6.3.2 Visualization of Singular Linear Mappings 282
6.3.3 Null space of a linear mapping 283
6.3.4 Other Examples of Singular Linear Mappings 285
6.3.5 Exercises for Section 6.3 287
6.4 Introduction to Digital Filters 288
6.4.1 De.nitions 288
6.4.2 Noise Ampli.cation by Digital Filters 291
6.4.3 Di.erence Operators 292
6.4.4 Exercises for Section 6.4 298
6.5 Trace and Determinant 299
6.5.1 Trace of a Linear Mapping 299
6.5.2 Determinants 300
6.5.3 Exercises for Section 6.5 309
6.6 Solution of Linear Equations 310
6.6.1 Basic Facts about Linear Equations 310
6.6.2 Matrix Formulation of Gaussian Elimination 312
6.6.3 Computational Aspects of Gaussian Elimination 317
6.6.4 The LU and LDMT Decompositions 317
6.6.5 Bases of the Range and Null Space 319
6.6.6 Rank-nullity Theorem 321
6.6.7 Exercises for Section 6.6 322
6.7 Complements of Null Space 324
6.7.1 Quotient Space V/null [A] 324
6.7.2 Isomorphism of the Range to a Complement of the Null Space 325
6.7.3 Rank-nullity Theorem (Again) 327
6.7.4 Right Inverses of a Linear Mapping 327
6.7.5 Examples of Right Inverses 328
6.7.6 Exercises for Section 6.7 330
6.8 Bibliography 330

7 LINEAR FUNCTIONALS 331
7.1 Motivation for Studying Functionals 331
7.2 Dual Spaces 332
7.2.1 De.nitions 332
7.2.2 Range and Null Space of a Linear Functional 334
7.2.3 Exercises for Section 7.2 335
7.3 Coordinate Functionals 336
7.3.1 De.nitions 336
7.3.2 Coordinate Functionals on Fn 337
7.3.3 Isomorphism ofV* to V 338
7.3.4 Coordinate Functionals on Two-Dimensional Euclidean Space 339
7.3.5 Coordinate Functionals and the Reciprocal Lattice 341
7.3.6 Isomorphism of V to V** 345
7.3.7 Exercises for Section 7.3 346
7.4 Annihilator of a Subspace 347
7.4.1 De.nitions 347
7.4.2 Bases of the Annihilator 347
7.4.3 Exercises for Section 7.4 348
7.5 Other Realizations of Dual Spaces 349
7.5.1 Dual space of C 349
7.5.2 Dual of FZ+ 349
7.5.3 Boundary and Initial Conditions for Di.erential Equations 349
7.6 Polynomial Interpolation 350
7.6.1 Lagrangian Interpolation 350
7.6.2 Exercises for Section 7.6 352
7.7 Tensors 352
7.7.1 De.nitions and Basic Properties 353
7.7.2 Components of Second-Rank Tensors 356
7.7.3 Tensor Products of Vectors 358
7.7.4 Tensors of Rank m 361
7.7.5 Linear Mappings of Tensors 362
7.7.6 Exercises for Section 7.7 365

8 INNER PRODUCTS AND NORMS 367
8.1 Inner-product spaces 367
8.1.1 De.nitions 367
8.1.2 Canonical Inner Products 369
8.1.3 Metric Tensor 372
8.1.4 Inde.nite Inner Products 378
8.1.5 Orthogonality 379
8.1.6 Exercises for Section 8.1 383
8.2 Geometry of Inner-Product Spaces 384
8.2.1 Pythagorasís Theorem 384
8.2.2 Orthonormal Bases 392
8.2.3 Orthogonal Polynomials 397
8.2.4 Exercises for Section 8.2 403
8.3 Projection Methods 406
8.3.1 Projection of a Vector onto a Subspace: De.nition 406
8.3.2 Orthogonal Projectors 407
8.3.3 Orthogonal Complement 409
8.3.4 Exercises for Section 8.3 416
8.4 Least-squares Approximations 417
8.4.1 Motivation 417
8.4.2 Abstract Formulation 418
8.4.3 Inequalities for Least-squares Approximations 419
8.4.4 Approximation by Finite Fourier Sums 420
8.4.5 Chebyshev Approximations 421
8.4.6 Mapping a Function to its Fourier Coe.cients 422
8.4.7 Exercises for Section 8.4 423
8.5 Discrete Fourier Transform 424
8.5.1 Approximation of Fourier Coe.cients 424
8.5.2 Discrete Fourier Basis 425
8.5.3 Periodic Extension 428
8.5.4 Aliasing 430
8.5.5 Sampling Theorem and Alias Mapping 433
8.5.6 Exercises for Section 8.5 437
8.6 Volume of an m-Parallelepiped 437
8.6.1 Parallelepipeds 437
8.6.2 Recursive De.nition of Volume 438
8.6.3 Volume as a Determinant 438
8.6.4 Determinant as a Volume Ratio 440
8.6.5 Jacobian Determinant 441
8.6.6 Exercises for Section 8.6 443
8.7 Vector and Matrix Norms 443
8.7.1 Vector Norms 443
8.7.2 Norm of a Linear Mapping 446
8.7.3 Matrix Norms 450
8.7.4 Norm of an Integral 453
8.7.5 Exercises for Section 8.7 453
8.8 Inner Products and Linear Functionals 455
8.8.1 Introduction 455
8.8.2 Inner-product Mapping 456
8.8.3 Inverse Inner-product Mapping 459
8.8.4 Exercises for Section 8.8 464
8.9 Bibliography and Endnotes 464
8.9.1 Bibliography 465
8.9.2 Endnotes 465

9 LINEAR MAPPINGS II 466
9.1 Dyads 466
9.1.1 Motivation 466
9.1.2 De.nition of a Dyad 466
9.1.3 Dyadic Expansions 469
9.1.4 Resolutions of the Identity Mapping 471
9.1.5 Exercises for Section 9.1 473
9.2 Transpose and Adjoint 473
9.2.1 Transpose 473
9.2.2 Adjoint 476
9.2.3 Other Realizations of the Adjoint 480
9.2.4 Properties of the Adjoint 483
9.2.5 Hermitian and Self-adjoint Mappings 485
9.2.6 Isometric and Unitary Mappings 487
9.2.7 Exercises for Section 9.2 491
9.3 Eigenvalues and Eigenvectors 493
9.3.1 Secular Equation 493
9.3.2 Diagonalization of Hermitian Matrices 495
9.3.3 Normal Linear Mappings 502
9.3.4 Exercises for Section 9.3 504
9.4 Singular-Value Decomposition 507
9.4.1 Derivation of the Singular-Value Decomposition 507
9.4.2 Matrix Version of the Singular-Value Decomposition 509
9.4.3 The Fundamental Subspaces of a Linear Mapping 511
9.4.4 Inverse and Pseudo-inverse in the SVD 512
9.4.5 Data Compression Using the SVD 514
9.4.6 Exercises for Section 9.4 514
9.5 Linear Equations II 515
9.5.1 Numerical Versus Analytical Methods 515
9.5.2 Diagonal Dominance 516
9.5.3 Condition Number of the Linear-equation Problem 517
9.5.4 The LDLÜ and Cholesky decompositions 520
9.6 Selected Applications of Linear Equations 521
9.6.1 The Linear Least-squares Problem 521
9.6.2 Linear Di.erence Equations 523
9.6.3 Solution of Tridiagonal Systems 529
9.6.4 Exercises for Section 9.6 530
9.7 Bibliography 531

10 CONVERGENCE IN NORMED VECTOR SPACES 532
10.1 Metrics and Norms 532
10.1.1 Metric Spaces 532
10.1.2 Normed Vector Spaces 534
10.1.3 Examples of Metric and Normed Vector Spaces 536
10.1.4 Open Sets 539
10.1.5 Exercises for Section 10.1 541
10.2 Limit Points 543
10.2.1 Limit Points and Closed Sets 543
10.2.2 Dense Sets and Separable Spaces 548
10.2.3 Exercises for Section 10.2 552
10.3 Convergence of Sequences and Series 553
10.3.1 Convergence of Sequences 553
10.3.2 Numerical Sequences 558
10.3.3 Numerical Series 560
10.3.4 Exercises for Section 10.3 565
10.4 Strong and Pointwise Convergence 566
10.4.1 Strong Convergence 566
10.4.2 Operators 570
10.4.3 Sequences of Real-valued Functions 572
10.4.4 Series of Real-valued Functions 575
10.4.5 Exercises for Section 10.4 576
10.5 Continuity 577
10.5.1 Pointwise Continuity 577
10.5.2 Uniform Continuity 580
10.6 Best Approximations in the Maximum and Supremum Norms 581
10.6.1 Best Approximations in the Maximum Norm 583
10.6.2 Best Approximations in the Supremum Norm 589
10.6.3 Exercises for Section 10.6 592
10.7 Hilbert and Banach Spaces 594
10.7.1 Survey of Complete Metric Vector Spaces 594
10.7.2 Complete Orthonormal Sets 597
10.7.3 Orthogonal Series 599
10.7.4 Practical Aspects of Fourier Series 603
10.7.5 Orthogonal-polynomial Expansions 610
10.7.6 Exercises for Section 10.7 613
10.8 Bibliography 615

11 GROUP REPRESENTATIONS 616
11.1 Preliminaries 616
11.1.1 Background 616
11.1.2 Symmetry-adapted Functions 618
11.1.3 Partner Functions 619
11.1.4 Exercises for Section 11.1 621
11.2 Reducibility of Representations 621
11.2.1 Invariant Subspaces and Irreducibility 622
11.2.2 Schurís Lemma 623
11.2.3 Eigenvectors of Invariant Operators 627
11.2.4 Exercises for Section 11.2 629
11.3 Unitarity and Orthogonality 630
11.3.1 Consequences of the Rearrangement Theorem 630
11.3.2 Unitary Representations 631
11.3.3 Orthogonality Theorems 633
11.3.4 Product Relation for Characters 638
11.3.5 Reduction of Unitary Representations 640
11.3.6 Construction of Character Tables 643
11.3.7 Characters of Kronecker Products 644
11.3.8 Exercises for Section 11.3 646
11.4 Two-dimensional rotation group 647
11.4.1 Representation space for SO(2) 648
11.4.2 Representations of SO(2) 649
11.4.3 Completeness Relation for e.imŤ 650
11.4.4 Exercise for Section 11.4 652
11.5 Symmetry and the One-dimensional Wave Equation 652
11.5.1 Boundary Conditions and Symmetry 652
11.5.2 Wave Equation for a Vibrating String 653
11.5.3 Boundary Conditions for the One-dimensional Wave Equation 653
11.5.4 Form Invariance of the Wave Equation 653
11.5.5 Invariance of the Wave Equation under Translations 656
11.5.6 Invariance of the Wave Equation under Lorentz Transformations 656
11.5.7 DíAlembertís Solution of the Wave Equation 657
11.5.8 Solution for a String of In.nite Length 658
11.5.9 Solution for a String of Finite Length 659
11.5.10 Exercises for Section 11.5 661
11.6 Discrete Translation Groups 662
11.6.1 Motivation 662
11.6.2 Invariance Under the Discrete Translation Group 662
11.6.3 Discrete-shift-invariant Digital Filters 663
11.6.4 Representations of the Discrete Translation Group 664
11.6.5 Discrete-time Transfer Function 665
11.6.6 Exercises for Section 11.6 668
11.7 Continuous Translation Groups 669
11.7.1 Translation Group of the Real Line 669
11.7.2 Irreducible Representations of T (R) 669
11.7.3 Ý  as Momentum Eigenfunctions 671
11.7.4 Representation of T(E2) Carried by Ýk 672
11.7.5 Translation Group of Euclidean n-space 673
11.7.6 Exercises for Section 11.7 676
11.8 Fourier transforms 676
11.8.1 Fourier Transform in One Dimension 676
11.8.2 Completeness Relation for the Ýk 677
11.8.3 Fourier Transforms in n-dimensional Euclidean Space 678
11.8.4 Poisson sum formula 679
11.8.5 Exercises for Section 11.8 679
11.9 Linear, Shift-invariant Systems 680
11.9.1 Continuous-time-shift Invariance 680
11.9.2 Continuous-time Transfer Function 681
11.9.3 Exercises for Section 11.9 682
11.10Two-dimensional Euclidean Group E(2) 682
11.10.1 Representation of E(2) Carried by Ýk 684
11.10.2 Discussion 684
11.10.3 Exercises for Section 11.10 685
11.11Bibliography 685

12 SPECIAL FUNCTIONS 686
12.1 Group Theory and Special Functions 686
12.1.1 Separation of Variables 686
12.1.2 Special Functions as Matrix Elements 687
12.1.3 Symmetries of the Helmholtz Equation 687
12.1.4 Exercise for Section 12.1 690
12.2 De.nition of the Bessel Functions 690
12.2.1 Fourier Expansion of a Plane Wave 690
12.2.2 De.nition of the Bessel Function Jm of Integer Order 692
12.2.3 Jacobi-Anger expansion 692
12.2.4 Frequency Content of an FM Signal 694
12.2.5 Exercises for Section 12.2 694
12.3 Bessel-function addition formulas 695
12.3.1 Exercises for Section 12.3 698
12.4 Bessel Raising and Lowering Operators 698
12.4.1 Recurrence Relations 698
12.4.2 Raising and Lowering Operators for Jm 700
12.4.3 Raising and Lowering Operators for the Helmholtz functions 700
12.4.4 Exercises for Section 12.4 701
12.5 Bessel Di.erential Equations 701
12.5.1 Besselís Di.erential Equation 701
12.5.2 The Helmholtz Equation in Two Dimensions 702
12.5.3 Qualitative Behavior of Jm 702
12.5.4 Exercises for Section 12.5 704
12.6 Orthogonal Series in Jn 704
12.6.1 Boundary Conditions that Ensure Self-adjointness 704
12.6.2 Orthogonality Relations 708
12.6.3 Fourier-Bessel Series 709
12.6.4 Exercise for Section 12.6 711
12.7 Vibrations of a Drumhead 711
12.7.1 Exercise for Section 12.7 713
12.8 Power Series for Jm 713
12.8.1 Derivation using Raising and Lowering Operators 713
12.8.2 Properties Deduced from the Power Series 715
12.8.3 Exercises for Section 12.8 715
12.9 Completeness Relations using Jn 716
12.10Bibliography 718

A INDEX OF NOTATION 719
A.1 Quanti.ers and Other Logical Symbols 719
A.2 Sets and Mappings 719
A.3 Vector Spaces, Linear Mappings and Matrices 720
A.4 Norms and Inner Products 721
A.5 Functions 721
A.5.1 General Notation for Functions 721
A.5.2 Special Functions 722
A.6 Probability 722

B AFFINE MAPPINGS 723
B.1 A.ne Group of a Vector Space 723
B.2 Coordinate Transformations 726
B.2.1 Active Transformations 727
B.2.2 Passive Transformations 727
B.2.3 Relation between Active and Passive Transformations 728
B.3 Exercises 728

C PSEUDO-UNITARY SPACES 730

D REMAINDER TERM 733

E BOLZANO-WEIERSTRASS THEOREM 735
E.1 Real Numbers 735
E.2 Finite-dimensional Hilbert Spaces 736

F WEIERSTRASS APPROXIMATION THEOREM 738