We consider the linear problem Ax = b where x is the vector of unknowns, A is a matrix and b is a known vector. Formally, the solution for this problem can be written as x = A^-1b. In class, we considered the conjugate gradient solution of this problem using f(x) = (Ax - b)^t(Ax - b). A concrete, step-by-step algorithm was outlined.

An alternative target function is g(x) = .5x^tAx - bx solves exactly the same problem.

1. Show that minimizing g(x) indeed solves the original problem.
2. Write the following matlab routines:
   1. A routine to compute the gradient of the function that accepts as input the coordinates.
   2. A routine to compute the coefficient lambda for the one-dimensional search. The output should be the minimized coordinate along the search direction.
   3. A routine to perform a convergence test that checks if the norm of the gradient is smaller epsilon, where epsilon is an input parameter.
   4. A "main engine" that loops over the one-dimensional minimization.
3. Derive an expression for the new search direction, h₁, to be used at the first step of a conjugate gradient minimization of the function g(x).