CPBS 7620 - Lecture 3 - Functions of Real Numbers

Overview

Nicholas Dwork introduces continuity, roots, and numerical methods for functions of real numbers, using examples such as the jump discontinuity and sin(1/x). He explains bisection for locating roots in a sign-changing interval, then develops golden-section search for a single minimum, showing how the golden ratio lets each iteration reuse a function evaluation.

Key takeaways

The function sin(1/x) has no limit at x = 0 because its values continue oscillating throughout [-1, 1] arbitrarily close to zero.
Bisection requires a sign-changing bracket and, for a guaranteed root, continuity; once the interval width is at most 2ε, the midpoint is within ε of any root inside it.
A maximum-iteration condition supplements an error-based stopping rule and protects bisection from running indefinitely.
Searching in thirds reduces an interval using two function evaluations each round, which can be costly when evaluations involve experiments or substantial computation.
For a single minimum in a unimodal interval, golden-section search reuses one candidate point after each interval reduction and needs only one new function evaluation per iteration.

Chapters

0:00 Continuity, Roots, and Bisection for Sign-Changing Intervals

A jump has different left- and right-hand limits, while sin(1/x) oscillates between -1 and 1 near x = 0, so its limit there does not exist.
A root is an input x for which f(x) = 0; applications include ray-surface intersections, population estimates, and collision times.
Bisection starts with endpoints a and b whose function values have opposite signs, then repeatedly halves the interval and keeps the half containing the sign change.
The code stops when the remaining interval has width at most 2ε, making its midpoint an estimate within ε; an iteration limit can prevent an excessively long loop.

8:00 Unimodal Minimization and the Cost of Searching in Thirds

Optimization examples include minimizing drug-recovery time, maximizing resource-purchase profit, and choosing radiation intensity to balance cancer killed against other tissue saved.
Golden-section search applies when an interval contains one minimum, with the function decreasing to its left and increasing to its right.
Searching in thirds compares two interior points and removes one third of the interval, but requires two function evaluations per iteration.
Repeated evaluations can be expensive when each requires an experiment or a long computational process.

10:45 Golden-Ratio Reuse in Golden-Section Search

The golden ratio is φ = (1 + √5) / 2, approximately 1.618; Dwork illustrates it with Fibonacci ratios and recursively divided rectangles.
Golden-section search places two candidate points inside [a, b], compares their function values, and discards the region that cannot contain the minimum.
The golden-ratio spacing makes one candidate from the previous iteration reusable, reducing the work to one new function evaluation per iteration.
The algorithm tracks lower and upper bounds, updates the candidate point and its function value, and returns the midpoint of the remaining uncertainty interval.

Transcript excerpt

0:00 Hi, I'm Nicholas Twork, and in this lecture we're going to discuss functions of real numbers. That is, in this lecture we will discuss functions that map the real numbers to the real numbers. A function f is continuous at x naught means that the limit as x approaches x naught of f of x exists. As an example, here are two axes and here's the location x naught. Here is one such function, and this function approaches the same value from the left and the right at x naught. Therefore, the limit as x approaches x naught of f of x exists. Since the function approaches the same value from both sides at x naught, it is continuous at x naught. In fact, this function is continuous everywhere. Here's a different function. Here the function jumps at x naught. Since the function approaches two different values from the left and the right, the

0:47 function is discontinuous at x naught. It is not continuous at x naught. Here's another example, f of x is equal to the sine of 1 over x. Now, here's its graph. It's sine, so it oscillates, but the oscillations increase frequency as you get closer and closer to x equals zero. One can get arbitrarily close to x equals zero and find function values that range between -1 and 1. Therefore, this function is not continuous at x equals zero. A function f is continuous means it is continuous everywhere in its domain. A value x is a root of f means that f of x equals zero. The r level set of f is the pre-image of r under f.

1:36 And the zero level set of f is the set of all values that map to zero. That is, it is the set of all roots of

This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.

Related notes

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Nicholas Dwork.