$Post := If[MatrixQ[#1], MatrixForm[#1], #1] & (* outputs matrices in MatrixForm*) Remove[ "Global`*"] // Quiet (* remove all variables *)

Introduction to Computational Linear Algebra by Nabil Nassif

So far, we discussed stationary iterative methods based on transferring the given linear algebra problem A x = b into fixed point problem

\[ \mathbf{x} = g({\bf x}) . \]
Using an initial guess x(0), we generate a sequence of iterative values
\[ \mathbf{x}^{(k+1)} = g\left( {\bf x}^{(k)} \right) , \qquad k=0,1,2,\ldots . . \]
Its realization involves splitting the main matrix A into two parts, A = S + (A − S), where S must be invertible square matrix. Upon multiplication both sides of the given equation by S−1, we can reduce the given problem to a fixed point problem:
\[ \mathbf{x} = {\bf B}\,{\bf x} + {\bf d} , \qquad {\bf B} = {\bf I} - {\bf S}^{-1} {\bf A} , \]
which is suitable for sequential iterations. However, stationary iterative methods utilize the same function g(x) for every iteration loosing all information gathered throughout the iteration. Now we are going to use function g(x) that depends on every iteration, so g(x) = gk(x) for every step k.

Gradient Method

In the method of steepest descent, also known as the gradient method, we choose direction vectors as residue vectors r(k) = b − A x(k), the negative gradient, and the optimal αk. Starting from x(0), we compute for k = 0, 1, 2, …,

\[ \mathbf{x}^{(k+1)} = \mathbf{x}^{(k)} + \left( \frac{\left\| \mathbf{r}^{(k)} \right\|^2}{\left\langle \mathbf{r}^{(k)} \mid {\bf A}\,\mathbf{r}^{(k)} \right\rangle} \right) \mathbf{r}^{(k)} , \qquad k = 0, 1, 2, \ldots . \]

The methods considered in this section is based on solution in the form:

\[ \mathbf{x}^{(k+1)} = \mathbf{x}^{(k)} + \alpha_k {\bf p}_k , \qquad k=0,1,2,\ldots , \]
where vector pk is the search direction and the scalar αk is the step size. Note that this formula includes basic stationary methods, since such methods operate with α ≡ 1 and vector pk does not depend on k.

The simplest nonstationary scheme based on setting a varying search direction and step size is obtained by setting p k = r k , i.e., M k −1 = α k I , with I the identity matrix. The resulting family of methods is called gradient descent.

Using splitting with nonsingular matrix S, we rewrite the main equation A x = b as
\[ \mathbf{S}\,\mathbf{x} = \left( \mathbf{S} - \mathbf{A} \right) \mathbf{x} + \mathbf{b} \qquad \iff \qquad \mathbf{x} = \mathbf{x} - \mathbf{S}^{-1} \mathbf{A}\,\mathbf{x} + \mathbf{S}^{-1} \mathbf{b} . \]
This identity leads to the iterative scheme
\[ \mathbf{x}^{(k+1)} = \mathbf{x}^{(k)} - \mathbf{S}^{-1} \mathbf{A}\,\mathbf{x}^{(k)} + \mathbf{S}^{-1} \mathbf{b} , \qquad k=0,1,2,\ldots . \]
We are looking at the gradient descent iteration
\[ \mathbf{x}^{(k+1)} = \mathbf{x}^{(k)} + \alpha_k \mathbf{r}_k , \]
where the residual vector is
\[ \mathbf{r}_k = {\bf b} - {\bf A}\,{\bf x}^{(k)} , \qquad k=0,1,2,\ldots . \]

Gradient Method

The methods considered in this section is based on solution in the form:

\[ \mathbf{x}^{(k+1)} = \mathbf{x}^{(k)} + \alpha_k {\bf p}_k , \qquad k=0,1,2,\ldots , \]
where vector pk is the search direction and the scalar αk is the step size. Note that this formula includes basic stationary methods, since such methods operate with α ≡ 1 and vector pk does not depend on k.

The simplest nonstationary scheme based on setting a varying search direction and step size is obtained by setting p k = r k , i.e., M k −1 = α k I , with I the identity matrix. The resulting family of methods is called gradient descent.

Using splitting with nonsingular matrix S, we rewrite the main equation A x = b as
\[ \mathbf{S}\,\mathbf{x} = \left( \mathbf{S} - \mathbf{A} \right) \mathbf{x} + \mathbf{b} \qquad \iff \qquad \mathbf{x} = \mathbf{x} - \mathbf{S}^{-1} \mathbf{A}\,\mathbf{x} + \mathbf{S}^{-1} \mathbf{b} . \]
This identity leads to the iterative scheme
\[ \mathbf{x}^{(k+1)} = \mathbf{x}^{(k)} - \mathbf{S}^{-1} \mathbf{A}\,\mathbf{x}^{(k)} + \mathbf{S}^{-1} \mathbf{b} , \qquad k=0,1,2,\ldots . \]
We are looking at the gradient descent iteration
\[ \mathbf{x}^{(k+1)} = \mathbf{x}^{(k)} + \alpha_k \mathbf{r}_k , \]
where the residual vector is
\[ \mathbf{r}_k = {\bf b} - {\bf A}\,{\bf x}^{(k)} , \qquad k=0,1,2,\ldots . \]

 

  1. Burden, R.L. and Faires, J.D., Numerical Analysis, nineth edition, Broks/Cole, Cengage, Boston, MA,
  2. Darve, E. and Wootters, M., Numerical Linear Algebra with Julia, SIAM, Philadelphia, 2021.
  4. Watkins, D.S., Fundamentals of Matrix Computations, Wiley; 3rd edition, 2010.
  5. White, R.E., Computational Linear Algebra with Applications and MATLAB Computations, CRC Press Boca Raton, FL, 2023. doi: 10.1201/9781003304128

 

  1. Darve, E. and Wootters, M., Numerical Linear Algebra with Julia, SIAM, Philadelphia, 2021.
  2. Loehr, N., Advanced Linear Algebra, CRC Press, 2014.