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

标签：

• Tokyo-University
• Condition-Number
• Matrix-Norm
• Matrix-Inverse

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/.