To put the world of linear algebra to advanced use, it is not enough to merely understand the theory; there is a significant gap between the theory of linear algebra and its myriad expressions in nearly every computational domain. To bridge this gap, it is essential to process the theory by solving many exercises, thus obtaining a firmer grasp of its diverse applications. Similarly, from a theoretical perspective, diving into the literature on advanced linear algebra often reveals more and more topics that are deferred to exercises instead of being treated in the main text. As exercises grow more complex and numerous, it becomes increasingly important to provide supporting material and guidelines on how to solve them, supporting students’ learning process.
This book provides precisely this type of supporting material for the textbook “Numerical Linear Algebra and Matrix Factorizations,” published as Vol. 22 of Springer’s Texts in Computational Science and Engineering series. Instead of omitting details or merely providing rough outlines, this book offers detailed proofs, and connects the solutions to the corresponding results in the textbook. For the algorithmic exercises the utmost level of detail is provided in the form of MATLAB implementations. Both the textbook and solutions are self-contained. This book and the textbook are of similar length, demonstrating that solutions should not be considered a minor aspect when learning at advanced levels.
Author(s): Tom Lyche, Georg Muntingh, Øyvind Ryan
Series: Texts in Computational Science and Engineering
Publisher: Springer
Year: 2020
Language: English
Pages: 284
Preface
Acknowledgments
Contents
Listings
Chapter 1 A Short Review of Linear Algebra
Exercises section 1.1
Exercise 1.1: Strassen multiplication (Exam exercise 2017-1)
Exercises section 1.3
Exercise 1.2: The inverse of a general 2 X 2 matrix
Exercise 1.3: The inverse of a special 2 X 2 matrix
Exercise 1.4: Sherman-Morrison formula
Exercise 1.5: Inverse update (Exam exercise 1977-1)
Exercise 1.6: Matrix products (Exam exercise 2009-1)
Exercises section 1.4
Exercise 1.7: Cramer’s rule; special case
Exercise 1.8: Adjoint matrix; special case
Exercise 1.9: Determinant equation for a plane
Exercise 1.10: Signed area of a triangle
Exercise 1.11:Vandermonde matrix
Exercise 1.12: Cauchy determinant (1842)
Exercise 1.13: Inverse of the Hilbert matrix
Chapter 2 Diagonally Dominant Tridiagonal Matrices; Three Examples
Exercises section 2.1
Exercise 2.1: The shifted power basis is a basis
Exercise 2.2: The natural spline, n = 1
Exercise 2.3: Bounding the moments
Exercise 2.4: Moment equations for 1. derivative boundary conditions
Exercise 2.5: Minimal norm property of the natural spline
Theorem 2.5 (Minimal norm property of a cubic spline)
Exercise 2.6: Computing the D2-spline
Exercise 2.7: Spline evaluation
Exercises section 2.2
Exercise 2.8: Central difference approximation of 2. derivative
Exercise 2.9: Two point boundary value problem
Exercise 2.10: Two point boundary value problem; computation
Exercises section 2.3
Exercise 2.11:Approximate force
Exercise 2.12: Symmetrize matrix (Exam exercise 1977-3)
Exercises section 2.4
Exercise 2.13: Eigenpairs T of order 2
Exercise 2.14:LU factorization of 2. derivative matrix
Exercise 2.15: Inverse of the 2. derivative matrix
Exercises section 2.5
Exercise 2.16: Matrix element as a quadratic form
Exercise 2.17: Outer product expansion of a matrix
Exercise 2.18: The product AT A
Exercise 2.19: Outer product expansion
Exercise 2.20: System with many right hand sides; compact form
Exercise 2.21: Block multiplication example
Exercise 2.22: Another block multiplication example
Chapter 3 Gaussian Elimination and LU Factorizations
Exercises section 3.3
Exercise 3.1: Column oriented backsolve
Exercise 3.2: Computing the inverse of a triangular matrix
Exercise 3.3: Finite sums of integers
Exercise 3.4: Multiplying triangular matrices
Exercises section 3.4
Exercise 3.5: Using PLU for A*
Exercise 3.6: Using PLU for determinant
Exercise 3.7: Using PLU for A–1
Exercise 3.8: Upper Hessenberg system (Exam exercise (1994-2)
Exercises section 3.5
Exercise 3.9:# operations for banded triangular systems
Exercise 3.10: L1U and LU1
Exercise 3.11:LU of nonsingular matrix
Exercise 3.12: Row interchange
Exercise 3.13:LU and determinant
Exercise 3.14: Diagonal elements in U
Exercise 3.15: Proof of LDU theorem
Exercise 3.16: Proof of LU1 theorem
Exercise 3.17: Computing the inverse (Exam exercise 1978-1)
Exercise 3.18: Solving TH x =b (Exam exercise 1981-3)
Exercise 3.19: L1U factorization update (Exam exercise 1983-1)
Exercise 3.20: U1L factorization (Exam exercise 1990-1)
Exercises section 3.6
Exercise 3.21: Making block LU into LU
Chapter 4 LDL* Factorization and Positive Definite Matrices
Exercises section 4.2
Exercise 4.1: Positive definite characterizations
Exercise 4.2: L1U factorization (Exam exercise 1982-1)
Exercise 4.3:A counterexample
Exercise 4.4: Cholesky update (Exam exercise 2015-2)
Exercise 4.5: Cholesky update (Exam exercise 2016-2)
Chapter 5 Orthonormal and Unitary Transformations
Exercises section 5.1
Exercise 5.1: The A* A inner product
Exercise 5.2: Angle between vectors in complex case
Exercise 5.3: xT Ay inequality (Exam exercise 1979-3)
Exercises section 5.2
Exercise 5.4: What does algorithm housegen do when x = e1?
Exercise 5.5: Examples of Householder transformations
Exercise 5.6: 2 X 2 Householder transformation
Exercise 5.7: Householder transformation (Exam exercise 2010-1)
Exercises section 5.4
Exercise 5.8:QR decomposition
Exercise 5.9: Householder triangulation
Exercise 5.10: Hadamard’s inequality
Exercise 5.11:QL factorization (Exam exercise 1982-2)
Exercise 5.12: QL-factorization (Exam exercise 1982-3)
Exercise 5.13:QR Fact. of band matrices (Exam exercise 2006-2)
Exercise 5.14: Find QR factorization (Exam exercise 2008-2)
Exercises section 5.5
Exercise 5.15:QR using Gram-Schmidt, II
Exercises section 5.6
Exercise 5.16: Plane rotation
Exercise 5.17: Updating the QR decomposition
Exercise 5.18: Solving upper Hessenberg system using rotations
Exercise 5.19:A Givens transformation (Exam exercise 2013-2)
Exercise 5.20: Givens transformations (Exam exercise 2016-3)
Exercise 5.21: Cholesky and Givens (Exam exercise 2018-2)
Chapter 6 Eigenpairs and Similarity Transformations
Exercises section 6.1
Exercise 6.1: Eigenvalues of a block triangular matrix
Exercise 6.2: Characteristic polynomial of transpose
Exercise 6.3: Characteristic polynomial of inverse
Exercise 6.4: The power of the eigenvector expansion
Exercise 6.5: Eigenvalues of an idempotent matrix
Exercise 6.6: Eigenvalues of a nilpotent matrix
Exercise 6.7: Eigenvalues of a unitary matrix
Exercise 6.8: Nonsingular approximation of a singular matrix
Exercise 6.9: Companion matrix
Exercise 6.10: Find eigenpair example
Exercise 6.11: Right or wrong? (Exam exercise 2005-1)
Exercise 6.12 : Eigenvalues of tridiagonal matrix (Exam exercise 2009-3)
Exercises section 6.2
Exercise 6.13: Jordan example
Exercise 6.14:A nilpotent matrix
Exercise 6.15: Properties of the Jordan factorization
Exercise 6.16: Powers of a Jordan block
Exercise 6.17: The minimal polynomial
Exercise 6.18: Cayley Hamilton Theorem (Exam exercise 1996-3)
Exercises section 6.3
Exercise 6.19: Schur factorization example
Exercise 6.20: Skew-Hermitian matrix
Exercise 6.21: Eigenvalues of a skew-Hermitian matrix
Exercise 6.22: Eigenvector expansion using orthogonal eigenvectors
Exercise 6.23: Rayleigh quotient (Exam exercise 2015-3)
Exercises section 6.4
Exercise 6.24: Eigenvalue perturbation for Hermitian matrices
Exercise 6.25: Hoffman-Wielandt
Exercise 6.26: Biorthogonal expansion
Exercise 6.27: Generalized Rayleigh quotient
Chapter 7 The Singular Value Decomposition
Exercises section 7.1
Exercise 7.1: SVD1
Exercise 7.2: SVD2
Exercise 7.3: SVD examples
Exercise 7.4: More SVD examples
Exercise 7.5: Singular values of a normal matrix
Exercise 7.6: The matrices A* A, AA* and SVD
Exercise 7.7: Singular values (Exam exercise 2005-2)
Exercises section 7.2
Exercise 7.8: Nonsingular matrix
Exercise 7.9: Full row rank
Exercise 7.10: Counting dimensions of fundamental subspaces
Exercise 7.11: Rank and nullity relations
Exercise 7.12: Orthonormal bases example
Exercise 7.13: Some spanning sets
Exercise 7.14: Singular values and eigenpairs of composite matrix
Exercise 7.15: Polar decomposition (Exam exercise 2011-2)
Exercise 7.16: Underdetermined system (Exam exercise 2015-1)
Exercises section 7.4
Exercise 7.17: Rank example
Exercise 7.18: Another rank example
Exercise 7.19: Norms, Cholesky and SVD (Exam exercise 2016-1)
Chapter 8 Matrix Norms and Perturbation Theory for Linear Systems
Exercises section 8.1
Exercise 8.1: An A-norm inequality(Exam exercise 1982-4)
Exercise 8.2: A-orthogonal bases (Exam exercise 1995-4)
Exercises section 8.2
Exercise 8.3: Consistency of sum norm?
Exercise 8.4: Consistency of max norm?
Exercise 8.5: Consistency of modified max norm
Exercise 8.6: What is the sum norm subordinate to?
Exercise 8.7: What is the max norm subordinate to?
Exercise 8.8: Spectral norm
Exercise 8.9: Spectral norm of the inverse
Exercise 8.10: p-norm example
Exercise 8.11: Unitary invariance of the spectral norm
Exercise 8.12: A2 rectangular A
Exercise 8.13: p-norm of diagonal matrix
Exercise 8.14: Spectral norm of a column vector
Exercise 8.15: Norm of absolute value matrix
Exercise 8.16: An iterative method (Exam exercise 2017-3)
Exercises section 8.3
Exercise 8.17: Perturbed linear equation (Exam exercise 1981-2)
Exercise 8.18: Sharpness of perturbation bounds
Exercise 8.19: Condition number of 2. derivative matrix
Exercise 8.20: Perturbation of the Identity matrix
Exercise 8.21: Lower bounds in Equations
Exercise 8.22: Periodic spline interpolation (Exam exercise 1993-2)
Exercise 8.23: LSQ MATLAB program (Exam exercise 2013-4)
Exercises section 8.4
Exercise 8.24: When is a complex norm an inner product norm?
Exercise 8.25: p norm for p = 1 and p = ∞
Exercise 8.26: The p-norm unit sphere
Exercise 8.27: Sharpness of p-norm inequality
Exercise 8.28: p-norm inequalities for arbitrary p
Chapter 9 Least Squares
Exercises section 9.1
Exercise 9.1: Fitting a circle to points
Exercise 9.2: Least square fit (Exam exercise 2018-1)
Exercises section 9.2
Exercise 9.3:A least squares problem (Exam exercise 1983-2)
Exercise 9.4:Weighted least squares (Exam exercise 1977-2)
Exercises section 9.3
Exercise 9.5: Uniqueness of generalized inverse
Exercise 9.6:Verify that a matrix is a generalized inverse
Exercise 9.7: Linearly independent columns and generalized inverse
Exercise 9.8: More orthogonal projections
Exercise 9.9: The generalized inverse of a vector
Exercise 9.10: The generalized inverse of an outer product
Exercise 9.11: The generalized inverse of a diagonal matrix
Exercise 9.12: Properties of the generalized inverse
Exercise 9.13: The generalized inverse of a product
Exercise 9.14: The generalized inverse of the conjugate transpose
Exercise 9.15: Linearly independent columns
Exercise 9.16: Analysis of the general linear system
Exercise 9.17: Fredholm’s alternative
Exercise 9.18: SVD (Exam exercise 2017-2)
Exercises section 9.4
Exercise 9.19: Condition number
Exercise 9.20: Equality in perturbation bound
Exercise 9.21: Problem using normal equations
Exercises section 9.5
Exercise 9.22: Singular values perturbation (Exam exercise 1980-2)
Chapter 10 The Kronecker Product
Exercises sections 10.1 and 10.2
Exercise 10.1: 4 X 4 Poisson matrix
Exercise 10.2: Properties of Kronecker products
Exercise 10.3: Eigenpairs of Kronecker products (Exam exercise 2008-3)
Exercises section 10.3
Exercise 10.4: 2. derivative matrix is positive definite
Exercise 10.5: 1D test matrix is positive definite?
Exercise 10.6: Eigenvalues for 2D test matrix of order 4
Exercise 10.7: Nine point scheme for Poisson problem
Exercise 10.8: Matrix equation for nine point scheme
Exercise 10.9: Biharmonic equation
Chapter 11 Fast Direct Solution of a Large Linear System
Exercises section 11.3
Exercise 11.1: Fourier matrix
Exercise 11.2: Sine transform as Fourier transform
Exercise 11.3: Explicit solution of the discrete Poisson equation
Exercise 11.4: Improved version of Algorithm 11.1
Exercise 11.5: Fast solution of 9 point scheme
Exercise 11.6: Algorithm for fast solution of 9 point scheme
Exercise 11.7: Fast solution of biharmonic equation
Exercise 11.8: Algorithm for fast solution of biharmonic equation
Exercise 11.9 : Check algorithm for fast solution of biharmonic equation
Exercise 11.10 : Fast solution of biharmonic equation using 9 point rule
Chapter 12 The Classical Iterative Methods
Exercises section 12.3
Exercise 12.1: Richardson and Jacobi
Exercise 12.2: R-method when eigenvalues have positive real part
Exercise 12.3: Divergence example for J and GS
Exercise 12.5: Example: GS converges, J diverges
Exercise 12.6: Example: GS diverges, J converges
Exercise 12.7: Strictly diagonally dominance; the J method
Exercise 12.8: Strictly diagonally dominance; the GS method
Exercise 12.9: Convergence example for fix point iteration
Exercise 12.10: Estimate in Lemma 12.1 can be exact
Exercise 12.11: Iterative method (Exam exercise 1991-3)
Exercise 12.12: Gauss-Seidel method (Exam exercise 2008-1)
Exercises section 12.4
Exercise 12.13:A special norm
Exercise 12.14: Is A + E nonsingular?
Exercise 12.15: Slow spectral radius convergence
Chapter 13 The Conjugate Gradient Method
Exercises section 13.1
Exercise 13.1: A-norm
Exercise 13.2: Paraboloid
Exercise 13.3: Steepest descent iteration
Exercise 13.4: Steepest descent (Exam exercise 2011-1)
Exercises section 13.2
Exercise 13.5: Conjugate gradient iteration, II
Exercise 13.6: Conjugate gradient iteration, III
Exercise 13.7: The cg step length is optimal
Exercise 13.8: Starting value in cg
Exercise 13.9: Program code for testing steepest descent
Exercise 13.10: Using cg to solve normal equations
Exercise 13.11: AT A inner product (Exam exercise 2018-3)
Exercises section 13.3
Exercise 13.12: Krylov space and cg iterations
Exercise 13.13: Antisymmetric system (Exam exercise 1983-3)
Exercise 13.14: cg antisymmetric system (Exam exercise 1983-4)
Exercises section 13.4
Exercise 13.15: Another explicit formula for Chebyshev polynomials
Exercise 13.16: Maximum of a convex function
Exercises section 13.5
Exercise 13.17:Variable coefficient
Chapter 14 Numerical Eigenvalue Problems
Exercises section 14.1
Exercise 14.1:Yes or No (Exam exercise 2006-1)
Exercises section 14.2
Exercise 14.2: Nonsingularity using Gershgorin
Exercise 14.3: Gershgorin, strictly diagonally dominant matrix
Exercise 14.4: Gershgorin disks (Exam exercise 2009-2)
Exercises section 14.3
Exercise 14.5: Continuity of eigenvalues
Exercise 14.6: ∞-norm of a diagonal matrix
Exercise 14.7: Eigenvalue perturbations (Exam exercise 2010-2)
Exercises section 14.4
Exercise 14.8 : Number of arithmetic operations, Hessenberg reduction
Exercise 14.9: Assemble Householder transformations
Exercise 14.10: Tridiagonalize a symmetric matrix
Exercises section 14.5
Exercise 14.11: Counting eigenvalues
Exercise 14.12: Overflow in LDL* factorization
Exercise 14.13: Simultaneous diagonalization
Exercise 14.14: Program code for one eigenvalue
Exercise 14.15: Determinant of upper Hessenberg matrix
Chapter 15 The QR Algorithm
Exercise 15.1: Orthogonal vectors
