Introduction We learned in the previous chapter that Ax b need not possess a solution when the number of rows of A exceeds its rank, i.e., rm . As this situation arises quite often in practice, typically in the guise of 'more equations than unknowns,' we establish a rationale for the absurdity Ax b .

The Normal Equations The goal is to choose x such that Ax is as close as possible to b. Measuring closeness in terms of the sum of the squares of the components we arrive at the 'least squares' problem of minimizing res Ax b 2 Ax b Ax b over all x . The path to the solution is illuminated by the Fundamental Theorem. More precisely, we write bR bN bR ℝA bN ℕ A b bR bN . On noting that (i) bR x ℝn Ax bR ℝA and (ii) ⊥ ℝA ℕ A we arrive at the Pythagorean Theorem. Pythagorean Theorem norm Ax b 2 Ax bR bN 2 Ax bR 2 bN 2 It is now clear from the Pythagorean Theorem that the best x is the one that satisfies Ax bR As bR ℝA this equation indeed possesses a solution. We have yet however to specify how one computes bR given b. Although an explicit expression for bR , the so called orthogonal projection of b onto ℝA , in terms of A and b is within our grasp we shall, strictly speaking, not require it. To see this, let us note that if x satisfies the above equation then Ax b Ax bR bN bN As bN is no more easily computed than bR you may claim that we are just going in circles. The 'practical' information in the above equation however is that Ax b A , i.e., A Ax b 0 , i.e., A Ax A b As A b ℝ A regardless of b this system, often referred to as the normal equations, indeed has a solution. This solution is unique so long as the columns of A A are linearly independent, i.e., so long as ℕ A A 0 . Recalling Chapter 2, Exercise 2, we note that this is equivalent to ℕA 0 . We summarize our findings in The set of x bR for which the misfit Ax b 2 is smallest is composed of those x for which A A x A b . There is always at least one such x. There is exactly one such x if ℕA 0 . As a concrete example, suppose with reference to that A 11 01 00 and b 1 1 1 .

The decomposition of b. As b ℝA there is no x such that Ax b . Indeed, Ax b 2 x1 x2 -1 2 x2 1 2 1 1 , with the minimum uniquely attained at x 0 1 , in agreement with the unique solution of the above equation, for A A 1 1 1 2 and A b 1 2 . We now recognize, a posteriori, that bR Ax 1 1 0 is the orthogonal projection of b onto the column space of A.

Applying Least Squares to the Biaxial Test Problem We shall formulate the identification of the 20 fiber stiffnesses in this previous figure, as a least squares problem. We envision loading, f, the 9 nodes and measuring the associated 18 displacements, x. From knowledge of x and f we wish to infer the components of K diagk where k is the vector of unknown fiber stiffnesses. The first step is to recognize that A K A x f may be written as B B A diag Ax Bk f Though conceptually simple this is not of great use in practice, for B is 18-by-20 and hence the above equation possesses many solutions. The way out is to compute k as the result of more than one experiment. We shall see that, for our small sample, 2 experiments will suffice. To be precise, we suppose that x1 is the displacement produced by loading f1 while x2 is the displacement produced by loading f2 . We then piggyback the associated pieces in B A diag A x1 A diag A x2 and f f1 f2 This B is 36-by-20 and so the system Bk f is overdetermined and hence ripe for least squares. We proceed then to assemble B and f. We suppose f1 and f2 to correspond to horizontal and vertical stretching f1 -1 0 0 0 1 0 -1 0 0 0 1 0 -1 0 0 0 1 0 f2 0 1 0 1 0 1 0 0 0 0 0 0 0 -1 0 -1 0 -1 respectively. For the purpose of our example we suppose that each kj 1 except k8 5 . We assemble A K A as in Chapter 2 and solve A K A xj fj with the help of the pseudoinverse. In order to impart some `reality' to this problem we taint each xj with 10 percent noise prior to constructing B. Regarding B B k B f we note that Matlab solves this system when presented with k=B\f when B is rectangular. We have plotted the results of this procedure in the . The stiff fiber is readily identified.

Results of a successful biaxial test.

Projections From an algebraic point of view )is an elegant reformulation of the least squares problem. Though easy to remember it unfortunately obscures the geometric content, suggested by the word 'projection,' of . As projections arise frequently in many applications we pause here to develop them more carefully. With respect to the normal equations we note that if ℕA 0 then x A A -1 A b and so the orthogonal projection of b onto ℝA is: bR Ax A A A -1 A b Defining P A A A -1 A takes the form bR P b . Commensurate with our notion of what a 'projection' should be we expect that P map vectors not in ℝA onto ℝA while leaving vectors already in ℝA unscathed. More succinctly, we expect that P bR bR , i.e., P bR P bR . As the latter should hold for all b Rm we expect that P2 P With respect to we find that indeed P2 A A A -1 A A A A -1 A A A A -1 A P We also note that the P in is symmetric. We dignify these properties through orthogonal projection A matrix P that satisfies P2 P is called a projection. A symmetric projection is called an orthogonal projection. We have taken some pains to motivate the use of the word 'projection.' You may be wondering however what symmetry has to do with orthogonality. We explain this in terms of the tautology b Pb IP b Now, if P is a projection then so too is IP . Moreover, if P is symmetric then the dot product of b's two constituents is Pb IP b b P IP b b P P2 b b 0 b 0 i.e., P b is orthogonal to IP b . As examples of a nonorthogonal projections we offer P 1 0 0 -12 0 0 -14 -12 1 and IP . Finally, let us note that the central formula, P A A A -1 A , is even a bit more general than advertised. It has been billed as the orthogonal projection onto the column space of A. The need often arises however for the orthogonal projection onto some arbitrary subspace M. The key to using the old P is simply to realize that every subspace is the column space of some matrix. More precisely, if x1 ... xm is a basis for M then clearly if these xj are placed into the columns of a matrix called A then ℝA M . For example, if M is the line through 11 then P 1 1 12 11 12 1 1 1 1 is orthogonal projection onto M.

Exercises Gilbert Strang was stretched on a rack to lengths ℓ 6 , 7, and 8 feet under applied forces of f1 , 2, and 4 tons. Assuming Hooke's law ℓL cf , find his compliance, c, and original height, L, by least squares. With regard to the example of § 3 note that, due to the the random generation of the noise that taints the displacements, one gets a different 'answer' every time the code is invoked. Write a loop that invokes the code a statistically significant number of times and submit bar plots of the average fiber stiffness and its standard deviation for each fiber, along with the associated M--file. Experiment with various noise levels with the goal of determining the level above which it becomes difficult to discern the stiff fiber. Carefully explain your findings. Find the matrix that projects 3 onto the line spanned by 1 0 1 . Find the matrix that projects 3 onto the plane spanned by 1 0 1 and 1 1 -1 . If P is the projection of m onto a k--dimensional subspace M, what is the rank of P and what is P?