Gram-Schmidt Orthogonalization Process


Introduction

Gram-Schmidt Orthogonalization Process is an algorithm or a procedure to get a set of orthonormal basis from a set of basis of a vector space(linearly independent vectors). It includes both finding the mutually orthogonal vectors and then normalizing them (See Video 1). It is based on the projection property of orthogonal basis.

1

2

Video 1: Introduction to Gram-Schmidt Orthogonalization Process

Bird's Eye View

If $V$ is an inner product space and $\beta_1,\beta_2,\cdots,\beta_n$ be any linearly independent vectors in $V$. Then one may construct orthogonal vectors $\alpha_1, \alpha_2, \cdots, \alpha_k$ in $V$ such that for each $k=1,2,3, \cdots, n$, the set $\alpha_1, \alpha_2, \cdots, \alpha_k$ is a basis for the subspace spanned by $\beta_1,\beta_2,\cdots,\beta_n$.

Gram-Schmidt Orthogonalization Process is an algorithm which takes in a set of linearly independent vectors and produces orthonormal vectors. First vector $\beta_1$ is normalised to get $\alpha_1$. For second vector $\alpha_2$, we take the inner product of $\beta_2$ and $\alpha_1$ which gives the magnitude of the projection of $\beta_2$ on $\alpha_1$, then we subtract the projection to get the orthogonal vector which is normalised and we get $\alpha_2$. See video 2 (it shows how we get orthogonal vectors using projections).

The set of orthonormal vectors which we get depends on the set of linearly independent vectors given initially and also their order. 

3

4

Video 2: Obtaining orthogonal vectors using projections

The Gram-Schmidt Orthogonalization Process

If $V$ is a vector space and we have a set of non-orthogonal basis $\{\beta_1, \beta_2, \beta_3, \cdots, \beta_n\}$. Our aim to get a set of orthonormal basis, say, $\{\alpha_1, \alpha_2, \alpha_3, \cdots, \alpha_n\}$. Follow this procedure or algorithm to get orthonormal basis.

$\alpha_1 = \frac{w_1}{||w_1||}$    where $w_1 = \beta_1$

$\alpha_2 = \frac{w_2}{||w_2||}$    where $w_2 = \beta_2 - <\beta_2,\alpha_1> \alpha_1$

$\alpha_3 = \frac{w_3}{||w_3||}$    where $w_3 = \beta_3 - (<\beta_3,\alpha_1> \alpha_1 + <\beta_3,\alpha_2> \alpha_2)$

$\vdots$

$\alpha_n = \frac{w_n}{||w_n||}$    where $w_n = \beta_n - (<\beta_n,\alpha_1> \alpha_1 + <\beta_n,\alpha_2> \alpha_2 + \cdots + <\beta_n,\alpha_{n-1}> \alpha_{n-1})$

5

So, at the end of the process, you get the set of orthonormal basis $\{\alpha_1, \alpha_2, \alpha_3, \cdots, \alpha_n\}$. This method is based on the property of projections(inner product) of orthonormal basis (refer to lecture notes of Inner Product Spaces and Orthonormal basis for more details).

6

Now let us refer to video 2 again. Let the normalised vector of $a$ be $\alpha_1$. From Video 2 we can see that $b-p$ is orthogonal to $a$ where $p$ is the projection of $b$ on $a$ i.e. $p = <b,\alpha_1> \alpha_1$. Here, we using $\alpha_1$ to calculate $p$ as $\alpha_1\in$ Linear Span$(a)$ and it is normalised(i.e. $||\alpha_1|| = 1$ ). So we can directly multiply magnitude of projection $(<b,\alpha_1>)$ with $\alpha_1$ to get $p$.

Then we normalise the vector (b-p) to get orthonormal vector. Now we have $\alpha_1$ and $\alpha_2$ (2 orthonormal vectors) and a linearly independent vector $\beta_3$ so another mutually orthogonal vector $\alpha_3$ will be as follows:

$\alpha_3 = \frac{w_3}{||w_3||}$    where $w_3 = \beta_3 - (<\beta_3,\alpha_1> \alpha_1 + <\beta_3,\alpha_2> \alpha_2)$

Refer to video 3 for a visual explanation of how Gram-Schmidt Orthogonalization Process give mutually orthonormal vectors.

8

9

Video 3: Visual Explanation of how Gram-Schmidt Orthogonalization Process give mutually orthonormal vectors

For simplicity and ease in visualization, we considered the vectors $\beta_1,\beta_2,\beta_3$ such that $\alpha_1,\alpha_2$ and $\alpha_3$ came out to be standard basis i.e. $\left( \begin{array}{c} 1 \\ 0 \\ 0 \end{array} \right),\left( \begin{array}{c} 0 \\ 1 \\ 0 \end{array} \right)$ and $\left( \begin{array}{c} 0 \\ 0 \\ 1 \end{array} \right)$. But it is not necessary that we will get only standard basis(See Video 4). The set of orthonormal basis which we will get depends on the set of initial vectors $\beta_1,\beta_2,\cdots,\beta_n$ and on their order. If we can now generalise this for n-dimension vector space. The algorithm which we get is the same procedure that we described above i.e. Gram-Schmidt Orthogonalization Process.

10

13

Video 4: Example of Orthonormal Vectors which are different from standard basis

Applications

This algorithm is primarily used to get orthonormal bases easily.

15

Pause And Ponder

Take a set of vectors which has some linearly dependent vectors in it and try to come with an explanation of why we get some zero vectors when we apply Gram-Schmidt Orthogonalization Process on those vectors.

16

History

Erhard Schmidt got his doctorate in 1905 under David Hilbert for a problem which involved integral equations. Also, he published a paper on integral equations in which he gave Gram-Schmidt process for getting orthonormal bases for some functions. This generalized results of J.P. Gram who considered this problem when studying the least squares. However, Laplace presented earlier than Gram or Schmidt. [3]

17

References

  1. Linear Algebra (Second Edition) by Kenneth Hoffman and Ray Kunze Pg 280,281
  2. https://www.math.tamu.edu/~yvorobet/MATH304-2011A/Lect3-05web.pdf
  3. Numerical Analysis(8 th edition) Book by J. Douglas Faires and Richard L. Burden(Pg 500)

18


Contributor:
Mentor & Editor:
Verified by:
Approved On:

The following notes and their corrosponding animations were created by the above-mentioned contributor and are freely avilable under CC (by SA) licence. The source code for the said animations is avilable on GitHub and is licenced under the MIT licence.




The work under this website is licenced under a Creative Commons Attribution-Share Alike 4.0 International License CC BY-SA