Orthogonal Transformations (numerical analysis)¶
Problem¶
The problem with using normal equations to solve an overdetermined linear system of equations
is that although it works theoretically, in practice this approach yields numerical inaccuracy. There are two reasons for this behaviour.
First, information can be lost in forming the cross-product matrix and right-hand-side vector. For example
where \(\epsilon\) is some small error in a given floating point system in a machine. Then we have
This resulting matrix is singular.
Second, the condition number of a cross-product matrix, which determines the sensitivity of the solution to the normal equations, is the square of that of the original matrix \(\mathbf{A}\):
Thus, the normal equations suffer a condition squaring effect even when the fit is good and the residual is small, making the computed solution more sensitive than it should be for that least squares problem.
How can we solve this issue?
Orthogonal Transformations¶
We need an alternative from the normal equations approach due to the problems presented in the Problems section above.
Reducing a matrix to triangular form is a good way to simplify least squares problems, however we do not want to use Gaussian elimination. This is because such a transformation does not preserve the Euclidean norm and hence doesn't preserve the least squares solution.
We define a type of linear transformation that does preserve the Euclidean norm. A square real matrix \(\mathbf{Q}\) is said to be orthogonal if its columns are orthonormal (orthogonal columns and they are normalized), \(i\).\(e\), if \(\mathbf{Q^{\top}Q =I}\), the identity matrix.
How Does \(\mathbf{Q}\) Preserve the Euclidean Norm?¶
An orthogonal transformation \(\mathbf{Q}\) preserves the Euclidean norm of any vector \(\mathbf{v}\), since
Orthogonal matrices can transform vectors in various ways, such as rotation or reflection, but doesn't change the Euclidean length of a vector. Hence, if we multiply both sides of a linear least squares problem by an orthogonal matrix, the solution is unchanged.
Orthogonal matrices are incredibly important due to this norm-preserving property and that they do not amplify error. However, they are computationally expensive; much more so than Gaussian elimination methods.
Triangular Least Squares Problems¶
Triangular Least Squares Problems