Toán học - Chapter 5: The orthogonality and least squares

Math Dept, Faculty of Applied Science, HCM University of Technology ------------------------------------------------------------------------------------- Math 415: Linear Algebra Chapter 5: The Orthogonality and Least Squares • Instructor Dr. Dang Van Vinh (6/2006) CONTENTS --------------------------------------------------------------------------------------------------------------------------- 3.1 – The Scalar Product in Rn 3.2 – Orthogonal Subspaces 3.4 – The Gram - Schmidt Orthogonalization Process 3.3 – Orthonormal set 3.5 – Inner Product Spaces 3.6 – Least Square Problem 3.1 The Scalar Product in Rn --------------------------------------------------------------------------------------------------------------------------- Definition of Inner Product in Rn Let u and v are vectors in Rn. 1 2 n u u u u              1 2 n v v v v              The inner product of u and v is   1 2 1 2 1 1 2 2n n n n v v u v u u u u v u v u v v                     3.1 The Scalar Product in Rn ------------------------------------------------------------------------------------------------------------ -- Example. Let . Compute (u,v) and (v,u) 2 3 5 ; 2 1 3 u v                       Solution.   3 ( , ) 2 5 1 2 3 Tu v u v              2 3 ( 5) 2 ( 1)( 3) 1            2 ( , ) 3 2 3 5 1 1 Tv u v u               3.1 The Scalar Product in Rn ------------------------------------------------------------------------------------------------------------ -- d. (u,u) (v,u), and (u,u) = 0 if and only if u = 0.  Theorem Let u, v and w be vectors in Rn, and let c be a scalar. Then a. (u,v) = (v,u) b. (u+v,w) = (u,w) + (v,w) c. (cu,v) = c(u,v)=(u,cv) The Length of a Vector The length (or norm) of vector u is the nonnegative scalar ||u|| defined by 2 2 2 1 2|| || ( , ) nu u u u u u     3.1 The Scalar Product in Rn ----------------------------------------------------------------------------------------------------------- A vector whose length is 1 is called a unit vector. If we divide a nonzero vector u by its length, we obtain a unit vector. The process of creating a unit vector is called normalizing The Distance between two vectors For u and v in Rn, the distance between u and v, written as dist(u,v), is the length of the vector u – v. That is dist(u,v) = ||u – v|| Example. 1) Let v = (1,-2,2,0). Find a unit vector u in the same direction as v. 2) Compute the distance between the vectors u = (7,1) and v = (3,2). 3.2 Orthogonal Subspaces ------------------------------------------------------------------------------------------------------------ -- Definition of Orthogonality Two vectors u and v in Rn are orthogonal (to each other) if (u,v) = 0 The Pythagorean Theorem Two vectors u and v in Rn are orthogonal if and only if 2 2 2|| || || || || ||u v u v   Orthogonal Complements If a vector z is orthogonal to every vector in a subspace W of Rn, then z is said to be orthogonal to W. The set of all vectors z that are orthogonal to W is called the orthogonal complement of W and is denoted by W  3.2 Orthogonal Subspaces ------------------------------------------------------------------------------------------------------------ -- Theorem 1. A vector x is in if and only if x is orthogonal to every vector in a set that span W. W  2. is a subspace of Rn. W  Proof. Theorem Let A be an mxn matrix. Then the orthogonal complement of the row space of A is the nullspace of A, and the orthogonal complement of the column space of A is the nullspace of AT. (Row A)T = Null A; (Col A)T = Null AT. Proof. 3.2 Orthogonal Subspaces ------------------------------------------------------------------------------------------------------------ -- Example. Let be a subspace of R3. Find the basis and dimension of (1,1,1),(2,1,0),(1,0, 1)F    F Solution. 1 2 3( , , )x x x x F x F      1 2 3 1 2 1 3 (1,1,1) 0 (2,1,0) 2 0 (1,0, 1) 0 x x x x x x x x x x                   1 2 3 2 ( , 2 , ) (1, 2,1) x x x x                    {(1, 2,1)}F span   Dim =1; basis: {(1,-2,1)} F 3.2 Orthogonal Subspaces ------------------------------------------------------------------------------------------------------------ -- Example. Let F  1 2 3 3 1 2 3 1 2 3( , , ) | 0 & 2 0F x x x R x x x x x x        be a subspace of R3. Find the basis and dimension of Solution. Step 1. Find the spanning set of F. 1 2 3 1 2 3 1 2 3 0 ( , , ) 2 0 x x x x x x x F x x x            1 2 3 2 3 (2 , 3 , ) (2, 3,1) x x x x                    The spanning set of F is {(2,-3,1)} Step 2. Analogous the previous example. 3.3 Orthonormal Set ------------------------------------------------------------------------------------------------------------ Definition of an Orthogonal Set A set of vectors {u1, u2, ..., up} is said to be an orthogonal set if each pair of distinct vectors from the set is orthogonal. Theorem If S= {u1, u2, ..., up} is an orthogonal set of nonzero vectors in Rn, then S is linearly independent and hence is a basic for the subspace spanned by S. Proof. Example. Show that {u1, u2, u3} is an orthogonal set, where 1 1 3(3,1,1); ( 1,2,1); (1,4, 7)u u u     3.3 Orthonormal Set ------------------------------------------------------------------------------------------------------------ -- Theorem Let E = {u1, u2, ..., up} be an orthogonal basis for a subspace W of Rn. Then each y in W has a unique representation as a linear combination of E. In fact, if y = c1u1 + c2u2 + ... + cpup then Proof. ( , ) ( , ) j j j j y u c u u  1 1 3(3,1,1); ( 1,2,1); (1,4, 7)u u u     Example. The set E = {u1, u2, u3} is an orthogonal basis for R3, where Express the vector y = (6,1,-8) as a linear combination of the vectors in E. 3.3 Orthonormal Set ------------------------------------------------------------------------------------------------------------ -- Solution. Compute 1 2 3( , ) 11;( , ) 12;( , ) 33y u y u y u     1 1 2 2 3 3 33 ( , ) 11;( , ) 6;( , ) 2 u u u u u u   31 2 1 2 3 1 1 2 2 3 3 ( , )( , ) ( , ) ( , ) ( , ) ( , ) y uy u y u y u u u u u u u u u    1 2 3 1 2 3 11 12 33 2 2 11 6 33/ 2 y u u u u u u         Remark. How easy it is to compute the weights needed to build y from an orthogonal basis. If the basis were not orthogonal, it would be necessary to solve a system of linear equations to find the weights. 3.3 Orthonormal Set ------------------------------------------------------------------------------------------------------------ -- Definition of an Orthonormal Set A set E = {u1, u2, ..., up} is an orthonormal set if it is an orthogonal set of unit vectors. If W is a subspace spanned by such of set, then E is an orthonormal basis for W, since the set is automatically linearly independent. Theorem An mxn matrix U has orthonormal columns if and only if UTU=I. Proof. Example. Show that {v1, v2, v3} is an orthonormal set, where 1 2 3 (3 / 11,1 / 11,1 / 11); ( 1 / 6 , 2 / 6 ,1 / 6 ); (1 / 66 , 4 / 66 , 7 / 66 ) u u u      3.3 Orthonormal Set ------------------------------------------------------------------------------------------------------ Theorem Let U be an mxn matrix with orthonormal columns, and let x and y be in Rn. Then || || || ||Ux xa. ( , ) ( , )Ux Uy x yb. ( , ) 0 ( , ) 0Ux Uy x y  c. Proof. Definition of an Orthogonal Matrix An orthogonal matrix is a square invertible matrix U such that U-1 = UT. Theorem A square matrix with orthonormal columns is an orthogonal matrix 3.4 The Gram-Schmidt Orthogonalization Process -------------------------------------------------------------------------------------------------------------- The Gram – Schmidt process is a simple algorithm for producing an orthogonal or orthonormal basis for any subspace of Rn. Example. Let W = Span{x1, x2}, where x1 = (3,6,0) and x2 = (1,2,2). Construct an orthogonal basis {v1, v2} for W. Solution. Let p be the projection of x2 onto x1. The component of x2 orthogonal to x1 is x2 – p, which is in W because it is formed from x2 and a multiple of x1. Let v1= x1 and 2 1 2 2 2 1 1 1 ( , ) ( , ) x x v x p x x x x     15 (1,2,2) (3,6,0) (0,0,2) 45    Then {v1, v2} is an orthogonal set of nonzero vectors in W. 3.4 The Gram-Schmidt Orthogonalization Process -------------------------------------------------------------------------------------------------------------- Example. Let W = Span{x1=(1,1,1,1), x2=(0,1,1,1), x3 = (0,0,1,1)} Construct an orthogonal basis {v1, v2, v3} for W. Solution. Step1. Let v1 = x1 and W1 = Span{x1} = Span{v1} To simplify later computations, choose v2 = (-3,1,1,1) Step2. 1 2 1 2 2 2 2 1 1 1 ( , ) ( , )W x v v x proj x x v v v     3 3 1 1 1(0,1,1,1) (1,1,1,1) ( , , , ) 4 4 4 44    Step3. 2 3 1 3 2 3 1 2 1 1 2 2 ( , ) ( , ) ( , ) ( , ) W x v x v proj x v v v v v v   2 3 1 3 1 3 3 3 3 1 1 1 1 1 1 ( , ) ( , ) ( , ) ( , )W x v x v v x proj x x v v v v v v      3 2 2 1 1(0, , , ) (0, 2,1,1) 3 3 3 v v     3.4 The Gram-Schmidt Orthogonalization Process -------------------------------------------------------------------------------------------------------------- The Gram – Schmidt Process Given a basis {x1, x2, ..., xp} for a subspace W of R n, define 1 1v x 2 1 2 2 1 1 1 ( , ) ( , ) x v v x v v v   3 1 3 2 3 3 1 2 1 1 2 2 ( , ) ( , ) ( , ) ( , ) x v x v v x v v v v v v     1 2 1 1 2 1 1 1 2 2 1 1 ( , ) ( , ) ( , ) ( , ) ( , ) ( , ) p p p p p p p p p x v x v x v v x v v v v v v v v v          Then {v1, v2, ..., vp} is an orthogonal basis for W. In addition 1 2 1 2{ , , , } { , , , };1k kSpan v v v Span x x x k p    3.5 Inner Product Spaces --------------------------------------------------------------------------------------------------------------------------- Definition of Inner Product An inner product on a vector space V is a function that, to each pair of vectors u and v in V, associates a real number (u,v) and satisfies the following axioms, for all u, v, w and all scalars c a. ( , ) ( , )u v v u b. ( , ) ( , ) ( , )u v w u w v w   c. ( , ) ( , )cu v c u v d. ( , ) 0;( , ) 0 0u u u u u    A vector space with an inner product space is called an inner product space. 3.5 Inner Product Spaces --------------------------------------------------------------------------------------------------------------------------- Example. For vectors x = (x1, x2) and y = (y1, y2) in R 2, set 1 1 2 2( , ) 3 4x y x y x y  Show that (x,y) is an inner product. Example. For vectors x = (x1, x2) and y = (y1, y2) in R 2, set 1 1 1 2 2 1 2 2( , ) 3 4x y x y x y x y x y    Show that (x,y) is an inner product. Example. For vectors x = (x1, x2, x3); y = (y1, y2, y3) in R 3, set 1 1 1 2 2 1 2 2 3 3( , ) 4x y x y x y x y x y x y     Show that (x,y) is an inner product. 3.5 Inner Product Spaces --------------------------------------------------------------------------------------------------------------------------- Example. For vectors p(x) and q(x) in P2, set a. Show that (p,q) is an inner product. 1 0 ( , ) ( ) ( )p q p x q x dx  b. Compute (p,q) where 2( ) 2 3 1; ( ) 3p x x x q x x     c. Compute the length of the vector ( ) 2 3p x x  d. Compute the distance between p(x) and q(x) where 2 2( ) 2; ( ) 2 3p x x x q x x x      e. Compute the angle between two vector in d) 3.5 Inner Product Spaces --------------------------------------------------------------------------------------------------------------------------- 2{ ( ) | (1) 0; ( 1) 0}F p x P p p    Given a subspace Example. For vectors p(x) and q(x) in P2, set 1 1 ( , ) ( ) ( )p q p x q x dx    a. Find the spanning set of subspace F. c. Find the basis and dimension of F 2( ) 2p x x x m  b. Determine m such that is be long to F d. Produce an orthogonal basis for P2 by applying the Gram-Schmidt process to the polynomials 1, x, x2. 3.6 Least Square Problem ---------------------------------------------------------------------------------------------------------------------------