Subsection8.2.3Relation to Splitting Methods

Let us pick some really simple search directions in the right-most algorithm in Homework 8.2.2.2: $p^{(k)} = e_{i\!\! \mod \!\!n} \text{,}$ which cycles through the standard basis vectors.

Homework8.2.3.1.

For the right-most algorithm in Homework 8.2.2.2, show that if $p^{(0)} = e_0 \text{,}$ then

\begin{equation*} \chi_0^{(1)} = \chi_0^{(0)} + \frac{1}{\alpha_{0,0}} \left( \beta_0 - \sum_{j=0}^{n-1} \alpha_{0,j} \chi_j^{(0)} \right) = \frac{1}{\alpha_{0,0}} \left( \beta_0 - \sum_{j=1}^{n-1} \alpha_{0,j} \chi_j^{(0)} \right). \end{equation*}
Solution
• $p^{(0)} = e_0 \text{.}$

• $p^{(0)\,T} A p^{(0)} = e_0^T A e_0= \alpha_{0,0}$ (the $(0,0)$ element in $A \text{,}$ not to be mistaken for $\alpha_0$).

• $r^{(0)} = A x^{(0)} - b \text{.}$

• $p^{(0)\,T} r^{(0)} = e_0^T ( b - A x^{(0)} ) = e_0^T b - e_0^T A x^{(0)} = \beta_0 - \widetilde a_0^T x^{(0)} \text{,}$ where $\widetilde a_k^T$ denotes the $k$th row of $A \text{.}$

• $x^{(1)} = x^{(0)} + \alpha_0 p^{(0)} = x^{(0)} + \frac{p^{(0)\,T} r^{(0)}}{p^{(0)\,T} A p^{(0)}} e_0 = x^{(0)} + \frac{\beta_0 - \widetilde a_0^T x^{(0)}}{\alpha_{0,0}} e_0 \text{.}$ This means that only the first element of $x^{(0)}$ changes, and it changes to

\begin{equation*} \chi_0^{(1)} = \chi_0^{(0)} + \frac{1}{\alpha_{0,0}} \left( \beta_0 - \sum_{j=0}^{n-1} \alpha_{0,j} \chi_j^{(0)} \right) = \frac{1}{\alpha_{0,0}} \left( \beta_0 - \sum_{j=1}^{n-1} \alpha_{0,j} \chi_j^{(0)} \right). \end{equation*}

This looks familiar...

Careful contemplation of the last homework reveals that this is exactly how the first element in vector $x \text{,}$ $\chi_0 \text{,}$ is changed in the Gauss-Seidel method!

Ponder This8.2.3.2.

Continue the above argument to show that this choice of descent directions yields the Gauss-Seidel iteration.