The Frobenius norm is not an operator norm. Matrix norms

»Lesson 12. The rank of the matrix. Calculation of the rank of the matrix. Matrix norm

Lesson number 12. The rank of the matrix. Calculation of the rank of the matrix. Norm of matrices.

If all the minors of the matrixAorderkare equal to zero, then all minors of order k + 1, if such exist, are also equal to zero.
By the rank of the matrix A is the largest of the orders of the minors of the matrix A nonzero.
The maximum rank can be equal to the minimum number of the number of rows or columns of the matrix, i.e. if the matrix is 4x5, then the maximum rank will be 4.
The minimum rank of a matrix is 1, unless you are dealing with a zero matrix, where the rank is always zero.

The rank of a nondegenerate square matrix of order n is equal to n, since its determinant is a minor of order n and the nondegenerate matrix is nonzero.
When a matrix is transposed, its rank does not change.

Let the rank of the matrix be. Then any minor order other than zero is called base minor.
Example. Given matrix A.

The determinant of the matrix is zero.
Minor of the second order ... Therefore, r (A) = 2 and the basic minor.
The base minor is also the minor .
Minor since = 0, so it will not be basic.
Exercise: independently check which other second-order minors will be basic and which will not.

Finding the rank of a matrix by calculating all its minors requires too much computational work. (The reader can verify that there are 36 second-order minors in a fourth-order square matrix.) Therefore, a different algorithm is used to find the rank. A number of additional information is required to describe it.

Let's call the following actions on matrices elementary transformations of matrices:
1) permutation of rows or columns;
2) multiplying a row or column by a number other than zero;
3) adding to one of the rows another row multiplied by a number or adding to one of the columns of another column multiplied by a number.

Elementary transformations do not change the rank of the matrix.
Algorithm for calculating the rank of a matrix is similar to the algorithm for calculating the determinant and consists in the fact that, using elementary transformations, the matrix is reduced to a simple form, for which it is not difficult to find the rank. Since the rank did not change with each transformation, then by calculating the rank of the transformed matrix, we thereby find the rank of the original matrix.

Let it be required to calculate the rank of the size matrix mxn.

As a result of calculations, the matrix A1 has the form

If all lines starting from the third are zero, then since minor ... Otherwise, by rearranging rows and columns with numbers greater than two, we achieve that the third element of the third row is nonzero. Further, by adding the third row, multiplied by the corresponding numbers, to the rows with large numbers, we get zeros in the third column, starting from the fourth element, and so on.
At some stage, we come to a matrix in which all rows, starting from the (r + 1) th, are equal to zero (or are absent for), and the minor in the first rows and first columns is the determinant of a triangular matrix with nonzero elements on the diagonal ... The rank of such a matrix is. Therefore, Rang (A) = r.

In the proposed algorithm for finding the rank of a matrix, all calculations should be performed without rounding. An arbitrarily small change in at least one of the elements of the intermediate matrices can lead to the fact that the answer obtained will differ from the rank of the original matrix by several units.
If the elements in the original matrix were integers, then it is convenient to perform calculations without using fractions. Therefore, at each stage, it is advisable to multiply the strings by numbers such that fractions do not appear in the calculations.

In practical laboratory work, consider an example of finding the rank of a matrix.

LOCATION ALGORITHM MATRIX STANDARDS .
There are only three matrix norms.
The first norm of the matrix= the maximum of the numbers obtained by adding all the elements of each column, taken modulo.
Example: let a 3x2 matrix A be given (Fig. 10). The first column contains elements: 8, 3, 8. All elements are positive. Let's find their sum: 8 + 3 + 8 = 19. The second column contains elements: 8, -2, -8. Two elements are negative, therefore, when adding these numbers, it is necessary to substitute the modulus of these numbers (that is, without the "minus" signs). Let's find their sum: 8 + 2 + 8 = 18. The maximum of these two numbers is 19. So the first norm of the matrix is 19.

Figure 10.

Second norm of the matrix is the square root of the sum of the squares of all elements of the matrix. And this means we square all the elements of the matrix, then add the resulting values and extract the square root from the result.
In our case, the 2 norm of the matrix is equal to the square root of 269. In the diagram, I roughly extracted the square root of 269 and as a result I got about 16.401. Although it is more correct not to extract the root.

The third norm of the matrix is the maximum of the numbers obtained by adding all the elements of each row, taken modulo.
In our example: the first line contains elements: 8, 8. All elements are positive. Let's find their sum: 8 + 8 = 16. The second line contains elements: 3, -2. One of the elements is negative, therefore, when adding these numbers, it is necessary to substitute the modulus of this number. Let's find their sum: 3 + 2 = 5. The third line contains elements 8, and -8. One of the elements is negative, therefore, when adding these numbers, it is necessary to substitute the modulus of this number. Let's find their sum: 8 + 8 = 16. The maximum of these three numbers is 16. So the third norm of the matrix is 16.

Compiled by: Saliy N.A.

Collegiate YouTube

1 / 1

✪ Vector norm. Part 4.

Subtitles

Definition

Let K be the ground field (usually K = R or K = C ) and is the linear space of all matrices with m rows and n columns, consisting of elements K. On the space of matrices, a norm is given if each matrix is associated with a non-negative real number ‖ A ‖ (\ displaystyle \ | A \ |), called its norm, so that

In the case of square matrices (i.e. m = n), matrices can be multiplied without leaving the space, and therefore the norms in these spaces usually also satisfy the property submultiplicativity :

Submultiplicativity can also be performed for the norms of non-square matrices, but defined for several required sizes at once. Namely, if A is a matrix ℓ × m, and B is the matrix m × n, then A B- matrix ℓ × n .

Operator norms

An important class of matrix norms are operator norms, also referred to as subordinates or induced ... The operator norm is uniquely constructed according to two norms defined in and, proceeding from the fact that any matrix m × n is represented by a linear operator from K n (\ displaystyle K ^ (n)) v K m (\ displaystyle K ^ (m))... Specifically,

‖ A ‖ = sup (‖ A x ‖: x ∈ K n, ‖ x ‖ = 1) = sup (‖ A x ‖ ‖ x ‖: x ∈ K n, x ≠ 0). (\ displaystyle (\ begin (aligned) \ | A \ | & = \ sup \ (\ | Ax \ |: x \ in K ^ (n), \ \ | x \ | = 1 \) \\ & = \ sup \ left \ ((\ frac (\ | Ax \ |) (\ | x \ |)): x \ in K ^ (n), \ x \ neq 0 \ right \). \ end (aligned)))

Under the condition of a consistent specification of norms on vector spaces, such a norm is submultiplicative (see).

Examples of operator norms

Spectral norm properties:

The spectral norm of an operator is equal to the maximum singular number of this operator.
The spectral norm of a normal operator is equal to the absolute value of the maximum modulo eigenvalue of this operator.
The spectral norm does not change when the matrix is multiplied by an orthogonal (unitary) matrix.

Non-operator Matrix Norms

There are matrix norms that are not operator norms. The concept of non-operator norms of matrices was introduced by Yu. I. Lyubich and investigated by G.R.Belitskii.

An example of a non-operator norm

For example, consider two different operator norms ‖ A ‖ 1 (\ displaystyle \ | A \ | _ (1)) and ‖ A ‖ 2 (\ displaystyle \ | A \ | _ (2)), such as row and column norms. Forming a new norm ‖ A ‖ = m a x (‖ A ‖ 1, ‖ A ‖ 2) (\ displaystyle \ | A \ | = max (\ | A \ | _ (1), \ | A \ | _ (2)))... The new norm has the ring property ‖ A B ‖ ≤ ‖ A ‖ ‖ B ‖ (\ displaystyle \ | AB \ | \ leq \ | A \ | \ | B \ |), preserves unity ‖ I ‖ = 1 (\ displaystyle \ | I \ | = 1) and is not an operator.

Examples of norms

Vector p (\ displaystyle p)-norm

Can be considered m × n (\ displaystyle m \ times n) matrix as a vector of size m n (\ displaystyle mn) and use standard vector norms:

‖ A ‖ p = ‖ vec (A) ‖ p = (∑ i = 1 m ∑ j = 1 n | aij | p) 1 / p (\ displaystyle \ | A \ | _ (p) = \ | \ mathrm ( vec) (A) \ | _ (p) = \ left (\ sum _ (i = 1) ^ (m) \ sum _ (j = 1) ^ (n) | a_ (ij) | ^ (p) \ right) ^ (1 / p))

Frobenius norm

Frobenius norm, or Euclidean norm is a special case of the p-norm for p = 2 : ‖ A ‖ F = ∑ i = 1 m ∑ j = 1 naij 2 (\ displaystyle \ | A \ | _ (F) = (\ sqrt (\ sum _ (i = 1) ^ (m) \ sum _ (j = 1) ^ (n) a_ (ij) ^ (2)))).

The Frobenius norm is easy to calculate (in comparison, for example, with the spectral norm). Possesses the following properties:

‖ A x ‖ 2 2 = ∑ i = 1 m | ∑ j = 1 n a i j x j | 2 ≤ ∑ i = 1 m (∑ j = 1 n | a i j | 2 ∑ j = 1 n | x j | 2) = ∑ j = 1 n | x j | 2 ‖ A ‖ F 2 = ‖ A ‖ F 2 ‖ x ‖ 2 2. (\ displaystyle \ | Ax \ | _ (2) ^ (2) = \ sum _ (i = 1) ^ (m) \ left | \ sum _ (j = 1) ^ (n) a_ (ij) x_ ( j) \ right | ^ (2) \ leq \ sum _ (i = 1) ^ (m) \ left (\ sum _ (j = 1) ^ (n) | a_ (ij) | ^ (2) \ sum _ (j = 1) ^ (n) | x_ (j) | ^ (2) \ right) = \ sum _ (j = 1) ^ (n) | x_ (j) | ^ (2) \ | A \ | _ (F) ^ (2) = \ | A \ | _ (F) ^ (2) \ | x \ | _ (2) ^ (2).)

Sub-multiplicativity: ‖ A B ‖ F ≤ ‖ A ‖ F ‖ B ‖ F (\ displaystyle \ | AB \ | _ (F) \ leq \ | A \ | _ (F) \ | B \ | _ (F)), because ‖ A B ‖ F 2 = ∑ i, j | ∑ k a i k b k j | 2 ≤ ∑ i, j (∑ k | a i k | | b k j |) 2 ≤ ∑ i, j (∑ k | a i k | 2 ∑ k | b k j | 2) = ∑ i, k | a i k | 2 ∑ k, j | b k j | 2 = ‖ A ‖ F 2 ‖ B ‖ F 2 (\ displaystyle \ | AB \ | _ (F) ^ (2) = \ sum _ (i, j) \ left | \ sum _ (k) a_ (ik) b_ (kj) \ right | ^ (2) \ leq \ sum _ (i, j) \ left (\ sum _ (k) | a_ (ik) || b_ (kj) | \ right) ^ (2) \ leq \ sum _ (i, j) \ left (\ sum _ (k) | a_ (ik) | ^ (2) \ sum _ (k) | b_ (kj) | ^ (2) \ right) = \ sum _ (i, k) | a_ (ik) | ^ (2) \ sum _ (k, j) | b_ (kj) | ^ (2) = \ | A \ | _ (F) ^ (2) \ | B \ | _ (F) ^ (2)).
‖ A ‖ F 2 = tr ⁡ A ∗ A = tr ⁡ AA ∗ (\ displaystyle \ | A \ | _ (F) ^ (2) = \ mathop (\ rm (tr)) A ^ (*) A = \ mathop (\ rm (tr)) AA ^ (*)), where t r ⁡ A (\ displaystyle \ mathop (\ rm (tr)) A)- matrix trace A (\ displaystyle A), A ∗ (\ displaystyle A ^ (*)) is a Hermitian conjugate matrix.
‖ A ‖ F 2 = ρ 1 2 + ρ 2 2 + ⋯ + ρ n 2 (\ displaystyle \ | A \ | _ (F) ^ (2) = \ rho _ (1) ^ (2) + \ rho _ (2) ^ (2) + \ dots + \ rho _ (n) ^ (2)), where ρ 1, ρ 2,…, ρ n (\ displaystyle \ rho _ (1), \ rho _ (2), \ dots, \ rho _ (n))- singular values of the matrix A (\ displaystyle A).
‖ A ‖ F (\ displaystyle \ | A \ | _ (F)) does not change on matrix multiplication A (\ displaystyle A) left or right into orthogonal (unitary) matrices.

Module maximum

The modulus maximum norm is another special case of the p-norm for p = ∞ .

‖ A ‖ max = max (| a i j |). (\ displaystyle \ | A \ | _ (\ text (max)) = \ max \ (| a_ (ij) | \).)

Schatten's norm

Consistency of Matrix and Vector Norms

‖ A x ‖ b ≤ ‖ A ‖ a b ‖ x ‖ a (\ displaystyle \ | Ax \ | _ (b) \ leq \ | A \ | _ (ab) \ | x \ | _ (a))

for any A ∈ K m × n, x ∈ K n (\ displaystyle A \ in K ^ (m \ times n), x \ in K ^ (n))... The operator norm by construction is consistent with the original vector norm.

Examples of agreed, but not subordinate, matrix norms:

Equivalence of norms

All norms in space K m × n (\ displaystyle K ^ (m \ times n)) are equivalent, that is, for any two norms ‖. ‖ Α (\ displaystyle \ |. \ | _ (\ Alpha)) and ‖. ‖ Β (\ displaystyle \ |. \ | _ (\ Beta)) and for any matrix A ∈ K m × n (\ displaystyle A \ in K ^ (m \ times n)) the double inequality is true.

Matrix norm we will call the real number assigned to this matrix || A || such that which, as a real number, is assigned to each matrix from n-dimensional space and satisfies 4 axioms:

1. || A || ³0 and || A || = 0 only if A is a zero matrix;

2. || αA || = | α | · || A ||, where a R;

3. || A + B || £ || A || + || B ||;

4. || A · B || £ || A || · || B ||. (multiplicative property)

The norm of the matrices can be entered in various ways. Matrix A can be viewed as n 2 - dimensional vector.

This norm is called the Euclidean norm of the matrix.

If for any square matrix A and any vector x, the dimension of which is equal to the order of the matrix, the inequality || Ax || £ || A || · || x ||

then the norm of the matrix A is said to be consistent with the norm of the vector. Note that on the left of the last condition is the norm of the vector (Ax is a vector).

Various matrix norms are coordinated with the given vector norm. Let's choose the smallest one among them. This will be

This matrix norm is subordinate to a given vector norm. The existence of a maximum in this expression follows from the continuity of the norm, because there always exists a vector x -> || x || = 1 and || Ax || = || A ||.

Let us show that the norm N (A) is not subject to any vector norm. The norms of the matrix, subject to the previously introduced vector norms, are expressed as follows:

1. || A || ¥ = | a ij | (norm-maximum)

2. || A || 1 = | a ij | (norm-sum)

3. || A || 2 =, (spectral norm)

where s 1 is the largest proper value of the symmetric matrix A ¢ A, which is the product of the transposed and the original matrices. T k the matrix A ¢ A is symmetric, then all its eigenvalues are real and positive. The number of l -properties is the value, and the nonzero vector x is the eigenvector of the matrix A (if they are related by the relation Ax = lx). If the matrix A itself is symmetric, A ¢ = A, then A ¢ A = A 2 and then s 1 =, where is the largest modulus eigenvalue of the matrix A. Therefore, in this case we have =.

The eigenvalues of the matrix do not exceed any of its agreed norms. Normalizing the relation defining the eigenvalues, we obtain || λx || = || Ax ||, | λ | · || x || = || Ax || £ || A || · || x ||, | λ | £ || A ||

Since || A || 2 £ || A || e, where the Euclidean norm is easy to calculate, in the estimates, instead of the spectral norm, the Euclidean norm of the matrix can be used.

30. Conditionality of systems of equations. Condition factor .

Conditionality- the influence of the decision on the initial data. Ax = b: vector b corresponds to the decision x... Let be b will change by the amount. Then the vector b + the new solution will match x + : A (x + ) = b +... Since the system is linear, then Ax + A = b +, then A = ; = ; = ; b = Ax; = then; *, where is the relative error of the solution perturbation, - condition factorcond (A) (how many times the solution error can increase), is the relative perturbation of the vector b. cond (A) = ; cond (A) * Coefficient properties: depends on the choice of the matrix norm; cond ( = cond (A); multiplying a matrix by a number does not affect the condition factor. The larger the coefficient, the more the error in the initial data affects the solution of the SLAE. The condition number cannot be less than 1.

31. The sweep method for solving systems of linear algebraic equations.

It is often necessary to solve systems whose matrices, being weakly filled, i.e. containing many nonzero elements. The matrices of such systems usually have a certain structure, among which there are systems with matrices of a strip structure, i.e. in them, nonzero elements are located on the main diagonal and on several side diagonals. For solving systems with strip matrices, the Gaussian method can be transformed into more efficient methods. Let us consider the simplest case of band systems, to which, as we will see later, the solution of discretization problems for boundary value problems for differential equations by the methods of finite differences, finite elements, etc. adjacent to it:

Three diagonal matrices have only (3n-2) nonzero entries.

Let's rename the coefficients of the matrix:

Then, in component notation, the system can be represented as:

A i * x i-1 + b i * x i + c i * x i + 1 = d i , i = 1, 2, ..., n; (7)

a 1 = 0, c n = 0. (eight)

The structure of the system assumes a relationship only between neighboring unknowns:

x i = x i * x i +1 + h i (9)

x i -1 = x i -1 * x i + h i -1 and substitute in (7):

A i (x i-1 * x i + h i-1) + b i * x i + c i * x i + 1 = d i

(a i * x i-1 + b i) x i = –c i * x i + 1 + d i –a i * h i-1

Comparing the resulting expression with the representation (7), we get:

Formulas (10) represent recurrence relations for calculating the sweep coefficients. They require initial values to be set. In accordance with the first condition (8) for i = 1 we have a 1 = 0, and hence

Further, the remaining sweep coefficients are calculated and stored by formulas (10) for i = 2,3, ..., n, and for i = n, taking into account the second condition (8), we obtain x n = 0. Therefore, in accordance with formula (9) x n = h n.

After that, according to the formula (9), the unknowns x n -1, x n -2, ..., x 1 are sequentially found. This step of the calculation is called the reverse run, while the calculation of the sweep factors is called the forward sweep.

For the successful application of the sweep method, it is necessary that in the process of calculations there are no situations with division by zero, and with a large dimension of the systems, there should not be a rapid increase in rounding errors. We will call the run correct if the denominator of the sweep coefficients (10) does not vanish, and sustainable if ½x i ½<1 при всех i=1,2,…, n. Достаточные условия корректности и устойчивости прогонки, которые во многих приложениях выполняются, определяются теоремой.

Theorem. Let the coefficients a i and c i of equation (7) for i = 2,3, ..., n-1 differ from zero and let

½b i ½> ½a i ½ + ½c i ½ for i = 1, 2, ..., n. (eleven)

Then the sweep defined by formulas (10), (9) is correct and stable.