324 CHAPTER 12. INNER PRODUCT SPACES, LEAST SQUARES

15. The Gram Schmidt process starts with a basis for a subspace {v1, · · · ,vn} and pro-duces an orthonormal basis for the same subspace {u1, · · · ,un} such that

span(v1, · · · ,vk) = span(u1, · · · ,uk)

for each k. Show that in the case of Rm the QR factorization does the same thing.Specifically, if A =

(v1 · · · vn

)and if A = QR≡

(q1 · · · qn

)R then the

vectors {q1, · · · ,qn} is an orthonormal set of vectors and for each k,

span(q1, · · · ,qk) = span(v1, · · · ,vk)

16. Verify the parallelogram identify for any inner product space,

|x+ y|2 + |x− y|2 = 2 |x|2 +2 |y|2 .

Why is it called the parallelogram identity?

17. Let H be an inner product space and let K ⊆ H be a nonempty convex subset. Thismeans that if k1,k2 ∈ K, then the line segment consisting of points of the form

tk1 +(1− t)k2 for t ∈ [0,1]

is also contained in K. Suppose for each x ∈ H, there exists Px defined to be a pointof K closest to x. Show that Px is unique so that P actually is a map. Hint: Supposez1 and z2 both work as closest points. Consider the midpoint, (z1 + z2)/2 and use theparallelogram identity of Problem 16 in an auspicious manner.

18. In the situation of Problem 17 suppose K is a closed convex subset and that H iscomplete. This means every Cauchy sequence converges. Recall a sequence {kn} isa Cauchy sequence if for every ε > 0 there exists Nε such that whenever m,n > Nε ,it follows |km− kn|< ε. Let {kn} be a sequence of points of K such that

limn→∞|x− kn|= inf{|x− k| : k ∈ K}

This is called a minimizing sequence. Show there exists a unique k ∈ K such thatlimn→∞ |kn− k| and that k = Px. That is, there exists a well defined projection maponto the convex subset of H. Hint: Use the parallelogram identity in an auspiciousmanner to show {kn} is a Cauchy sequence which must therefore converge. Since Kis closed it follows this will converge to something in K which is the desired vector.

19. Let H be an inner product space which is also complete and let P denote the projec-tion map onto a convex closed subset, K. Show this projection map is characterizedby the inequality Re(k−Px,x−Px)≤ 0 for all k ∈ K. That is, a point z ∈ K equalsPx if and only if the above variational inequality holds. This is what that inequalityis called. This is because k is allowed to vary and the inequality continues to hold forall k ∈ K.

20. Using Problem 19 and Problems 17 - 18 show the projection map, P onto a closedconvex subset is Lipschitz continuous with Lipschitz constant 1. That is |Px−Py| ≤|x− y|