Question:

We choose as our solution the r which minimizes r in the 2-norm, i.e., Irl|2 = 16 - Axl|2- The first method uses calculus, and we begin by writing the 2-norm explicitly as a function of the elements of r by 9(T1, 12, . .., In) = 13- (box;) (12.74a) which is quadratic in each of the ry 's. We find the minimum by setting dg for { E N[1, n], (12.74b) so we obtain n equations for the n unknown elements of c. Carrying out the partial differentiation with respect to re, where Or;/Ork = 6; k is the Kronecker delta function, we obtain 0 = _ 2(b, - [ajr; ) (-aik) for k E N[1, n), (12.74c) which can be written as [ axb = EE ajaikI;. (12.74d) 1=1 j= 1 This equation might look quite complicated, but the left-hand side, a column vector, is simply the &th element of A b, and the right-hand side is the th element of A Ac. The result is Ab = A Ar. (12.74e) The second derivation of the normal equation doesn't require calculus or summation notation, only linear algebra. Ar = b only has a solution if b e R(A), which almost never happens if m > n. Instead, we write b = s + z, where s ( R(A) and z 1 R(A) are unique, which can always be done by Theorem 1.25. We now write the residual as r = b - Ar = z + (s - Ax). By the Pythagorean theorem, since z 1 R(A) and 8-Ar E R(A), it follows that | r 2 = z|2+|8-Ax|2. z and s are fixed but I is free, so we can minimize the right-hand side by letting Ar = s - which must have a solution since s e R(A). Thus, |r|2 is minimized when r = z, and so r 1 R(A). We show a schematic in Figure 12.17 where, clearly, b = s + z. Since Figure 12.17: A schematic of the solution to Ax" " b in three dimensions where A = (a| |a2) E R3x2. The two-dimensional plane R(A) = span{ a1, a2 } is shown where a, and a2 lie in the plane. b is written as s + z where & E R(A) and = 1 R(A). The minimum distance between the head of b and the plane R(A) is clearly the r=b-Ax length of the vector z by the Pythagorean theorem, and Z x is the solution to Ax = s so r = z. This also proves that r I R(A) since r = b - Ax = = + (s - Ax) = =+0. Finally, 0 is the angle shown of the triangle with sides b, AX-s s, and z, and this triangular is perpendicular to the subspace R(A). R ( A ) T I R(A) and R(A)! = N(AT) by Section 10.4, re N(AT) so 0 = ATr = AT(b - Ax) = Ab - ATAc. Returning to the original form of the least squares equation, i.e., y" " N'c, there is a second way in MATLAB to calculate the coefficients. We have already used polyfit for interpolation, but it can also be used for approximation byIn our calculation of the normal equation using eqs. (12.74), we stated that eq. (12.74d) is the k*" row of ATb = A Ar. So, for practice, let's play around with some vector and matrix multiplications where AER"X", TER", and be R.. For example, the it element of the column vector Ar is j=1 All the answers must explicitly use the elements of the vectors and the matrices. a) We begin with an outer product: what is the it row of rw where r, we R". What is the size of the resulting matrix? b) What is the jth element of the row vector b A? What is the size of the resulting vector? c) What is ca; if C = AB and BE Roxp. What is the size of the resulting matrix? d) What is di; if D = BAT. What is the size of the resulting matrix? e) From the previous two parts, verify that BEAT = (AB) by showing that di j = cji. f) What is the (i, j) element of A A? What is the size of the resulting matrix? g) What is the (i, j)th element of AAT? What is the size of the resulting matrix? h) What is the ith element of A.A b? What is the size of the resulting vector? Warning: Your answers cannot involve anything like a,, since a, is a scalar so its transpose is itself