function [ x, it ] = gradient_descent_linear ( A, b, alpha, tol, it_max )

%*****************************************************************************80
%
%% gradient_descent_linear() solves a least squares problem using gradient descent.
%
%  Discusssion:
%
%    We are given an MxN matrix A and a right hand side M-vector B.
%    We seek an N-vector X which minimizes the L2 norm |A*X-B|.
%    We apply gradient descent to the function f(x) = 1/2 ||A*x-b||^2
%    with derivative f'(x) = A'*x
%
%  Licensing:
%
%    This code is distributed under the MIT license.
%
%  Modified:
%
%    27 July 2022
%
%  Author:
%
%    Original R code by James Howard;
%    MATLAB version by John Burkardt.
%
%  Reference:
%
%    James Howard,
%    Computational Methods for Numerical Analysis with R,
%    CRC Press, 2017,
%    ISBN13: 978-1-4987-2363-3.
%
%  Input:
%
%    real A(M,N): the matrix.
%
%    real B(M): the right hand side.
%
%    real ALPHA: the stepsize.
%
%    real TOL: the step tolerance.
%
%    integer IT_MAX: the maximum number of steps.
%
%  Output:
%
%    real X(N): the approximate least squares solution.
%
%    integer IT: the number of steps taken.
%
  [ m, n ] = size ( A );
  x = zeros ( n, 1 );

  for it = 1 : it_max

    e = A * x - b;
    d = A' * e;
    xold = x;
    x = x - alpha * d;

    if ( norm ( x - xold ) < tol )
      break;
    end

  end

  return
end

