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

标签：

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

Author

kainoj, shuncleopasfang, 祭音Myyura

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

题目描述

考虑 $n$ 维实线性方程组 $A\boldsymbol{x}=\boldsymbol{b}$，其中 $A$ 为非奇异系数矩阵， $\boldsymbol{x}$ 为未知向量，$\boldsymbol{b}\ne\boldsymbol0$ 为给定向量。 本题中的向量范数均为 $2$-范数，矩阵范数均为其对应的诱导范数。回答下列问题。

（1）给出矩阵 $A$ 的条件数定义。

（2）设 $\widetilde{\boldsymbol{x}}\ne\boldsymbol0$ 是方程组的近似解，残差为 $\boldsymbol{r}=\boldsymbol{b}-A\widetilde{\boldsymbol{x}}$。用 $\boldsymbol{r}$ 和 $\widetilde{\boldsymbol{x}}$ 构造一个秩为 $1$ 的矩阵 $E$，使

$$(A+E)\widetilde{\boldsymbol{x}}=\boldsymbol{b}$$

严格成立。

（3）考虑 $A$ 的误差 $\delta A$，使方程组变为

$$(A+\delta A)(\boldsymbol{x}+\delta\boldsymbol{x}) =\boldsymbol{b},$$

其中 $\delta\boldsymbol{x}$ 是解的变化。假设 $A+\delta A$ 非奇异，且此处 $\delta A$ 与第（2）问的 $E$ 无关。通过估计 $\delta\boldsymbol{x}$，证明

$$\frac{\|\delta\boldsymbol{x}\|} {\|\boldsymbol{x}+\delta\boldsymbol{x}\|} \le \operatorname{cond}_2(A)\frac{\|\delta A\|}{\|A\|}.$$

（4）证明对任意 $n$ 维实奇异矩阵 $B$，恒有

$$\|A-B\|\ge\frac1{\|A^{-1}\|}.$$

可以使用：若实矩阵 $C$ 奇异，则存在非零实向量 $\boldsymbol{y}$ 使 $C\boldsymbol{y}=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\neq0} \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}$$

Thus

$$E=\frac{r\hat{x}^T}{\hat{x}^T\hat{x}}$$

The numerator $r\hat{x}^T$ is the outer product of two vectors; every column is a scalar multiple of $r$. The denominator $\hat{x}^T\hat{x}=\|\hat{x}\|_2^2$ is a nonzero scalar, so dividing by it does not change the rank. Moreover,

$$E\hat{x} =\frac{r\hat{x}^T\hat{x}}{\hat{x}^T\hat{x}} =r.$$

Thus $E$ has rank $1$ when $r\neq0$ and satisfies $(A+E)\hat{x}=b$. If $r=0$ and $n\geq2$, one may instead take $E=uv^T$ with $u,v\neq0$ and $v^T\hat{x}=0$. For $n=1$ and $r=0$, no rank-$1$ solution exists; $E=0$ is the only choice.

(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 $A$ is nonsingular. Taking norms gives

$$\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 \| }{\| A \|} \| \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/.