Today I Learned

Some of the things I've learned every day since Oct 10, 2016

Monthly Archives: February 2018

192: GIGO

Garbage In, Garbage Out.

To quote my numerical analysis professor John Strain, “If you have a really fancy method and give it garbage data, what you’ll get out is some really fancy garbage.”


191: Stability, Instability of Numerical Integration, Differentiation

Numerical integration methods such as use of the composite Simpson’s rule, composite trapezoidal rule, etc., are stable. That is, their round-off error as a result of being performed with machine arithmetic does not depend on the number of sub-intervals the integrating interval is split up into.

By contrast, numerical differentiation methods such as the 2-point, 3-point, and 5-point formulas are unstable, because these formulas involve division by the width of the step-size h used. So at a certain point as h \rightarrow 0, round-off error overtakes the increased accuracy of a small step-size and the approximations actually start to get worse.

190: A Greedy Scheduling Algorithm

Suppose you have a ‘time’ interval (a, b) with a, b \in \mathbb{R}, a < b, and that you have a set E of ‘events’ (s_1, t_1), (s_2, t_2), \dots, (s_n, t_n) with a \leq s_i < t_i \leq b for all i. And suppose you want to schedule as many events from E into (a, b) as possible. That is, you want to select a subset of non-overlapping members of E of maximum size. The following greedy algorithm does this in an optimal way (optimal solution, not necessarily runtime):


The total runtime is O(n \log n).

189: Depth-First, Breadth-First, Uniform Cost, and A* Search Differ Only In Their Fringe

As graph exploration algorithms through search problem state spaces, depth-first, breadth-first, uniform cost, and A* search all have the following general form:


Credit: University of California, Berkeley

They differ only in the type of fringe used. Depth first uses a stack, breadth-first a queue, and both uniform cost and A* use a priority queue. (Uniform cost’s priority is based on the distance from the starting point to a given node, while that of A* is the sum of this distance and the node’s heuristic function.)


188: Lagrange Interpolation

Given a real function f, a set of n+1 points x_0, \dots, x_n, and the values f(x_0), \dots, f(x_n) of f at those points, the Lagrange polynomial uses this information to give an n-th degree polynomial P which approximates f. The formula for P is

P = L_0 f(x_0) + \cdots + L_n f(x_n),


L_k = (\prod_{i \neq k} (x - x_i))/(\prod_{j \neq k} (x_k - x_j)).

Example: where n = 1 and we are given x_0, x_1, f(x_0), f(x_1), the Lagrange polynomial approximating f is

P = \frac{x - x_1}{x_0 - x_1} f(x_0) + \frac{x - x_0}{x_1 - x_0} f(x_1).

Examination of the polynomial should make it clear that it is, in a way, the simplest polynomial where P(x_k) = f(x_k) at each x_k.