<jupyter_start><jupyter_text>Exam Rules  1. You can use your own notes and any class materials posted eClass, including Jupyter notebooks and anything else posted or linked to in eClass (however, see 4 below)  2. You cannot use any external internet sources (e.g., Google, Wikipedia, StackExchange, etc)  3. You can use your own books as long as they are paper or PDF  4. You cannot use any sort of computer search functionality (internet or otherwise)  5. You must work alone for this exam  6. You may use any theorems proved in class  7. Your answers do not need to be rigorous proofs, but try to be precise      You must turn in your exam before midnight on Saturday (Oct 9th)  (Even if you start it during the day on Saturday.)  -------------------------------------------  Q1Let $x_0, \ldots, x_n \in [a, b]$, and let $f$ be sufficiently smooth on $[a, b]$ (i.e., $f\in C^{n+1}[a, b]$). Suppose that $\hat{p}(x)$ is a polynomial of degree at most $n$ satisfying $\vert f(x_i) - \hat{p}(x_i)\vert < \delta$ for $i=0,\ldots, n$. Show that $$ \vert f(x) - \hat{p}(x)\vert \leq \frac{\Vert f^{(n+1)} \Vert_{\infty}}{(n+1)!}\prod_{i=0}^n \vert x - x_i \vert + \Lambda \delta $$for all $x\in [a, b]$, in which $\Lambda$ is the Lebesgue constant.  Solution:Let $p(x)$ be the polynomial of degree at most $n$ that interpolates $f$ at $x_i$, $i=0,\ldots n$. We know this polynomial exists and is unique by the existence uniqueness theorem. Since $p(x_i) = f(x_i)$ it follows that $$\vert f(x_i) - \hat{p}(x_i)\vert = \vert f(x_i) - p(x_i) - (\hat{p}(x_i) - p(x_i)) \vert = \vert \hat{p}(x_i) - p(x_i)\vert< \delta. $$From the above inequality, we can use the stability theorem given in lecture to obtain the bound$$\vert \hat{p}(x) - p(x)\vert < \Lambda \delta ,$$for all $x\in [a, b]$.From the interpolation accuracy theorem given in lecture, we have that$$ \vert f(x) - p(x)\vert \leq \frac{\Vert f^{(n+1)} \Vert_{\infty}}{(n+1)!}\prod_{i=0}^n \vert x - x_i \vert,$$for all $x\in [a, b]$.Finally, from the triangle inequality we have$$\vert f(x) - \hat{p}(x)\vert = \vert f(x) + p(x) - (\hat{p}(x) - p(x))\vert < \vert \hat{p}(x) - p(x)\vert + \vert f(x) - p(x)\vert.$$Combining these three inequalities yields the desired result.  Q2Consider the series$$ S_N = \sum_{n=1}^{N} \frac{1}{n}.$$ AShow that the limit $$ \lim_{N\to \infty} S_N = \infty .$$  Solution:It suffices to apply an integral test (which also helps us with part D) since the terms $1/n$ are monotonically decreasing. We can bound the partial sums from below with$$f(N) = \int_{1}^{N}\frac{1}{x}dx < \sum_{n=1}^{N} \frac{1}{n}. $$Since $f(x) = \log(x) \to \infty $ as $x\to \infty$, the series diverges.  BExplain why summing the series in finite precision floating point arithmetic converges after a finite number of terms; i.e.,$$ \sum_{n=1}^{\infty} \frac{1}{{\rm fl}(n)} = L < \infty.$$  Solution:The set of floating point numbers (either 32bit and 64bit) has a finite number of elements. It follows that there is a largest floating point number. Any real number that is larger than the largest floating point number is given the value of `inf` (called overflow). The corresponding value of `1/inf` is considered to be zero. Hence, there exists an $N>0$ such that ${\rm fl}(\frac{1}{{\rm fl}(n)}) = 0$ for all $n > N$. The sequence of partial sums is non decreasing. We must therefore have a finite limit as $n\to \infty$ since $S_n \leq S_N$ for all $n$.  CTry to predict the number of terms $N$ after which the partial sum $S_N$ will cease to change for  1. 32 bit floating point numbers  2. 64 bit floating point numbers  Solution:The question only asks you to **try** to predict the value. I gave full marks for any reasonable guess based on facts about the floating point number system. An allowable answer can be based on the largest floating point number even though this turns out to be a bad guess. Since the true cause of convergence is rounding error (i.e., from ${\rm fl}(S_{n-1} + \frac{1}{n})$) a better guess would be $1/\varepsilon$, where $\varepsilon$ is the rounding unit. The rounding unit is approximately $10^{-8}$ and $10^{-16}$ for `float32` and `float64`, respectively.  DConfirm your prediction from part C numerically. *Hint: This should just require a simple `for` loop and an `if` statement. Use the `float32()` function to compute the sum in 32 bit float (make sure you do this correctly). For float64, you might not want to compute every single term in the sum, unless you are happy to potentially wait a long time.*  Answer:In part C, you might have formulated a bad guess based on an incorrect reason for convergence of the sum. The cause of numerical convergence of the sum is due to rounding error from ${\rm fl}({\rm fl}(S_{n-1}) + {\rm fl}(\frac{1}{{\rm fl}(n)}))$. As discussed in an example during lecture, if we add a very large floating point number $L$ and a much smaller floating point number $s$, we have ${\rm fl}(L + s) = L$. This is due to the finite number of digits in the mantissa, which determines the rounding unit $\varepsilon$.<jupyter_code>## The float32 sum can be computed directly
Sn = float32(0)
for n in arange(1, 10**7):
    y = Sn + float32(1)/float32(n)
    if absolute(Sn - y) == 0:
        break
    Sn = y
print(n)<jupyter_output>2097152<jupyter_text>float64 caseI am not taking off any points if you couldn't think of a way to "short cut" the sum for float64. Since $S_n$ grows like $\log(n)$, we can approximate. Let us assume that $S_n \sim C + \log(n)$, $n\to \infty$, for some constant $C$. We will first approximate the constant**Note: the constant probably does not affect the answer, but we will include it anyway since it is easy to approximate. By the way, $C$ should be Euler's constant $\gamma$.**<jupyter_code>S0 = 0.
for n0 in arange(1, 10**7):
    S0 += 1./n0

## we will restart the sum at a very large number n1
## S0 ~ C + log(n0) =>  C ~ S0 - log(n0)
C = S0 - log(n0)
print(C)
guess = 1/finfo(float64).eps/32
print(guess)
## this should yield an approximation that has around 8 correct digits
n1 = around(guess)
n = n1
for _ in arange(1e8):
    n += 1e7
    Sn = C + log(n) ## approximate
    y = Sn + 1./n
    if absolute(Sn - y) == 0:
        break
    
print(n)
## this should yield the (possibly exact) answer
n2 = n - 1e7
n = n2
for _ in arange(1e7):
    n += 1
    Sn = C + log(n) ## approximate
    y = Sn + 1./n
    if absolute(Sn - y) == 0:
        break
    
print(n)<jupyter_output>281474976710657.0
{'fraction_non_alphanumeric': 0.13627223511214231, 'fraction_numerical': 0.022892498066511988, 'mean_word_length': 3.5793201133144477, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 10, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '97608', 'license': 'Apache-2.0', 'n_tokens_mistral': 2141, 'n_tokens_neox': 2020, 'n_words': 967, 'path': 'Midterm Exam Solutions.ipynb', 'repo_name': 'newby-jay/MATH381-Fall2021-JupyterNotebooks', 'size': '6465'}