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

标签：

• Tokyo-University
• Matrix-Norm
• Eigenvalues-and-Eigenvectors
• Stationary-Iterative-Method

Author

kainoj, 祭音Myyura

Description

For a positive integer $p$, the $p$-norm $\|\boldsymbol{x}\|_p$ of an $n$-dimensional real vector

$$\boldsymbol{x} = \begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{pmatrix}$$

is defined by

$$\|\boldsymbol{x}\|_p := \left( \sum_{j=1}^n |x_j|^p \right)^{1/p}.$$

Answer the following questions

(1) Prove that

$$\|\boldsymbol{x}\|_2 \le \|\boldsymbol{x}\|_1 \le \sqrt{n} \|\boldsymbol{x}\|_2$$

holds for every $n$-dimensional real vector $\boldsymbol{x}$. You may use the Cauchy-Schwarz inequality:

$$|\boldsymbol{x} \cdot \boldsymbol{y}| \le \|\boldsymbol{x}\|_2 \|\boldsymbol{y}\|_2$$

for any $n$-dimensional real vectors $\boldsymbol{x}$ and $\boldsymbol{y}$. Here $\boldsymbol{x} \cdot \boldsymbol{y}$ stands for the inner product of vectors $\boldsymbol{x}$ and $\boldsymbol{y}$.

(2) Define the $p$-norm $\|A\|_p$ of an $n \times n$ real matrix $A$ by

$$\|A\|_p := \max_{\boldsymbol{x} \neq \boldsymbol{0}} \frac{\|Ax\|_p}{\|\boldsymbol{x}\|_p},$$

where $\boldsymbol{x}$ ranges over the set of $n$-dimensional real vectors.

• (2.1) Prove that if $\|A\|_p < 1$ then $\lim_{k \to \infty} \|A^k x_0\|_p = 0$ for every $n$-dimensional real vector $x_0$.
• (2.2) Suppose that $A$ is an $n \times n$ real symmetric matrix. Prove that $\|A\|_2$ is the maximum of the absolute values of the eigenvalues of $A$.

(3) Consider solving an $n$-dimensional linear system $A \boldsymbol{x} = \boldsymbol{b}$, where $A$ is a non-singular real symmetric matrix, and $\boldsymbol{x}$ and $\boldsymbol{b}$ are unknown and constant real vectors, respectively.

Given an initial vector $\boldsymbol{x}^{(0)}$, the vector $\boldsymbol{x}^{(j)}$ $(j = 1, 2, \ldots)$ is computed by

$$\boldsymbol{x}^{(j)} = \boldsymbol{b} + (I - A)\boldsymbol{x}^{(j-1)},$$

where $I$ stands for the identity matrix.

Give a necessary and sufficient condition on $A$ such that the sequence $\boldsymbol{x}^{(1)}, \boldsymbol{x}^{(2)}, \ldots$ converges to the true solution for every initial vector $\boldsymbol{x}^{(0)}$.

题目描述

对正整数 $p$，定义 $n$ 维实向量 $\boldsymbol{x}=(x_1,\ldots,x_n)^\mathsf{T}$ 的 $p$-范数为

$$\|\boldsymbol{x}\|_p :=\left(\sum_{j=1}^n|x_j|^p\right)^{1/p}.$$

回答下列问题。

（1）证明任意 $n$ 维实向量 $\boldsymbol{x}$ 均满足

$$\|\boldsymbol{x}\|_2\le \|\boldsymbol{x}\|_1 \le \sqrt n\,\|\boldsymbol{x}\|_2.$$

可以使用柯西—施瓦茨不等式

$$|\boldsymbol{x}\cdot\boldsymbol{y}| \le\|\boldsymbol{x}\|_2\|\boldsymbol{y}\|_2,$$

其中“$\cdot$”表示内积。

（2）定义实矩阵 $A\in\mathbb{R}^{n\times n}$ 的诱导 $p$-范数为

$$\|A\|_p :=\max_{\boldsymbol{x}\ne\boldsymbol 0} \frac{\|A\boldsymbol{x}\|_p}{\|\boldsymbol{x}\|_p}.$$

• （2.1）证明：若 $\|A\|_p<1$，则对任意初始向量 $\boldsymbol{x}_0$，都有 $\lim_{k\to\infty}\|A^k\boldsymbol{x}_0\|_p=0$。
• （2.2）设 $A$ 为实对称矩阵，证明 $\|A\|_2$ 等于 $A$ 的各特征值绝对值中的最大值。

（3）考虑求解 $n$ 维线性方程组 $A\boldsymbol{x}=\boldsymbol{b}$，其中 $A$ 是非奇异实对称矩阵， $\boldsymbol{x}$ 为未知向量，$\boldsymbol{b}$ 为给定实向量。给定初值 $\boldsymbol{x}^{(0)}$，按

$$\boldsymbol{x}^{(j)} =\boldsymbol{b}+(I-A)\boldsymbol{x}^{(j-1)} \qquad(j=1,2,\ldots)$$

生成迭代序列。给出关于 $A$ 的充要条件，使该序列对任意 $\boldsymbol{x}^{(0)}$ 都收敛到方程组的真解。

Kai

(1)

$$||x||_2 = \sqrt{\sum_{i=1}^{n} x_{i}^2} \leq \sum_{i=1}^{n} \sqrt{x_{i}^2} = \sum_{i=1}^{n} |x_{i}| = ||x||_{1}$$

On the other hand, let $y_i=\operatorname{sgn}(x_i)$, with $y_i=0$ when $x_i=0$. Since

$$\|y\|_2^2=\sum_{i=1}^n y_i^2\leq n,$$

we have

$$\begin{aligned} ||x||_1 = x \cdot y &\leq ||x||_{2} ||y||_{2} \\ &\leq \sqrt{n} ||x||_{2}. \end{aligned}$$

The first inequality comes from Cauchy-Schwarz inequality: $|xy| \leq ||x||_2 ||y||_2$.

(2)

(2.1)

Matrix $A$ defines some transformation and $||A||_p$ measures how original vector will be stretched by the transformation. If $||A||_p < 1$ then the transformation \textit{shrinks} the vector. By applying the transformation multiple times, we will shrink the vector more and more. In particular, applying it infinitely many times will shrink the vector to zero. Formally:

$$\begin{aligned} 0 &\leq \lim_{k \to \infty} ||A^k x_0||_p \\ &\leq \lim_{k \to \infty} ||A^k||_p || x_0||_p \\ &= || x_0||_p \lim_{k \to \infty} ||A^k||_p \\ &= || x_0||_p \: 0 \\ &= 0 \end{aligned}$$

First equality holds because norm is always non-negative, second is a property of a norm. Moreover, limit $\lim_{k \to \infty} ||A^k||_p = 0$, because:

$$\lim_{k \to \infty} ||A^k||_p \leq \lim_{k \to \infty} (||A||_p)^k =0$$

NB: $||AB||_p \leq ||A||_p ||B||_p$ for any matrices $A,B \in \mathbb{R}^{n\times n}$.

(2.2)

Since $A$ is symmetric, $A=Q\Lambda Q^T$ for an orthogonal $Q$. Put $y=Q^Tx$. For $\|x\|_2=1$, orthogonality gives

$$\|y\|_2^2=y^Ty=x^TQQ^Tx=x^Tx=1.$$

Therefore

$$\|Ax\|_2^2=\|\Lambda y\|_2^2 =\sum_i\lambda_i^2y_i^2 \leq \left(\max_i|\lambda_i|\right)^2.$$

Equality holds when $x$ is a unit eigenvector corresponding to an eigenvalue of maximum absolute value. Hence $\|A\|_2=\max_i|\lambda_i|$.

(3)

Let $e^{(j)} = x^{(j)} - x$ be the error vector. We want $\lim_{j\to \infty} e^{(j)} = 0$. In other words, we want $e^{(j+1)} < e^{(j)}$ for all sufficiently big $j$.

$$\begin{aligned} e^{(j+1)} = x^{(j+1)} - x &= b - x + (I -A) x^{(j)} \\ &= Ax - x + (I -A) x^{(j)} \\ &= -(I-A)x + (I -A) x^{(j)} \\ &= (I -A)(x^{(j)} - x) \\ \end{aligned}$$

Here, we obtain: $e^{(j+1)} = (I -A) e^{(j)}$. Taking a norm both sides:

$$\begin{aligned} ||e^{(j+1)}|| &= ||(I -A) e^{(j)}|| \\ &\leq ||I -A|| \: || e^{(j)}|| \end{aligned}$$

Thus $e^{(j)}=(I-A)^je^{(0)}$. Since $I-A$ is symmetric, this tends to zero for every $e^{(0)}$ iff

$$\max_i|1-\lambda_i(A)|<1,$$

or equivalently, iff every eigenvalue of $A$ satisfies $0<\lambda_i(A)<2$.

Knowledge

More reading: http://runge.math.smu.edu/Courses/Math3315_Spring10/iterative_linear.pdf