CSE1729 – Introduction to Programming
June 15, 2021
Problem Set 4
1. Abstracting the summation of a series
Consider the harmonic numbers 𝐻𝑛 = 1 + 1 + 1 + ··· + 1. Last week you wrote a recursive Scheme
123 𝑛
function (named harmonic) which, given a number 𝑛, computes 𝐻𝑛. Revise your harmonic function,
keeping the name (harmonic n), to take advantage of the sum function seen in the textbook (Section 1.3.1) and shown below:
Of course, your new and improved definition of harmonic should not be recursive itself and should rely on sum to do the hard work.
2. Abstracting the product of a series
(a) The function sum in Question 1 is an abstraction of the sigma notation for summation:
𝑏
𝑓 (𝑛) = 𝑓 (𝑎) + · · · + 𝑓 (𝑏) 𝑛=𝑎
Write a function (product term a next b) that abstracts the pi notation for the product of a series. You should name your function(product term a next b).
𝑏
𝑓 (𝑛) = 𝑓 (𝑎) × · · · × 𝑓 (𝑏) 𝑛=𝑎
(b) In mathematics, Wallis’ product for 𝜋, documented in 1655 by John Wallis, states that
(define (sum term a next b) (if (> a b)
0
(+ (term a)
(sum term (next a) next b))))
𝜋 ∞ 2 𝑛 2 𝑛 2 2 4 4 6 6 8 8
= · =··········
2 𝑛=1 2𝑛−1 2𝑛+1 1 3 3 5 5 7 7 9
Use your one of your product functions to define an function (wallis-pi n) that returns an approximation of 𝜋 using the first n terms of the infinite product above. You will need to define appropriate functions for term and next.
3. For two functions 𝑓 and 𝑔 and an integer 𝑛 ≥ 0 we are interested in the sum of fractions of the form:
𝑓 (−𝑛) 𝑓 (𝑛) +···+ .
𝑔(−𝑛) 𝑔(𝑛)
(Note that this sum has 2𝑛 + 1 terms in it, as it evaluates the fraction 𝑓 (𝑥)/𝑔(𝑥) at all points between −𝑛 and 𝑛.) Note that a little care is required here, because the quantity is not even defined if 𝑔(𝑘) = 0 for one of the 𝑘 ∈ {−𝑛, . . . , 𝑛}. To work around this issue, we define
𝑅( 𝑓 , 𝑔; 𝑛) = 𝑞(−𝑛) + · · · + 𝑞(𝑛) 1
where
0 if 𝑔(𝑘) = 0, and
𝑞(𝑘) = 𝑓 (𝑘) 𝑔(𝑘)
otherwise.
WriteaSchemeprogram,calledfrac-sumsothat(frac-sum f g n)returnsthevalue𝑅(𝑓,𝑔;𝑛)as defined above.
4. Recallthedefinitionofthederivativeofafunctionfromcalculus(youwillnotneedtoknowanycalculus to solve this problem):
′ 𝑓(𝑥+h)− 𝑓(𝑥) 𝑓 (𝑥) = lim
h→0 h
By choosing very small values for h in the above equation, we can get a good approximation of 𝑓 ′(𝑥).
(a) Write a function (call it der for derivative) in Scheme that takes a function 𝑓 and a value for h as formal parameters and returns the function 𝑔 defined by the rule
𝑔(𝑥) =
𝑓(𝑥+h)− 𝑓(𝑥) h
.
As mentioned above, for small h, 𝑔 is a good approximation for the derivative of 𝑓 .
Important note: Your function should take a function and a number as arguments (for example (der f h) where f is a function and h is a number) and return a function.
(b) Now take it a step further and write a function which takes three formal parameters 𝑓 , 𝑛 and h and returnsanapproximationofthe𝑛𝑡hderivativeof𝑓.Callyourfunctionder-n;then(der-n f n h) is an example call to the function. Make use of the derivative function you just wrote. (Specifically, you wish to return the function obtained by applying der to your function 𝑛 times.)
5. Newton’s Method is an iterative method for finding successively better approximations to the roots (that is, the zeroes) of a real-valued function. To be more precise, given a function 𝑓 , Newton’s Method is an approach to find a value 𝑥 for which 𝑓 (𝑥) ≈ 0. Newton’s Method requires an initial guess for the root (𝑥0) and determines a sequence of values 𝑥1, 𝑥2, . . . defined by the recursive rule:
𝑓 (𝑥𝑛)
For many functions of interest, these “iterates” converge very quickly to a root.
For example, consider the polynomial 𝑝(𝑥) = 𝑥2 − 𝑥 − 1. It turns out that the positive root of 𝑝 is the number 1.618… that you computed in many ways on the last problem set (the golden ratio). Let’s see Newton’s method in action. It turns out that the derivative of 𝑝 is the polynomial 𝑝′(𝑥) = 2𝑥 − 1. (You don’t need to know how to determine the explicit derivative of functions for this problem—you’ll be using instead the code you generated in the last problem.) Starting with the guess 𝑥0 = 2, we may run Newton’s method forward to find that:
𝑥0 = 2
𝑥1=𝑥0− 𝑝(𝑥0) =2− 𝑝(2) =5=1.666…
𝑥2=𝑥1− 𝑝(𝑥1) =5− 𝑝(5/3) =113 =1.61904…
…
𝑓 (𝑥𝑛) 𝑥𝑛+1=𝑥𝑛− ′ .
𝑝′(𝑥0) 𝑝′(2) 3
𝑝′(𝑥1) 3
𝑝′(5/3) 21
2
Write a Scheme function that implements Newton’s Method–call it newton. Your function should accept three formal parameters, a function 𝑓 , an initial guess for the root 𝑥0 and the number of iterations to run, 𝑛. You can make use of the derivative function from the previous problem (with h set to .01).
Specifically, the call (newton f x n) should return the 𝑛th iterate, as defined above, of Newton’s method. (Thus (newton f x 0) should return 𝑥.)
To test your implementation, you can try the following in DrRacket.
(a) Use your implementation can find the root of the function 𝑓 (𝑥) = 2𝑥2 − 1. (start with an initial guess of 4).
(b) Use your solution to find a good approximation to the golden ratio by working with the polynomial 𝑔(𝑥) = 𝑥2 − 𝑥 − 1 (start with the guess 2).
6. SICP, Problem 1.29 (Simpson’s rule). Recall that the integral of a function 𝑓 between 𝑎 and 𝑏 (with 𝑎 < 𝑏) is the area underneath the function on the interval [𝑎, 𝑏]. See Figure 1. Simpson’s rule, described in your book, is a method for approximating this value.
To begin with, define a function (sum-term term a b) that takes a function term and two integers 𝑎 and 𝑏 as arguments and returns the sum term(𝑎) + term(𝑎 + 1) + · · · + term(𝑏). Use this in your solution by defining a function that computes the Simpson’s rule terms and passing this to sum-term.
Once sum-term is defined, as above, use this to construct a function simpson-integrate so that (simpson-integrate f a b n)
returns the estimate to the integral of the function 𝑓 , on the interval [𝑎, 𝑏] with 𝑛 samples, according to Simpson’s rule. Recall that Simpson’s rule is simply:
∫𝑏 Δ𝑥 𝑓(𝑥)𝑑𝑥=
·(𝑓(𝑥0)+4· 𝑓(𝑥1)+2· 𝑓(𝑥2)+4· 𝑓(𝑥3)+2· 𝑓(𝑥4)+...+4· 𝑓(𝑥𝑛−1)+ 𝑓(𝑥𝑛)) where Δ𝑥 = 𝑏−𝑎 and 𝑥𝑖 = 𝑎 + 𝑖 · Δ𝑥.
𝑛
Figure 1: The integral of 𝑓 from 𝑎 to 𝑏 is the area of the shaded region above.
To check your solution, you might try integrating the functions 𝑓1(𝑥) = 𝑥, 𝑓2(𝑥) = 𝑥2, and 𝑓4(𝑥) = 𝑥4 on the interval [0, 1] (so 𝑎 = 0 and 𝑏 = 1). You should find that the integral of 𝑓1 is 1/2 (the area of the triangle), the integral of 𝑓2 is 1/3, and the integral of 𝑓4 is 1/5.
𝑎
3
3