Numerical linear approximation in C

Numerical Linear Approximation in C......Page 4
Contents......Page 6
List of Figures......Page 18
Preface......Page 20
Warranties......Page 24
William A. Malek......Page 25
PART 1: Preliminaries and Tutorials......Page 27
1.1 Introduction......Page 29
1.2 Applications to social sciences and economics......Page 31
1.2.2 Annual teacher salaries......Page 32
1.2.3 Factors affecting survival of island species......Page 33
1.2.5 Examining factors affecting the mortality rate......Page 34
1.2.7 Factors affecting gross national products......Page 35
1.3.1 Windmill generating electricity......Page 36
1.3.2 A chemical process......Page 37
1.4.1 Smoothing of random noise in digital images......Page 38
1.4.2 Filtering of impulse noise in digital images......Page 40
1.4.3 Applications to pattern classification......Page 41
1.4.4 Restoring images with missing high-frequency components......Page 42
1.4.5 De-blurring digital images using the Ridge equation......Page 44
1.4.6 De-blurring images using truncated eigensystem......Page 45
1.4.7 De-blurring images using quadratic programming......Page 46
References......Page 49
Appendix D: Utilities and Common Functions......Page 0
2.1 Introduction......Page 51
2.2 Discrete linear approximation and solution of overdetermined linear equations......Page 52
2.3 Comparison between the L1, the L2 and the…......Page 56
2.4 Error tolerances in the calculation......Page 58
2.5 Representation of vectors and matrices in C......Page 59
2.6 Outliers and dealing with them......Page 60
2.6.1 Data editing and residual analysis......Page 62
References......Page 63
3.1 Introduction......Page 65
3.1.1 Exceptional linear programming problems......Page 67
3.2 Notations and definitions......Page 70
3.3 The simplex algorithm......Page 71
3.3.1 Initial basic feasible solution......Page 73
3.3.2 Improving the initial basic feasible solution......Page 74
3.4 The simplex tableau......Page 77
3.5.1 Phase 1......Page 81
3.5.3 Detection of the exceptional cases......Page 82
The dual problem......Page 83
3.6.1 Fundamental properties of the dual problems......Page 85
3.6.2 Dual problems with mixed constraints......Page 86
3.6.3 The dual simplex algorithm......Page 87
3.7.1 Degeneracy in the simplex method......Page 88
3.7.3 Resolving degeneracy resulting from equal thetamin......Page 89
3.8.1 Linear programming and the L1 approximation......Page 90
3.8.2 Linear programming and Chebyshev approximation......Page 92
3.9 Stability of the solution in linear programming......Page 93
References......Page 95
4.1 Introduction......Page 97
4.2.1 Vector norms......Page 98
4.2.3 Hermitian matrices and vectors......Page 99
4.2.4 Other matrix norms......Page 102
4.2.5 Euclidean and the spectral matrix norms......Page 103
4.2.6 Euclidean norm and the singular values......Page 104
4.2.7 Eigenvalues and the singular values of the sum and the product of two matrices......Page 105
4.2.8 Accuracy of the solution of linear equations......Page 106
4.3 Elementary matrices......Page 109
4.4 Gauss LU factorization with complete pivoting......Page 110
4.4.1 Importance of pivoting......Page 111
4.4.2 Using complete pivoting......Page 112
4.4.3 Pivoting and the rank of matrix A......Page 114
4.5.2 Householder's QR factorization with pivoting......Page 116
4.5.3 Pivoting in Householder's method......Page 118
4.5.4 Calculation of the matrix inverse A-1......Page 119
4.6 Gauss-Jordan method......Page 120
4.7.1 Normalized floating-point representation......Page 121
4.7.2 Overflow and underflow in arithmetic operations......Page 122
4.7.3 Arithmetic operations in a d.p. accumulator......Page 123
4.7.5 Arithmetic operations in a s.p. accumulator......Page 126
4.7.7 Extended simple s.p. operations in a d.p. accumulator......Page 127
4.7.9 More conservative error bounds......Page 130
4.7.10 D.p. summations and inner-product operations......Page 131
4.7.11 Rounding error in matrix computation......Page 132
4.7.12 Forward and backward round-off error analysis......Page 133
References......Page 135
PART 2: The L1 Approximation......Page 137
5.1 Introduction......Page 139
5.2 Linear programming formulation of the problem......Page 142
5.3 Description of the algorithm......Page 144
5.4 The dual simplex method......Page 146
5.5 Modification to the algorithm......Page 150
5.6 Occurrence of degeneracy......Page 152
5.7 A significant property of the L1 approximation......Page 155
5.8 Triangular decomposition of the basis matrix......Page 156
5.9 Arithmetic operations count......Page 158
5.10 Numerical results and comments......Page 160
References......Page 163
5.11 DR_L1......Page 166
5.12 LA_L1......Page 171
5.13 DR_Lone......Page 191
5.14 LA_Lone......Page 196
6.1 Introduction......Page 209
6.2 A special problem of a general constrained one......Page 212
6.3 Linear programming formulation of the problem......Page 213
6.4.1 Obtaining an initial basic feasible solution......Page 214
6.5 Numerical results and comments......Page 217
References......Page 219
6.6 DR_Loneside......Page 221
6.7 LA_Loneside......Page 229
7.1 Introduction......Page 239
7.2 A special problem of a general constrained one......Page 242
7.3 Linear programming formulation of the problem......Page 243
7.3.1 Properties of the matrix of constraints......Page 246
7.4 Description of the algorithm......Page 247
7.5 Numerical results and comments......Page 248
References......Page 249
7.6 DR_Lonebv......Page 251
7.7 LA_Lonebv......Page 259
8.1.1 Two basic issues......Page 271
8.1.2 Approaches for polygonal approximation......Page 272
8.1.3 Other unique approaches......Page 274
8.1.5 Direction of error measure......Page 275
8.1.6 Comparison and stability of polygonal approximations......Page 276
8.2 The L1 approximation problem......Page 277
8.3 Description of the algorithm......Page 278
8.4 Linear programming technique......Page 279
8.5 Numerical results and comments......Page 281
References......Page 283
8.6 DR_L1pol......Page 287
8.7 LA_L1pol......Page 293
9.1 Introduction......Page 301
9.2 Characteristics of the piecewise approximation......Page 302
9.3 The discrete linear L1 approximation problem......Page 304
9.4.1 Piecewise linear L1 approximation with pre-assigned tolerance......Page 305
9.4.2 Piecewise linear approximation with near-balanced L1 norms......Page 306
9.5 Numerical results and comments......Page 307
References......Page 310
9.6 DR_L1pw1......Page 311
9.7 LA_L1pw1......Page 315
9.8 DR_L1pw2......Page 320
9.9 LA_L1pw2......Page 324
PART 3: The Chebyshev Approximation......Page 331
10.1 Introduction......Page 333
10.1.1 Characterization of the Chebyshev solution......Page 335
10.2 Linear programming formulation of the problem......Page 336
10.2.1 Property of the matrix of constraints......Page 337
10.3 Description of the algorithm......Page 341
10.4 A significant property of the Chebyshev approximation......Page 346
10.5 Numerical results and comments......Page 347
References......Page 348
10.6 DR_Linf......Page 351
10.7 LA_Linf......Page 360
11.1 Introduction......Page 373
11.1.1 Applications of the algorithm......Page 375
11.2 A special problem of a general constrained one......Page 376
11.3 Linear programming formulation of the problem......Page 377
11.3.1 Properties of the matrix of constraints......Page 379
11.4 Description of the algorithm......Page 382
11.4.1 One-sided Chebyshev solution from below......Page 386
11.5 Numerical results and comments......Page 387
11.5.1 Simple relationships between the Chebyshev and one-sided Chebyshev approximations......Page 388
References......Page 389
11.6 DR_Linfside......Page 391
11.7 LA_Linfside......Page 399
12.1 Introduction......Page 413
12.2 A special problem of a general constrained one......Page 415
12.3 Linear programming formulation of the problem......Page 416
12.3.1 Properties of the matrix of constraints......Page 418
12.4 Description of the algorithm......Page 420
12.5 Numerical results and comments......Page 422
References......Page 423
12.6 DR_Linfbv......Page 425
12.7 LA_Linfbv......Page 434
13.1 Introduction......Page 445
13.1.2 Special cases......Page 447
13.2 A special problem of general constrained algorithms......Page 448
13.3 Linear programming formulation of the problem......Page 449
13.3.1 Properties of the matrix of constraints......Page 451
13.4 Description of the algorithm......Page 453
13.5 Triangular decomposition of the basis matrix......Page 454
13.6 Arithmetic operations count......Page 455
13.7 Numerical results and comments......Page 456
References......Page 458
13.8 DR_Restch......Page 461
13.9 LA_Restch......Page 472
14.1 Introduction......Page 495
14.2 The problem as presented by Descloux......Page 497
14.3 Linear programming analysis of the problem......Page 498
How to obtain the characteristic set R1......Page 499
14.3.2 Calculating matrix (DT)–1......Page 501
14.4 Numerical results and comments......Page 502
References......Page 505
14.5 DR_Strict......Page 507
14.6 LA_Strict......Page 515
15.1 Introduction......Page 543
15.3 The discrete linear Chebyshev approximation problem......Page 545
15.4.1 Piecewise linear Chebyshev approximation with pre-assigned tolerance......Page 546
15.5 Numerical results and comments......Page 547
References......Page 549
15.6 DR_Linfpw1......Page 551
15.7 LA_Linfpw1......Page 555
15.8 DR_Linfpw2......Page 560
15.9 LA_Linfpw2......Page 564
16.1 Introduction......Page 571
16.1.1 Linear programming techniques......Page 574
16.2 Pattern classification problem......Page 575
16.4 Linear one-sided Chebyshev approximation algorithm......Page 577
16.5 Linear one-sided L1 approximation algorithm......Page 578
16.6 Numerical results and comments......Page 579
References......Page 583
16.7 DR_Chineq......Page 586
16.8 DR_L1ineq......Page 592
PART 4: The Least Squares Approximation......Page 598
17.1 Introduction......Page 600
17.2 Least squares solution of linear equations......Page 601
17.2.1 Minimal-length least squares solution......Page 603
17.3.1 Gauss LU factorization......Page 604
17.3.2 Householder's factorization......Page 606
17.3.4 Classical and modified Gram-Schmidt methods......Page 607
17.4 Explicit expression for the pseudo-inverse......Page 608
17.4.2 A+ in terms of Householder's factorization......Page 609
17.5 The singular value decomposition (SVD)......Page 610
17.5.2 Main properties of the pseudo-inverse A+......Page 612
17.6.2 Solution of the normal equation......Page 613
17.6.5 Calculation of A+......Page 614
17.6.6 Influence of the round-off error......Page 615
17.7.1 Definitions, notations and related theorems......Page 616
17.7.2 Subspaces and their dimensions......Page 617
17.7.3 Gram-Schmidt orthogonalization......Page 619
17.7.4 Range spaces of A and AT and their orthogonal complements......Page 621
17.7.5 Representation of vectors in Vm......Page 623
17.7.6 Orthogonal projection onto range and null spaces......Page 624
17.8 Multicollinearity, collinearity or the ill-conditioning of matrix A......Page 626
17.8.1 Sources of multicollinearity......Page 628
17.8.2 Detection of multicollinearity......Page 629
17.9.1 Derivation of the principal components......Page 630
17.10 Partial least squares method (PLS)......Page 632
17.10.1 Model building for the PLS method......Page 634
17.11 Ridge equation......Page 637
17.11.1 Estimating the Ridge parameter......Page 638
17.12 Numerical results and comments......Page 639
References......Page 643
17.13 DR_Eluls......Page 646
17.14 LA_Eluls......Page 655
17.15 DR_Hhls......Page 670
17.16 LA_Hhls......Page 679
18.1 Introduction......Page 696
18.3 The discrete linear least squares approximation problem......Page 698
18.4 Description of the algorithms......Page 699
18.5 Numerical results and comments......Page 700
18.6 The updating and downdating techniques......Page 702
18.6.1 The updating algorithm......Page 703
18.6.2 The downdating algorithm......Page 704
References......Page 705
18.7 DR_L2pw1......Page 707
18.8 LA_L2pw1......Page 711
18.9 DR_L2pw2......Page 716
18.10 LA_L2pw2......Page 720
19.1 Introduction......Page 728
19.2 Solution of ill-posed linear systems......Page 729
19.3 Estimation of the free parameter......Page 733
19.4.1 Steps of the algorithm......Page 734
19.5.1 The parameters TOLER and EPS......Page 739
19.6 Use of linear programming techniques......Page 740
19.7 Numerical results and comments......Page 742
References......Page 745
19.8 DR_Mls......Page 749
19.9 LA_Mls......Page 755
PART 5: Solution of Underdetermined Systems Of Linear Equations......Page 761
20.1 Introduction......Page 763
20.1.1 Applications of the algorithm......Page 764
20.2 Linear programming formulation of the problem......Page 765
20.2.1 Properties of the matrix of constraints......Page 766
20.3 Description of the algorithm......Page 768
20.4 Numerical results and comments......Page 771
References......Page 772
20.5 DR_Fuel......Page 773
20.6 LA_Fuel......Page 779
21.1 Introduction......Page 788
21.2 Linear programming formulation of the two problems......Page 790
21.2.1 Properties of the matrix of constraints......Page 792
21.3.1 Occurrence of degeneracy......Page 794
21.4 Numerical results and comments......Page 795
References......Page 797
21.5 DR_Tmfuel......Page 799
21.6 LA_Tmfuel......Page 806
22.1 Introduction......Page 822
22.2 The linear programming problem......Page 824
22.2.1 Properties of the matrix of constraints......Page 826
22.3 Description of the algorithm......Page 829
22.3.1 The reduced tableaux......Page 834
22.4 Numerical results and comments......Page 835
References......Page 836
22.5 DR_Effort......Page 838
22.6 LA_Effort......Page 845
23.1 Introduction......Page 855
23.1.1 Applications of the algorithm......Page 856
23.2 Quadratic programming formulation of the problems......Page 858
23.3 Solution of problem (E0)......Page 859
23.4 Solution of problem (E)......Page 862
23.4.1 Asymmetries in the simplex tableau......Page 863
23.4.2 The condensed tableau for problem (E)......Page 864
23.4.3 The dual method of solution......Page 865
23.4.5 The method of solution of problem (E)......Page 866
23.5 Numerical results and comments......Page 867
References......Page 868
23.6 DR_Energy......Page 870
23.7 LA_Energy......Page 874
Appendices......Page 889
Appendix A: References......Page 891
Appendix B: Main Program......Page 915
Appendix C: Constants, Types and Function Prototypes......Page 919
Appendix D: Utilities and Common Functions......Page 939