Gram–Schmidt process

Summary

Let $V$ be an inner product space over $\R$ or $\C$, and let $v_1, \dots, v_k \in V$ be linearly independent. The Gram–Schmidt process defines vectors $u_1, \dots, u_k$ by $u_1 = v_1$ and, for $2 \le j \le k$, $$u_j = v_j - \sum_{i=1}^{j-1} \frac{\langle v_j, u_i \rangle}{\langle u_i, u_i \rangle} u_i.$$ Then the vectors $e_j = u_j / \norm{u_j}$ form an orthonormal family with the same span as $v_1, \dots, v_j$ for each $j$.

Remarks

Each step subtracts from $v_j$ its projections on the earlier vectors $u_i$. For $v_1 = (1, 1)$ and $v_2 = (1, 0)$ in $\R^2$, it gives $u_1 = (1, 1)$ and $u_2 = (1/2, -1/2)$. In floating point arithmetic, the modified Gram–Schmidt process is more stable. In matrix form, the process gives the QR decomposition.

Explanations

L1 human

The Gram–Schmidt process turns any independent list of vectors into a list of perpendicular unit vectors. It treats the vectors one at a time, and it removes from each one its components along the earlier ones. Then it scales each result to length one.