Orthogonal Sets
A set { v 1 → , v 2 → , . . . , v n → } of nonzero vectors is orthogonal if for all i ≠ j , v i → , v j → → v i → ⊥ v j → Example: { ( 1 0 0 ) , ( 0 1 0 ) , ( 0 0 1 ) } is orthogonal ( 1 0 0 ) ⋅ ( 0 1 0 ) = 0 , ( 1 0 0 ) ⋅ ( 0 0 1 ) = 0 , ( 0 0 1 ) ⋅ ( 0 1 0 ) = 0 \text{A set } \{\overrightarrow{v_1}, \overrightarrow{v_2}, ..., \overrightarrow{v_n} \} \text{ of nonzero vectors is orthogonal if for all } i \neq j, \overrightarrow{v_i}, \overrightarrow{v_j} \rightarrow \overrightarrow{v_i} \perp \overrightarrow{v_j} \\
\text{Example: } \{ \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix}, \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix}, \begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix} \} \text{ is orthogonal} \\
\begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix} \cdot \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix} = 0, \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix} \cdot \begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix} = 0, \begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix} \cdot \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix} = 0 A set { v 1 , v 2 , ... , v n } of nonzero vectors is orthogonal if for all i = j , v i , v j → v i ⊥ v j Example: { ⎝ ⎛ 1 0 0 ⎠ ⎞ , ⎝ ⎛ 0 1 0 ⎠ ⎞ , ⎝ ⎛ 0 0 1 ⎠ ⎞ } is orthogonal ⎝ ⎛ 1 0 0 ⎠ ⎞ ⋅ ⎝ ⎛ 0 1 0 ⎠ ⎞ = 0 , ⎝ ⎛ 1 0 0 ⎠ ⎞ ⋅ ⎝ ⎛ 0 0 1 ⎠ ⎞ = 0 , ⎝ ⎛ 0 0 1 ⎠ ⎞ ⋅ ⎝ ⎛ 0 1 0 ⎠ ⎞ = 0 Theorem: An orthogonal set is linearly independent \text{Theorem: An orthogonal set is linearly independent} Theorem: An orthogonal set is linearly independent { v 1 → , . . . , v n → } is orthonormal if it is already orthogonal and ∣ ∣ v i → ∣ ∣ = 1 (AKA all vectors are unit vectors) Can easily get an orthonormal set from an orthogonal one by dividing each vector in the set by its norm \{\overrightarrow{v_1}, ..., \overrightarrow{v_n} \} \text{ is orthonormal if it is already orthogonal and } ||\overrightarrow{v_i}|| = 1 \text{ (AKA all vectors are unit vectors)} \\
\text{Can easily get an orthonormal set from an orthogonal one by dividing each vector in the set by its norm} { v 1 , ... , v n } is orthonormal if it is already orthogonal and ∣∣ v i ∣∣ = 1 (AKA all vectors are unit vectors) Can easily get an orthonormal set from an orthogonal one by dividing each vector in the set by its norm Orthonormal sets are good for getting a standard basis for a subspace, such as Rn . In other words, orthonormal bases are as good as standard bases.
Gram-Schmidt Orthogonalization
Turns linearly independent sets into orthonormal ones
{ v 1 → , . . . , v n → } is linearly independent Let u 1 → = v 1 → u 2 → = v 2 → − u 1 → ⋅ v 2 → u 1 → ⋅ u 1 → u 1 → u 3 → = v 3 → − u 1 → ⋅ v 3 → u 1 → ⋅ u 1 → u 1 → − u 2 → ⋅ v 3 → u 2 → ⋅ u 2 → u 2 → . . . u n → = v n → − ∑ i = 1 n − 1 u i → ⋅ v n → u i → ⋅ u i → u i → To get the orthonoaml set, normalize all of the u vectors: { u 1 ^ , u 2 ^ , . . . , u n ^ } \{\overrightarrow{v_1}, ..., \overrightarrow{v_n} \} \text{ is linearly independent} \\
\text{Let } \overrightarrow{u_1} = \overrightarrow{v_1} \\
\overrightarrow{u_2} = \overrightarrow{v_2} - \frac{\overrightarrow{u_1} \cdot \overrightarrow{v_2}}{\overrightarrow{u_1} \cdot \overrightarrow{u_1}} \overrightarrow{u_1} \\
\overrightarrow{u_3} = \overrightarrow{v_3} - \frac{\overrightarrow{u_1} \cdot \overrightarrow{v_3}}{\overrightarrow{u_1} \cdot \overrightarrow{u_1}} \overrightarrow{u_1} - \frac{\overrightarrow{u_2} \cdot \overrightarrow{v_3}}{\overrightarrow{u_2} \cdot \overrightarrow{u_2}} \overrightarrow{u_2} \\
... \\
\overrightarrow{u_n} = \overrightarrow{v_n} - \sum_{i = 1}^{n - 1} \frac{\overrightarrow{u_i} \cdot \overrightarrow{v_n}}{\overrightarrow{u_i} \cdot \overrightarrow{u_i}} \overrightarrow{u_i} \\
\text{To get the orthonoaml set, normalize all of the u vectors: } \{\hat{u_1}, \hat{u_2}, ..., \hat{u_n} \} { v 1 , ... , v n } is linearly independent Let u 1 = v 1 u 2 = v 2 − u 1 ⋅ u 1 u 1 ⋅ v 2 u 1 u 3 = v 3 − u 1 ⋅ u 1 u 1 ⋅ v 3 u 1 − u 2 ⋅ u 2 u 2 ⋅ v 3 u 2 ... u n = v n − i = 1 ∑ n − 1 u i ⋅ u i u i ⋅ v n u i To get the orthonoaml set, normalize all of the u vectors: { u 1 ^ , u 2 ^ , ... , u n ^ } Example
{ ( 1 − 1 ) , ( 2 1 ) } u 1 → = v 1 → = ( 1 − 1 ) → u 1 ^ = 1 2 ( 1 − 1 ) u 2 → = ( 2 1 ) − ( 1 − 1 ) ⋅ ( 2 1 ) ( 1 − 1 ) ⋅ ( 1 − 1 ) ( 1 − 1 ) = ( 2 1 ) − 1 2 ( 1 − 1 ) = ( 1.5 1.5 ) u 2 ^ = 1 2 ( 1 1 ) Thus, { u ^ 1 , u ^ 2 } is orthonormal \{ \begin{pmatrix} 1 \\ -1 \end{pmatrix}, \begin{pmatrix} 2 \\ 1 \end{pmatrix} \} \\
\overrightarrow{u_1} = \overrightarrow{v_1} = \begin{pmatrix} 1 \\ -1 \end{pmatrix} \rightarrow \hat{u_1} = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 \\ -1 \end{pmatrix} \\
\overrightarrow{u_2} = \begin{pmatrix} 2 \\ 1 \end{pmatrix} - \frac{\begin{pmatrix} 1 \\ -1 \end{pmatrix} \cdot \begin{pmatrix} 2 \\ 1 \end{pmatrix}}{\begin{pmatrix} 1 \\ -1 \end{pmatrix} \cdot \begin{pmatrix} 1 \\ -1 \end{pmatrix}} \begin{pmatrix} 1 \\ -1 \end{pmatrix} \\
= \begin{pmatrix} 2 \\ 1 \end{pmatrix} - \frac{1}{2} \begin{pmatrix} 1 \\ -1 \end{pmatrix} = \begin{pmatrix} 1.5 \\ 1.5 \end{pmatrix} \\
\hat{u_2} = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 \\ 1 \end{pmatrix} \\
\text{Thus, } \{ \hat{u}_1, \hat{u}_2 \} \text{ is orthonormal} { ( 1 − 1 ) , ( 2 1 ) } u 1 = v 1 = ( 1 − 1 ) → u 1 ^ = 2 1 ( 1 − 1 ) u 2 = ( 2 1 ) − ( 1 − 1 ) ⋅ ( 1 − 1 ) ( 1 − 1 ) ⋅ ( 2 1 ) ( 1 − 1 ) = ( 2 1 ) − 2 1 ( 1 − 1 ) = ( 1.5 1.5 ) u 2 ^ = 2 1 ( 1 1 ) Thus, { u ^ 1 , u ^ 2 } is orthonormal Solving an SLE with No Real Solutions
Method: Least Squares
Definition: an m x n matrix A and b → ∈ R m A least squares solution to A x → = b → is a vector x ^ = x L S → ∈ R n such that for all v → ∈ R n , ∣ ∣ A x ^ − b → ∣ ∣ ≤ ∣ ∣ A v → − b → ∣ ∣ \text{Definition: an m x n matrix A and } \overrightarrow{b} \in \mathbb{R}^m \\
\text{A least squares solution to } A\overrightarrow{x} = \overrightarrow{b} \text{ is a vector } \hat{x} = \overrightarrow{x_{LS}} \in \mathbb{R}^n \text{ such that for all } \overrightarrow{v} \in \mathbb{R}^n , ||A\hat{x} - \overrightarrow{b} || \leq ||A\overrightarrow{v} - \overrightarrow{b}|| Definition: an m x n matrix A and b ∈ R m A least squares solution to A x = b is a vector x ^ = x L S ∈ R n such that for all v ∈ R n , ∣∣ A x ^ − b ∣∣ ≤ ∣∣ A v − b ∣∣ Theorem: If A is a m x n matrix and b → ∈ R m , the least squares solution of A x → = b → corresponds to solutions of A T A x → = A T b → , which is always consistent. \text{Theorem: If A is a m x n matrix and } \overrightarrow{b} \in \mathbb{R}^m \text{, the least squares solution of } A\overrightarrow{x} = \overrightarrow{b} \text{ corresponds to solutions of } A^T A\overrightarrow{x} = A^T \overrightarrow{b} \text{, which is always consistent.} Theorem: If A is a m x n matrix and b ∈ R m , the least squares solution of A x = b corresponds to solutions of A T A x = A T b , which is always consistent. Steps
1. Compute A T A and A T b → 2. Form the augmented matrix ( A T A ∣ A T b → ) and row reduce 3. This is always consistent, and any solution is a least squares solution of A x → = b → \text{1. Compute } A^T A \text{ and } A^T \overrightarrow{b} \\
\text{2. Form the augmented matrix} ( A^T A | A^T \overrightarrow{b} ) \text{ and row reduce} \\
\text{3. This is always consistent, and any solution is a least squares solution of } A\overrightarrow{x} = \overrightarrow{b} 1. Compute A T A and A T b 2. Form the augmented matrix ( A T A ∣ A T b ) and row reduce 3. This is always consistent, and any solution is a least squares solution of A x = b Examples
A = ( 0 11 1 2 1 ) , b → = ( 6 0 0 ) A T A = ( 0 1 2 1 1 1 ) ( 0 1 1 1 2 1 ) = ( 5 3 3 3 ) A T b → = ( 0 1 2 1 1 1 ) ( 6 0 0 ) = ( 0 6 ) ( 5 3 0 3 3 6 ) → ( 1 0 − 3 0 1 5 ) x ^ = ( − 3 5 ) A = \begin{pmatrix}
0 & 1
1 & 1 \\
2 & 1
\end{pmatrix},
\overrightarrow{b} = \begin{pmatrix}6\\0\\0\end{pmatrix} \\
A^T A =
\begin{pmatrix}
0 & 1 & 2 \\
1 & 1 & 1
\end{pmatrix}
\begin{pmatrix}
0 & 1 \\
1 & 1 \\
2 & 1
\end{pmatrix} =
\begin{pmatrix}
5 & 3 \\
3 & 3 \\
\end{pmatrix} \\
A^T \overrightarrow{b} =
\begin{pmatrix}
0 & 1 & 2 \\
1 & 1 & 1
\end{pmatrix}
\begin{pmatrix}6\\0\\0\end{pmatrix} =
\begin{pmatrix}0\\6\end{pmatrix} \\
\left(
\begin{array}{cc|c}
5 & 3 & 0 \\
3 & 3 & 6
\end{array}
\right) \rightarrow
\left(
\begin{array}{cc|c}
1 & 0 & -3 \\
0 & 1 & 5
\end{array}
\right) \\
\hat{x} = \begin{pmatrix}-3\\5\end{pmatrix} A = ( 0 2 11 1 1 ) , b = ⎝ ⎛ 6 0 0 ⎠ ⎞ A T A = ( 0 1 1 1 2 1 ) ⎝ ⎛ 0 1 2 1 1 1 ⎠ ⎞ = ( 5 3 3 3 ) A T b = ( 0 1 1 1 2 1 ) ⎝ ⎛ 6 0 0 ⎠ ⎞ = ( 0 6 ) ( 5 3 3 3 0 6 ) → ( 1 0 0 1 − 3 5 ) x ^ = ( − 3 5 ) A = ( 1 3 1 − 1 1 1 ) , b → = ( 5 1 0 ) A T A = ( 1 1 1 3 − 1 1 ) ( 1 3 1 − 1 1 1 ) = ( 3 3 3 11 ) A T b → = ( 1 1 1 3 − 1 1 ) ( 5 1 0 ) = ( 6 14 ) ( 3 3 6 3 11 14 ) → ( 1 0 1 0 1 1 ) x ^ = ( 1 1 ) A = \begin{pmatrix}
1 & 3 \\
1 & -1 \\
1 & 1
\end{pmatrix},
\overrightarrow{b} = \begin{pmatrix}5\\1\\0\end{pmatrix} \\
A^T A =
\begin{pmatrix}
1 & 1 & 1 \\
3 & -1 & 1
\end{pmatrix}
\begin{pmatrix}
1 & 3 \\
1 & -1 \\
1 & 1
\end{pmatrix} =
\begin{pmatrix}
3 & 3 \\
3 & 11 \\
\end{pmatrix} \\
A^T \overrightarrow{b} =
\begin{pmatrix}
1 & 1 & 1 \\
3 & -1 & 1
\end{pmatrix}
\begin{pmatrix}5\\1\\0\end{pmatrix} =
\begin{pmatrix}6\\14\end{pmatrix} \\
\left(
\begin{array}{cc|c}
3 & 3 & 6 \\
3 & 11 & 14
\end{array}
\right) \rightarrow
\left(
\begin{array}{cc|c}
1 & 0 & 1 \\
0 & 1 & 1
\end{array}
\right) \\
\hat{x} = \begin{pmatrix}1\\1\end{pmatrix} A = ⎝ ⎛ 1 1 1 3 − 1 1 ⎠ ⎞ , b = ⎝ ⎛ 5 1 0 ⎠ ⎞ A T A = ( 1 3 1 − 1 1 1 ) ⎝ ⎛ 1 1 1 3 − 1 1 ⎠ ⎞ = ( 3 3 3 11 ) A T b = ( 1 3 1 − 1 1 1 ) ⎝ ⎛ 5 1 0 ⎠ ⎞ = ( 6 14 ) ( 3 3 3 11 6 14 ) → ( 1 0 0 1 1 1 ) x ^ = ( 1 1 ) Can find the distance from the least squares solution to the desired point as well:
∣ ∣ A x L S → − b → ∣ ∣ = ∣ ∣ ( 1 3 1 − 1 1 1 ) ( 1 1 ) − ( 5 1 0 ) ∣ ∣ = ∣ ∣ ( 4 0 2 ) − ( 5 1 0 ) ∣ ∣ = 6 || A\overrightarrow{x_{LS}} - \overrightarrow{b}|| = ||
\begin{pmatrix}
1 & 3 \\
1 & -1 \\
1 & 1
\end{pmatrix}
\begin{pmatrix}1\\1\end{pmatrix} -
\begin{pmatrix}5\\1\\0\end{pmatrix}
||
= ||
\begin{pmatrix}4\\0\\2\end{pmatrix} -
\begin{pmatrix}5\\1\\0\end{pmatrix}
|| =
\sqrt{6} ∣∣ A x L S − b ∣∣ = ∣∣ ⎝ ⎛ 1 1 1 3 − 1 1 ⎠ ⎞ ( 1 1 ) − ⎝ ⎛ 5 1 0 ⎠ ⎞ ∣∣ = ∣∣ ⎝ ⎛ 4 0 2 ⎠ ⎞ − ⎝ ⎛ 5 1 0 ⎠ ⎞ ∣∣ = 6 Orthogonal Example
A = ( 1 1 1 − 1 − 1 1 1 1 ) , b → = ( 2 4 6 8 ) Project b onto C o l ( A ) = S p a n { v → , w → } v → ⊥ w → , so p r o j C o l ( A ) ( b → ) = b → ⋅ v → v → ⋅ v → v → + b → ⋅ w → w → ⋅ w → w → = ( 5 − 1 1 5 ) ( 1 1 5 1 − 1 − 1 − 1 1 1 1 1 5 ) → ( 1 0 2 0 − 1 3 0 0 0 0 0 0 ) x ^ = ( 2 3 ) A = \begin{pmatrix}
1 & 1 \\
1 & -1 \\
-1 & 1 \\
1 & 1
\end{pmatrix},
\overrightarrow{b} = \begin{pmatrix}2\\4\\6\\8\end{pmatrix} \\
\text{Project b onto } Col(A) = Span\{\overrightarrow{v}, \overrightarrow{w}\} \\
\overrightarrow{v} \perp \overrightarrow{w} \text{, so } proj_{Col(A)} (\overrightarrow{b}) = \frac{\overrightarrow{b} \cdot \overrightarrow{v}}{\overrightarrow{v} \cdot \overrightarrow{v}} \overrightarrow{v} + \frac{\overrightarrow{b} \cdot \overrightarrow{w}}{\overrightarrow{w} \cdot \overrightarrow{w}} \overrightarrow{w} = \begin{pmatrix}5\\-1\\1\\5\end{pmatrix} \\
\left(
\begin{array}{cc|c}
1 & 1 & 5 \\
1 & -1 & -1\\
-1 & 1 & 1\\
1 & 1 & 5
\end{array}
\right) \rightarrow
\left(
\begin{array}{cc|c}
1 & 0 & 2 \\
0 & -1 & 3\\
0 & 0 & 0\\
0 & 0 & 0
\end{array}
\right)
\hat{x} = \begin{pmatrix} 2 \\ 3 \end{pmatrix} A = ⎝ ⎛ 1 1 − 1 1 1 − 1 1 1 ⎠ ⎞ , b = ⎝ ⎛ 2 4 6 8 ⎠ ⎞ Project b onto C o l ( A ) = Sp an { v , w } v ⊥ w , so p ro j C o l ( A ) ( b ) = v ⋅ v b ⋅ v v + w ⋅ w b ⋅ w w = ⎝ ⎛ 5 − 1 1 5 ⎠ ⎞ ⎝ ⎛ 1 1 − 1 1 1 − 1 1 1 5 − 1 1 5 ⎠ ⎞ → ⎝ ⎛ 1 0 0 0 0 − 1 0 0 2 3 0 0 ⎠ ⎞ x ^ = ( 2 3 )