1

Which of the following are necessarily true when solving a system of linear equations Ax=b for a matrix A that is nearly singular?

Note: the residual of a solution is defined here to be the Euclidian norm of the vector r, where r = Ax - b calculated using your computed solution for x.

Here are the choices:

determinant of A is large

the residual of the solution is small

roundoff-error will degrade the solution

the condition number of A will be very large

the condition number of A will be very small

truncation error will degrade the solution

the residual of the solution is large

1 Answers1

0

1) When solving a system of equations $Ax=b$ for a matrix $A$ that is nearly singular, the determinant of $A$ is large: FALSE

Example: $A=\alpha I\in\mathbb{R}^{n\times n}$, $\det(A)=\alpha^n$ (arbitrarily large or small depending on $\alpha$, conditioning $\kappa(A)=1$.

Example: $A$ an upper triangular matrix with $1$ on the diagonal and $-1$ in the remainder of the upper part. There is an analytic expression for the condition number which I do not remember but it grows with $n$ really fast (e.g., for $n=10$, $\kappa(A)\approx 2000$). On the other hand, $\det(A)=1$.

2) When solving a system of equations $Ax=b$ for a matrix $A$ that is nearly singular, the residual of the solution is large / small: FALSE

Consider an equivalent system $(\alpha A)x=\alpha b$, which does not change anything on "near" singularity of $A$. The residual $\alpha(b-Ax)$ of the computed solution $x$ can be by a choice of $\alpha$ made arbitrarily large or small.

3) When solving a system of equations $Ax=b$ for a matrix $A$ that is nearly singular, the condition number of $A$ will be very large: TRUE

As far as I know, this is the common definition of what "nearly" singular matrix is. This can be defined as having "large" condition number or equivalently small singular values relatively to its largest one (note that for the spectral condition number, $\kappa(A)=\sigma_{\max}(A)/\sigma_{\min}(A)$ is the ratio of the extreme singular values of $A$). Also it can be defined as having "large" sensitivity of the solution with respect to the changes in data.

Also note that $1/\kappa(A)$ is the relative (with respect to $\|A\|$) distance to the nearest singular matrix.

4) When solving a system of equations $Ax=b$ for a matrix $A$ that is nearly singular, roundoff-error will degrade the solution: TRUE (at least it can be expected)

When solving $Ax=b$ by a computer, a reasonable algorithm for doing so is so-called backward stable, that is, your computed $x$ satisfy $$ (A+E)x=b+f $$ with the perturbations $E$ and $f$ being "small", usually one wants to have, e.g., something like $$ \|E\|\leq\epsilon\|A\|, \quad \|f\|\leq\epsilon\|b\|. $$ where $\epsilon$ is the machine precision (e.g., double precision floating arithmetic has something like $10^{-16}$). From a perturbation theory for linear systems, we have that the relative error of the solution $x^*-x$ ($x^*$ is the exact solution of $Ax=b$) is related to $\epsilon$ (the relative changes in $A$ and $b$) by $$ \frac{\|x^*-x\|}{\|x^*\|} \leq \frac{2\kappa(A)}{1-\epsilon\kappa(A)} $$ (provided that $\epsilon\kappa(A)<1$ meaning that the perturbed matrix remains nonsingular). Hence having a nearly singular matrix with large condition number, you can normally expect to have large forward error approximately (neglecting the denominator) proportional to the backward error (which is normally small for good algorithms independently how bad is your system).

NOTE: I'm not sure what exactly means the truncation error in this context so I won't discuss it.