Skip to main content

Subsection 8.2.3 Relation 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_{k\!\! \mod \!\!n} \text{,}\) which cycles through the standard basis vectors.

Homework 8.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 This 8.2.3.2.

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

login