# User:Egm6341.s11/Lecture plan

Under construction throughout the semester. Egm6321.f10 21:49, 31 October 2010 (UTC)

Give me a fish, I eat for one day. Teach me to fish, I eat for a lifetime.

Proverb quoted in [Lebesgue integration, S.B. Chae, 1995].

Algos is the Greek word for pain. Algor is Latin, to be cold. Neither is the root for Algorithm, which stems instead from al-Khwārizmī, the name of the ninth-century Arab scholar whose book al-jabr wa’l muqabalah devolved into today’s high school algebra textbooks. Al-Khwarizmi stressed the importance of methodical procedures for solving problems. Were he around today,he’d no doubt be impressed by the advances in his eponymous approach.

B.A. Cipra, [The Best of the 20th Century: Editors Name Top 10 Algorithms], SIAM News, May 16, 2000.

# All versions

Spring 2011, Spring 2010

EML 5526, Spring 2011, Lecture plan

# Recorded lectures, TA user page

Recorded lectures in E-Learning at UF

# Lecture notes, report table

Additional presentations (video, wiki, static html) made in class may not be recorded on these transparencies.

A mtg number n followed by a version letter in parentheses ([a-z]) indicates that this pdf file had been updated with a 2nd version "b", 3rd version "c", etc. The second letter "x" after a version letter designates an extra lecture; this letter became "m" after the extra lecture had become a make-up lecture. If you had downloaded this pdf file before, you want to clear the cache of your browser so to get the new version.

djvu: (install the viewers DjView4 or evince)
Mtg 1 (b), Mtg 2, Mtg 3 (e), Mtg 4 (b), Mtg 5 (d), Mtg 6 (b,m), Mtg 7 (d,m), Mtg 8 (d), Mtg 9 (e), Mtg 10 (b,m), Mtg 11 (c), Mtg 12, Mtg 13 (b), Mtg 14 (b), Mtg 15 (b), Mtg 16 (b,m), Mtg 17 (c), Mtg 18 (c), Mtg 19 (c), Mtg 20 (b), Mtg 21 (c),
Mtgs 22+23: Exam 1 (thus the Mtg no. from 22 to 26 should be incremented by 2, i.e., Mtg 22 should be numbered Mtg 24, ..., Mtg 26 should be numbered Mtg 28) Mtg 22 (b,m), Mtg 23 (a,m), Mtg 24 (d), Mtg 25 (c), Mtg 26 (b), (Mtg numbers are readjusted from Mtg 29 on)
Mtg 29 (b,m) {old}, Mtg 30 (3,m), Mtg 31 (b), Mtg 32 (b,x), Mtg 33 (b), Mtg 34 (b), Mtg 35, Mtg 36 (b,x), Mtg 37 (b), Mtg 38, Mtg 39,
Mtg 40 (c) (S10 Mtg 38, S10 Mtg 39, S10 Mtg 40, S10 Mtg 41),
Mtg 41 (c) (S10 Mtg 41),
Mtg 42 (b) (S10 Mtg 38, S10 Mtg 39, S10 Mtg 40, S10 Mtg 41, S10 Mtg 42),
Mtgs 43+44: Exam 2

Report table

Course billboard

Inspiring video on teamwork and learning: A hole in the wall: How children learn without a teacher

Mourning the Death of Handwriting, By Claire Suddath. Time Magazine, Monday, Aug. 03, 2009.

Op-Art: The Write Stuff, by Inga Dubay and Barbara Getty, NY Times, 8 Sep 2009.

# References

## Open-source software and documentation

### $\displaystyle \color{red}{\spadesuit}$NEW:Fast Clenshaw-Curtis quadrature, Matlab central

by Greg von Winckel, 12 Feb 2005 (Updated 16 Feb 2005). This extremely fast and efficient algorithm uses MATLAB's ifft routine to compute the Clenshaw-Curtis nodes and weights in linear time. The routine appears optimal for 2^N+1 points. Running on an average laptop, this routine computed N=2^20+1 (1048577 points) in about 4.5 seconds. Great for integrating highly oscillatory functions.

## Books

$\displaystyle \clubsuit$ K. Atkinson, An Introduction to Numerical Analysis, Wiley, 1989. UF library QA297 .A84 1989 Google Amazon

$\displaystyle \clubsuit$ Suli & Mayers, An introduction to numerical analysis, Cambridge, 2003. UF library E-book Google Amazon

$\displaystyle \color{red}{\clubsuit}$ NEW: NIST Digital Library of Mathematical Functions, companion of the NIST Handbook of Mathematical Functions, ed. by F.W.J. Olver, et al., Cambridge U. Press, 2010. "Together these works represent a successor to the highly successful Handbook of Mathematical Functions (M. Abramowitz and I. Stegun, Eds.; see below), which was published by the National Bureau of Standards in 1964." NA Digest, Vol.10, No.19, May 2010.

$\displaystyle \clubsuit$ M. Abramowitz & I. Stegun, Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, New York: Dover Publications, 1972. Read online, Download Wikipedia

$\displaystyle \clubsuit$ L.N. Trefethen, Spectral Methods in Matlab, SIAM, Philadelphia, 2000. google matlab codes, e.g., clencurt; $\displaystyle \color{red}{\clubsuit}$ NEW: see also Fast Clenshaw-Curtis quadrature by von Winckel, 2005.

$\displaystyle \clubsuit$ L.N. Trefethen, Approximation Theory and Approximation Practice: A 21st Century Treatment in the Form of 32 Executable Chebfun M-Files, 2010 draft of first 8 chapters, pdf.

$\displaystyle \clubsuit$ J.D. Murray, Mathematical biology I: An introduction, 3rd edition, Springer, 2002. UF library QH323.5.M88 2002 google amazon

$\displaystyle \clubsuit$ R.H. Battin, An Introduction to the Mathematics and Methods of Astrodynamics, AIAA, 1999. google amazon. Battin was a speaker in the symposium Apollo: Reflections and Lessons (40th anniversary of the first moon landing), MIT, 11 Jun 2009.

$\displaystyle \clubsuit$ D. Zwillinger, Handbook of Differential Equations, Third Edition, Academic Press, 1998. ISBN-10: 0127843965. ISBN-13: 978-0127843964. UF library QA371.Z88 1989, 2 copies, one for in-library use. Google books Amazon.com

## Web references

$\displaystyle \spadesuit$ Algorithm (wikipedia)

$\displaystyle \spadesuit$ Related MIT OpenCourseWare courses

$\displaystyle \spadesuit$ Wolfram|Alpha is ... "learning resource available to your students at no cost that works as a computational knowledge engine. Wolfram|Alpha is not a search engine like Google or Yahoo!, because unlike a traditional search engine, Wolfram|Alpha has the capability to instantly compute the answer to previously unasked questions instead of scouring the web and returning links to pages that already exist. The results are displayed in an easy-to-read, understandable format that can be used as a primary source for educational and academic purposes."

$\displaystyle \color{red}{\spadesuit}$ NEW: Stephen Wolfram: Computing the theory of everything, video on TED.com

$\displaystyle \spadesuit$ EqWorld, The World of Mathematical Equations. It is a good idea to verify the sources, as the site is not responsible for accuracy and correctness; see Rights and obligations of contributors and website administration.

$\displaystyle \spadesuit$ ODE (Wikipedia): Be careful; always verify the sources.

$\displaystyle \color{red}{\spadesuit}$ NEW: Sitmo: Resources for financial engineers, latex equation editor, Clenshaw-Curtis quadrature, etc.

## Papers

$\displaystyle \clubsuit$ L.N. Trefethen and Z. Battles, The Chebfun project, Oxford.

$\displaystyle \clubsuit$ P. Kessler, Trapezoidal rule error, Math 128a, Berkeley, 2006. These notes were referred to in a paper by S.G. Johnson, 2008.

$\displaystyle \clubsuit$ S. G. Johnson, Notes on the convergence of trapezoidal-rule quadrature, online MIT course notes (2008). This document mentioned Kessler's notes in a footnote.

$\displaystyle \clubsuit$ Lloyd N. Trefethen, Is Gauss quadrature better than Clenshaw-Curtis?, SIAM Review 50 (1), 67-87 (2008).

$\displaystyle \clubsuit$ B.A. Cipra, The Best of the 20th Century: Editors Name Top 10 Algorithms, SIAM News, May 16, 2000. A look at ten algorithms named some of the "best" of the computer age. The Fast Fourier Transform (FFT) is one of them.

$\displaystyle \clubsuit$ D.N. Rockmore, The FFT — an algorithm the whole family can use, Computing in Science & Engineering, January/February 2000, Volume 2, Number 1, pp. 60--6. Contained a historical account of the development of the FFT.

$\displaystyle \clubsuit$ Sri Welaratna, 30 years of FFT Analyzers, Sound and Vibration (January 1997, 30th anniversary issue). A historical review of hardware FFT devices. See Fast Fourier transform (wikipedia).

$\displaystyle \clubsuit$ B.A. Conway, The choices available to space trajectory optimizers, seminar given at UF on Tue, 23 Feb 2010. By listening to this talk, I noticed an application of the Simpson's rule; I thought about teaching this application and searched the literature as shown below. Prof. Conway later graciously shared his talk slides with me (I did the literature search below, and found the paper by Hargraves & Paris 1987 and other papers before I received his talk slides, which I also shared with the students in the class). Another seminar on the use of the Hermite-Simpson algorithm was given at UF on 30 Mar 2010.

$\displaystyle \clubsuit$ Gauss, Legendre, ... pseudospectral methods

• Web of Science literature search: Topic=(gauss legendre pseudospectral method*) Timespan=All Years. Databases=SCI-EXPANDED, SSCI, A&HCI.
• Hermite-Legendre-Gauss-Lobatto Direct Transcription in Trajectory Optimization. Author(s): Williams P. Source: JOURNAL OF GUIDANCE CONTROL AND DYNAMICS Volume: 32 Issue: 4 Pages: 1392-1395 Published: JUL-AUG 2009
• Rational Legendre pseudospectral approach for solving nonlinear differential equations of Lane-Emden type Author(s): Parand K, Shahini M, Dehghan M Source: JOURNAL OF COMPUTATIONAL PHYSICS Volume: 228 Issue: 23 Pages: 8830-8840 Published: DEC 10 2009
• Leaky mode analysis of optical waveguides by legendre and laguerre pseudospectral method Author(s): Huang CC Source: MICROWAVE AND OPTICAL TECHNOLOGY LETTERS Volume: 50 Issue: 10 Pages: 2507-2509 Published: OCT 2008
• Pseudospectral methods for infinite-horizon optimal control problems Author(s): Fahroo F, Ross IM Source: JOURNAL OF GUIDANCE CONTROL AND DYNAMICS Volume: 31 Issue: 4 Pages: 927-936 Published: JUL-AUG 2008

# News

$\displaystyle \color{red}{\clubsuit}$ NEW: Is openness in the digital space killing creativity?, Digital Planet, BBC, 15 Mar 2011.

$\displaystyle \color{red}{\spadesuit}$ NEW: Bing, Now With More Wolfram, NY Times, November 11, 2009. ... Microsoft today announced that it will begin integrating statistics and other data from computational engine WolframAlpha into its search engine Bing.

$\displaystyle \color{red}{\spadesuit}$ NEW: Ask.com to Return to Old Service, NY Times, November 9, 2010. ... Other search engines have taken on Google with little success. Cuil, one of the upstarts, closed in September after two years. But new challengers include Blekko and WolframAlpha.

$\displaystyle \color{red}{\spadesuit}$ NEW: Fun With WolframAlpha, NY Times, June 5, 2009.

# Motivation: Simulations

$\displaystyle \color{red}{\spadesuit}$ NEW: Humans to Asteroids: Watch Out!, NY Times, By RUSSELL SCHWEICKART Published: October 25, 2010. Deflect That Asteroid, NY Times, November 2, 2010

An asteroid breakup 160 Myr ago as the probable source of the K/T impactor, William F. Bottke, David Vokrouhlický & David Nesvorný, Nature 449, 48-53 (6 September 2007).

Asteroids: Spun in the sun, William F. Bottke, Nature 446, 382-383 (22 March 2007).

Asteroids: How to make a flying saucer, William F. Bottke, Nature 454, 173-174 (10 July 2008).

Asteroid, NASA. Pictures of asteroids Ida, Eros, and Chicxulub impact (Yucatan peninsula), extinction of dinausaurs.

Large asteroid impacting the Earth, simulation

Hubble Space Telescope Captures Rare Jupiter Collision, 07.24.09

Solar system collision: Set Target Earth (land only), Projectile Rock, Projectile diameter 10 km, Projectile velocity 60 km / sec; click Kaboom; see photo of Chicxulub impact.

# Numerical integration of functions: Preliminaries

Atkinson, 1989, p.249

## Mathematical preliminaries

### Error

#### Norms

Atkinson, 1989, p.10

## Taylor series expansion

### Error term, remainder

#### Integral mean value theorem

Atkinson, 1989, p.4

Mean value theorem (wikipedia)

## Simpson's rule

Thomas Simpson (20 August 1710, Market Bosworth, Leicestershire, England –

14 May 1761, Market Bosworth, Leicestershire, England) was a weaver by training who taught mathematics in the London coffee-houses. His two-volume work entitled The Doctrine and Application of Fluxions published in 1750 contains some of the work that Cotes hoped to publish with Cambridge University Press but was prevented by his premature death. In 1796 fellow mathematician Charles Hutton gave the following description of Simpson: It has been said that Mr Simpson frequented low company, with whom he used to guzzle porter and gin: But it must be observed that the misconduct of his family put it out of his power to keep the company of gentlemen, as well as to procure better liquor. [Suli & Mayers, 2003, p.203].

On the history of the Newton-Raphson method:

Newton’s De analysi per aequationes numero terminorum infinitas, probably dating from mid-1669, is sometimes regarded as the historical source of the method, despite the fact that, surprisingly, there is no trace in this tract of the familiar recurrence relation $x_{k+1} = x_k - f(x_k) / f^\prime (x_k)$ bearing Newton’s name, nor is there a mention of the idea of derivative. ... In 1690, Joseph Raphson (1648–1715) in the Preface to his Analysis aequationum universalis describes his version of Newton’s method as ‘not only, I believe, not of the same origin, but also, certainly, not with the same development’ as Newton’s method. Further improvements to the method, and its form as we know it today, were given by Thomas Simpson in his Essays in Mathematicks (1740). Simpson presents it as ‘a new method for the solution of equations’ using the ‘method of fluxions’, i.e., derivatives. ... Simpson’s contributions to this subject have been underestimated, and ‘it would seem that the Newton–Raphson–Simpson method is a designation more nearly representing facts of history of this method which lurks inside millions of modern computer programs and is printed with Newton’s name attached in so many textbooks’. [Suli & Mayers, 2003, p.33-34].

## Computation, comparison

 $\displaystyle I = \int\limits_0^x \frac{e^t - 1}{t} d t = Ei(x) - ln(x) - \gamma$ (1)

The exact result of the above integral is given in Abramowitz & Stegun, p.230, with the Euler's constant $\gamma\,\;$ given in Abramowitz & Stegun, p.255.

A more accurate Euler's constant can be found at Wolfram|Alpha.

Since the exponential integral is defined as

 $\displaystyle Ei(x) := ln(x) + \gamma + \sum_{n=1}^{\infty} \frac{x^n}{n n!}$ (2)

the integral in Eq.(1) is nothing but the series in the 3rd term in Eq.(2), which can also be obtained by integrating the Taylor series.

## Newton-Cotes formula

On Thu, 11 Feb 2010, I listened to the following interesting NPR program at the University of Illinois at Urbana-Champaign; of course Newton plays an important role in the current course (and in many other areas):

Newton and the Counterfeiter: The Unknown Detective Career of the World's Greatest Scientist,

Thomas Levenson, Head of the Graduate Program in Science Writing, MIT; Emmy- and Peabody-Award-Winning Documentary Filmmaker, Radio program: NPR Afternoon Magazine, Thu, 11 Feb 2010. [Book on amazon.com] with interesting comments. See also the NOVA program Newton's dark secret.

Roger Cotes (10 July 1682, Burbage, Leicestershire, England – 5 June 1716, Cambridge,

Cambridgeshire, England) was a fellow of Trinity College in Cambridge. At the age of 26 he became the first Plumian Professor of Astronomy and Experimental Philosophy. Even though he only published one paper in his lifetime, entitled ‘Logometria’, Cotes made important contributions to the theory of logarithms and integral calculus, particularly interpolation and table construction. In reference to Cotes’ early death, Newton said: If he had lived we might have known something. [Suli & Mayers, 2003, p.201].

# Lagrange interpolation error: Theorem

Atkinson, 1989, p.134

## Comparison with Taylor series

Intelligence consists of this; that we recognize the similarity of different things and the difference between similar ones.

Baron de la Brède et de Montesquieu (1689-1755); quoted in [Quantum field theory, E. Zeidler, 2008, p.175].

## Proof

### Derivative mean-value theorem

Atkinson, 1989, p.4

Mean value theorem (wikipedia)

#### Rolle's theorem

Rolle's theorem (wikipedia)

Rolle’s Theorem, was published in an obscure book in 1691 by the French mathematician Michel Rolle (1652–1719) who invented the notation

$\sqrt[n]{x}\,\;$ for the nth root of $x\,\;$. [Suli & Mayers, 2003, p.419].

## Application: Error estimates

### Runge phenomenon

#### Application: Cauchy distribution

The formula for the Cauchy distribution and its variants have been studied for around 300 years in a variety of contexts. In its oldest form it is known as the WITCH OF AGNESI. The history of the use of the function in probability is traced in S. M. Stigler “Cauchy and the Witch of Agnesi” (in Stigler (1999)). The function was introduced by Poisson in 1824 in his “Sur la probabilité des résultats moyens des observations,” Connaissance des Temps pour l’an 1827, 273-302 and the association is duly noted in Bertand’s Calcul des Probabilités (1889, p. 257). However, the name most often associated with the function is that of Cauchy who reintroduced the function in 1853 in his “Sur les résultats moyens d’observations de même nature, et sur les résultats les plus probables,” Comptes Rendus de l'Académie des Sciences, 37, (1853), 198-206. The name, “la loi de Cauchy,” appears in Lévy’s Calcul des Probabilités (1925, p. 179); Lévy had an interest in the law as one of the STABLE LAWS. In the English literature the name “Cauchy distribution” entered circulation in the 1930s: see e.g. B. O. Koopman’s “On Distributions Admitting a Sufficient Statistic,” Transactions of the American Mathematical Society, 39, (1936), pp. 399-409. Earlier writers had other ways of referring to the distribution; thus to R. A. Fisher (Mathematical Foundations of Theoretical Statistics (1922), pp. 321-2) it was a Pearson “Type VII” distribution; for this terminology see the entry PEARSON CURVES.

A version of the function is used in optics where it is called the LORENTZIAN FUNCTION after H. A. Lorentz “The width of spectral lines,” Proc. Acad. Sci. Amsterdam, 18, (1915), 134-150; see MathWorld Lorentzian Function. In particle physics there is another version called the BREIT-WIGNER DISTRIBUTION after G. Breit & E. P. Wigner “Capture of slow neutrons,” Physical Review, 49, (1936), 519-544. See Chronology of Milestone Events in Particle Physics and Wikipedia Relativistic Breit–Wigner distribution. Section C (for Cauchy) in Earliest Known Uses of Some of the Words of Mathematics, Jeff Miller.

Lorentzian distribution of spectral line width (Lecture 08), in Astronomy course on Nebulae, K. Wood, Univ. of St Andrews, Scotland, UK.

[The normal distribution] was sometimes called the Gaussian distribution, in honor of the man once believed to have first formulated it, except that it was not Carl Friedrich Gauss but an earlier mathematician named Abraham de Moivre who first wrote down the formula for the distribution. There is good reason to believe that Daniel Bernoulli came across the formula before this. All this is an example of what Stephen Stigler, a contemporary historian of science, called the law of misnomy, that nothing in mathematics is ever named after the person who discovered it.

Salsburg, [The Lady Tasting Tea: How statistics revolutionized science in the 20th century], 2001, p.29.

Portrait of Gauss on the Deutsch mark: Notice the normal distribution curve next to Gauss' portrait. Gauss "developed the Gaussian Bell Curve, to account for the statistical variation in individual observations of stellar locations." So even though Gauss was not the first to have come across the normal distribution, he may have invented it independently of de Moivre, and applied it to astronomy.

See also the quotation on Pythagoras' theorem (and the corresponding NPR program in which there was a mention of Stigler's law of misnomy).

# Higher-order error analysis of trapezoidal rule

## Euler-MacLaurin series

Euler–Maclaurin formula

### Application: Corrected trapezoidal rules

#### Corrected trapezoidal rules $CT_k (n)$

Another notation $CT_k (n) \equiv CT^{(2i+1)}_n (f)$ with (2i+1)th derivative and (n+1) integration points.

### Periodic functions

#### Application: Arc length of ellipse

##### Arc length integral

Another surprising fact about the Pythagorean theorem — it wasn't really discovered by Pythagoras. Pythagoras was a shaman ... In the sixth century B.C., Pythagoras set up a colony in the southern part of Italy. It was there that his followers came up with the formula, ... and, of course, Pythagoras took or was given credit for it.

NPR, All Things Considered, Pythagorean Theorem: There's More To This Equation, 2011.03.09

##### Two representations of ellipse
###### Elliptic integral of second kind

Ellipse (wikipedia)

##### Orbital mechanics

The 18th-century battle over lunar motion, Siegfried Bodenmann, Physics Today, Jan 2010. In a dispute with more than just scientific import, Alexis Clairaut, Leonhard Euler, and Jean le Rond d’Alembert each employed their own strategies to establish that they were the first to understand a puzzling feature of the Moon’s orbit.

The Sky Is Falling; The Threat of Near Earth Objects (audio) (From the US National Academies) The US spends approximately \$4 million each year searching for near-Earth objects to detect those that may collide with Earth. What is the true threat that we are facing and what can we do about it?

The Phuto Files (video): An excellent, funny, lively, and highly informative NOVA program on the history of the discovery and the current status of the (dwarf) planet Pluto.

The case for Pluto (talk video), Alan Boyle, MSNBC, Distinctive voices @ the Beckman Center, National Academies, 2010. While watching this presentation, it may be useful to take a look at the excellent article Pluto (wikipedia) now and then to identify the names of different people mentioned in the talk; the main story of the talk is also recorded in this Wikipedia article.

The Clenshaw-Curtis quadrature is used in spectral methods for efficient integration, and the spectral methods are among the important numerical methods of the 20th century:

Spectral methods are one of the "big three" technologies for the numerical solution of PDEs, which came into their own roughly in successive decades:

• 1950s: finite difference methods
• 1960s: finite element methods
• 1970s: spectral methods

... Then in the 1970s, a transformation of the field was initiated by Orszag and others on problems in fluid dynamics and meteorology, and the spectral methods became famous.
Trefethen, [Spectral Methods in Matlab, 2000], Preface, pp.ix-x.

L.N. Trefethen, Approximation Theory and Approximation Practice: A 21st Century Treatment in the Form of 32 Executable Chebfun M-Files, 2010 draft of first 8 chapters, pdf.

### Discrete cosine transform

Fourier transform

S.A. Khayam, The Discrete Cosine Transform (DCT): Theory and Application (pdf), 2003: Application of DCT to image/video compression.

# Application: Optimal control of trajectory

## Supersonic interceptor at minimum time

Bryson, Denham, A steepest-ascent method for solving optimum programming problems, Journal of Applied Mechanics, Jun 1962, p.247-257.

## Minimum altitude aircraft bunting maneuver

Computational optimal control of the terminal bunt manoeuvre - Part 1: minimum altitude case, S. Subchan, R. Zbikowski, Volume 28 Issue 5 , Pages 311 - 395 (September/October 2007). Bunt (maneuver): "2. (Engineering / Aeronautics) to cause (an aircraft) to fly in part of an inverted loop or (of an aircraft) to fly in such a loop".

## Application: Population dynamics

J.D. Murray, Mathematical biology I: An introduction, 3rd edition, Springer, 2002. UF library QH323.5.M88 2002 google amazon

# Orthogonal polynomials

## General theory

### Orthogonality

Lecture plan of other courses