2017 Numerical Analysis Final Exam  
Numerical Analysis
Final Examination
Friday December 15, 2017
18:00 — 21:00

Question #1
Knowing that $$ |\epsilon_{n+1}|_{\rm Newton}=\left|\frac{1}{2} \frac{f^{\prime\prime}(r)}{f'(r)} \right| |\epsilon_n|^2 $$ and $$ |\epsilon_{n+1}|_{\rm secant}=\left|\frac{1}{2} \frac{f^{\prime\prime}(r)}{f'(r)} \right|^{1/1.618} |\epsilon_n|^{1.618} $$ Prove that $$ \frac{|\epsilon_n|_{\rm Newton}}{|\epsilon_n|_{\rm secant}}=\left( \left|\frac{1}{2} \frac{f^{\prime\prime}(r)}{f'(r)} \right| |\epsilon_0|\right)^{\left(2^n-1.618^n \right)} $$ Note: the latter should be proven fully without skipping steps or making an assumption/simplification.
Question #2
Using a second-order Runge-Kutta method, solve $q$ at $t=1$ for the RC circuit equation $$ R \frac{dq}{dt}+\frac{q}{C}=0 $$ with $RC=3$, with the initial condition being $q_0=2$, with $\Delta t=0.5$, and with the constraint $a=0.5$. Do so in two different ways:
(a)  By hand
(b)  With a C code that starts as follows:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <assert.h>

#define dt 0.5
#define tmax 1.0

double f(
Note: your algorithm should make use of the defined dt and tmax and work for any value of dt or tmax.
Question #3
Consider a real number stored with 5 bytes. Bit #1 is reserved for the sign, while bits #2 to #10 are reserved for the biased exponent, and bits #11 to #40 are related to the significand. Do the following:
(a)  Find the minimum and maximum possible exponent $p$
(b)  Find the smallest possible positive number
(c)  Find the largest possible number
(d)  Find the smallest possible positive subnormal number
Question #4
Consider the following data points:
It is given that at $x=1$, $f^{\prime\prime\prime}=0$. Using a cubic spline, find the value of $f(x)$ at $x=3$. Derive proper boundary conditions and perform basic verifications to ensure that your answer is correct.
Question #5
Consider the system of equations $AX=B$ with $A$ equal to: $$ A=\left[ \begin{array}{cccc} -2 & 0 & 1 &1 \\ 2 & 1 & 0 &0 \\ 0 & 1 & 1 &2 \\ 0 & 0 & 2 &1 \\ \end{array} \right] $$ and $B$ equal to: $$ B=\left[ \begin{array}{c} -1 \\ -7 \\ 3\\ -6 \end{array} \right] $$ Using partial pivoting only when the pivot is zero, find the lower and upper triangular matrices associated with matrix $A$. Outline all the steps needed to obtain the matrix $L$, the matrix $U$, and the permutation matrices. Also, indicate clearly how $A$ can be written as a function of $L$, $U$, and the permutation matrices.
Question #6
You wish to create a new numerical integration method. To do so, you come up with the idea of evaluating the integral $I_i$ by fitting a 2nd degree polynomial of the form $$ P_i(x)=a_i + b_i(x-x_i) + c_i (x-x_i)^2 $$ through 3 data points within the $i$th interval. For this purpose, do the following:
(a)  Express the polynomial coefficients $a_i$, $b_i$, and $c_i$ as a function of the data points $(x_i,~f_i)$, $(x_{i+1/2},~f_{i+1/2})$, $(x_{i+1},~f_{i+1})$.
(b)  Using the polynomial coefficients derived in (a), find an expression for $I_i$ over the interval $x_i\le x \le x_{i+1}$ and simplify as much as possible.
The 2nd order Runge-Kutta scheme can be expressed as $$ k_1 = \Delta t f(t_n,~ \phi_n) \\ k_2 = \Delta t f(t_n+\alpha \Delta t, ~ \phi_n + \beta k_1)\\ \phi_{n+1}=\phi_n + a k_1 + b k_2 $$ with the constraints $$ a+b=1\\ b\alpha=\frac{1}{2}\\ b\beta=\frac{1}{2} $$ A third order spline can be expressed as: $$ f_i(x)=a_i(x-x_i)^3 + b_i(x-x_i)^2 + c_i(x-x_i)+d_i $$ $$ d_i=y_i $$ $$ a_i=(b_{i+1}-b_i)/(3\Delta x_i) ~~\textrm{for}~1\le i \le N-1 $$ $$ c_i = \frac{\Delta y_i}{\Delta x_i} - b_i \Delta x_i - \left( \frac{b_{i+1}-b_i}{3}\right)\Delta x_i ~~\textrm{for}~1\le i \le N-1 $$ $$ \Delta x_{i-1} b_{i-1} + 2 \left(\Delta x_i + \Delta x_{i-1} \right) b_i + \Delta x_i b_{i+1} = 3 \left(\frac{\Delta y_i}{\Delta x_i} - \frac{\Delta y_{i-1}}{\Delta x_{i-1}}\right)~~\textrm{for}~2\le i \le N-1 $$
Make PDF