Preliminary Exam, Math 6610 August 2025

Least Squares Problems. Let \(A \in \mathbb {R}^{m \times n}\) with \(m > n\) have rank \(n\) and \(b \in \mathbb {R}^m\). The Least Squares problem is to find \(x \in \mathbb {R}^n\) which makes \(\|Ax - b\|_2\) as small as possible.

1. Show that \(x\) solves this Least Squares problem if and only if \(A^T Ax = A^T b\).
2. What is meant by the QR factorization of matrix \(A\)?
3. Show how to use the QR factorization of \(A\) to solve the Least Squares problem.

Sensitivity. For nonsingular \(A \in \mathbb {R}^{n \times n}\), and nonzero \(b \in \mathbb {R}^n\), consider the problems

1. Show that \[ \frac {\|x-\hat {x}\|}{\|x\|} \le \|A\|\|A^{-1}\|\frac {\|A-\hat {A}\|}{\|A\|}. \]
2. Give a bound on \(\|A-\hat {A}\|_2\) which ensures that \(\hat {A}\) is nonsingular if \(A\) is nonsingular.

Singular Value Decomposition. Let \(A \in \mathbb {R}^{m \times n}\), with \(m \ge n\).

1. What is the singular value decomposition (SVD) of \(A\)? Does every such matrix \(A\) have an SVD? Prove that it does or show an example of a matrix \(A\) which does not have an SVD.
2. For any \(m \times n\) matrix \(A\) with an SVD and \(\epsilon > 0\), show that there is a full-rank matrix \(B\) for which \(\|A - B\|_2 < \epsilon \).
3. For \(m \times n\) matrix \(A\), give orthonormal bases for the subspaces \(\operatorname {range}(A)\), \(\operatorname {null}(A)\), \(\operatorname {range}(A^*)\), and \(\operatorname {null}(A^*)\).

Solution of a nonlinear fixed point problem

Consider the fixed-point problem \(x = g(x)\) for a continuously differentiable real-valued function \(g\) and assume that it has a solution \(\alpha \) for which \(|g'(\alpha )| < 1\). State and prove a convergence theorem for fixed point iteration \(x^{(k+1)} = g(x^{(k)})\) for this problem. Note: Do not assume more about the function \(g\) than is stated in the problem.

Fixed-point iteration for linear systems.

1. For \(T \in \mathbb {R}^{m \times m}\) and any matrix norm, show that \(\|T^k\| \to 0\) as \(k \to \infty \) if and only if \(\rho (T) < 1\) where \(\rho (T)\) is the spectral radius of \(T\). Do not assume that the matrix \(T\) is diagonalizable.
2. Suppose \(A \in \mathbb {R}^{m \times m}\) is nonsingular, that \(b \in \mathbb {R}^m\), and that \(Ax = b\). Suppose that \(x = T x + c\) is a fixed point problem equivalent to this linear system. What are the implications of part (a) for the convergence of the fixed-point iteration \(x^{(k+1)} = T x^{(k)} + c\) to the solution \(x\) of the linear system?

3. Suppose \(A\) is a symmetric, weakly diagonally dominant, and irreducible matrix. Define the Jacobi iterative method for solving \(Ax = b\), and show that this method converges to the solution of the linear system starting with any initial vector \(x^{(0)}\). (Hint: You might find it helpful to use the fact that a matrix which is both weakly diagonally dominant and irreducible is nonsingular.)

   Recall that: An \(m \times m\) matrix \(A\) is irreducible iff for all \(i,j \in \{1,2,\ldots ,m\}\), \(i \ne j\), either \(a_{ij} \ne 0\) or there are \(i_1,i_2,\ldots ,i_s\), each between 1 and \(m\), such that \(a_{i,i_1}a_{i_1,i_2}a_{i_2,i_3}\cdots a_{i_s,j} \ne 0\). A symmetric \(m \times m\) matrix \(A\) is weakly diagonally dominant if \(|a_{ii}| \ge \sum _{j\ne i}|a_{ij}|\) for all \(i\), and \(|a_{ii}| > \sum _{j\ne i}|a_{ij}|\) for at least one \(i\).