<jupyter_start><jupyter_text>Q1We showed that the finite difference formula,$$ \frac{f(x + h) - f(x - h)}{2h} ,\quad h>0,$$is a second order accurate method for approximating the derivative of a smooth and continuous function at a point $x$. Show that this method is **exact** for **any** second degree polynomial.---------------------------------------------------- SolutionLet $f(x) = ax^2 + bx + c$. We have that $f'(x) = 2ax + b$. Applying the above formula to $f$ yields\begin{align*}&\frac{1}{2h}\left[a(x+h)^2 + b(x+h) + c -  \left( a(x-h)^2 + b(x-h) + c \right)  \right] \\&= \frac{1}{2h}\left[a(x+h)^2 + b(x+h) - a(x-h)^2 - b(x-h) \right] \\&= \frac{1}{2h}\left[a(x^2 + 2xh + h^2) + b(x + h) -  a(x^2 - 2xh + h^2) - b(x-h)  \right] \\&= \frac{1}{2h}\left[a(x^2 + 2xh + h^2) - a(x^2 - 2xh + h^2) + b(x + h) - b(x-h)  \right] \\&= \frac{1}{2h}\left[4axh  + 2b h  \right] \\&= 2ax  + b.\end{align*}  Q2The Lagrange interpolating polynomial is given by$$p(x) = \sum_{j=0}^n\left[ y_j \prod_{\substack{i=0\\\\i\neq j}}^n\frac{(x-x_i)}{(x_j-x_i)}  \right].$$**Note: this problem should be done with "pencil and paper" and not Python.** AUsing the above formula, compute the Lagrange interpolating polynomial $p(x)$ for a function $f(x)$ on the interval $[-h, h]$ with three equally spaced node points (i.e., at $x_0=-h$, $x_1=0$, and $x_2=h$). ---------------------------------------------------- SolutionFrom the Lagrange polynomial formula we have\begin{align*}p(x) &= \frac{f(-h)}{2h^2}x(x-h) \\&\quad + \frac{f(0)}{-h^2} (x+h)(x-h)\\&\quad+ \frac{f(h)}{2h^2}x(x+h).\end{align*}  B Compute the exact derivative $p'(x)$ and evaluate $p'(0)$. ---------------------------------------------------- SolutionDifferentiating and evaluating at $x=0$ yields$$p'(0) = \frac{f(-h)}{2h^2}(-h) + \frac{f(0)}{-h^2}( -h + h) + \frac{f(h)}{2h^2}h = \frac{f(h) - f(-h)}{2h}.$$  CShow that the resulting expression is identical to the finite difference formula from Q1 with $x=0$. ---------------------------------------------------- SolutionThe finite difference formula at $x = 0$ is $\frac{f(h) - f(-h)}{2h}$, which is identical to the expression derived in part B.  Extra Credit [5 pts]:Show that the formula holds for any $x$ and not just $x=0$. Note that you cannot get more than 40 points total for this exam.------------------------------------- SolutionLet $g(y) = f(y + x)$. The derivation of the finite difference formula holds for $g'(0)$. Since $g'(0) = f'(x)$, the formula also holds for $f'(x)$ for any valid $x$.  Q3The Lagrange interpolating polynomial is given by$$p(x) = \sum_{j=0}^n\left[ y_j \prod_{\substack{i=0\\\\i\neq j}}^n\frac{(x-x_i)}{(x_j-x_i)}  \right].$$ AUsing the idea established in Q2, use the Lagrange interpolating polynomial and the values $x_j = jh$, $j=0,1,2,3$, to derive a third order accurate finite difference formula for the derivative of $f(x)$ at the point $x=0$.------------------------------------------------------------------- SolutionFrom the Lagrange polynomial formula we have\begin{align*}p(x) &= \frac{f(0)}{-6h^3}(x-h)(x-2h)(x-3h) \\&\quad + \frac{f(h)}{2h^3} x(x-2h)(x-3h)\\&\quad+ \frac{f(2h)}{-2h^3}x(x-h)(x-3h) \\&\quad+ \frac{f(3h)}{6h^3}x(x-h)(x-2h)\end{align*}Differentiating the above and evaluating at $x=0$ yields\begin{align*}p'(0) &= \frac{f(0)}{-6h^3}[(-2h)(-3h) + (-h)(-3h) + (-h)(-2h)] \\&\quad + \frac{f(h)}{2h^3} 6h^2 + \frac{f(2h)}{-2h^3}3h^2 + \frac{f(3h)}{6h^3}2h^2 \\&= \frac{1}{h}\left\{- \frac{11}{6}f(0)  + 3f(h) - \frac{3}{2}f(2h) + \frac{1}{3}f(3h)\right\}\end{align*}  Solution using automatic derivatives for Lagrange polynomials (Week 5)We are using uniform nodes $x_j = jh$. From the homework (Week 4), the general formula for the weights for uniform nodes is$$ w_j  = (-1)^j \binom{n}{j}.$$From the Week 5 notes we have that$$ p'(x_i) = \sum_{j=0}^n d_{ij} f(x_j).$$We want the derivative at $x_0 = 0$, \begin{align*}p'(0) = \sum_{j=0}^n d_{0j} f(x_j) = - f(0) \sum_{k=1}^n d_{0k} + \sum_{j=1}^n d_{0j}f(jh).\end{align*}The off-diagonal elements of the first row of the derivative matrix are\begin{align*} d_{0j} &= \frac{w_j}{w_0(x_0 - x_j)} = -\frac{w_j}{w_0jh} = -\frac{1}{h} \frac{(-1)^j}{j}\binom{n}{j}.\end{align*}Bringing these together we have\begin{align*}p'(0) &= \frac{1}{h}\left\{ f(0) \sum_{k=1}^n \frac{(-1)^k}{k}\binom{n}{k} - \sum_{j=1}^n \frac{(-1)^j}{j}\binom{n}{j}f(jh)\right\}.\end{align*}  For $n=3$ we have \begin{align*}p'(0) &= \frac{1}{h}\left\{- \left[3 - \frac{3}{2} + \frac{1}{3}\right]f(0)  + 3f(h) - \frac{3}{2}f(2h) + \frac{1}{3}f(3h)\right\} \\ &= \frac{1}{h}\left\{- \frac{11}{6}f(0)  + 3f(h) - \frac{3}{2}f(2h) + \frac{1}{3}f(3h)\right\}.\end{align*}  BBy Taylor expanding the function $f(x)$ around $x=0$, derive the leading-order approximation of the discretization error for your method from part A [it should be $O(h^3)$].------------------------------------------------------------------- SolutionThe Taylor expansion around zero is $$ f(jh) = \sum_{i=0}^{\infty} \frac{(jh)^i}{i!}f^{(i)}(0).$$The discretization error is given by\begin{align*} &\frac{1}{h}\left\{- \frac{11}{6}f(0)  + 3f(h) - \frac{3}{2}f(2h) + \frac{1}{3}f(3h)\right\} - f'(0)\\& = \frac{1}{6h}\left(- 11f(0)  + 18f(h) - 9f(2h) + 2f(3h)\right) - f'(0)\end{align*}After substituting the expansion into the discretization error, we need to show that the first four terms ($i=0,1,2,3$) cancel out. The next term (the fifth term) will be the discretization error.Note that all of the $f(jh)$ terms appear linearly, so we can consider them one at a time.Substituting the first term $f(jh) = f(0)$ yields\begin{align*} \frac{1}{6h}\left(- 11f(0)  + 18f(0) - 9f(0) + 2f(0)\right) - f'(0)= \frac{f(0)}{6h}\left(- 11  + 18 - 9 + 2 \right) = -f'(0)\end{align*}Note that after accounting for the first term of the Taylor series, the $f(0)$ term cancels out of the discretization error for subsequent terms.Substituting the second term $f(jh) = jhf'(0)$ yields$$ \frac{1}{6h}\left(18 hf'(0) - 9(2h)f'(0) + 2(3h)f'(0)\right) - f'(0)= \frac{hf'(0)}{6h}\left(18  - 18 + 6\right) - f'(0) = 0$$Note that after accounting for the second term of the Taylor series, the $f'(0)$ term cancels out of the error for subsequent terms.Substituting the third term $f(jh) = \frac{(jh)^2}{2}f''(0)$ yields$$ \frac{1}{6h}\left(18\frac{h^2}{2}f''(0) - 9\frac{4h^2}{2}f''(0) + 2\frac{9h^2}{2}f''(0)\right)= \frac{h^2f''(0)}{12h}\left(18 - 9(4) + 2(9)\right) = 0.$$Substituting the fourth term $f(jh) = \frac{(jh)^3}{6}f'''(0)$ yields$$ \frac{1}{6h}\left(18\frac{h^3}{6}f'''(0) - 9\frac{8h^3}{6}f'''(0) + 2\frac{27h^3}{6}f'''(0)\right)= \frac{h^3 f'''(0)}{36h}\left(18 - 9(8) + 2(27)\right) = 0$$The final term, which is nonzero and $O(h^3)$, will be the discretization error$$\frac{1}{6h}\left(18\frac{h^4}{24}f^{(4)}(0) - 9\frac{2^4 h^4}{24}f^{(4)}(0) + 2\frac{3^4 h^4}{24}f^{(4)}(0)\right)= \frac{h^4f^{(4)}(0)}{6(24)h}\left(18 - 9(2^4) + 2(3^4)\right)= \frac{h^3f^{(4)}(0)}{4}.$$  CImplement your method in Python and apply it to the function $$f(x) = \sin(x + 1.2)$$ to compute the derivative at the point $x_0 = 0$ for a range of values of $10^{-16}\leq h \leq 10^{-1}$. Plot the resulting empirical error and show that the discretization error is $O(h^3)$ by comparing the empirical error to the leading-order approximation of the discretization error derived in part B. This should be done using a `loglog` plot.  ------------------------------------------------------------------- SolutionSee code and figures below<jupyter_code>def f(x):
    return sin(x0 + x)
x0 = 1.2
f0 = sin(x0)
fp = cos(x0)
fpp = -sin(x0)
fppp = -cos(x0)
fpppp = sin(x0)
i = linspace(-15, 0, 40)
h = 10.0**i

#### The 3rd orer accurate FD formula
fp_3rd_order = (-11./6.*f0 + 3.*f(h) - 3./2.*f(2*h) + 1./3.*f(3*h))/h
#### The empirical error
err3 = absolute(fp - fp_3rd_order)
#### The formula for the discretization error
d3_err = h**3/4*absolute(fpppp)


### I am including the other finite difference approximations we studied for comparison
### They are not required for the question
fp_approx = (sin(x0 + h) - f0)/h ## from Week 2 notebook example
fp_center_diff_approx = (sin(x0 + h) - sin(x0 - h))/(2*h) ## from homework 2
err = absolute(fp - fp_approx) ## from Week 2 notebook example
err2 = absolute(fp - fp_center_diff_approx) ## from homework 2
d_err = h/2*absolute(fpp)  ## from Week 2 notebook example
d2_err = h**2/6*absolute(fppp) ## from homework 2


figure(1, [8, 5])
loglog(h, err, '-*')
loglog(h, err2, '-*')
loglog(h, err3, '-*')
loglog(h, d_err, 'r-', label=r'$\frac{h}{2}\vert f^{\prime\prime}(x) \vert $')
loglog(h, d2_err, label=r'$\frac{h^2}{6}\vert f^{\prime\prime\prime}(x) \vert $')
loglog(h, d3_err, label=r'$\frac{h^3}{4}\vert f^{(4)}(x) \vert $')
xlabel('h', fontsize=20)
ylabel('absolute error', fontsize=20)
ylim(1e-16, 1)
legend(fontsize=24);<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.2723158728362937, 'fraction_numerical': 0.051928951238827924, 'mean_word_length': 3.4489179667840966, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 6, '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': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '553757', 'license': 'Apache-2.0', 'n_tokens_mistral': 3630, 'n_tokens_neox': 3437, 'n_words': 909, 'path': 'Last Year - Midterm Exam - 2020 - Solutions.ipynb', 'repo_name': 'newby-jay/MATH381-Fall2021-JupyterNotebooks', 'size': '8839'}