Conditioning, Sensitivity, and Perturbation Bounds

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.

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.

(Rank-One Perturbation of the Identity). If \(u\) and \(v\) are \(n\)-vectors, the matrix \(B = I + uv^*\) is known as a rank-one perturbation of the identity. Show that if \(B\) is nonsingular, then its inverse has the form \(B^{-1} = I + \beta uv^*\) for some scalar \(\beta \), and give an expression for \(\beta \). For what \(u\) and \(v\) is \(B\) singular? If it is singular, what is \(\operatorname {null}(B)\)?

(Rank-One Perturbation of the Identity). If \(u\) and \(v\) are \(n\)-vectors, the matrix \(B = I + uv^*\) is known as a rank-one perturbation of the identity. Show that if \(B\) is nonsingular, then its inverse has the form \(B^{-1} = I + \beta uv^*\) for some scalar \(\beta \), and give an expression for \(\beta \). For what \(u\) and \(v\) is \(B\) singular? If it is singular, what is \(\operatorname {null}(B)\)?

(Moore-Penrose pseudo-inverse)

Let \(A \in \mathbb {C}^{m \times n}\) have rank \(r\) and reduced SVD \[ A = \tilde {U}\tilde {\Sigma }\tilde {V}^* . \]

The Moore-Penrose pseudoinverse of \(A\) is defined as

a. In the induced matrix \(\ell ^2\) norm \(\|\cdot \|\), is the operation \(A \mapsto A^+\) well-conditioned? That is, given an arbitrary but fixed \(A\) and a perturbation matrix \(B\), is \(\|(A + B)^+ - A^+\|/\|A^+\|\) controllable by \(\|B\|/\|A\|\)? Prove it, or give a counterexample.

b. If \(m \ge n\) and \(A\) has full rank \(n\) and \(b \in \mathbb {C}^m\) is a given vector, prove that \(x = A^+b\) is identical to the least-squares solution \(z\) of the over-determined linear system \(Az = b\).

Rank-One Perturbation of the Identity

If \(x\) and \(y\) are \(m\)-vectors, the matrix \(A=I+xy^*\) is known as a rank-one perturbation of the identity. Show that if \(A\) is nonsingular, then its inverse has the form \(A^{-1}=I+\beta xy^*\) for some scalar \(\beta \), and give an expression for \(\beta \). For what \(x\) and \(y\) is \(A\) singular? If it is singular, what is \(\operatorname {null}(A)\)?

Rank-One Perturbation of the Identity

If \(u\) and \(v\) are \(n\)-vectors, the matrix \(B=I+uv^*\) is known as a rank-one perturbation of the identity. Show that if \(B\) is nonsingular, then its inverse has the form \(B^{-1}=I+\beta uv^*\) for some scalar \(\beta \), and give an expression for \(\beta \). For what \(u\) and \(v\) is \(B\) singular? If it is singular, what is \(\operatorname {null}(B)\)?

Error Analysis Consider the linear system \[ Ax=b \tag {1} \] where \(A\) is an invertible matrix. Let \(\hat {x}\) be an approximation of the solution of (1) and let \[ e=x-\hat {x}\qquad \text {and}\qquad r=b-A\hat {x}. \] Let \(\|\cdot \|\) denote any vector norm or the corresponding induced matrix norm. Show that \[ \frac {\|e\|}{\|x\|} \leq \|A\|\|A^{-1}\|\frac {\|r\|}{\|b\|}. \] Comment on the significance of the condition number \(\|A\|\|A^{-1}\|\) and give a lower bound for it in terms of the eigenvalues of \(A\).

ODEs

Consider the initial value problem for a system of ODEs \[ y'=Ay \] where \(A\) has eigenvalues with real parts ranging from \(-10^6\) to \(-1\). Which of the following schemes would be the best choice for solving this problem? Justify your answer in terms of stability, accuracy, and efficiency. Does your answer change depending on the size and condition number of \(A\)? Explain your answer. \[ y^{n+1}=y^n+kAy^n, \tag {1} \] \[ y^{n+1}=y^n+kAy^{n+1}, \tag {2} \] \[ y^{n+1}=y^n+\frac {k}{2}(Ay^n+Ay^{n+1}). \tag {3} \]

Sensitivity Analysis

(a) Let \(X\in \mathbb {R}^{n\times n}\) such that \(\lVert X\rVert <1\) for some induced norm. Show that \(I-X\) is nonsingular and \[ \lVert (I-X)^{-1}\rVert \le \frac {1}{1-\lVert X\rVert }. \]

(b) Assume that \(A\in \mathbb {R}^{n\times n}\) is nonsingular, and the linear system \[ Ax=b \] is perturbed to \[ (A+\delta A)(x+\delta x)=b+\delta b, \] and the perturbations are small enough so that \[ \lVert \delta A\rVert \le \epsilon \lVert A\rVert ,\qquad \lVert \delta b\rVert \le \epsilon \lVert b\rVert , \] for some small \(\epsilon >0\), and \(\epsilon \kappa (A)=r<1\), where \(\kappa (A)\) is the condition number of \(A\). Show that \(A+\delta A\) is nonsingular.

(c) Let \(\tilde {x}=x+\delta x\), show that \[ \lVert \tilde {x}\rVert \le \frac {1+r}{1-r}\lVert x\rVert ; \] and \[ \frac {\lVert \delta x\rVert }{\lVert x\rVert } \le \frac {2\epsilon }{1-r}\kappa (A). \]

Sensitivity Consider a \(6\times 6\) symmetric positive definite matrix \(A\) with singular values \(\sigma _1=1000\), \(\sigma _2=500\), \(\sigma _3=300\), \(\sigma _4=20\), \(\sigma _5=1\), \(\sigma _6=0.01\).

a) Suppose you use a Cholesky factorization package on a computer with a machine epsilon \(10^{-14}\) to solve the system \(Ax=b\) for some nonzero vector \(b\). How many digits of accuracy do you expect in the computed solution? Justify your answer in terms of condition and stability. You may assume that the entries of \(A\) and \(b\) are exactly represented in the computer’s floating-point system.

b) Suppose that instead you use an iterative method to find an approximate solution to \(Ax=b\) and you stop iterating and accept iterate \(x^{(k)}\) when the residual \(r^{(k)}=Ax^{(k)}-b\) has 2-norm less than \(10^{-9}\). Give an estimate of the maximum size of the relative error in the final iterate? Justify your answer.

Eigenvalue Problems

a) Let \(A\) be a real \(n\times n\) matrix with simple eigenvalue \(\lambda \), right eigenvector \(x\) (i.e., \(Ax=\lambda x\)), and left eigenvector \(y\) (i.e., \(y^*A=\lambda y^*\)). Assume that \(\lVert x\rVert _2=\lVert y\rVert _2=1\). Show that the condition number for \(\lambda \) to changes in \(A\) is given by \(s(\lambda )=1/\lvert y^*x\rvert \). Give an example of a matrix \(A\) which has a badly conditioned eigenvalue, and another matrix \(A\) which has only well-conditioned eigenvalues.

b) Consider the problem of computing an eigenvalue/eigenvector pair of a real symmetric \(m\times m\) matrix \(A\) with eigenvalues of distinct magnitudes. One algorithm for trying to do this is Rayleigh Quotient Iteration:

Guess \(v^{(0)}\) with \(\lVert v^{(0)}\rVert _2=1\).

Set \(\lambda ^{(0)}=(v^{(0)})^TAv^{(0)}\).

For \(k=1,2,3,\ldots \): \[ \text {Solve }(A-\lambda ^{(k-1)}I)w=v^{(k-1)}\text { for }w, \] \[ v^{(k)}=\frac {w}{\lVert w\rVert _2}, \] \[ \lambda ^{(k)}=(v^{(k)})^TAv^{(k)}. \] Until convergence.

Suppose that the Rayleigh Quotient Iteration iterates \(\lambda ^{(k)}\) converge to a simple eigenvalue \(\lambda \) of \(A\). Analyze the speed of convergence of \(\lambda ^{(k)}\) to \(\lambda \).

Sensitivity Analysis In this problem, we consider a real, non-singular \(n\times n\) matrix \(A\) and vectors \(b,x\in \mathbb {R}^n\). We are concerned with the error in solving the linear system \(Ax=b\). It turns out that the numerical solution \(\hat {x}\) is only an approximate solution to this equation. However, it satisfies a perturbed equation \(\hat {A}\hat {x}=b\) exactly, where \(\hat {A}=A+\delta A\). Let the error be defined as \(\delta x=\hat {x}-x\); we are interested in bounding \(\lVert \delta x\rVert \) in terms of \(\lVert \delta A\rVert \lVert A^{-1}\rVert \), or \(\lVert \delta A\rVert \lVert \hat {A}^{-1}\rVert \), and \(\lVert x\rVert \), or \(\lVert \hat {x}\rVert \), where \(\lVert \cdot \rVert \) is some suitable norm, and we proceed as follows:

a) First prove the identity \[ A^{-1}-\hat {A}^{-1}=A^{-1}\cdot \delta A\cdot \hat {A}^{-1}, \] and hence deduce that \[ \lVert A^{-1}-\hat {A}^{-1}\rVert \le \lVert A^{-1}\rVert \cdot \lVert \delta A\rVert \cdot \lVert \hat {A}^{-1}\rVert . \]

b) Assuming that \(\hat {\delta }=\lVert \delta A\rVert \lVert \hat {A}^{-1}\rVert <1\), show that \[ \lVert A^{-1}\rVert \le \frac {1}{1-\hat {\delta }}\lVert \hat {A}^{-1}\rVert ,\qquad \lVert A^{-1}-\hat {A}^{-1}\rVert \le \frac {\hat {\delta }}{1-\hat {\delta }}\lVert \hat {A}^{-1}\rVert . \]

c) By comparing the equations \(Ax=b\) and \((A+\delta A)(x+\delta x)=b\), show that \[ \lVert \delta x\rVert \le \frac {\hat {\delta }}{1-\hat {\delta }}\lVert \hat {x}\rVert . \] Similarly, show that if \(\delta =\lVert \delta A\rVert \lVert A^{-1}\rVert <1\), \[ \lVert \delta x\rVert \le \frac {\delta }{1-\delta }\lVert x\rVert . \]

Singular Value Decomposition The singular value decomposition (SVD) of a real \(m\times n\) matrix \(A\) (you may assume \(m\ge n\)) is defined by \[ A=U\Sigma V^T \] where \(U\) is \(m\times m\) and orthogonal. \(\Sigma \) is \(m\times n\) and diagonal. \(V\) is \(n\times n\) and orthogonal.

a) Prove that every matrix \(A\) has an SVD.

b) Use the SVD of \(A\) to prove the famous result from linear algebra that the null space of \(A\) is the orthogonal complement of the range of \(A^T\) (the adjoint of \(A\)).

c) For a nonsingular \(m\times m\) matrix \(A\), the solution to the system \(Ax=b\) can be expressed in terms of \(A\)’s SVD. Write \(b=\sum _{j=1}^m c_j u_j\) where \(u_j\) is the \(j\)th column of \(U\). Then the solution \(x\) is \[ x=\sum _{j=1}^m \frac {c_j}{\sigma _j}v_j \] where \(v_j\) is the \(j\)th column of \(V\) and \(\sigma _j\) is the \(j\)th singular value. Verify this formula. Consider the special case \(b=u_1\). What perturbation \(\delta b\) in \(b\), with \(\lVert \delta b\rVert _2=1\), causes the largest change \(\delta x\) in the solution \(x\)?

Eigenvalue Problems

a) Let \(A\) be a real \(n\times n\) matrix with simple eigenvalue \(\lambda \), right eigenvector \(x\) (i.e., \(Ax=\lambda x\)), and left eigenvector \(y\) (i.e., \(y^*A=\lambda y^*\)). Assume that \(\lVert x\rVert _2=\lVert y\rVert _2=1\). Show that the condition number for \(\lambda \) to changes in \(A\) is given by \(s(\lambda )=1/\lvert y^*x\rvert \). Give an example of a matrix \(A\) which has a badly conditioned eigenvalue, and another matrix \(A\) which has only well-conditioned eigenvalues.

b) Consider the problem of computing an eigenvalue/eigenvector pair of a real symmetric \(m\times m\) matrix \(A\) with eigenvalues of distinct magnitudes. One algorithm for trying to do this is Rayleigh Quotient Iteration:

Guess \(v^{(0)}\) with \(\lVert v^{(0)}\rVert _2=1\).

Set \(\lambda ^{(0)}=(v^{(0)})^TAv^{(0)}\).

For \(k=1,2,3,\ldots \): \[ \text {Solve }(A-\lambda ^{(k-1)}I)w=v^{(k-1)}\text { for }w, \] \[ v^{(k)}=\frac {w}{\lVert w\rVert _2}, \] \[ \lambda ^{(k)}=(v^{(k)})^TAv^{(k)}. \] End.

Suppose that the Rayleigh Quotient Iteration iterates \(\lambda ^{(k)}\) converge to a simple eigenvalue \(\lambda \) of \(A\). Analyze the speed of convergence of \(\lambda ^{(k)}\) to \(\lambda \).

Sensitivity Analysis In this problem, we consider a real, non-singular \(n\times n\) matrix \(A\) and vectors \(f\), \(b\), \(x\in \mathbb {R}^n\).

a) (6%) First we consider the conditioning of matrix-vector multiplication \(f=Ax\), that is, find the smallest factor \(\kappa >0\) such that, when \(x\) is perturbed by any small \(\delta x\), the perturbation for \(f\) satisfies \[ \frac {\lVert \delta f\rVert }{\lVert f\rVert } \le \kappa \frac {\lVert \delta x\rVert }{\lVert x\rVert }. \] Here we assume no perturbation in matrix \(A\).

b) (8%) For the linear system \(Ax=b\), a numerical solution \(\hat {x}\) actually solves a slightly different problem due to roundoff errors: \[ (A+\delta A)\hat {x}=b+\delta b. \] If we denote \(\delta x=\hat {x}-x\), derive an upper bound for the relative error \[ E=\frac {\lVert \delta x\rVert }{\lVert x\rVert } \] in terms of the condition number of \(A\), \(\kappa (A)\), and the norms of \(A\), \(\delta A\), \(b\) and \(\delta b\), where \(\lVert \cdot \rVert \) is a suitable vector norm.

c) (6%) In practice, \(x\) is not available so \(\hat {x}\) is often used in the above bound to generate an approximate bound for \(\delta x\). Comment on this practice as what the advantages and disadvantages are, point out cases where this approximation may be inappropriate.

Sensitivity Analysis Consider the (square, non-singular) linear system \[ Ax=b. \tag {8} \] Suppose you compute (by any method) a numerical solution \(\hat {x}\) and you are concerned about the relative error \[ E=\frac {\lVert x-\hat {x}\rVert }{\lVert x\rVert } \tag {9} \] where \(\lVert \cdot \rVert \) denotes a suitable vector norm. Derive upper and lower bounds on \(E\) in terms of the residual \(r=b-A\hat {x}\) and the condition number of \(A\) with respect to \(\lVert \cdot \rVert \).

Ill Conditioning Define the condition number of a square matrix \(A\) and its significance for the solution of the linear system \[ Ax=b. \tag {5} \] Can you define a similar number that describes the conditioning of the eigenvalue problem \[ Ax=\lambda x? \tag {6} \]

Sensitivity Analysis For the linear system \(Ax=b\) where \(A\) is a square, real non-singular matrix, a numerical solution \(\hat {x}\) actually solves a slightly different problem due to roundoff errors: \[ (A+\delta A)\hat {x}=b+\delta b. \]

(a) If we denote \(\delta x=\hat {x}-x\), derive an upper bound for the relative error \[ E_1=\frac {\lVert \delta x\rVert }{\lVert \hat {x}\rVert } \] in terms of the condition number of \(A\), \(\kappa (A)\), and the norms of \(A,\hat {x},\delta A,\delta b\), where \(\lVert \cdot \rVert \) is a suitable vector norm.

(b) We can define another relative error \[ E_2=\frac {\lVert \delta x\rVert }{\lVert x\rVert }, \] based on the exact solution. Derive an upper bound for \(E_2\) in terms of \(\kappa (A)\) and the norms of \(\delta A,A,\delta b\) and \(b\).

(c) Strictly speaking, the relative error is given by \(E_2\), even though in many applications we simply use \(E_1\) since it is more readily available. Point out cases where this approximation may not be appropriate. Explain the significance of the condition number \(\kappa (A)\), and express the relative distance of \(A\) to its nearest singular matrix in terms of \(\kappa (A)\).

Singular Value Decomposition The singular value decomposition (SVD) of a real \(m\times n\) matrix \(A\) (you may assume \(m\ge n\)) is defined by \[ A=U\Sigma V^T \] where \(U\) is \(m\times m\) and orthogonal, \(\Sigma \) is \(m\times n\) and diagonal, \(V\) is \(n\times n\) and orthogonal.

a) Prove that every matrix \(A\) has an SVD.

b) Use the SVD of \(A\) to prove the famous result from linear algebra that the null space of \(A\) is the orthogonal complement of the range of \(A^T\) (the adjoint of \(A\)).

c) For a nonsingular \(m\times m\) matrix \(A\), the solution to the system \(Ax=b\) can be expressed in terms of \(A\)’s SVD. Write \(b=\sum _{j=1}^m c_j u_j\) where \(u_j\) is the \(j^{\text {th}}\) column of \(U\). Then the solution \(x\) is \[ x=\sum _{j=1}^m \frac {c_j}{\sigma _j}v_j \] where \(v_j\) is the \(j^{\text {th}}\) column of \(V\) and \(\sigma _j\) is the \(j^{\text {th}}\) singular value. Verify this formula. Consider the special case \(b=u_1\). What perturbation \(\delta b\) in \(b\), with \(\lVert \delta b\rVert _2=1\), causes the largest change \(\delta x\) in the solution \(x\)?

Eigenvalue Problems

a) Let \(A\) be a real \(n\times n\) matrix with simple eigenvalue \(\lambda \), right eigenvector \(x\) (i.e., \(Ax=\lambda x\)), and left eigenvector \(y\) (i.e., \(y^*A=\lambda y^*\)). Assume that \(\lVert x\rVert _2=\lVert y\rVert _2=1\). Show that the condition number for \(\lambda \) to changes in \(A\) is given by \(s(\lambda )=1/\lvert y^*x\rvert \). Give an example of a matrix \(A\) which has a badly conditioned eigenvalue, and another matrix \(A\) which has only well-conditioned eigenvalues.

b) Consider the problem of computing an eigenvalue/eigenvector pair of a real symmetric \(m\times m\) matrix \(A\) with eigenvalues of distinct magnitudes. One algorithm for trying to do this is Rayleigh Quotient Iteration:

Guess \(v^{(0)}\) with \(\lVert v^{(0)}\rVert _2=1\).

Set \(\lambda ^{(0)}=(v^{(0)})^TAv^{(0)}\).

For \(k=1,2,3,\ldots \) \[ \begin {aligned} &\text {Solve }(A-\lambda ^{(k-1)}I)w=v^{(k-1)}\text { for }w,\\ &v^{(k)}=w/\lVert w\rVert _2,\\ &\lambda ^{(k)}=(v^{(k)})^TAv^{(k)}. \end {aligned} \] End

Suppose that the Rayleigh Quotient Iteration iterates \(\lambda ^{(k)}\) converge to a simple eigenvalue \(\lambda \) of \(A\). Analyze the speed of convergence of \(\lambda ^{(k)}\) to \(\lambda \).

Krylov Subspace Methods Consider the system \(Ax=b\), in which \(A\) is a symmetric positive definite real \(m\times m\) matrix, and denote by \(x_*\) its true solution. The conjugate gradient (CG) algorithm for finding the solution to the system is:

Set \(x_0=0\), \(r_0=b\), and \(p_0=r_0\).

For \(n=1,2,3,\ldots \) \[ \begin {aligned} \alpha _n &= r_{n-1}^T r_{n-1}/p_{n-1}^T A p_{n-1},\\ x_n &= x_{n-1}+\alpha _n p_{n-1},\\ r_n &= r_{n-1}-\alpha _n A p_{n-1},\\ \beta _n &= r_n^T r_n/r_{n-1}^T r_{n-1},\\ p_n &= r_{n-1}+\beta _n p_{n-1}. \end {aligned} \] End

The vectors generated by this algorithm have the property that, provided \(r_{n-1}\ne 0\), \[ \begin {aligned} \mathcal {K}_n &\equiv \operatorname {span}\{b,Ab,A^2b,\ldots ,A^{n-1}b\} =\operatorname {span}\{x_1,x_2,\ldots ,x_n\}\\ &=\operatorname {span}\{r_0,r_1,\ldots ,r_{n-1}\} =\operatorname {span}\{p_0,p_1,\ldots ,p_{n-1}\} \end {aligned} \] and \(r_n^T r_j=0\) and \(p_n^T A p_j=0\) for all \(j<n\).

Let \(e_n=\lVert x_n-x_*\rVert _A\), where the \(A\)-norm of a vector \(x\) is defined by \(\lVert x\rVert _A=(x^TAx)^{1/2}\).

a) Prove the following:

Suppose the CG algorithm is applied to the symmetric positive definite system \(Ax=b\) and that it has not yet converged (\(r_{n-1}\ne 0\)). Then \(e_n<\lVert y-x_*\rVert _A\) for all \(y\in \mathcal {K}_n\), \(y\ne x_n\); \(\lVert e_n\rVert _A\le \lVert e_{n-1}\rVert _A\); and \(e_N=0\) for some \(N\le m\).

b) In practice this result is not very useful. Why is this, and what determines the speed of convergence of \(x_n\) to \(x_*\)? What is ‘preconditioning’ and how is it related to the speed of convergence of the CG algorithm?

Sensitivity Analysis Consider the linear system \(Ax=b\) where \(A\) is a square, non-singular matrix. A numerical solution \(\hat {x}\) actually satisfies \[ (A+\delta A)\hat {x}=b+\delta b. \] If we denote \(\delta x=\hat {x}-x\), derive an upper bound for the relative error \[ E_1=\frac {\lVert \delta x\rVert }{\lVert \hat {x}\rVert } \] in terms of the condition number of \(A\) and the norms of \(A,\hat {x},\delta A,\delta b\), where \(\lVert \cdot \rVert \) is a suitable vector norm. Also, we can define another relative error \[ E_2=\frac {\lVert \delta x\rVert }{\lVert x\rVert }. \] Derive an upper bound for \(E_2\) in terms of the condition number of \(A\) and the norms of \(\delta A,A,\delta b\) and \(b\). When are these two errors close to each bound? What’s the significance of the condition number?

Eigenvalue Problems Let \(\lambda \) be a simple eigenvalue of \(A\) (not necessarily symmetric), with right eigenvector \(x\) (i.e., \(Ax=\lambda x\)), and left eigenvector \(y\) (i.e., \(y^*A=\lambda y^*\)). Assume that \(\lVert x\rVert _2=\lVert y\rVert _2=1\). Let \(\lambda +\delta \lambda \) be the corresponding eigenvalue of \(A+\delta A\).

a) Show that \[ \delta \lambda =\frac {y^*\delta A x}{y^*x}+O(\lVert \delta A\rVert ^2), \] and derive an upper bound for \(\lvert \delta \lambda \rvert \). What is the condition number for \(\lambda \) with respect to changes in \(A\)?

b) Consider the matrix \[ \begin {bmatrix} 0 & 1 & 0 & \cdots & 0\\ 0 & 0 & 1 & \ddots & 0\\ \vdots & \ddots & \ddots & \ddots & 1\\ \epsilon & 0 & \cdots & 0 & 0 \end {bmatrix}. \] Compute \(d\lambda /d\epsilon \) and show that the condition number becomes infinite as \(\epsilon \) approaches zero.

c) Describe the power method for finding the eigenvalue of the largest absolute magnitude, and inverse iteration for the eigenvalue closest to a given value. How fast do you expect these algorithms to converge?

Singular Value Decomposition Define the singular value decomposition of a real \(m\times n\) matrix with \(m\ge n\). Is the SVD unique for a given matrix \(A\)? How is an SVD problem connected with an eigendecomposition of a symmetric matrix? Sketch the general structure of algorithms for those imported from eigendecomposition, namely, how do you reduce \(A\) to some form more manageable? How do you obtain the information about the rank of \(A\) through the SVD of \(A\)? If \(A\) is square and nonsingular, how does the SVD of \(A\) help you determine the sensitivity of the solution \(x\) for \(Ax=b\)?

Sensitivity Analysis Consider the (square, non-singular) linear system \[ Ax=b. \tag {3} \] Suppose you compute (by any method) a numerical solution \(\hat {x}\) and you are concerned about the relative error \[ E=\frac {\lVert x-\hat {x}\rVert }{\lVert x\rVert } \tag {4} \] where \(\lVert \cdot \rVert \) denotes a suitable vector norm. Derive upper and lower bounds on \(E\) in terms of the residual \(r=b-A\hat {x}\) and the condition number of \(A\) with respect to \(\lVert \cdot \rVert \).

Singular Value Decomposition Suppose that \(A\) is a real \(m\times n\) matrix, \(m\ge n\).

a) What is the singular value decomposition (SVD) of \(A\)? Does every matrix \(A\) of this type have an SVD? If your answer is yes, prove the assertion. If your answer is no, give an example of a matrix \(A\) which has no SVD.

b) For a matrix \(A\) which does have an SVD, how would having the SVD give easy access to information about the rank of \(A\)? If \(A\) were \(m\times m\) and nonsingular, how would knowing \(A\)’s SVD help you determine the sensitivity of the solution of a linear system of the following form \[ Ax=b? \]

c) For a nonsingular matrix \(A\) which does have an SVD, express the relative distance from \(A\) to the nearest rank deficient matrix in terms of \(A\)’s singular values.

Krylov Subspace Methods Consider the system \(Ax=b\), in which \(A\) is a symmetric positive definite real \(m\times m\) matrix, and denote by \(x_*\) its true solution. The conjugate gradient (CG) algorithm for finding the solution to the system is:

Set \(x_0=0\), \(r_0=b\), and \(p_0=r_0\).

For \(n=1,2,3,\ldots \) \[ \begin {aligned} \alpha _n &= r_{n-1}^T r_{n-1}/p_{n-1}^T A p_{n-1},\\ x_n &= x_{n-1}+\alpha _n p_{n-1},\\ r_n &= r_{n-1}-\alpha _n A p_{n-1},\\ \beta _n &= r_n^T r_n/r_{n-1}^T r_{n-1},\\ p_n &= r_{n-1}+\beta _n p_{n-1}. \end {aligned} \] End

The vectors generated by this algorithm have the property that, provided \(r_{n-1}\ne 0\), \[ \begin {aligned} \mathcal {K}_n &\equiv \operatorname {span}\{b,Ab,A^2b,\ldots ,A^{n-1}b\} =\operatorname {span}\{x_1,x_2,\ldots ,x_n\}\\ &=\operatorname {span}\{r_0,r_1,\ldots ,r_{n-1}\} =\operatorname {span}\{p_0,p_1,\ldots ,p_{n-1}\} \end {aligned} \] and \(r_n^T r_j=0\) and \(p_n^T A p_j=0\) for all \(j<n\).

Let \(e_n=\lVert x_n-x_*\rVert _A\), where the \(A\)-norm of a vector \(x\) is defined by \(\lVert x\rVert _A=(x^TAx)^{1/2}\).

a) Prove the following:

Theorem: Suppose the CG algorithm is applied to the symmetric positive definite system \(Ax=b\) and that it has not yet converged (\(r_{n-1}\ne 0\)). Then \(e_n<\lVert y-x_*\rVert _A\) for all \(y\in \mathcal {K}_n\), \(y\ne x_n\); \(\lVert e_n\rVert _A\le \lVert e_{n-1}\rVert _A\); and \(e_N=0\) for some \(N\le m\).

b) In practice this result is not very useful. Why is this, and what determines the speed of convergence of \(x_n\) to \(x_*\)? What is ‘preconditioning’ and how is it related to the speed of convergence of the CG algorithm?

Sensitivity of Solution of Linear System Suppose that \(A\) is a real non-singular \(n\times n\) matrix. Consider the family of linear systems \(Ax(\epsilon )=b+\epsilon c\), where \(b\) and \(c\) are given nonzero vectors in \(\mathbb {R}^n\), and \(\epsilon \) is a real parameter. Let \(x=x(0)\) be the solution for \(\epsilon =0\). Let \(\lVert \cdot \rVert _2\) denote the Euclidean vector norm. Show that \[ \frac {\lVert x(\epsilon )-x\rVert _2}{\lVert x\rVert _2} \le \lVert A\rVert _2\lVert A^{-1}\rVert _2 \frac {\lVert \epsilon c\rVert _2}{\lVert b\rVert _2}. \] The expression \(\lVert A\rVert _2\lVert A^{-1}\rVert _2\) is the condition number of \(A\). Interpret the above inequality and explain its significance?

Singular Value Decomposition Suppose that \(A\) is a real \(m\times n\) matrix with \(m\ge n\). What is the singular value decomposition (SVD) of \(A\)? Does every matrix \(A\) of this type have an SVD? If your answer is yes, prove the assertion. If your answer is no, give an example of a matrix \(A\) which has no SVD. For a matrix \(A\) which does have an SVD, how would having the SVD give easy access to information about the rank of \(A\)? If \(A\) were \(n\times n\) and nonsingular, how would knowing \(A\)’s SVD help you determine the sensitivity of the solution of a linear system of the following form \[ Ax=b? \]

Eigenvalue Problems Let \(A\) be a real \(n\times n\) matrix with simple eigenvalue \(\lambda \), right eigenvector \(x\) (i.e., \(Ax=\lambda x\)), and left eigenvector \(y\) (i.e., \(y^*A=\lambda y^*\)). Assume that \(\lVert x\rVert _2=\lVert y\rVert _2=1\). a) Show that the condition number for \(\lambda \) to changes in \(A\) is given by \(s(\lambda )=1/\lvert y^*x\rvert \). b) Give an example of a matrix \(A\) which has a badly conditioned eigenvalue, and another matrix \(A\) which has only well-conditioned eigenvalues. c) Sketch a reasonably efficient algorithm for finding the largest eigenvalue of a symmetric matrix \(A\) with distinct eigenvalues. How fast do you expect this algorithm to converge?

Sensitivity of Solution of Linear System Suppose that \(A\) is a real non-singular \(n\times n\) matrix. Consider the family of linear systems \(Ax(\epsilon )=b+\epsilon c\), where \(b\) and \(c\) are given nonzero vectors in \(\mathbb {R}^n\), and \(\epsilon \) is a real parameter. Let \(x=x(0)\) be the solution for \(\epsilon =0\). Let \(\lVert \cdot \rVert _2\) denote the Euclidean vector norm.

a) Show that \[ \frac {\lVert x(\epsilon )-x\rVert _2}{\lVert x\rVert _2} \le \lVert A\rVert _2\lVert A^{-1}\rVert _2 \frac {\lVert \epsilon c\rVert _2}{\lVert b\rVert _2}. \] The expression \(\lVert A\rVert _2\lVert A^{-1}\rVert _2\) is the condition number of \(A\). Interpret the above inequality and explain its significance?

b) What is the Singular Value Decomposition (SVD) of \(A\)? Express the condition number above in terms of \(A\)’s singular values.

c) When the condition number is very large, the matrix is called ill-conditioned. Sometimes people say that an ill-conditioned matrix is ‘nearly-singular’. Make this precise by expressing the (relative) distance between \(A\) and the nearest singular matrix to \(A\) in terms of the condition number of \(A\).

Eigenvalue Problems Let \(A\) be a real \(n\times n\) matrix with simple eigenvalue \(\lambda \), right eigenvector \(x\) (i.e., \(Ax=\lambda x\)), and left eigenvector \(y\) (i.e., \(y^*A=\lambda y^*\)). Assume that \(\lVert x\rVert _2=\lVert y\rVert _2=1\). a) Show that the condition number for \(\lambda \) to changes in \(A\) is given by \(s(\lambda )=1/\lvert y^*x\rvert \). b) Give an example of a matrix \(A\) which has a badly conditioned eigenvalue, and another matrix \(A\) which has only well-conditioned eigenvalues. c) Sketch a reasonably efficient algorithm for finding the largest eigenvalue of a symmetric matrix \(A\) with distinct eigenvalues. How fast do you expect this algorithm to converge?

a) Give an example to demonstrate the role of pivoting in Gaussian elimination in solving \(Ax=b\). Define and explain the significance of the condition number of \(A\). Compare the condition numbers, with respect to the norm of your choice, of \(A\) and \(PA\), where \(P\) is a permutation matrix.

b) Explain the \(LU\) decomposition of a matrix \(A\), in particular why the entries of \(L\) are multipliers used in Gaussian elimination, and how to solve \(Ax=b\) using \(L\) and \(U\). How much work does this take?