跳到主要内容

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

Author

kainoj, shuncleopasfang

Description

Consider an dimensional linear system , where , , and are an dimensional real coefficient matrix, an dimensional real vector of unknowns, and an dimensional real given vector, respectively. Assume that is not singular and . 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 .

(2) Suppose that is an approximate solution of the linear system. Using the residual and , find a rank matrix which satisfies exactly.

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

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

where is the condition number of .

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

is always satisfied. You may use the following fact: when an dimensional real matrix is singular, there is a non-zero real vector such that .

Kai

(1)

Condition number of is:

where denotes a norm of a matrix:

(2)

We know and let :

The matrix can be formed by taking the outer product of the vector and the transpose of the vector (), and then dividing each element of the outer product by the scalar . Here, is the inner product of the vector with itself, representing the squared norm (sum of squares) of .

The matrix is a rank-1 matrix, and this can be explained simply as follows:

  1. Outer product property: The matrix 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 ( and ).

  2. Scalar division: Dividing each element of the matrix by the scalar (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, is a rank-1 matrix because it is derived from the outer product of two vectors.

(3)

Substituting :

because matrix is not singular, so inverse exist. Now, take the norm both sides. We are assuming that is not singular, so it has inverse and thus a norm:

(4)

When an dimensional real matrix C is singular, there is a non-zero, real vector such that . In particular, we can choose a unit vector .

Let be a unit vector i.e. and .

On the other hand:

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