Numerical Analysis and Computing Lecture Notes #10 — Approximation Theory — Discrete Least Squares Approximation Joe Mahaffy, [email protected] DepartmentofMathematics DynamicalSystemsGroup ComputationalSciencesResearchCenter SanDiegoStateUniversity SanDiego,CA92182-7720 http://www-rohan.sdsu.edu/∼jmahaffy Spring 2010 JoeMahaffy,[email protected] DiscreteLeastSquaresApproximation —(1/33) Outline 1 Approximation Theory: Discrete Least Squares Introduction Discrete Least Squares 2 Discrete Least Squares A Simple, Powerful Approach 3 Discrete Least Squares Application: Cricket Thermometer JoeMahaffy,[email protected] DiscreteLeastSquaresApproximation —(2/33) ApproximationTheory:DiscreteLeastSquares Introduction DiscreteLeastSquares DiscreteLeastSquares Introduction: Matching a Few Parameters to a Lot of Data. Sometimes we get a lot of data, many observations, and want to fit it to a simple model. 8 6 4 2 0 0 1 2 3 4 5 Measured Data JoeMahaffy,[email protected] DiscreteLeastSquaresApproximation —(3/33) ApproximationTheory:DiscreteLeastSquares Introduction DiscreteLeastSquares DiscreteLeastSquares Introduction: Matching a Few Parameters to a Lot of Data. Sometimes we get a lot of data, many observations, and want to fit it to a simple model. 8 6 4 2 0 0 1 2 3 4 5 Measured Data Average JoeMahaffy,[email protected] DiscreteLeastSquaresApproximation —(3/33) ApproximationTheory:DiscreteLeastSquares Introduction DiscreteLeastSquares DiscreteLeastSquares Introduction: Matching a Few Parameters to a Lot of Data. Sometimes we get a lot of data, many observations, and want to fit it to a simple model. 8 6 4 2 0 0 1 2 3 4 5 Measured Data Linear Best Fit JoeMahaffy,[email protected] DiscreteLeastSquaresApproximation —(3/33) ApproximationTheory:DiscreteLeastSquares Introduction DiscreteLeastSquares DiscreteLeastSquares Introduction: Matching a Few Parameters to a Lot of Data. Sometimes we get a lot of data, many observations, and want to fit it to a simple model. 8 6 4 2 0 0 1 2 3 4 5 Measured Data Quadratic Best Fit JoeMahaffy,[email protected] DiscreteLeastSquaresApproximation —(3/33) ApproximationTheory:DiscreteLeastSquares Introduction DiscreteLeastSquares DiscreteLeastSquares Introduction: Matching a Few Parameters to a Lot of Data. Sometimes we get a lot of data, many observations, and want to fit it to a simple model. 8 6 4 2 0 0 1 2 3 4 5 Underlying function f(x) = 1 + x + x^2/25 Measured Data JoeMahaffy,[email protected] DiscreteLeastSquaresApproximation —(3/33) ApproximationTheory:DiscreteLeastSquares Introduction DiscreteLeastSquares DiscreteLeastSquares Introduction: Matching a Few Parameters to a Lot of Data. Sometimes we get a lot of data, many observations, and want to fit it to a simple model. 8 6 4 2 0 0 1 2 3 4 5 Underlying function f(x) = 1 + x + x^2/25 Measured Data Average Linear Best Fit Quadratic Best Fit PDF-link:code. JoeMahaffy,[email protected] DiscreteLeastSquaresApproximation —(3/33) ApproximationTheory:DiscreteLeastSquares Introduction DiscreteLeastSquares DiscreteLeastSquares Why a Low Dimensional Model? Low dimensional models (e.g. low degree polynomials) are easy to work with, and are quite well behaved (high degree polynomials can be quite oscillatory.) All measurements are noisy, to some degree. Often, we want to use a large number of measurements in order to “average out” random noise. Approximation Theory looks at two problems: [1] Given a data set, find the best fit for a model (i.e. in a class of functions, find the one that best represents the data.) [2] Find a simpler model approximating a given function. JoeMahaffy,[email protected] DiscreteLeastSquaresApproximation —(4/33) ApproximationTheory:DiscreteLeastSquares Introduction DiscreteLeastSquares DiscreteLeastSquares Interpolation: A Bad Idea? We can probably agree that trying to interpolate this data set: 8 6 4 2 0 0 1 2 3 4 5 Measured Data with a 50th degree polynomial is not the best idea in the world... Even fitting a cubic spline to this data gives wild oscillations! [I tried, and it was not pretty!] JoeMahaffy,[email protected] DiscreteLeastSquaresApproximation —(5/33)