How to find a derivative?

How to find a derivative?

How to find a derivative? Gordon Li The Problem

is trivial to compute for smooth continuous functions Real data is always discrete (and noisy!) The Problem Q: Given some empirical data can we find a method to approximate ?

A: Not really numerical differentiation is non-trivial! Why is Numerical Differentiation needed? We may want to find rates of change for the unknown function Needed to numerically solve many nonlinear differential equations

Used to compute Taylor polynomial approximations for Because my supervisor told me to do it Forward/Backward Difference Method We approximate using the gradient of the secant between each pair of adjacent points.

Forward: Backward: Forward/Backward Difference Method We can estimate the error using Taylors Theorem:

The error is and the time complexity is . Attempt #1 +() Rounding Error

We assume that creates a rounding error of the form: The total error is . Floating-point Representation Both types of error are fundamentally due to the floating-point representation of real numbers by computers.

Floating-point Representation Numerical differentiation is ill-conditioned, so floating-point error gets compounded with each use cannot be chosen too small, otherwise it will get rounded to zero and produce is probably inconsistent (changes for different )

It is still the best system we have Central Difference Method We can improve on the forward/backward difference method by using triplets instead of pairs. The idea is that all the even terms will cancel in the Taylor expansion.

Central Difference Method We can estimate the error using Taylors Theorem: The error is and the time complexity is . Attempt #2

() Richardson Extrapolation The idea is to compute for 2 different values of , and combine the results in some appropriate manner, as guided by our knowledge of the error behaviour.

The error is and the time complexity is . Attempt #3 ( ) ( )

Polynomial Interpolation We can look at the data globally instead of locally to try and minimise the noise by fitting a polynomial of degree . Polynomial Interpolation

We can approximate by differentiating the polynomial The error is and the time complexity is . Attempt #4 ()

Why is Numerical Differentiation difficult? We can show that numerical differentiation is fundamentally difficult using Fourier analysis. Write in terms of the inverse Fourier Transform of :

differentiation is equivalent to multiplication in the frequency domain. Why is Numerical Differentiation difficult? Noise is caused by high frequency Fourier components These high frequency components get amplified by the multiplication in the frequency domain, hence creating large errors

The same logic can be used to show that integration is equivalent to division in the frequency domain, hence minimising the error and making numerical integration a trivial task Spectral Methods The idea is to use Fourier analysis to filter out the noise, but lose some accuracy in the process.

1. Compute the discrete Fourier transform (DFT) of using the FFT algorithm 2. Filter out the high frequency components (but not too much) 3. Perform the multiplication in the frequency domain 4. Compute the inverse DFT using the FFT algorithm. The error depends on the filter and the time complexity is .

Attempt #5 Summary Method

Error Forward/Backward Difference Central Difference Richardson Extrapolation Polynomial Interpolation FFT

Depends on how you filter Time Complexity

Recently Viewed Presentations

  • Presentazione di PowerPoint - GuidaTu

    Presentazione di PowerPoint - GuidaTu

    Sindona viene ucciso, così come Boris Giuliano che alla guida della mobile di Palermo aveva dato un colpo micidiale alla mafia di Bagarella, scoprendo le radici del traffico di stupefacenti internazionale e di armi, e poi il giudice Costa, il...
  • Dialogue for Building Communion in The Mission

    Dialogue for Building Communion in The Mission

    Ethnorelativism refers to relativity of cultural values. Here what is acceptable is not judged basing on one's own culture, but made on the criteria of transcend cultural values. It refers to the empirical observation that cultures differ. It therefore helps...
  • Assessment - Building Bridges

    Assessment - Building Bridges

    Test . According to Bachman (1990) defines tests as "a measurement instrument designed to elicit a specific sample of an individual behavior" ... Supera. Criterion-reference - evaluate students in terms of mastery of the course content. Example:
  • Applications - University of Wisconsin-Madison

    Applications - University of Wisconsin-Madison

    * CS 640 * Gnutella One of the first decentralized P2P networks for file sharing No central registry of objects. Example topology of a Gnutella P2P network Edges of the graph correspond to the relationship "A and B know each...
  • So, What is in it for You?! - STC India

    So, What is in it for You?! - STC India

    So, What is in it for You?Life hacks to being empathetic in the workplace. Manisha Khurana, Senior Manager, Spice Digital. Radhika Hari, Senior Technical Writer, Oracle India. Cognitive diversity at workplace. Use your skills and talents to meet business goals...
  • The Thesis Writing Process - Trinity College, Dublin

    The Thesis Writing Process - Trinity College, Dublin

    * Based on Rowena Murray's book, How to Write a Thesis (2002) from research on writing process and experience. Three aspects to the process that need attending: Social aspect: Feedback;discussion with peers, free thinking - helps with the thinking/writing process....
  • Using BEA to Modify Packaged Reading Interventions for

    Using BEA to Modify Packaged Reading Interventions for

    We would like to thank our undergraduate student assistant, Jessa Quick, for her time and dedication.Funding for this study was provided by the UWEC Office of Research and Sponsored Programs. Discussion. Results suggest that BEA methodology empirically-selected reading fluency interventions...
  • Jim Crow - Mr. Kelly

    Jim Crow - Mr. Kelly

    Arial Calibri Times New Roman Wingdings Office Theme What was Jim Crow? Examples of Jim Crow Laws Plessy vs. Ferguson Court Case The _____ is re-founded in 1917 and its membership grows into the millions during the _____ Most members...