So, I am comparing different methods for finding the least square solution for $Ax=b$ where $$A(i,j)=\frac{1}{i+j+10}$$ for $i=1,2,...,10$ and $j=1,2,...,8$.
Also $$b=[1,2,...,10]^T$$
I have made different matlab functions for each method. At first I approximate x by using Normal Equations. Then I approximate the solution using QR decomposition with Modified Gram-Schmidt and Householder.
The thing here is that the error vector ($b-Ax$) when using Householder reflections is really close to the error vector when using normal equations. On the other hand, the error vector for Modified Gram-Schmidt contains values really close to $0$, so the approximation is better.
I have learned that Householder is more stable than both normal equations and modified gram-schmidt. How come, in this example there is a greater error when using Householder reflections? Does it have to do with some sprecific characteristics of A?
I also used $SVD$ analysis for the same problem and the error values where almost identical to the error values for modified gram-schmidt.
I'll simply address why Householder is more numerically stable than either of the normal equations and modified Gram Schmidt. I wrote this code roughly 8 months ago I believe.. Except for the case when the condition number of a matrix is very low House Householder out-performs all other methods. In the case the condition number of the matrix is rather low then the methods will be roughly equal.
Addressing the point. Modified Gram Schmidt is equivalent to Classic Gram Schmidt except how it computes the sequence of orthogonal components. In Trefethan the methods CGS/MGS and Householder are compared in the following method. CGS/MGS is affectionately known as "triangular orthogonalization" whereas Householder is "orthogonal triangularization"
To grasp this the actual method by which CGS/MGS is performed the QR decomposition is the following.
Suppose $A \in \mathbb{C}^{m \times n} , A = QR $ and $Q \in \mathbb{C}^{m \times n} , R \in \mathbb{C}^{n \times n} $ ok...CGS/MGS actually compute it in the following way..
$$ A \underbrace{R_{1}R_{2} \cdots R_{n}}_{\hat{R}^{-1}} = \hat{Q} $$
This is triangular orthogonalization. Ok..Now householder
$$ \underbrace{Q_{n} \cdots Q_{2} Q_{1} }_{Q^{*}} A = R $$
I am going to take a moment to talk about the critical difference here...the critical difference regardless of how MGS uses projections is the following. Consider this.
If I am making a lot of triangular matrices and suppose n is very large. Triangular matrices don't have a condition number of 1. Orthogonal matrices do. Then the condition number no matter how small it is will amplify.
Suppose that the condition number is at max in this sequence of matrices $R_{i}$ is 2 but there are $50$ of them. What is my condition number? Now how does that affect the error of solving the system of equations?