跳到主要内容

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

Author​

kainoj

Description​

For a positive integer , the -norm of an -dimensional real vector

is defined by

Answer the following questions

(1) Prove that

holds for every -dimensional real vector . You may use the Cauchy-Schwarz inequality:

for any -dimensional real vectors and . Here stands for the inner product of vectors and .

(2) Define the -norm of an real matrix by

where ranges over the set of -dimensional real vectors.

  • (2.1) Prove that if then for every -dimensional real vector .
  • (2.2) Suppose that is an real symmetric matrix. Prove that is the maximum of the absolute values of the eigenvalues of .

(3) Consider solving an -dimensional linear system , where is a non-singular real symmetric matrix, and and are unknown and constant real vectors, respectively.

Given an initial vector , the vector is computed by

where stands for the identity matrix.

Give a necessary and sufficient condition on such that the sequence converges to the true solution for every initial vector .

Kai​

(1)​

On the other hand, let be a unit vector:

The first inequality comes from Cauchy-Schwarz inequality: .

(2)​

(2.1)​

Matrix defines some transformation and measures how original vector will be stretched by the transformation. If 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:

First equality holds because norm is always non-negative, second is a property of a norm. Moreover, limit , because:

NB: for any matrices .

(2.2)​

Since is symmetric, then it can be diagonalized , where is orthogonal matrix (i.e. ). Note that

Let be a unit vector which maximizes the above. We have:

By substituting :

Because . On the other hand, let be eigenvector corresponding to . Of course , because is orthogonal.

(3)​

Let be the error vector. We want . In other words, we want for all sufficiently big .

Here, we obtain: . Taking a norm both sides:

Thus, the sequence converge to real solution if

Knowledge​

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