Linear Algebra — Gram-Schmidt, Gram-Schmidt Orthogonalization (Part 2)

Gram-Schmidt Orthogonalization Process

So far, we have been repeatedly emphasizing “for the unsolvable system of equations Ax=b, if the matrix A is an orthonormal matrix, it will be fine…”. Because, whether it is to find the projection or calculate the normal equation of the least squares, they all contain $A^{T}A$ . When A is a standard orthogonal matrix Q $Q^{T}Q=I$ , at the same time can directly find the optimal solution $\hat{x}=Q^{T}b$ . From now on, we will introduce in detail how to use Gram Schmidt’s method to construct a set of orthonormal bases that are orthogonal to each other.

Gram-Schmidt process:

There is an equation system Ax=b, matrix A is composed of three linearly independent column vectors a, b, c. First, we construct three mutually orthogonal vectors A, B, and C based on a, b, and c. After the construction, we divide A, B, and C by their respective lengths, and finally get a set of orthonormal bases we want $q_{1}$ , $q_{2}$ , $q_{3}$ . Let $q_{1}$ , $q_{2}$ , $\$ are three column vectors of the matrix respectively, Get the orthonormal matrix Q.

Step 1: Make vector A equal to vector a, get the first vector A, and determine the first direction.

$A=a$

Step 2: Since the set of orthogonal bases I want to construct are mutually orthogonal, our second vector B must be perpendicular to vector A. We let b subtract the projection vector of b on A $p_{b}$ , get another component B of b in the direction perpendicular to A. In fact, B is perpendicular to the projection vector $p_{b}$ $e_{b}$ .

$B=b-p_{b}=b-\frac{A^{T}b}{A^{T}A}A$

Step 3: Use the vector c to subtract the projection of c on the subspace (plane) spanned by A and B $p_{c}$ , get another component C perpendicular to this subspace. That is, perpendicular to the projection vector $p_{c}$ error vector $e_{c}$ . The new vector C is perpendicular to both A and B.

$C=c-p_{c}=c-\frac{A^{T}c}{A^{T}A}A-\frac{B^{T}c}{ B^{T}B}B$

Step 4: Normalize A, B, and C that are orthogonal to each other to obtain a set of orthonormal bases with a vector length of 1 $q_{1}$ , $q_{2}$ , $q_{3}$ .

$q_{1}=\frac{A}{\left \| A \right \|},\; q_{2}=\frac{B}{\ left \| B \right \|},\; q_{3}=\frac{C}{\left \| C \right \|}$

If there is still d, you need to subtract the projection of d in the three directions of the constructed vectors A, B, and C from d (or subtract the projection of d in the space formed by A, B, and C Projection), get another component D perpendicular to the vector A, B, C.

The core idea of the Gram Schmidt orthogonalization process is: Continuously use new known vectors, subtract the projection components of the vectors on the already constructed vectors, and get what we are looking for vertical component.

That is: old_vector – projection = new_vector

Example:

Finally, we give an example of the Gram Schmidt orthogonalization calculation process. At the beginning, there are three linearly independent vectors a,b,c that are not orthogonal to each other, where a=[1, -1, 0], b=[2, 0, -2], c=[3, -3, 3], as shown in the figure below:

Use Gram schmidt’s idea of orthogonalization to construct a set of orthogonal bases q1,q2,q3 containing three column vectors:

q1, q2, q3 are a set of orthonormal bases, they are orthogonal to each other and their length is 1, as shown in the following figure:

This is a diagram containing intermediate results A, B, and C. It can be seen that q1, q2, and q3 are in the same direction as A, B, and C. The only difference is that A, B, and C have not been normalized:

Matlab code:

%% Example of CSDN
%Original points
X=[0,0,0];
Y=[0,0,0];
Z=[0,0,0];
U=[1,2,3];
V=[-1,0,-3];
W=[0, -2, 3];
quiver3(X,Y,Z,U,V,W,0,'LineWidth',1)
axis equal
legend('a,b,c','Location','northwest')
hold on

%Orthogonal vectors
U=[1,1,1];
V=[-1,1,1];
W=[0,-2,1];
quiver3(X,Y,Z,U,V,W,0,'LineWidth',1)
axis equal
legend('a,b,c','A,B,C','Location','northwest')

%Orthonormal bases
U=[1/sqrt(2),1/sqrt(6),1/sqrt(3)];
V=[-1/sqrt(2),1/sqrt(6),1/sqrt(3)];
W=[0,-2/sqrt(6), 1/sqrt(3)];
quiver3(X,Y,Z,U,V,W,0,'LineWidth',3)
axis equal
legend('a,b,c','A,B,C','q1,q2,q3','Location','northwest')

(full text)

Author — Panasonic J27

References (thanks):

1. Introduction to Linear Algebra, Fifth Edition – Gilbert Strang

2. Linear Algebra and Its Applications, Hou Zixin, Nankai University Press, 1990

(The accompanying picture has nothing to do with this article)

Copyright Statement: Some pictures, text or other materials in this article may come from many different websites and instructions, so I cannot list them here. If there is any infringement, please inform and delete it immediately. Everyone is welcome to reprint, but if someone quotes or copies my article, you must indicate in your article that the pictures or text you use come from my article, otherwise, the infringement will be investigated. —-Panasonic J27