Math317Fa26 Lec22 GammaFnNewtonMethod

Overview

Steven Miller connects efficient algorithms with growth estimates and numerical methods: the gamma function extends factorials to a continuous domain, enabling calculus-based estimates such as Stirling’s formula. He then compares bisection with Newton’s method for computing √3 and introduces contraction maps as a general way to find fixed points and solve equations.

Key takeaways

The gamma recurrence Γ(s + 1) = sΓ(s), derived by integration by parts, extends factorials through Γ(n + 1) = n! and makes continuous analysis tools available.
Stirling’s formula, n! ≈ √(2πn)(n/e)ⁿ, follows approximately by turning log(n!) into a sum and estimating it with an integral; the more precise expansion begins with a 1/(12n) correction.
Newton’s iteration xₙ₊₁ = ½(xₙ + 3/xₙ) computes √3 with quadratic convergence: starting at 2, the error reaches about 10⁻⁴ after two updates and can fall to around 10⁻³⁷ after five.
Bisection provides a reliable but slower comparison: each step halves the interval, so 10 steps shrink its length by 2¹⁰, approximately 1,000.
A contraction requires one uniform factor C < 1 across the entire domain; f(x) = x + e⁻ˣ fails this test on [0, ∞) because f′(x) approaches 1.
The mean value theorem makes a uniform derivative bound |f′| ≤ C < 1 a useful sufficient condition for contraction and geometric convergence of fixed-point iteration.

Chapters

0:00 From Factorial Search Spaces to the Gamma Function

A matching problem can have n! possible matchings, while a constructive stable-matching algorithm finds a solution in roughly n² steps.
Steven Miller motivates runtime analysis by contrasting algorithms that solve a problem efficiently with methods that are too slow to be practical.
The gamma function transforms the integer-based factorial into a continuous function, making calculus available for studying factorial growth.

5:29 Integration by Parts Gives the Gamma Recurrence

For Re(s) > 0, the gamma integral is Γ(s) = ∫₀∞ e⁻ˣxˢ⁻¹ dx.
Integration by parts, with u = xˢ and dv = e⁻ˣ dx, yields Γ(s + 1) = sΓ(s); the boundary term vanishes because exponential decay outpaces polynomial growth.
Since Γ(1) = 1, the recurrence gives Γ(n + 1) = n!, connecting the continuous gamma function to integer factorials.

12:00 The Gamma Integrand Peaks at x = n

Writing n! as ∫₀∞ e⁻ˣxⁿ dx, differentiation shows the integrand reaches its maximum at x = n.
The maximum value is e⁻ⁿnⁿ, which captures the main growth scale in Stirling’s formula.
The full estimate is n! ≈ √(2πn)(n/e)ⁿ, with a relative correction beginning with 1/(12n).
The factor √(2π) also appears in the standard normal density, linking factorials, the gamma function, and probability.

18:00 Logarithms and Integrals Estimate Factorial Growth

Taking one logarithm converts the product n! into the sum log(n!) = Σₖ₌₁ⁿ log k.
Approximating that sum by ∫₁ⁿ log t dt gives log(n!) ≈ n log n − n + 1.
Exponentiating produces n! ≈ e nⁿe⁻ⁿ, a rough estimate that captures the leading scale of Stirling’s formula.
A semi-log plot makes the rapid factorial growth easier to inspect; Stirling’s formula predicts log(n!) grows mainly like n log n.

26:00 Newton’s Method Quickly Computes the Square Root of 3

For √3, Newton’s iteration is xₙ₊₁ = ½(xₙ + 3/xₙ), and √3 is a fixed point of this update.
Starting from x₀ = 2 gives x₁ = 7/4 and x₂ = 97/56, with the second iterate already within about 10⁻⁴ of √3.
After several iterations, the error drops from roughly 10⁻⁹ to 10⁻¹⁸ and then 10⁻³⁷, as each step approximately doubles the number of correct decimal digits.
Bisection on [1, 2] halves the uncertainty each step; about 10 iterations reduce the interval by 2¹⁰, or roughly a factor of 1,000.

33:00 Using Algebra to Examine Newton Iteration Errors

Steven Miller demonstrates using AI to simplify xₙ₊₁ − xₙ for the √3 iteration, a task that mainly involves substitution and algebra.
Because the target satisfies (√3)² = 3, the squared error 3 − xₙ² is a convenient quantity to study without differentiating a square root.
The iteration’s rapid improvement is tied to behavior near its fixed point, motivating a broader discussion of fixed-point methods.

37:12 The Contraction Mapping Theorem Guarantees a Fixed Point

A contraction on a set S has a single constant C < 1 such that |f(x) − f(y)| ≤ C|x − y| for every x and y in S.
The same uniform C must work throughout the set; allowing the factor to approach 1 at different points is not enough.
For a contraction mapping a suitable complete set into itself, repeated iteration from an initial value converges to its unique fixed point.
Fixed-point reformulation provides a general route to solving equations by iterating a function.

40:50 Why x + e⁻ˣ Is Not a Contraction on [0, ∞)

For f(x) = x + e⁻ˣ, the derivative is f′(x) = 1 − e⁻ˣ, which is less than 1 but approaches 1 as x grows.
On the unbounded interval [0, ∞), no single constant C < 1 bounds the contraction factor everywhere, so this function is not a contraction there.
The mean value theorem gives |f(x) − f(y)| = |f′(c)||x − y| for some c between x and y.
A uniform derivative bound |f′(x)| ≤ C < 1 on the interval is a practical sufficient test for contraction.

46:07 Repeated Contraction Bounds Lead Toward Convergence

If xₙ₊₁ = f(xₙ) and f contracts by C, then successive differences shrink geometrically: |xₙ₊₁ − xₙ| ≤ Cⁿ|x₁ − x₀|.
Applying the contraction inequality repeatedly produces factors C, C², and C³, making later iterates progressively closer.
A real analysis proof uses these geometric bounds and a telescoping-sum argument to establish convergence to a fixed point.

Transcript excerpt

0:00 Okay, so welcome to math 317 operations research. What I want to do today is talk a little bit about the factorial function which showed up yesterday and talk a little bit about explicit algorithms in terms of how quickly they converge. And so we saw yesterday for the matching problem, not only does it tell us that a stable matching exists, it constructively tells us how to find it and it does it in a reasonable amount of time. There were n factorial possible ways to match n men with n women. And we're finding things on the order of n squared steps. Amazing in terms of just how many things to check, how long it takes versus how bad n factorial is. So there's a lot of times in life where you have these numbers that they give

0:48 you that make no sense because we don't understand the units. Uh did I give you the example of the energetic radiation? This is one of my favorites. They were trying to explain how powerful this is cosmic radiation. And they said, "You imagine you're going to the dentist. If they're taking x-rays, what do they do?" >> They give you radiation. >> Right, what do they do to when they're giving you the radiation? >> Cover you up. >> They cover you up and then they get out of the room. Now, they're being exposed to more often than you, but so it's understandable that they get out of the room, but they get out of the room and they give you that little apron. The quote was, "This radiation is so energetic, if you had a lead apron running from the Earth, not the Earth, the Sun to Pluto, that wouldn't be enough to stop it." That helps me internalize just how

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

In this course

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, Steven Miller.