Numerical linear approximation in C

Description

Illustrating the relevance of linear approximation in a variety of fields, Numerical Linear Approximation in C presents a unique collection of linear approximation algorithms that can be used to analyze, model, and compress discrete data. Developed by the lead author, the algorithms have been successfully applied to several engineering projects at the National Research Council of Canada. Basing most of the algorithms on linear programming techniques, the book begins with an introductory section that covers applications, the simplex method, and matrices. The next three parts focus on various L1, Chebyshev, and least squares approximations, including one-sided, bounded variables, and piecewise. The final section presents the solution of underdetermined systems of consistent linear equations that are subject to different constraints on the elements of the unknown solution vector. Except in the preliminary section, all chapters include the C functions of the algorithms, along with drivers that contain numerous test case examples and results. The accompanying CD-ROM also provides the algorithms written in C code as well as the test drivers. To use the software, it is not required to understand the theory behind each function. 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