Loading content...
In linear algebra, an orthonormal basis is a set of vectors that are both mutually orthogonal (perpendicular to each other) and normalized (each has unit length). Constructing such a basis is fundamental for simplifying computations in vector spaces, as it allows any vector to be uniquely expressed as a linear combination of basis vectors using simple dot products.
The Gram-Schmidt Orthogonalization Process is a classical algorithm that transforms a set of linearly independent vectors into an orthonormal set spanning the same subspace. The algorithm works iteratively:
Mathematical Formulation:
Given input vectors v₁, v₂, ..., vₖ, the orthonormal basis vectors u₁, u₂, ..., uₙ are computed as:
$$u_1 = \frac{v_1}{|v_1|}$$
For each subsequent vector vᵢ:
$$w_i = v_i - \sum_{j=1}^{i-1} \text{proj}_{u_j}(v_i)$$
where the projection is: $\text{proj}_u(v) = (v \cdot u) \cdot u$
If $|w_i| > \text{tol}$, then: $u_i = \frac{w_i}{|w_i|}$
Your Task: Write a Python function that computes an orthonormal basis for the subspace spanned by a list of 2D vectors using the Gram-Schmidt process. The function should:
vectors = [[1.0, 0.0], [1.0, 1.0]]
tol = 1e-10[[1.0, 0.0], [0.0, 1.0]]Step 1: Take the first vector [1.0, 0.0]. Its norm is 1.0, so normalizing it gives u₁ = [1.0, 0.0].
Step 2: Take the second vector [1.0, 1.0]. Compute its projection onto u₁: • proj_u₁(v₂) = ([1.0, 1.0] · [1.0, 0.0]) × [1.0, 0.0] = 1.0 × [1.0, 0.0] = [1.0, 0.0]
Subtract the projection: • w₂ = [1.0, 1.0] - [1.0, 0.0] = [0.0, 1.0]
The norm of w₂ is 1.0, which is greater than the tolerance 1e-10. Normalize to get u₂ = [0.0, 1.0].
Result: The orthonormal basis is [[1.0, 0.0], [0.0, 1.0]], which are the standard unit vectors.
vectors = [[3.0, 0.0], [0.0, 4.0]]
tol = 1e-10[[1.0, 0.0], [0.0, 1.0]]Step 1: Take [3.0, 0.0]. Its norm is 3.0. Normalize: u₁ = [3.0/3.0, 0.0/3.0] = [1.0, 0.0].
Step 2: Take [0.0, 4.0]. Compute projection onto u₁: • proj_u₁(v₂) = ([0.0, 4.0] · [1.0, 0.0]) × [1.0, 0.0] = 0 × [1.0, 0.0] = [0.0, 0.0]
Subtract projection: • w₂ = [0.0, 4.0] - [0.0, 0.0] = [0.0, 4.0]
Norm of w₂ is 4.0 > 1e-10. Normalize: u₂ = [0.0, 1.0].
Observation: The input vectors were already orthogonal (perpendicular to each other), so the algorithm only needed to normalize them.
vectors = [[1.0, 0.0], [0.0, 1.0]]
tol = 1e-10[[1.0, 0.0], [0.0, 1.0]]Input Analysis: The input vectors [1.0, 0.0] and [0.0, 1.0] are already orthonormal: • They have unit length: ||[1.0, 0.0]|| = 1.0, ||[0.0, 1.0]|| = 1.0 • They are orthogonal: [1.0, 0.0] · [0.0, 1.0] = 0
Algorithm Verification: • u₁ = [1.0, 0.0] (already normalized) • For [0.0, 1.0]: projection onto u₁ is zero, so w₂ = [0.0, 1.0] • ||w₂|| = 1.0 > tol, normalize to get u₂ = [0.0, 1.0]
Result: The output equals the input since the vectors were already orthonormal.
Constraints