blob: 0b02eee54a71266cf6aa50c92a005619efe4c2a4 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
---
title: "Gram-Schmidt method"
firstLetter: "G"
publishDate: 2021-02-22
categories:
- Mathematics
- Algorithms
date: 2021-02-22T21:36:08+01:00
draft: false
markup: pandoc
---
# Gram-Schmidt method
Given a set of linearly independent non-orthonormal vectors
$\ket*{V_1}, \ket*{V_2}, ...$ from a [Hilbert space](/know/concept/hilbert-space/),
the **Gram-Schmidt method**
turns them into an orthonormal set $\ket*{n_1}, \ket*{n_2}, ...$ as follows:
1. Take the first vector $\ket*{V_1}$ and normalize it to get $\ket*{n_1}$:
$$\begin{aligned}
\ket*{n_1} = \frac{\ket*{V_1}}{\sqrt{\braket*{V_1}{V_1}}}
\end{aligned}$$
2. Begin loop. Take the next non-orthonormal vector $\ket*{V_j}$, and
subtract from it its projection onto every already-processed vector:
$$\begin{aligned}
\ket*{n_j'} = \ket*{V_j} - \ket*{n_1} \braket*{n_1}{V_j} - \ket*{n_2} \braket*{n_2}{V_j} - ... - \ket*{n_{j-1}} \braket*{n_{j-1}}{V_{j-1}}
\end{aligned}$$
This leaves only the part of $\ket*{V_j}$ which is orthogonal to
$\ket*{n_1}$, $\ket*{n_2}$, etc. This why the input vectors must be
linearly independent; otherwise $\ket{n_j'}$ may become zero at some
point.
3. Normalize the resulting ortho*gonal* vector $\ket*{n_j'}$ to make it
ortho*normal*:
$$\begin{aligned}
\ket*{n_j} = \frac{\ket*{n_j'}}{\sqrt{\braket*{n_j'}{n_j'}}}
\end{aligned}$$
4. Loop back to step 2, taking the next vector $\ket*{V_{j+1}}$.
If you are unfamiliar with this notation, take a look at [Dirac notation](/know/concept/dirac-notation/).
|
