# 3.4: Exercises

Exercise 3.1

Least Square Error Solution We begin with a mini-tutorial on orthogonal and unitary matrices. An orthogonal matrix may be defined as a square real matrix whose columns are of unit length and mutually orthogonal to each other - i.e., its columns form an orthonormal set. It follows quite easily (as you should try and verify for yourself ) that:

• the inverse of an orthogonal matrix is just its transpose;
• the rows of an orthogonal matrix form an orthonormal set as well;
• the usual Euclidean inner product of two real vectors $$v$$ and $$w$$, namely the scalar $$v^{\prime}w$$, equals the inner product of $$Uv$$ and $$Uw$$, if $$U$$ is an orthogonal matrix - and therefore the length of $$v$$, namely $$\sqrt{v^{\prime} v}$$, equals that of $$Uv$$.

A unitary matrix is similarly defined, except that its entries are allowed to be complex - so its inverse is the complex conjugate of its transpose. A fact about orthogonal matrices that turns out to be important in several numerical algorithms is the following: Given a real $$m \times n$$ matrix $$A$$ of full column rank, it is possible (in many ways) to find an orthogonal matrix $$U$$ such that

$U A=\left(\begin{array}{c} R \\ 0 \end{array}\right)\nonumber$

where $$R$$ is a nonsingular, upper-triangular matrix. (If $$A$$ is complex, then we can find a unitary matrix $$U$$ that leads to the same equation.) To see how to compute $$U$$ in Matlab, read the comments obtained by typing help qr; the matrix $$Q$$ that is referred to in the comments is just $$U^{\prime}$$.

We now turn to the problem of interest. Given a real $$m \times n$$ matrix $$A$$ of full column rank, and a real m-vector $$y$$, we wish to approximately satisfy the equation $$y = Ax$$. Specifically, let us choose the vector $$x$$ to minimize $$\|y-A x\|^{2}=(y-A x)^{\prime}(y-A x)$$, the squared Euclidean length of the "error" $$y - Ax$$. By invoking the above results on orthogonal matrices, show that (in the notation introduced earlier) the minimizing $$x$$ is

$\hat{x}=R^{-1} y_{1}\nonumber$

where $$y_{1}$$ denotes the vector formed from the first $$n$$ components of $$Uy$$. (In practice, we would not bother to find $$R^{-1}$$ explicitly. Instead, taking advantage of the upper-triangular structure of $$R$$, we would solve the system of equations $$R \hat{x} = y_{1}$$ by back substitution, starting from the last equation.)

The above way of solving a least-squares problem (proposed by Householder in 1958, but sometimes referred to as Golub's algorithm) is numerically preferable in most cases to solving the "normal equations" in the form $$\hat{x}=\left(A^{\prime} A\right)^{-1} A^{\prime} y$$, and is essentially what Matlab does when you write $$\hat{x}=A \backslash y$$. An (oversimplified!) explanation of the trouble with the normal equation solution is that it implicitly evaluates the product $$\left(R^{\prime} R\right)^{-1} R^{\prime}$$, whereas the Householder/Golub method recognizes that this product simply equals $$R^{-1}$$, and thereby avoids unnecessary and error prone steps.

Exercise 3.2

Suppose the input sequence $$\left\{u_{j}\right\}$$ and the output sequence $$\left\{y_{j}\right\}$$ of a particular system are related by

$y_{k}=\sum_{i=1}^{n} h_{i} u_{k-i}\nonumber$

where all quantities are scalar.

(i) Assume we want to have $$y_{n}$$ equal to some specified number $$\bar{y}$$. Determine $$u_{0}+\ldots+u_{n-1}$$ so as to achieve this while minimizing $$u_{0}^{2}+\ldots+u_{n-1}^{2}$$.

(ii) Suppose now that we are willing to relax our objective of exactly attaining $$y_{n}=\bar{y}$$. This leads us to the following modified problem. Determine $$u_{0}+\ldots+u_{n-1}$$ so as to minimize

$r\left(\bar{y}-y_{n}\right)^{2}+u_{0}^{2}+\ldots+u_{n-1}^{2}\nonumber$

where r is a positive weighting parameter.

(a) Solve the modified problem.

(b) What do you expect the answer to be in the limiting cases of $$r = 0$$ and $$r = \infty$$? Show that your answer in (a) indeed gives you these expected limiting results.

Exercise 3.3

Return to the problem considered in Example 3.4. Suppose that, in addition to requiring $$p(T ) = y$$ for a specified $$y$$, we also want $$\dot{p}(T ) = 0$$. In other words, we want to bring the mass to rest at the position $$y$$ at time $$T$$. Of all the force functions $$x(t)$$ that can accomplish this, determine the one that minimizes $$<x(t), x(t)>=\int_{0}^{T} x^{2}(t) d t$$.

Exercise 3.4

(a) Given $$y=A^{\prime} x$$, with $$A^{\prime}$$ of full row rank, find the solution vector $$x$$ for which $$x^{\prime}Wx$$ is minimum, where $$W = L^{\prime}L$$ and $$L$$ is nonsingular (i.e. where $$W$$ is Hermitian and positive definite).

(b) A specified current $$I_{0}$$ is to be sent through the fixed voltage source $$V_{0}$$ in the figure. Find what values $$v_{1}$$, $$v_{2}$$, $$v_{3}$$ and $$v_{4}$$ must take so that the total power dissipation in the resistors is minimized.