Class Note for MATH 410 with Professor Dostert at UA
Class Note for MATH 410 with Professor Dostert at UA
Popular in Course
Popular in Department
This 15 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Arizona taught by a professor in Fall. Since its upload, it has received 20 views.
Reviews for Class Note for MATH 410 with Professor Dostert at UA
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
THE UNIVERSITY Q or ARIZONA Math 410 Matrix Analysis Section 41 Minimization Problems Section 42 Minimization of Quadratic Functions Section 43 Least Squares and The Closest Point Section 44 Data Fitting and Interpolation Paul Dostert February 21 2009 115 A Minimization Problems Consider finding the equilibrium points in a standard pendulum What points do we have Which would you consider stable What about a ball rolling on a series of hills Where might the ball stop Which of these would be stable These problems are all related to minimizing a set of equations potential energy in the pendulum case Consider solving f190 07 f290 07 fm90 07 90 E R We may consider the solution to this system as the minimum of 2996 J 1m2 fmx2 Clearly px 2 0 and px 0 iff c solves each of the original eqns Now instead formulate this as a matrix problem Ax b with m eqns and n unknowns We now wish to minimize 2993 b Al IIZ where H H is the Euclidean norm Again px 2 0 and px 0 iff Ax b A Minimization Problems If we have a unique soln to Ax b then we have gained nothing using this approach but what if b g rngA We define 7quot b Ax as the residual and minimzing px is the same as minimizing 7quot The soln minimizing 7quot is called the least squares solution Note that if Ax b then 7quot 0 so the least squares soln corresponds with a traditional soln when Ax b is consistent Now consider the problem of finding a point 11 e V C Rm closest to some point 9 e Rm ie minimize v b over 11 e V What if V is a subspace of Rm with basis v17 711 Then 11 1111 xnvn Ax for some constants 36239 Then minimzing v b is the same as minimizing Ax b with A v1 v2 11 7112 e Rm and ac 12anT7i ER A Quadratic Minimization How do we minimize px ax2 219x c using calculus Instead we could complete the square px a ac 2f g and immediately obtain a global minimum if a gt 0 at c ba and a minimum value of Mai Consider minimizing 1990 P9017790n E kij ci cg 2E fix 0 2391 251 over all of R with kij fi 0 e R We assume Islj kji Writing as a matrix we have 1930 xTKx Zfoc with K an n gtlt n symmetric matrix and f a vector of constants In order to have a minimum in the single quadratic equation we needed a gt 0 The matrix analog of a gt 0 is K SPD Ah Quadratic Minimization using SPD Thm If K is an SPD matrix then px xTKx minimizer which is the solution to Km f Pf sketch Since K is invertible Km f has a unique soln c Write Zfo c has a unique K lf 1930 xTKx ZxTKx 0 ac xTKac x c xTKx Since the non constant term is always positive the minimum must be where it is zero namely where c 9c Ex Use the previous theorem to find the unique minimizer to p 91017 302 2x 2931932 363 2302 1 How would you do this using calculus Note 1 The theorem REQUIRES K SPD You must check this condition first Note 2 If K is positive semidefinite then if f e rngK every solution to Km f is a minimizer as is c z where Kz 0 At The Closest Point We revisit the problem of finding 11 e V minimizing v b for some 9 e R Instead of restricted to the Euclidean norm we consider minimization in any norm with an associated inner product We wish to minimize llv bl2 v bw bgt llvll2 2 v71 W v e V C Rm Assuming v17 711 form a basis of V with n dim V we write 11 1111 xnvn Note n v2 1111 xnvn clvl xnvngt E xixj vhvj acTKx z39j1 v71 331111 907171717 5 2397 5 fo z391 A1 The Closest Point 2 Putting everything back into the distance eqn we have 1930 xTKx Zfo C7 With C Since v2 are linearly independent and K ATA is SPD we can apply our previous minimization theorem Thm Let v17 711 form a basis for the subspace V C Rm Given 9 e Rm the closest pt 11 c fvl 3011 e V is given by c Kilf with km 112715 and fj 112719 The distance between the pt and the subspace llvquot bll V llbll2 fo IS 1 1 Ex Consider V the space spanned by 111 1 and v2 2 Find 0 1 3 3 1 2 7 2 2 2 the weighted norm v 7 121 2112 3113 the point 11 e V closest to b in the Euclidean norm What about in Ah Least Squares A least squares solution to Ax b is a vector 93 e R that minimizes the Euclidean norm Aac b Thm Assume that kerA 0 Set K ATA and f ATb Then the least squares solution to Ax b is the unique solution c to the normal equa ons K90 f or ATA x ATb Ex Find the least squares solution to alc3y07 Zac y17 ar y3 A Data Fitting and Interpolation Suppose we have measured data ti yi 7239 1 m representing some linear process y a t Errors in measurement make this data nonlinear However we wish to find a best fit for the data with a line The error between M and the function value at t 72 is ez Z17quot3977 n which we can write in matrix form as ey Ax withee1yyilA t1andx 0 Herey Keg y i a 3 is the data vector and e is the error vector Clearly if e 0 then Ax y and y e mgA If not we seek the solution that minimizes the error in the Euclidean norm e2 6 efn and hence the term least squares Ah Normal Equations To solve the least squares problem we form the normal equations ATA x ATy gt 90 ATAY1 ATy In order for ATA to be solvable we need linearly independent columns of A hence the t2 cannot be constant why We find 751 ATM s i gswme ti AT911 225 25 where the bars indicate arithmetic averages Now solving ATA ac ATy we get 275239 Z yz39 205239 E2 ay f 76 gty6t fy Ala Least Squares Example Ex Biologists believe there is a linear relationship between temperature and the frequency of cricket chirps The following data were measured Temperature T ChirpsSec x 93 20 84 161 82 160 80 150 76 144 a Find the equation for the least squares line that best fits the data b Estimate the number of chirps per second if the temperature is 88 A Polynomial Interpolation We need not restrict ourselves to linear least squares Consider fitting with a general polynomial yt a0 alt antquot For an nth degree polynomial we form 1 751 75 yl O o A 7y 73 1 tm 39 39 39 75 ym an A is known as the Vandermonde matrix If m n 1 and Ax y has an exact solution we find a polynomial fitting the data exactly and call it an interpolating polynomial If there is no exact solution we can still solve the normal equations to find a least squares solution Lemma If t1 nonsingular Thm Let t1 tn1 are distinct then the Vandermonde matrix is tn1 be distinct Then for any data y1yn1 there exists a unique interpolating polynomial of degree 3 n At Lagrange Interpolation Thm Given distinct points 717 7tn1 the kth Lagrange interpolating polynomial is given by t 731 39 39 39 t 73127173 751c1 39 39 39 t 75n1 73k 751 39 39 39 75k tk71tk 751c1 39 39 39 75k 75nl39 It is the unique polynomial with Lk ti 1 if z k and Lk ti 07139 7 k Lk 75 Thm If 717 7tn1 are distinct then the polynomial that interpolates y17quot397yn1 PO 9113105 39 39 39 yn1Ln1 Ex Find an interpolating polynomial for the following data 751 07752 17753 291 2 92 1and y3 0 Ex Approximate the following data using a quadratic polynomial t1 07t2 17t3 27t4 3y1 2 y2 1y3 Q4 A Matlab Examples Least Squares We find the linear and quadratic least squares fit to the following data X 0 1 2 3 4 Y 5 4 1 0 6 The xx vector will be a large vector of 100 points used for plotting The X is the x data and the Y vector is the y data A1 is the A matrix for linear least squares and A2 is for quadratic coeffs1 contains the coefficients in the polynomial for the linear and coefst contains the coefficients for quadratic We then plot each function and the points xx linspace04 X 014 Y 5 4 1 0 61 A1 Xquot0 Xquot1 coeffs1 A1 A1 A1 Y A2 Xquot0 Xquot1 Xquot2 coeffs2 A2 A2 A2 Y plotxxcoeffs12xx coeffs11xxcoeffs23xxquot2 coefst2xx coeffs21XY ro title Least Squares Problem xlabel x ylabel y legend Linear Quadratic Data Pts A Matlab Interpolation or Least Squares 0 1 2 3 4 Y 5 4 1 0 6 but construct a polynomial which interpolates the data We use poly t which fits a polynomial of a given order to the data If the order is too small to exactly fit the data then poly t returns the least squares polynomial The input is the c points the y data points and the polynomial order N The output is a vectorp consisting of the coefficients of the polynomial 291 XN P2 XN l PN XpN 1 Matlab then has a routine called polyval which evaluates a polynomial at given points We can use this to plot the polynomial fit Take the same data as previously xx linspace04 X 01 4 Y 5 4 1 0 61 p1 polyfitXY1 p2 polyfitXY2 p3 polyfitXY3 p4 polyfitXY4 yy1 polyvalp1xx yy2 polyvalp2xx yy3 polyvalp3xx yy4 polyvalp4xx plotxxyy1 xxyy2 xxyy3 xxyy4 XY o legend Linear Quadratic Cubic Quartic Data Location NorthWest
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'