Algebra, Topology, Differential Calculus and Optimization for CS 2017

【实例简介】
Algebra, Topology, Differential Calculus, and Optimization Theory for Computer Science and Engineering Jean Gallier and Jocelyn Quaintance Book in Progress, Approx. 1440 pages (2017) http://www.cis.upenn.edu/~jean/gbooks/geomath.html
Contents 1 Introduction 13 2 Vector Spaces, Bases, Linear Maps 2.1 Groups, Rings, and Fields 2.2 Vector Spaces 26 3 Linear Independence, Subspaces 33 2. 4 Bases of a Vector Space 38 2.5 Linear Maps 45 6 Quotient Spaces 52 2.7 Summary 53 3 Matrices and Linear Maps 55 3.2 Haar Basis Vectors and a glimpse at Wavelets 71 3. 3 The Effect of a Change of Bases on Matrices 3. 4 Summary 91 4 Direct Sums, The Dual Space, Duality 93 4.1 Sums. Direct Sums. Direct Products 4.2 The Dual Space E* and Linear Forms 4.3 Hyperplanes and Linear Forms 126 4.4 Transpose of a Linear map and of a matrix 127 4.5 The Four Fundamental Subspaces 136 4.6 Summary 138 5 Determinants 141 5.1 Permutations, Signature of a Permutation 141 5.2 Alternating Multilinear Maps 145 5.3 Definition of a, determinant, 148 5.4 Inverse matrices and Determinants .155 5.5 Systems of Linear Equations and determinants 158 5.6 Determinant of a Linear Map 159 5.7 The Cayley-Hamilton Theorem 160 5.8 Permanents .165 CONTENTS 5.9 Further readings 167 6 Gaussian Elimination, LU, Cholesky, Echelon Form 169 6.1 Motivating Example: Curve Interpolation .169 6.2 Gaussian elimination and lU-factorization 17 6.3 Gaussian Elimination of Tridiagonal Matrices .199 6. 4 SPD Matrices and the Cholesky Decomposition 202 6.5 Reduced row Echelon form 206 6.6 Transvections and dilatations 224 6. 7 Summary 229 7 Vector norms and matrix norms 231 7.1 Normed Vector Spaces 231 7.2 Matrix norms .237 7.3 Condition Numbers of matric 250 7.4 An Application of Norms: Inconsistent Linear Systems 259 7.5 Summary ...,,,,,,..260 8 Eigenvectors and Eigenvalues 263 8.1 Eigenvectors and Eigenvalues of a Linear Map .,...263 8.2 Reduction to Upper Triangular Form 270 8.3 Location of Eigenvalues ...275 8.4 Summary 277 9 Iterative Methods for Solving Linear Systems 9.1 Convergence of Sequences of Vectors and Matrices 279 9.2 Convergence of Iterative Methods 282 9.3 Methods of Jacobi Gauss-Seidel and Relaxation ..284 9.4 Convergence of the Methods .289 9.5 Summary ..,,..,,...,...296 10 Euclidean Spaces 297 10.1 Inner Products, Euclidean Spaces 297 10.2 Orthogonality, Duality, Adjoint of a Linear Map .305 10.3 Linear Isometries(Orthogonal Transformations 317 10.4 The Orthogonal Group, Orthogonal Matrices 320 10.5 QR-Decomposition for Invertible Matrices ...322 10.6 Some Applications of Euclidean Geometry 326 10.7 Summary 327 11 QR-Decomposition for Arbitrary Matrices 329 11.1 Ort hogonal reflections 329 11.2 Q R-Decomposition Using Householder Matrices 333 CONTENTS 11.3 Summary 337 12 Basics of Affine Geometry 339 12.1 Affine Spaces .339 12.2 Examples of Affine Spaces 347 12.3 Chasles's Identity 348 12.4 Alline Combinations, Barycenters ..349 12.5 Affine Subspaces 353 12.6 Affine Independence and Affine frames .358 12.7 Affine Maps ..363 12.8 Affine groups .370 12.9 Affine Geometry: A Glimpse ..372 12.10 Affine Hyperplanes .375 12.11 Intersection of Affine Spaces 377 13 Embedding an Affine Space in a Vector Space 381 13.1 The"Hat Construction, or Homogenizing 381 13.2 Affine frames of e and bases of e 388 13.3 Another Construction of E 390 13.4 Extending Affine Maps to Linear Maps 393 14 Basics of Projective Geometry 399 14.1 Why Projective Spaces 14.2 Projective Spaces 404 14.3 Projective Subspaces 409 14.4 Projective frames ..412 14.5 Projective Maps ...426 14.6 Finding a homography between Two Projective Frames .432 14.7 Affine patches ..445 4.8 Projective Completion of an Affine Space 448 14.9 Making Good Use of Hyperplanes at Infinity 453 14.10 The Cross-Ratio 456 14.11 Fixed Points of Homographies and homologies 460 14.12 Duality in Projective geometry ,,,.474 14.13 Cross-Ratios of Hyperplanes 478 14.14 Complexification of a Real Projective Space 480 14.15 Similarity Structures on a projective Space ..482 14.16 Some Applications of Projective geometry 491 15 The Cartan-Dicudonne thcorem 497 15.1 The Cartan-Dieudonne Theorem for Linear isometries 497 15.2 Affine Isometries(Rigid Motions 509 15.3 Fixed Points of Affine Maps 511 6 CONTENTS 15.4 Affine isometries and fixed points 513 15.5 The Cartan Dieudonne Theorem for Affine isometries .519 16 Hermitian Spaces 523 16.1 Hermitian Spaces, Pre-Hilbert Spaces .523 16.2 Orthogonality, Duality, adjoint of a Linear map .532 16.3 Linear Isometries(Also Called Unitary Transformations 537 16.4 The Unitary Group, Unitary Matrices .539 16.5 Orthogonal Projections and Involutions ...,,,,542 16.6 Dual norms 544 16.7 Summary ..548 17 Isometries of Hermitian Spaces 551 17.1 The Cartan- Dieudonne Theorem hermitian Case 551 17.2 Affine Isometries(Rigid Motions 560 18 Spectral Theorems 565 18.1 Introduction 565 18.2 Normal Linear Maps .565 18.3 Self-Adioint and Other Special Linear Ma ,,,,.574 18.4 Normal and Other Special Matrices ...581 18.5 Conditioning of Eigenvalue Problems 584 18.6 Rayleigh Ratios and the Courant -Fischer Theorem 587 18.7 Summary .595 19 Introduction to The finite elements method 597 19. 1 A One-Dimensional Problem: Bending of a Beam 597 19.2 A Two-Dimensional Problem: An elastic Membrane ..607 19.3 Time-Dependent Boundary Problems 610 20 Singular Value Decomposition and Polar Form 619 20.1 Singular Value Decomposition for Square matrices 619 20.2 Singular Value Decomposition for Rectangular Matrices 627 20.3 Ky Fan Norms and Schatten norms .630 20.4 Summary 631 21 Applications of SVD and Pseudo-Inverses 633 21.1 Least Squares Problems and the Pseudo-Inverse ..633 21.2 Properties of the Pseudo-Inverse 638 21.3 Data Compression and svD 643 21.4 Principal Components Analysis(PCA) 644 21.5 Best Affine Approximation 651 21.6 Summary 654 CONTENTS 7 22 The Geometry of Bilinear Forms; Witt's Theorem 657 22.1 Bilinear forms .657 22.2 Sesquilinear Forms 665 22.3 Orthogonality 669 22.4 Adjoint of a Linear Map .674 22.5 Isometries Associated with Sesquilinear Forms 垂 676 22.6 Totally Isotropic Subspaces 680 22.7 Witt Decomposition ..686 22.8 Symplectic Groups 694 22.9 Orthogonal Groups and the Cartan-Dieudonne Theorem 698 22.10Witt’ s Theorem 705 23 Polynomials, Ideals and PIDs 711 711 23.2 Polynomials ...712 23. 3 Euclidean Division of polynomia. ls 718 23.4 Ideals. PIDS and Greatest Common Divisors 720 23.5 Factorization and Irreducible Factors in KX 72 23.6 Roots of polynomials ,,732 23.7 Polynomial Interpolation(Lagrange, Newton, Hermite ..739 24 Annihilating Polynomials; Primary Decomposition 747 24.1 Annihilating Polynomials and the Minimal polynomial 747 24.2 Minimal Polynomials of Diagonalizable Linear Maps 749 24. 3 The Primary Decomposition Theorem 755 24.4 Nilpotent Linear Maps and Jordan Form ..764 25 UFDS, Noetherian Rings, Hilbert's Basis theorem 771 25.1 Unique Factorization Domains(Factorial Rings) ..771 25.2 The Chinese Remainder Theorem 785 25.3 Noetherian Rings and Hilbert's Basis Theorem 791 25.4 Futher readings 795 26 Tensor Algebras and Symmetric Algebras 797 26.1 Linear Algebra Preliminaries: Dual Spaces and pairings 798 26.2 Tensors products ..,,,,,,,,,803 26.3 Bases of tensor products 814 26.4 Some Useful Isomorphisms for Tensor Products 26.5 Duality for Tensor Products .820 26.6 Tensor Algebras .824 26.7 Symmetric Tensor Powers 830 26.8 Bases of Symmetric Powers 26.9 Some Useful Isomorphisms for Symmetric powers 835 838 CONTENTS 26.10 Duality for Symmetric Powers 838 26 11 Symmetric Algebras 841 27 Exterior Tensor powers and exterior algebras 845 27.1 Exterior Tensor powers ..845 27.2 Bases of exterior powers 850 27.3 Some Useful Isomorphisms for Exterior Powers 853 27.4 Duality for Exterior Powers ..853 27.5 Exterior Algebras 856 27.6 The Hodge *-Operator 860 27.7 Left and right Hooks k) .863 27. 8 Testing Decomposability e 872 27. 9 The Grassmann-Plicker's Equations and grassmannians e 875 27.10 Vector-Valued Alternating Forms 28 Introduction to Modules: Modules over a pid 883 28.1 Modules over a Commutative ring .883 28.2 Finite Presentations of modules .892 28.3 Tensor Products of Modules over a Commutative Ring 898 28.4 Torsion Modules over a PID: Primary Decomposition 28.5 Finitely Generated Modules over a PID 907 28.6 Extension of the Ring of Scalars .923 29 Normal forms: The rational canonical form 929 9. 1 The Torsion Module Associated With An Endomorphism 929 29.2 The rational Canonical Form 937 29.3 The Rational Canonical Form. Second Version 944 29.4 The Jordan Form Revisited .945 29.5 The Smith normal form .948 30 Topology 961 30.1 Metric Spaces and Normed Vector Spaces 961 30.2 Topological Spaces 967 30.3 Continuous functions. Limits .976 30.4 Connected sets .,,,.983 30.5 Compact Sets 30.6 Sequential Compactness in Metric Spaces 003 30.7 Complete metric spaces and compactness .1011 30.8 The Contraction Mapping Theorem 1012 30.9 Continuous Linear and Multilinear Maps 1017 30.10 Normed Affine Spaces 1022 30.11 Futher readings 1022 CONTENTS 31A Detour On Fractals 1023 31.1 Iterated Function Systems and fractals 1023 32 Differential Calculus 1031 32.1 Directional derivatives. Total derivatives .1031 32.2 Jacobian matrices 1045 32.3 The Implicit and The Inverse Function Theorems .1053 32.4 Tangent Spaces and Differentials .,,1057 32.5 Second-Order and Higher-Order Derivatives .1058 32.6 Taylors formula, Faa di bruno's formula 1063 32.7 Vector Fields. Covariant Derivatives. Lie brackets 1067 32.8 Futher readings .1069 33 Quadratic Optimization Problems 1071 33.1 Quadratic Optimization: The Positive Definite Case .1071 33.2 Quadratic Optimization: The General case 1079 33.3 Maximizing a Quadratic Function on the Unit Sphere ..1083 33.4 Summary 1088 34 Schur Complements and Applications 1091 34.1 Schur complements ...1091 34.2 SPD Matrices and Schur Complements 1093 34.3 SP Semidefinite Matrices and Schur Complements .1095 35 Convex Sets, Cones, H-Polyhedra 1097 35.1 What is Linear Programming? .1097 35.2 Affine Subsets, Convex Sets, Hyperplanes, Half-Spaces 1099 35.3 Cones, Polyhedral cones, and H-polyhedra .1102 36 Linear Programs 1109 36.1 Linear Programs, Feasible Solutions, Optima. I Solutions 1109 36.2 Basic Feasible solutions and vertices .1115 37 The Simplex algorithn 1123 37. 1 The Idea behind the Simplex algorithm 1123 37.2 The Simplex Algorithm in General 1132 37.3 How Perform a Pivoting Step efficiently .1139 37. 4 The Simplex Algorithm Using Tableaux 1142 37.5 Computationa.l efficiency of the simplex method 1152 38 Linear Programming and duality 155 38.1 Variants of the farkas lemma 1155 38.2 The Duality Theorem in Linear Programming .1160 10 CONTENTS 38.3 Complementary Slackness Conditions 1168 38.4 Duality for Linear Programs in Standard Form .1170 38.5 The Dual Simplex Algorithm 38. The Primal-Dual Algorithm 1178 39 Extrema of real-valued functions 1189 39.1 Local Extrema and Lagrange multipliers .1189 39.2 USing Second Derivatives to Find Extrema .1199 39.3 USing Convexity to Find Extrema ..1202 39.4 Summary ..1212 40 Newton's method and Its generalizations 1213 40.1 Newton's Method for Real Functions of a Real argument 1213 40.2 Generalizations of newtons method 1214 40.3 Summary 1220 41 Basics of Hilbert Spaces 1221 41.1 The Projection Lemma, Duality ..1221 41.2 Farkas-Minkowski Lemma in Hilbert Spaces ...1238 42 General results of optimization theory 1241 42.1 Existence of Solutions of an Optimization Problem .1241 42.2 Gradient Descent methods for Unconstrained problems ..1255 42.3 Conjugate gradient Methods for Unconstrained Problems ·.· ....1271 42.4 Gradient Projection for Constrained Optimization 1281 42.5 Penalty Methods for Constrained Optimization 1284 42.6 Summary 1286 43 Introduction to Nonlinear optimization 1287 43.1 The Cone of Feasible directions 1287 43.2 The Karush- Kuhn-Tucker Conditions ...1301 43.8 Hard Margin Support Vector Machine 1311 43.4 Lagrangian Duality and Saddle Points ..1322 43.5 Uzawa's Method 1338 43.6 Handling equality Constraints Explicitly 1343 43.7 Conjugate Function and Legendre Dual Function 1351 43.8 Some Techniques to obtain a More Useful Dual Program ..1361 43.9 Summary 1370 44 Soft Margin Support Vector Machines 1373 44.1 Soft Margin Support Vector Machines;(SVMg1 .,,,.1374 44.2 Soft Margin Support Vector Machines;(SVM32) 383 44.3 Soft Margin Support Vector Machines;(SVMs2/) .1389 【实例截图】
【核心代码】