What are the main goals of Numerical Analysis? Besides keeping track of computational errors,
possibly the main goal of NA is finding algorithms (as stable, fast and lean as possible!) to solve continuous mathematical problems
(see this article by L. Trefethen).
Week 1, Lecture 2, August 25
Topics
Representing real numbers on a computer: scientific notation and floating point systems
(if you are brave enough, read "What Every Computer Scientist Should Know About Floating-Point Arithmetic"
by David Goldberg).
A floating point system consists in representing numbers in scientific notation (in some base - usually base 2 for nowadays computers)
while keeping only some fixed number of digits for both the number itself and its exponent.
See notes, page 1, for a toy decimal floating point system with three digits.
It is much easier to notice the quirks of floating point systems in such a toy one.
In a floating point system, there are numbers $x$ such that $1+x=1$! For instance, in double precision, $1+10^{-18}=1$.
Evaluation of $3\times(4/3-1)-1$ in single and double precision. This calculation does not give zero but rather $-\epsilon_m$, where
$\epsilon_m$ is the smallest number $x$ such that, in the floating point system you are using, $1+x\neq1$.
Using MATLAB as a calculator (see also this video).
Week 2, Lecture 6, September 3
Topics
Why $3\times 1/3$ gives precisely 1 in both single and double precision (and why it should not) - see notes, page 4.
Use https://octave-online.net/ as a calculator to evaluate the expression p^2-2q^2 for p=665857 and q=470832.
Recall that MATLAB uses by default double precision but you can force it to use single precision by writing
p=single(665857)
q=single(470832)
Evaluate the expression first with double precision and then with single precision and give me your explanation for the results you get.
Hint: remember to give the command 'format long' at the beginning and recall that single precision numbers have from 6 to 9 significant digits while double precision ones from 15 to 17.
Use https://octave-online.net/ as a calculator to evaluate "2.6+0.6" in two ways: the first by summing 0.6 to 2.6; the first by summing 0.2 three times to 2.6. Do you get the same result?
If not, provide some explanation of why they are not.
Hint: remember to give the command 'format long' at the beginning and use the facts that, in double precision, 0.1 is actually represented by 0.10000000000000001 while 0.6
is represented by 0.59999999999999998.
Use the command 'realmax' in https://octave-online.net/ to find the largest real number representable in double precision. Then, suppose you need to evaluate the length L of the vector
with a=1.5x10^300 and b=2.1x10^300. What do you get if you try to use naively the formula L=sqrt(a^2+b^2)? Why? Find a formula mathematically equivalent to sqrt(a^b+b^2) that MATLAB
is able to evaluate correctly.
Hint: assume a=b and see how the norm fomula simplifies in this case. Then find what one can do when a is not equal to b.
Use our 3-digits decimal system to evaluate the two mathematically equivalent expressions
1-sqrt(1-a)
and
a/(1+sqrt(1-a))
for a=0.01. Evaluate with MATLAB the first three exact digits of the result and use this number to evaluate the absolute and relative errors of the results you get in the 3-digits
system with the two expressions above. Which one of the two formulae works better? Why?
Write explicitly the Taylor formula that you find here for the case $n=3$. Rewrite the same formula
after putting $h=x-x_0$.
Modify the code at this page to evaluate numerically the derivative at $x_0=2$ of the exponential function $e^x$
(whose name in MATLAB is exp). Do we find the same kind of behavior as for the sine function or not?
Use our implementation of the bisection method to find a solution of the equation $3x + \sin x - e^x=0$
with an accuracy of $10^{-5}$ (namely so that the error is not larger than $10^{-5}$).
Find the first three digits of $\sqrt[3]{2}$ using our implementation of the bisection method.
Determine the number of iterations that grants to find a root of $x^3+4x^2-10$ with an accuracy of $10^{-5}$ (namely so that the error is not larger than $10^{-5}$) using $a=0$ and $b=2$.
Find all exact roots of $p$. (Hint: $p$ is divisible by $(3x-5)$).
Plot $p$ in the interval $[1.43,1.71]$. (Hint: you can use x=linspace(1.43,1.71) together with the plot function).
What do you get via Newton's method with $x_0=1.5$? (Hint: replace the function and the initial point in our Newton code).
What do you get via the secant method with $x_0=1$ and $x_1=2$? (Hint: replace the function and the initial points in our secant code)
What do you get via the bisection method applied to the interval $[1,2]$? (Hint: replace the function and the interval endpoints in our bisection code)
How many solutions does $\tan x=x$ have? Find the smallest three positive roots. (Hint: plot the function and use Newton's method with suitable initial points).
Use Newton's Method to estimate the value of $\pi$ to ten decimal places. (Hint: choose any trigonometric equation having $\pi$ as solution and choose an appropriate initial point).
Week 6, Lecture 14, October 4
Topics
MATLAB's fzero function.
Recap of MATLAB syntax.
Discussion about the implementation of the secant method.
Week 6, Lecture 15, October 6
Topics
Written together some code to generate Fibonacci numbers $\{f_n\}$ and verified numerically that $f_n\simeq c\cdot\phi^n$,
where $c$ is some constant and $\phi=(1+\sqrt{5})/2$ is the golden ratio.
Week 6, Lecture 16, October 8
Topics
Example: using the secant method to evaluate $\sqrt[3]{3}$.
Linear algebra recap: vector spaces and linear functions.
Performing by hand the Gaussian Elimination algorithm and evaluating the determinant of the upper triangular matrix you will end up with.
Modify any of the codes in Section 4.2.3 to find the LU decomposition of the $5\times5$ matrix
$$
\begin{pmatrix}3&2&1&0&-1\cr 0&-4&2&3&0\cr 10&6&-1&1&8\cr 5&1&7&1&-3\cr 1&1&1&1&1\cr\end{pmatrix}
$$
Use the Gaussian elimination algorithm in the floating point system $D_3$, namely keep three digits to represent numbers at every step of the algorithm,
to solve the system
$$
\begin{pmatrix}0.780&0.563\cr 0.913&0.659\cr \end{pmatrix} \begin{pmatrix}x\cr y\end{pmatrix} = \begin{pmatrix}0.217\cr0.254\end{pmatrix}.
$$
Then solve the equation exactly and compare the exact and numerical solutions.
INSTRUCTIONS: for the problems that entail the use of some code, send me the code you use
(in text format, not in picture format) together with your solutions. Be verbose and explain
what you are doing -- writing only the final solutions will not grant you full credit.
You can either write your solutions in a digital format or write them in paper and send me a picture.
Remember though to send me the code in text format.
Write MATLAB code to verify the presence of the round-off error in the formula for the discrete second
derivative we used in Section 4.4
as we did for the first derivative in
Section 2.2.
As test function use $f(x)=\log x$. Find by trial and error the slope with which the error
is initally going to zero and find out at which order of magnitude for $h$ the error starts going back up.
If you prefer not to write the code from zero, feel free to just modify our code for the first derivative in
Section 2.2
Find the first 10 digits of any solution of the equation $8+\frac{1}{x}=\ln x$ with any method you like.
Explain why you believe that the first 10 digits are correct.
Consider the function $f(x)=\frac{1}{1+x}-\frac{1}{1-x}$.
Explain why, when evaluated in a floating point system, this expression is subject to a large increase of its relative error
(catastrophic cancelation) when $x$ is a very small number.
Find a formula that is equivalent to the one above in exact mathematics and that does not suffer of catastrophic
cancelation.
Set up (do not attempt to solve it!) a linear system to solve numerically the ODE
$$x''(t)-x'(t)+4x(t)=t-1,\;\;x\in[0,1],\;\;x(0)=x(1)=0,$$
splitting the interval $[0,1]$ into four equal segments. Choose and use your favorite approximation for the discretize first and
second derivatives.
Explain why, if $\det A\neq0$, then the only solution of the equation $Ax=0$ is $x=0$.
Find "by hand" the LU-decomposition of $$A=\begin{pmatrix}1&2\cr 3&4\cr\end{pmatrix}$$ and verify that $A=LU$.
Write on paper the Jacobi and the Gauss-Seidel methods to solve the system
$$\begin{pmatrix}1&2\cr 3&4\cr\end{pmatrix}\begin{pmatrix}x\cr y\cr\end{pmatrix}=\begin{pmatrix}3\cr 7\cr\end{pmatrix}.$$
Then choose an initial vector and for each method do the first two steps.
