diff options
Diffstat (limited to 'source/know/concept/gram-schmidt-method/index.md')
| -rw-r--r-- | source/know/concept/gram-schmidt-method/index.md | 59 |
1 files changed, 43 insertions, 16 deletions
diff --git a/source/know/concept/gram-schmidt-method/index.md b/source/know/concept/gram-schmidt-method/index.md index 70ad512..a62522e 100644 --- a/source/know/concept/gram-schmidt-method/index.md +++ b/source/know/concept/gram-schmidt-method/index.md @@ -8,39 +8,66 @@ categories: layout: "concept" --- -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: +Given a set of $$N$$ linearly independent vectors $$\ket{V_1}, \ket{V_2}, ...$$ +from a [Hilbert space](/know/concept/hilbert-space/), +the **Gram-Schmidt method** is an algorithm that turns them +into an orthonormal set $$\ket{n_1}, \ket{n_2}, ...$$ as follows +(in [Dirac notation](/know/concept/dirac-notation/)): 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{\inprod{V_1}{V_1}}} + \ket{n_1} + = \frac{\ket{V_1}}{\sqrt{\inprod{V_1}{V_1}}} \end{aligned}$$ -2. Begin loop. Take the next non-orthonormal vector $$\ket{V_j}$$, and +2. Begin loop. Take the next input 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} \inprod{n_1}{V_j} - \ket{n_2} \inprod{n_2}{V_j} - ... - \ket{n_{j-1}} \inprod{n_{j-1}}{V_{j-1}} + \ket{g_j} + = \ket{V_j} - \ket{n_1} \inprod{n_1}{V_j} - \ket{n_2} \inprod{n_2}{V_j} - ... - \ket{n_{j-1}} \inprod{n_{j-1}}{V_j} \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. + This leaves only the part of $$\ket{V_j}$$ + that is orthogonal to all previous $$\ket{n_k}$$. + This why the input vectors must be linearly independent; + otherwise $$\ket{g_j}$$ could become zero. -3. Normalize the resulting ortho*gonal* vector $$\ket{n_j'}$$ to make it + On a computer, the resulting $$\ket{g_j}$$ will + not be perfectly orthogonal due to rounding errors. + The above description of step #2 is particularly bad. + A better approach is: + + $$\begin{aligned} + \ket{g_j^{(1)}} + &= \ket{V_j} - \ket{n_1} \inprod{n_1}{V_j} + \\ + \ket{g_j^{(2)}} + &= \ket{g_j^{(1)}} - \ket{n_2} \inprod{n_2}{g_j^{(1)}} + \\ + \vdots + \\ + \ket{g_j} + = \ket{g_j^{(j-1)}} + &= \ket{g_j^{(j-2)}} - \ket{n_{j-2}} \inprod{n_{j-2}}{g_j^{(j-2)}} + \end{aligned}$$ + + In other words, instead of projecting $$\ket{V_j}$$ directly onto all $$\ket{n_k}$$, + we instead project only the part of $$\ket{V_j}$$ that has already been made orthogonal + to all previous $$\ket{n_m}$$ with $$m < k$$. + This is known as the **modified Gram-Schmidt method**. + +3. Normalize the resulting ortho*gonal* vector $$\ket{g_j}$$ to make it ortho*normal*: $$\begin{aligned} - \ket{n_j} = \frac{\ket{n_j'}}{\sqrt{\inprod{n_j'}{n_j'}}} + \ket{n_j} + = \frac{\ket{g_j}}{\sqrt{\inprod{g_j}{g_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/). +4. Loop back to step 2, taking the next vector $$\ket{V_{j+1}}$$, + until all $$N$$ have been processed. |