東京大学 情報理工学系研究科 コンピュータ科学専攻 2019年2月実施 問題4

Author

kainoj, shuncleopasfang

Description

Consider an \(n\) dimensional linear system \(Ax = b\), where \(A\), \(x\), and \(b\) are an \(n\) dimensional real coefficient matrix, an \(n\) dimensional real vector of unknowns, and an \(n\) dimensional real given vector, respectively. Assume that \(A\) is not singular and \(b \neq 0\). The vector norm and the matrix norm used in this problem are the 2-norm and the matrix norm corresponding to the 2-norm, respectively.

Answer the following questions.

(1) Answer the definition of the condition number of \(A\).

(2) Suppose that \(\widetilde{x} \neq 0\) is an approximate solution of the linear system. Using the residual \(r = b - A\widetilde{x}\) and \(\widetilde{x}\), find a rank \(1\) matrix \(E\) which satisfies \((A+E)\widetilde{x} = b\) exactly.

(3) Consider the effect of inaccuracy \(\delta A\) of \(A\). Namely, the linear system becomes

\[ (A + \delta A)(x + \delta x) = b, \]

where \(\delta x\) is the effect on the solution vector \(x\). Assume that \(A + \delta A\) is not singular. In addition, \(\delta A\) has nothing to do with \(E\) in the question (2). By evaluating \(\delta x\), prove that the relative inaccuracy of \(x\) is related to that of \(A\) by the inequality:

\[ \frac{\|\delta x\|}{\| x+\delta x \|} \leq \text{cond}_2(A) \frac{\|\delta A \|}{\| A \|}, \]

where \(\text{cond}_2(A)\) is the condition number of \(A\).

(4) Prove that for any \(n\) dimensional real singular matrix \(B\), the relation

\[ \| A-B \| \geq \frac{1}{\| A^{-1} \|} \]

is always satisfied. You may use the following fact: when an \(n\) dimensional real matrix \(C\) is singular, there is a non-zero real vector \(y\) such that \(Cy = 0\).

Kai

(1)

Condition number \(\kappa(A)\) of \(A\) is:

\[ \kappa(A) = \|A\| \: \|A^{-1}\| \]

where \(\|\cdot \|\) denotes a norm of a matrix:

\[ \|A\| = \max_{x\in \mathbb{R^N}} \frac{\|Ax\|}{\|x\|} = \max_{x: \|x\|=1} \|Ax\| \]

(2)

We know \(Ax = b\) and let \(r = b- A\hat{x}\):

\[ \begin{aligned} (A+E)\hat{x} &= b \\ A\hat{x} + E\hat{x} &= b \\ E\hat{x} &= b - A\hat{x} \\ E\hat{x} &= r \end{aligned} \]

The matrix \(E = \frac{\mathbf{r} \hat{x}^\top}{\hat{x}^\top \hat{x}}\) can be formed by taking the outer product of the vector \(\mathbf{r}\) and the transpose of the vector \(\hat{x}\) (\(\hat{x}^\top\)), and then dividing each element of the outer product by the scalar \(\hat{x}^\top \hat{x}\). Here, \(\hat{x}^\top \hat{x}\) is the inner product of the vector \(\hat{x}\) with itself, representing the squared norm (sum of squares) of \(\hat{x}\).

The matrix \(E = \frac{\mathbf{r} \hat{x}^\top}{\hat{x}^\top \hat{x}}\) is a rank-1 matrix, and this can be explained simply as follows:

1. Outer product property: The matrix \(\mathbf{r} \hat{x}^\top\) is the outer product of two vectors, resulting in a matrix. An outer product matrix inherently has a rank of 1 because it can be expressed as the linear combination of the two generating vectors (\(\mathbf{r}\) and \(\hat{x}\)).

2. Scalar division: Dividing each element of the matrix by the scalar \(\hat{x}^\top \hat{x}\) (a single number) does not change the rank of the matrix, as scalar multiplication or division only scales the elements without affecting the linear dependencies.

Therefore, \(E\) is a rank-1 matrix because it is derived from the outer product of two vectors.

(3)

\[ \begin{aligned} (A+ \delta A)(x+ \delta x) = b \\ Ax + A(\delta x) + \delta A(x+ \delta x) = b \end{aligned} \]

Substituting \(Ax = b\):

\[ \begin{aligned} A(\delta x) + \delta A(x+ \delta x) &= 0 \\ - A(\delta x) &= \delta A(x+ \delta x) \\ -\delta x &= A^{-1} (\delta A)(x+ \delta x) \end{aligned} \]

because matrix \(A\) is not singular, so inverse \(A^{-1}\) exist. Now, take the norm both sides. We are assuming that \(A + \sigma A\) is not singular, so it has inverse and thus a norm:

\[ \begin{aligned} \|\delta x \| &= \| A^{-1} \: [\delta A(x+ \delta x) ]\| \\ &\leq \| A^{-1} \| \: \| \delta A(x+ \delta x) \| \\ &\leq \| A^{-1} \| \: \| \delta A \| \: \| x + \delta x \| \end{aligned} \]

\[ \begin{aligned} \frac{\|\delta x \|}{ \| x + \delta x \| } &\leq \| A^{-1} \| \: \| \delta A \| \\ &= \| A^{-1} \| \: \frac{\| A^{1} \| }{\| A^{1} \|} \| \delta A \| \\ &= \kappa(A) \frac{\|\delta A\|}{\|A\|} \end{aligned} \]

(4)

When an \(n\) dimensional real matrix C is singular, there is a non-zero, real vector \(y\) such that \(Cy = 0\). In particular, we can choose a unit vector \(y' = \frac{y}{\|y\|}\).

Let \(x \in nullspace(B)\) be a unit vector i.e. \(Bx = 0\) and \(\|x\| = 1\).

\[ \begin{aligned} \|A-B\| &= \|A-B\| \: \|x\| \\ &\geq \| (A-B)x \| \\ &= \|Ax - Bx\| \\ &= \|Ax\| \end{aligned} \]

On the other hand:

\[ \begin{aligned} 1 = \|x\| = \| A^{-1} \:(Ax) \| &\leq \| A^{-1} \| \: \|Ax\| \\ \|Ax\| &\geq \frac{1}{\|A^{-1}\|} \end{aligned} \]

More on condition numbers: https://blogs.mathworks.com/cleve/2017/07/17/what-is-the-condition-number-of-a-matrix/.