Math 307 Spring, 2005 Instructor: Irvin Roy Hentzel Office 432 Carver Phone 515-294-8141 E-mail: hentzel@iastate.edu http://www.math.iastate.edu/hentzel/class.307.05 ============================================================ Final Exam 307 Matrix Theory Wednesday, May 4, 2005 9:45-11:45 AM Friday, April 22 6.5 Main Idea: Multiply by the transpose of A. Key Words: Least Squares, Curve fitting, perpendicular projection. Orthogonal Matrix. Goal: Learn what we mean when we say "best solution" and how to find the best solution. ============================================================== T A real matrix is orthogonal if A A = I. That is, its transpose is its inverse. A matrix is orthogonal if it columns are an orthoNORMAL basis. That is, the columns are all orthogonal and of unit length. Orthogonal matrices represent things like rotations and reflections. The objects still "look" the same. Circles are not elongated into elipses, and right angles remain right angles. This is all a consequence of the fact that distances are preserved. n n Consider an orthogonal transformation T from R to R . Show that T preserves the dot product: i.e. VoW = T(V)oT(W). Let A be the orthogonal matrix for T. T T T T (A V)o (A W) = (A V) (A W) = V A A W = V W = VoW. ----------------------------------------------------------------- T If a matrix A is orthogonal, then A is also orthogonal. T T -1 If A is orthogonal, then A A = I, then A = A . The inverse works on both sides, so _ _ T | T | T T T |_A _| A = A A = I. Therefore A is also orthogonal. So if the columns are orthonormal, then the rows are orthonormal as well. ---------------------------------------------------------------- Find an orthogonal matrix of the form | 2/3 1/Sqrt[2] a | | 2/3 -1/Sqrt[2] b | | 1/3 0 c | We will start with | 2 1 a | | 2 -1 b | | 1 0 c | clearly a = b and c = -4a so | 1 | is orthogonal to the other two columns. | 1 | |-4 | Divide by the length = Sqrt[18] to make the orthonormal matrix | 2/3 1/Sqrt[2] 1/Sqrt[18] | | 2/3 -1/Sqrt[2] 1/Sqrt[18] | | 1/3 0 -4/Sqrt[18] | -------------------------------------------------------- Fitting Polynomials to curves. data set = { { 1,20}, { 3, 14}, {5, 16}, { 8, 13}, {10,12} } (a) Find the best straight line to the data set. (b) Find the best quadratic curve to the data set. (c) Find the best cubic curve to the data set. (d) Find the best quartic curve to the data set. Solution (a) y = m x + b x 1 | 1 1 | | m | | 20 | | 3 1 | | b | | 14 | | 5 1 | = | 16 | | 8 1 | | 13 | | 10 1 | | 12 | ----------------------------------------- 2 Solution (b) y = c x + c x + c 2 1 0 2 x x 1 | 1 1 1 | | c2| | 20 | | 9 3 1 | | c1| | 14 | | 25 5 1 | | c0| = | 16 | | 64 8 1 | | 13 | |100 10 1 | | 12 | ------------------------------------------------ 3 2 Solution (c) y = c x + c x + c x + c 3 2 1 0 3 2 x x x 1 | 1 1 1 1 | | c3| | 20 | | 27 9 3 1 | | c2| | 14 | | 125 25 5 1 | | c1| = | 16 | | 512 64 8 1 | | c0| | 13 | |1000 100 10 1 | | 12 | ---------------------------------------------------------- 4 3 2 Solution (d) y = c x + c x + c x + c x + c 4 3 2 1 0 4 3 2 x x x x 1 | 1 1 1 1 1 | | c4| | 20 | | 81 27 9 3 1 | | c3| | 14 | | 625 125 25 5 1 | | c2| = | 16 | | 4096 512 64 8 1 | | c1| | 13 | |10000 1000 100 10 1 | | c0| | 12 | ------------------------------------------------------ B = {20,14,16,13,12}; A2 = {{ 1, 1 }, { 3, 1 }, { 5, 1 }, { 8, 1 }, { 10, 1 }}; A3 = {{ 1, 1, 1 }, { 9, 3, 1 }, { 25, 5, 1 }, { 64, 8, 1 }, {100,10, 1 }}; A4 = {{ 1, 1, 1, 1 }, { 27, 9, 3, 1 }, { 125, 25, 5, 1 }, { 512, 64, 8, 1 }, {1000,100,10, 1 }}; A5 = {{ 1, 1, 1, 1, 1 }, { 81, 27, 9, 3, 1 }, { 625, 125, 25, 5, 1 }, { 4096, 512, 64, 8, 1 }, {10000, 1000,100,10, 1 }}; a2 = Inverse[ Transpose[A2].A2].Transpose[A2].B; a3 = Inverse[ Transpose[A3].A3].Transpose[A3].B; a4 = Inverse[ Transpose[A4].A4].Transpose[A4].B; a5 = Inverse[ Transpose[A5].A5].Transpose[A5].B; p2 = Plot[ a2[[1]] x+a2[[2]],{x,0,11}, PlotStyle->{RGBColor[1,0,0]}]; p3 = Plot[ a3[[1]] x^2+a3[[2]] x+a3[[3]],{x,0,11}, PlotStyle->{RGBColor[0,1,0]}]; p4 = Plot[ a4[[1]] x^3+a4[[2]] x^2+a4[[3]] x+a4[[4]],{x,0,11}, PlotStyle->{RGBColor[0,0,1]}]; p5 = Plot[a5[[1]] x^4+a5[[2]] x^3+a5[[3]] x^2+a5[[4]] x+a5[[5]],{x,0,11}, PlotStyle->{RGBColor[1/3,1/3,1/3]}]; p6 = ListPlot[ { { 1,20}, { 3, 14}, {5, 16}, { 8, 13}, {10,12} }, PlotStyle->{PointSize[0.05]}] ans = Show[p2,p3,p4,p5,p6]; Display["fit.ps",ans]; ---------------------------------------------------------------------- Find the best quadratic approximation to y = Sin[x]. { { 30, 1/2}, { 45, Sqrt[3]/2}, { 60, 1/Sqrt[2]}, { 90, 1 }, {120, Sqrt[3]/2}, {135, 1/Sqrt[2]}, {150, 1/2}}; A = | 30^2 30 1 | | c2 | | 1/2 | | 45^2 45 1 | | c1 | | Sqrt[3]/2| | 60^2 60 1 | | c0 | | 1/Sqrt[2]| | 90^2 90 1 | = | 1 | |120^2 120 1 | | Sqrt[3]/2| |135^2 135 1 | | 1/Sqrt[2]| |150^2 150 1 | | 1/2 | p(x) = -0.000122034 x^2 + 0.0217835 x -0.00935101 The quadratic error is 0.046174 The cubic error is 0.0451799 which is just a trifle better. -------------------------------------------------------- data = { { 30, 1/2}, { 45, 1/Sqrt[2]}, { 60, Sqrt[3]/2}, { 90, 1 }, {120, Sqrt[3]/2}, {135, 1/Sqrt[2]}, {150, 1/2}}; B = {1/2, Sqrt[3]/2, 1/Sqrt[2], 1, Sqrt[3]/2,1/Sqrt[2],1/2}; A ={{ 30^2, 30, 1 }, { 45^2, 45, 1 }, { 60^2, 60, 1 }, { 90^2, 90, 1 }, {120^2,120, 1 }, {135^2,135, 1 }, {150^2,150, 1 }}; ans = Inverse[ Transpose[A].A].Transpose[A].B; a = Plot[ans[[1]] x^2 + ans[[2]] x + ans[[3]],{x,0,180}]; b = ListPlot[data]; c = Plot[ Sin[x Pi/180],{x,0,180},PlotStyle->{RGBColor[1,0,0]}]; all = Show[a,b,c,PlotLabel->"red: y = Sin[x], black=approximation"]; Display["sin.ps",all]; cubic ={{ 30^3, 30^2, 30, 1 }, { 45^3, 45^2, 45, 1 }, { 60^3, 60^2, 60, 1 }, { 90^3, 90^2, 90, 1 }, {120^3, 120^2,120, 1 }, {135^3, 135^2,135, 1 }, {150^3, 150^2,150, 1 }}; cns = Inverse[ Transpose[cubic].cubic].Transpose[cubic].B; ca = Plot[cns[[1]] x^3+cns[[2]] x^2 + cns[[3]] x + cns[[4]],{x,0,180}]; cb = ListPlot[data]; cc = Plot[ Sin[x Pi/180],{x,0,180},PlotStyle->{RGBColor[1,0,0]}]; call = Show[ca,cb,cc,PlotLabel->"red: y = Sin[x], black=cubic approximation"]; Display["sincubic.ps",call]; error2 = (A.ans-B).(A.ans-B); error3 = (cubic.cns-B).(cubic.cns-B); ---------------------------------------------------------------- (1) What are we doing? (2) How do we measure success? (3) It enough for B-AXo to be perpendicular to the columns of A. Answer(1) Suppose we have a system AX = B which has no solution. We know we cannot get AX to actually equal B, so we try for an Xo which gets us a close as possible to B. That is, we want AXo-B to be as close to zero as possible. Or equivalently, we want AXo-B to be as small as possible. Answer(2) Closeness means that |B-AXo| is as small as possible. Answer(3) If B-AXo is perpendicular to each of the columns of A, then AXo is as close to B as it is possible to get. --------------------------------------------------------------- We will show that when B-AXo is perpendicular to each of the columns of A, then |B-A Xo| <= | B-A Yo | for any Yo. 2 2 |B-AYo| = | B-A Xo + A Xo - A Yo | 2 = | B-A Xo + A (Xo-Yo) | 2 2 = | B-AXo | + |A (Xo-Yo)| (Because they are orthogonal 2 >= |B-AXo| The method says that to solve AX = B, solve instead T T A A X = A B. Notice that if we have a solution Xo, then T A (AXo-B) = 0 and thus AXo-B is orthogonal to the COLUMNS of A. Since AXo is in the column space of A, then AXo is the closest we can get to B in the column space of A. We know this because the residue is perpendicular to the column space of A. T If the columns of A are linearly independent, then A A is an invertible matrix and there is a unique solution, namely T -1 T Xo = (A A) A B T Why is A A invertible. We will show that the columns T of A A are linearly independent. Suppose there exists an X such T T T 2 that A A X = 0. Then 0 = X A A X = | AX | . Thus AX = 0 and since the columns of A are linearly independent X = 0. ---------------------------------------------------------- Summary: We can apply this process to get the orthogonal projection of a vector onto a space spanned by the columns of a matrix A which are linearly independent. The best solution to AX = B will be the Xo such that AXo is the orthogonal projection of B. T -1 T Thus A (A A) A is the matrix of this projection. Assignment: Find the projection of three space onto the plane x+y+z = 0. We need two vectors which span this plane. | 1 | | 1 | | -1 | | 0 | | 0 | |-1 | _ _ -1 | | | 1 1 | | | 1 -1 0 || 1 1 | | | 1 -1 0 | |-1 0 | | | 1 0 -1 ||-1 0 | | | 1 0 -1 | | 0 -1 | | | 0 -1 | | |_ _| -1 | 1 1 | | 2 1 | | 1 -1 0 | |-1 0 | | 1 2 | | 1 0 -1 | | 0 -1 | | 1 1 | | 2 -1 | | 1 -1 0 | |-1 0 | |-1 2 | | 1 0 -1 | | 0 -1 | ----------- 3 | 1 1 | | 1 -1 0 | |-2 1 | | 1 0 -1 | | 1 -2 | ----------- 3 | 2 -1 -1 | 1/3 |-1 2 -1 | |-1 -1 2 | The matrix of the projection is; | 2 -1 -1 | 1/3 |-1 2 -1 | |-1 -1 2 | Apply this to a projection of the cube: ---------------------------------------------------------- Q = 1/3 {{2,-1,-1},{-1, 2,-1},{-1,-1, 2}}; A = {{6,6,6,6,6,6,6,8,8,8,8,6}, {6,6,6,6,6,8,8,6,6,8,6,8}, {6,6,6,8,8,6,6,6,8,6,8,8}}; B = {{6,6,8,6,8,6,8,8,8,8,8,8}, {6,8,6,8,6,8,8,6,8,8,8,8}, {8,6,6,8,8,8,6,8,8,8,8,8}}; A = Transpose[A]; B = Transpose[B]; H = Table[ Graphics3D[ Line[ { A[[i]],B[[i]] }]],{i,1,12}]; K = Table[ Graphics3D[ Line[ { Q.A[[i]],Q.B[[i]] }]],{i,1,12}]; u = 1/Sqrt[2] {1,0,-1}; v = 1/Sqrt[6] {1,-2,1}; t = Q.{6,8,8}; L = Graphics3D[ {RGBColor[1,0,0],Line[{ -5u-5v, -5u+5v, 5u+5v,5u-5v,-5u-5v}]}]; M = Table[ Graphics3D[{RGBColor[0,1,0],Line[ {B[[i]],Q.B[[i]]}]}],{i,1,8}]; bns = Show[L,H,K,M,PlotRange->All]; Display["proj.ps",bns]; f[t_] := {t/2,t/2,t/2}+ t( Cos[t] u + Sin[t] v); b = ParametricPlot3D[f[t],{t,0,5 Pi}]; c = ParametricPlot3D[ Join[ Q.f[t],{RGBColor[1,0,0]}],{t,0,5 Pi}]; cns = Show[b,c] dns = Show[b,c,ViewPoint->{10,10,10}]; Display["prox.ps",cns]; Display["proy.ps",dns]; -----------------------------------------------------