## Unit8.1.1Solving linear systems by solving a minimization problem

\begin{equation*} f( \chi ) = \frac{1}{2} \alpha \chi^2 - \beta \chi. \end{equation*}

Finding the value $\widehat \chi$ that minimizes this polynomial can be accomplished via the steps:

• Compute the derivative and set it to zero:

\begin{equation*} f'( \widehat \chi ) = \alpha \widehat \chi - \beta = 0. \end{equation*}

We notice that computing $\widehat \chi$ is equivalent to solving the linear system (of one equation)

\begin{equation*} \alpha \widehat \chi = \beta. \end{equation*}
• It is a minimum if $\alpha \gt 0$ (the quadratic polynomial is concaved up).

Obviously, you can turn this around: in order to solve $\alpha \widehat \chi = \beta$ where $\alpha \gt 0 \text{,}$ we can instead minimize the polynomial

\begin{equation*} f( \chi ) = \frac{1}{2} \alpha \chi^2 - \beta \chi. \end{equation*}

This course does not have multivariate calculus as a prerequisite, so we will walk you through the basic results we will employ. We will focus on finding a solution to $A x = b$ where $A$ is symmetric positive definite (SPD). (In our discussions we will just focus on real-valued problems). Now, if

\begin{equation*} f( x ) = \frac{1}{2} x^T A x - x^T b, \end{equation*}

The function $f( x )$ is minimized (when $A$ is SPD) when its gradient equals zero, which allows us to compute the vector for which the function achieves its minimum. The basic insight is that in order to solve $A \widehat x = b$ we can instead find the vector $\widehat x$ that minimizes the function $f( x ) = \frac{1}{2} x^T A x - x^T b \text{.}$
Let $A \widehat x = b \text{.}$ Then
Since $\widehat x^T A \widehat x$ is independent of $x \text{,}$ and $A$ is SPD, this is clearly minimized when $x = \widehat x \text{.}$