Possible Problems for Exams

Chapter ONE

1. Construct the floating point system where the numbers
   $$1000,\frac{1}{2}, \frac{1}{3},\frac{1}{4},\frac{1/5},\frac{1/6},\frac{1}{2048}$$
   may be exactly representable.
2. Consider the floating point system with $N=5$ digits with base $\beta=2$ and lower and upper values of exponents being $U=5$ and $L=-5$. Subnormals are allowed.
   • How many numbers are there between the number $\frac{1}{4}$ and number $4$ (not counting $\frac{1}{4}$ and $4$.
   • What is the number closest to $\frac{1}{5}$?
   • What is the smallest INTEGER which is not representable in this floating point system?
   • How would your answer change if $L$ and $U$ were to be $-5$ and $5$?

3. Let $x$ and $y$ be two adjacent positive Normalized Single Precision floating point numbers.
   • What is the minimal possible distance between $x$ and $y$?
   • What is the maximum possible distance between $x$ and $y$?
   • How many Double Precision Numbers are there between $x$ and $y$ (for double numbers $N=53$).

4. IEEE Single Precision has $\beta=2$, $p=24$, $L=-126$, $U=127$, and subnormals are allowed. What is the maximum integer value of $k$ for which the number
   $$x = 2^k+2^{-k}$$
   can be exactly re presentable in Single Precision?

5. IEEE Single Precision has $\beta=2$, $p=24$, $L=-126$, $U=127$, and subnormals are allowed.

   In class we have shown that if $x$ is a real number, and $\bar x$ is its floating point representation, then the maximum possible relative error in representing this number is given by

   $$\vert\frac{x-\bar{x}}{x}\vert\le\frac{\epsilon}{2},$$ (1)

   where $\epsilon$ is machine precision, $\epsilon = \beta^{1-N}.$

   How the equation (1) changes for the subnormals?

   To answer this question,

   1. First, consider $y = 2^{-128}$. How is $y$ going to be represented in IEEE SP?
   2. What is the floating point number that follows number $y$ on the computer number line?
   3. What is the maximum possible absolute error in representing numbers between $y$ and $2 y$?
   4. Consider number $z$ such that
      $$y<z<2y.$$
      What is the maximum possible relative error in representing the number $z$?
   5. extra credit Generalize the result of the previous question to any number between $2^{-149}<x<2^{-126}$. You can guess the correct result by contemplating equation (1).
6. In single precision, what is the floating point number that follows “32”? In other words, what is the smallest positive floating point number $x$ such that
   $$x>32?$$
   Please write the result the way it is stored in the computer, i.e. in binary floating point form.

7. Consider a floating-point arithmetic with base $2$, precision $8$ and exponent range $[-16,16]$. In other words, each number in this system can be represented as

   $$x = \left( d_0 + \frac{d_1}{2}+\frac{d_2}{4}+\frac{d_3}{8}+\frac{... ..._5}{32}+\frac{d_6}{64} +\frac{d_7}{128}\right)\times 2^{E}, -16\le E\le 16.$$
   Here $E$ is integer, and all $d_i, i =0\dots 7$ are either 0 or $1$.
   1. Show that addition is not necessarily associative. I.e., give an example of 3 numbers $a,$ $b,$ and $c,$ such that $(a+b)+c$ is not equal to $a+(b+c).$
   2. write down two adjacent normalized numbers $x$ and $y$ such that $\vert x-y\vert$ is maximal.
   3. In this floating point system, what is the range of possible relative errors in representing a given number by a machine number?

8. (a) Find the largest open interval around $x=16$ so that all real numbers from the interval are rounded to $x_f =16$. That is, find the smallest value of $L$ and the largest vlue of $R$ with $L<16<R$ so that any number from the interval $(L,R)$ is rounded to the floating point number $16$. Assume double precision is used (53 binary digits).

   (b)

   Redo the part (a) for the $x=50$, that is, find the interval $(L,R)$ that rounds to the floating point number

   $$x_f = 50 = \left(1+\frac{1}{2}+\frac{1}{2^4}\right)\times 2^5.$$

9. IEEE SP has $\beta=2$, $p=24$, $L=-126$, $U=127$.

   Calculate $UFL$, $OFL$ and $\epsilon_{\rm mach}$ for this system. Assume rounding by chopping.

   How many floating point numbers are there between any successive powers of $2$? For example, how many floating point numbers are there between 2 and 4?

10. Consider the floating point system with

    $$\beta=2, p=4, L=-5,U=5.$$

    (a) What is the distance from number $8$ to the next largest floating point number in this floating point system?

    (b) What is the distance from number $8$ to the next smallest floating point number in this floating point system?

    (c) What distance is larger, (a) or (b)? Why? What is the relation between these distances and machine precision $\epsilon_{\rm machine}$?

11. Consider IEEE SP, which has $\beta=2$, $p=24$, $L=-126$, $U=127$. What is the closest floating point number to the number
    $$x=75+\frac{1}{3}$$
    in IEEE SP?

12. Consider IEEE SP, which has $\beta=2$, $p=24$, $L=-126$, $U=127$. What is the absolute error in representing the number
    $$x=75+\frac{1}{3}$$
    in IEEE SP?
13. Consider IEEE SP, which has $\beta=2$, $p=24$, $L=-126$, $U=127$. What is the closest floating point number to the number
    $$x=75+\frac{1}{3}$$
    in IEEE SP?

14. What is the spacing of the floating point numbers between $16$ and $32$, i.e. $16 \le x \le 32$?
15. Define machine epsilon and explain its significance
16. What would be the output in MATLAB for the ratio $\epsilon /\epsilon$?
17. Consider
    $$f(x) = (e^x - 1) / x.$$

    a) Approximate $e^x - 1$ using third degree Taylor polynomial expanded about $x = 0$. Use this expansion to show that

    $$\lim\limits_{x\to 0}f(x) = 1.$$

    b) Explain why MATLAB would compute the limit of $f(x)$ to be 0.

18. What is the largest value of $k$ such that
    $${\rm {float}}(19+2^{-k})> {\rm {float}}(19)$$
    in IEEE SP system? Here ${\rm float(x)}$ is a floating point representation of the number $x$.
19. We have studied in class that the maximum possible relative error for normalized numbers is equal to
    $$\vert\frac{x - {\rm float}(x)}{x}\vert\le\frac{\epsilon_{\rm mach}}{2}.$$
    < What is the range of possible errors for the subnormal floating point numbers?

20. Consider
    $$f(x)=\frac{1-(1-x)}{x}$$
    function. The following values were obtained in MATLAB:
    

    $x$	$f(x)$
    $\frac{\epsilon}{4}(1+10^{-10})$	$2$
    ${\epsilon\over 4}(1+10^{-10})+{\epsilon\over 2}$	$4/3$
    ${\epsilon\over 4}(1+10^{-10})+\epsilon$	$6/5$
    $-{\epsilon\over 2}(1+10^{-10})-\epsilon$	$4/3$

    Please explain in details the values in the right column of this table.

21. For which positive integers $k$ can the number $5+2^{-k}$ be represented exactly, with no rounding error in IEEE SP floating point system?

22. Consider IEEE SP that has binary numbers $\beta=2$, with $N=24$ digits, and lower and upper values of the exponents of $L=-126$, $U=127$. As we discussed in class, the number $\frac{1}{3}$ is not representable in IEEE SP. What is the Floating Point Number that precedes $x=\frac{1}{3}$? In other words, find the largest Floating Point Number that is less then $x=\frac{1}{3}$.

    Hint: your answer should contain 24 binary digits of the mantissa and the value of the exponent.

23. (a)Which of the following operations of two positive floating point numbers can produce overflow?

    — addition

    — subtraction

    — multiplication

    — division

    If you answered “yes” to any of the questions, please give one example of two Single Precision numbers that produce overflow by given operation.

    (b) Which of the following operations of two positive floating point numbers can produce underflow?

    — addition

    — subtraction

    — multiplication

    — division

    If you answered “yes” to any of the questions, please give one example of two Single Precision numbers that produce underflow by given operation.

24. What is the number that follows the number “zero”, ${\rm zero}\equiv 0$. In other words, find the smallest possible positive number that is representable in this system. Write the result in both binary and decimal format.

25. Consider the following expression:

    $$\frac{1}{1-x}-\frac{1}{1+x},$$
    assuming $x\ne\pm 1.$

    (a) for what values of $x$ it is difficult to calculate this expresion accurately in floating point arithmetic?

    (b)Give a rearrangement of the terms such that, for the range of $x$ in part a, the computation is more accurate in floating point system

26. Consider IEEE SP that has binary numbers $\beta=2$, with $N=24$ digits, and lower and upper values of the exponents of $L=-126$, $U=127$. What is the Floating Point Number that is before $x=0.1$? In other words, what is the largest Floating Point Number that is less then $x=0.1$.

27. Consider the IEEE floating point system, where the binary numbers $\beta=2$, with $N=24$ digits, and lower and upper values of the exponents of $L=-126$, $U=127$ are used. Also, assume that the “rounding to nearest” rule is used, and if there is a tie, a smallest number is chosen.

    — For what numbers $x$ will the computer claim that inequality $1<x<2$ is true?

    — For what real numbers $x$ will a computer claim that $x=4$?

    — Suppose it is claimed that the solution $x$ of $x^2-2=0$ is exactly representable in this system. Why it is not possible? What is the distance between two floating point numbers that is right above and right below solution of $x^2-2=0$ in this system?

28. Consider the following toy floating point system: base $\beta=2$, with $N=8$ digits, with lower exponent of $L=-16$ and upper exponent $U=16$.

    Consider the following claim: If the two positive binary floating point numbers $x$ and $y$ in this toy floating point systems are such that

    $$\frac{1}{2}\le \frac{x}{y}\le 2,$$
    then their difference, $x-y$ is exactly representable number in the floating point system.

    Is this claim true or false? If it is true, explain why, if it is false, find counter example.

29. Consider the following function:

    $$f(x)=\frac{1-(1-x)}{x}.$$
    The value of this function for any $x$ is equal to one. However, when we calculate $f(x)$ on the computer for small value of $x$, result is not equal to $1$. Here is a computer generated graph of $f(x)$ for small value of $x$.

    Please explain why this graph looks the way it does.

    In particular, answer the following questions:

    1. Why $f(x)$ is zero for $0<x<0.555 \times 10^{-16}$?
    2. Why $f(x)$ is zero for $-1.1\times 10^{-16} <x<0$ ? Why the value of zero on the left is twice longer than the value of zero on the right?
    3. Why after zero, $f(x)$ jumps to the value of $2$ at $x\simeq 0.5556 \times 10^{-16}$?
    4. Why does $f(x)$ oscillate around $1$ for $0.5556 \times 10^{-16} <x< 5\times 10^{-16}$?
    5. Why does oscillation diminish, as $x$ become larger
    6. Why oscillations are twice as frequent for positive $x$ than for negative $x$?
    7. Explain why does the second jump appear at $x=1.665 \times 10^{-16}$.

30. Assume a normalized floating point system with base $\beta=10$, three digits of accuracy $d=3$ and the lowest possible exponent of $L=-98$.
    1. What is the smallest possible positive floating point number that is representable in this system (also called “UFL” for underflow level)?
    2. If $x=6.87\times 10^{-97}$ and $y=6.81\times 10^{-97}$, what is the result of computing $x-y$?
    3. If the subnormal numbers were to be allowed, what would be the result of $x-y$?

31. IEEE SP has $\beta=2$, $p=24$, $L=-126$, $U=127$. In single precision floating point system write down the floating point number that follows the number $x=17$. (In other words, find minimal value of $x>17$, that is exactly representable in this floating point system.

32. IEEE SP has $\beta=2$, $p=24$, $L=-126$, $U=127$. What is the smallest possible positive integer that is not a single precision number?

33. In a floating point system with precision $p=6$ decimal digits, $\beta=10$, let $x=1.23456$ and $y=1.23579$.
    1. How many significant digits does the difference $y-x$ contain?
    2. If the floating point system is normalizes, wwhat is hte minimum exponent range for which $x,y$ and $y-x$ are exactly representable?
    3. Is the fifference $y-x$ exctly representable, ragardless of exponent range, if gradual underflow is allowed? Why?

34. Suppose one calculates using computer arithmetic the following number:

    $$A=3*(\frac{4}{3}-1)-1.$$
    We have shown in class that one can estimate the machine precision by the number $A$, so that
    $$\epsilon_{\rm machine}\simeq A.$$

    Determine whether the following examples may be used to determine machine precision:

    $$B=(\frac{7}{3} - \frac{4}{3}) - 1,$$
    and
    $$C= (\frac{4}{3} - \frac{1}{3}) - 1.$$
    Explain your reasoning by using the system with two digits of precision.

    You may find it helpful to use calculator to gain intuition for this problem.

35. Consider a floating-point number system with base $2$, precision $5$ and exponent range $[-10,10].$ I.e., in this system any number can be written as $1.a_{1}a_{2}a_{3}a_{4} \ast 2^{L}.$

    (a) Write down two adjacent normalized numbers $x$ and $y$ such that $\left\vert x-y\right\vert$ is minimal.

    (b) In this floating-point system, what is the maximal possible error of representing $\pi$ by a machine number? What is the possible relative error in representing $\pi$ by a machine number?

    (c) In this floating-point system, how many numbers are there between number $2$ and number $4$.

36. Assume a decimal (base 10) floating point system having machine precision $\epsilon_{mach}=10^{-5}$ and an exponent range of $\pm 20$. What is the result of each of the following floating point arithmetic operations?
    

    $$1+ 10^{-7}=$$
    $$1+10^3=$$
    $$1+ 10^7=$$
    $$10^{10}+10^3=$$
    $$10^{10}/10^{-15}=$$
    $$10^{-10}\times 10^{-15}=$$

    Chapter TWO

37. Suppose you are solving $f(x)=0$ by iterations, and you have obtained $(x_{k-1},f(x_{k-1})$ and $(x_k,f(x_k)$. Now use linear interpolation to find $(x_{k+1},f(x_{k+1})$ such that $f(x_{k+1})\simeq 0$. What is the resulting method of solving $f(x)=0$ that you have obtained?

38. For the secant, Newton, and bisection methods: Looking at iterative error when solving $f(x)=0$, which of these methods converges to an error of $10^{-16}$ the fastest?
39. True or False:
    If Newton's method converges to a solution $x^*$ for a particular choice of $x_0$, then it will converge to $x^*$ for any starting point between $x_0$ and $x_*$.
    To get credit for this problem, you will need to give comprehensive explanation of your answer.

40. For compyting the midpoint $m$ of an interval $[a,b]$, which of the following two equations is prefereable in floating point system? Why? When? Devise the example when the midpoint given be the equation lies outside of the $[a,b]$ interval.
    1. $m=(a+b)/2$,
    2. $m=a+ (b-a)/2$.

41. Solve with three digits accuracy an equation

    $$x^2 + 3 x -8\times 10^{-14}=0.$$
    Note that you have to find two roots. What version of quadratic formulas are you going to use to find these roots?

42. The “divide and average” method for computing a square root $x_n$of a given number $a$ can be formulated as follows:
    $$x_{n+1} = \frac{x_n+ \frac{a}{x_n}}{2}.$$
    Show that this method converges to $\sqrt a$, i.e. that
    $$\lim\limits_{n\to\infty}x_n = \sqrt{a},$$
    and calculate the rate of convergence.

43. Show that if
    $$f(x) =\frac{1}{x}-b,$$
    for nonzero $b$, then the Newton method, converging to the root $r = 1/b$ can be implemented without performing any divisions. new

44. Newton method for solving a scalar nonlinear equation $f(x)=0$ requires computation of the derivative of $f$ at each iteration. Suppose that we instead replace the true derivative with a constant value $d$, that is we use the iteration scheme

    $$x_{k+1} = x_k - f(x_k)/d.$$

    (a) Under what condition on value of $d$ will this scheme be locally convergent?

    (b) What is the convergence rate of this scheme?

    (c) Is there any value of $d$ to give a quadratic convergence?

45. In class we have shown that Newton method

    $$x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)},$$ (2)

    has quadratic rate of convergence for simple root (i.e. when $f(x_*)=0$ and $f'(x_*)\ne 0$). In the homework you have shown that convergence rate is linear for the double root.

    Proove, that Newton method has linear rate of convergence for triple root, i.e. when $f(x_*)=f'(x_*)=f''(x_*)=0, f'''(x_*)\ne 0$.

    Extra Credit Proove it for roots of multiplicity $n$, i.e. when

    $$f(x_*)=0 \left(\frac{d}{d x}\right)^k f(x_*)= 0, k = 1,2, dots n-1, \left(\frac{d}{d x}\right)^{n+1} f(x_*)\ne 0 .$$

46. Suppose you came to the Ice Age, and computer in your Time Machine is broken. Suppose to come back to 2016 to complete the numerical computing exam, you need to calculate “two to the power one third”, i.e.
    $$2^\frac{1}{3}$$
    . You can only use $+$, $-$, $*$ and $/$. Set up the nonlinear equation that has $2^\frac{1}{3}$ as the solution.
    1. Describe how to use the bisection method to make this calculation. What is your initial bracket? How many iteration steps do you need to perform to get the solution with $10^{-3} \simeq 2^{-10}$ accuracy?
    2. Describe how to use the Newton method for this calculation. How many steps do you need to do to get the root with $10^{-3}$ accuracy?
47. Consider the following iteraton methods

    1. $$x_{n+1} = \frac{20 x_n + \frac{21}{x_n^2}}{21},$$

    2. $$x_{n+1} = x_n - \frac{x_n^3-21}{3 x_n^2},$$

    3. $$x_{n+1} = \sqrt{\Big(\frac{21}{x_n}\Big)}.$$

    4. $$x_{n+1} = \frac{ 21 + 2 x^3}{ 3 x^2}.$$

    Assume that all iterations start from $x_0=1$.
    1. 4 points Verify that each of these fixed-point iterations converge to $\sqrt[3]{21}$, i.e.
       $$\lim\limits_{n\to\infty}x_n=X=\sqrt[3]{21},$$
       and
    2. rank the methods in order based on their apparent speed of convergence (i.e. find the fastest method to converge, the second fastest, the third and the last to converge).

48. In class we have shown that fixed point iterations

    $$x_{k+1}= g(x_k), x^*=g(x^*),$$
    converge if
    $$\vert g(x^*)\vert<1.$$
    Under what condition fixed point iterations converge if
    $$g(x^*)=1?$$

    To gain an intuition on this problem, consider the fixed point iterations

    $$x_{k+1}= g(x_k), g(x)=x-x^2/2.$$
    For this problem the fixed point is $x^*=0$. Start with $x_0=1$. Then
    $$x_1=g(x_0)=1/2,$$
    $$x_2=g(x_1)=3/8=0.375,$$
    $$x_3=g(x_2)=39/128=0.304688.$$
    It seems to converge to the fixed point $x^*=0$, yet $g'(x^*=0)=1$. Why is that?

49. Consider the function

    $$f(x) = e^x - 2 x^2.$$
    The graph of the function is given by

    As you see from the graph, this function has three roots, given by $X_1=-0.539835$, $X_2= 1.48796$ and $X_3=2.61787$.

    The following two functions are defined as
    

    $$g_1(x) = -\sqrt{\frac{e^x}2}$$

    $$g_2(x) = \sqrt{\frac{e^x} 2}$$ (3)

    
    Consider the following fixed point iterations:
    

    $$x_{k+1} = g_1(x_k)$$ (4)

    $$x_{k+1} = g_2(x_k)$$ (5)

    
    
    1. Show that fixed point iterations (4) with $g_1(x)$ converges to the root $X_1$.
    2. Show that fixed point iterations (5) with $g_2(x)$ converges to the root $X_2$.
    3. Show that iterations with neither $g_1(x)$ nor $g_2(x)$ converge to the root $X_3$, regardless of the starting point.
    4. Propose a fixed point iteration scheme that will converge to the root $X_3$.

50. We have studied Secant method

    $$x_{k+1} = x_k - f(x_k)\frac{x_k-x_{k-1}}{f(x_k)-f(x_{k-1})}.$$
    • Show that it can be equivalently rewritten as
      $$x_{k+1}= \frac{x_{k-1} f(x_k)- x_k f(x_{k-1})}{f(x_k)-f(x_{k-1})}.$$

    • List two advantages and two disadvantages of Secant method relative to Newton method.
51. Suppose you are solving $f(x)=0$ by iterations, and you have obtained $(x_{k-1},f(x_{k-1}))$ and $(x_k,f(x_k))$. Now use linear interpolation to interpolate a straight line through these two points, and choose $x_{k+1}$ so that $f(x_{k+1})\simeq 0$. What is the resulting method of solving $f(x)=0$ that you have derived?
52. Express the Newton iteration method for solving the following system of nonlinear equations:
    $$x_1^2 + x_1 x_2 ^3 =9, 3 x_1^2 x_2 - x_2^3 = 4,$$
    and carry out one iteration starting from the starting point $(1,1)$.

53. Express the Newton iteration method for solving the following system of nonlinear equations:
    

    $$x_1^2 + x_1 x_2 ^3 =9,$$

    $$3 x_1^2 x_2 - x_2^3 = 4,$$

    
    and carry out one iteration starting from the starting point $(1,1)$.

54. Carry out one iteration of Newton's method applied to the system
    

    $$x_{1}^{2}-x_{2}^{2} =$$ 0

    $$x_{1}x_{2} = 1$$

    
    with starting value ${\bf x}_{0}=[0,1]^{T}.$

55. The following values for the solution of $f(x)=0$ were computed using Matlab. What method was used (bisection, Newton or secant)? Make sure you explain in details why it is the method you claim:

    X=50.25125628140704

    X=25.378140640072242

    X=12.944094811287638

    X=6.7320923307183715

    X=3.636103634563207

    X=2.1079101939699143

    X=1.3816957571715662

    X=1.0826201384421688

    X=1.0058580941730362

    X=1.0000339198559194

    X=1.0000000011504786

    X=1.0000000000000000

    X=1.0000000000000000

    Chapter THREE

56. Show that for arbitrary square matrices $A$ and $B$ the following is true
    $$(A\cdot B)^{-1} = B^{-1}\cdot A^{-1}.$$

57. Show that for arbitrary square matrices $A$ and $B$ the following is true
    $$(A\cdot B)^{\rm T} = B^{\rm T}\cdot A^{-\rm T},$$
    where ${\rm T}$ denotes the transposition
58. Prove or give counterexample: if $A$ is a singular matrix, then
    $$\vert\vert A^{-1}\vert\vert=\vert\vert A\vert\vert^{-1}.$$

59. Consider the following systems of equations:
    $$x^2+y^2=4, y = x^6.$$
    or
    $$x^3+4 y^3=4, \ \ 2 x^2+y^2y = 7.$$
    1. Sketch the two curves and explain where approximately the solutions are located
    2. Set up and explain the Newton method to find the solutions. Calculate the Jacobian $J$ and the RHS ${\bf f}$ of the Newton method.
    3. What would be the good starting point for your calculations?
    4. Write down in all details the system of equations to make the first iteration. Do not solve the resulting equations.

60. 
    Suppose that you use Newton method

    $$x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)},$$ (6)

    to find the solution of the equation
    $$f(x^*)=0$$
    for which
    $$f'(x^*)\ne 0, \rm {\ and \ } f''(x^*)=f'''(x^*)=f''''(x^*)=0.$$
    What would be the convergence rate for the Newton method for such a case? HINT: convergence of the Newton method is not necessarily quadratic.

61. (a) Let ${\bf A}$ be an arbitrary square matrix, and let $c$ be an arbitrary scalar.

    Prove or disprove the following statements:

    (i)

    $$\vert\vert c {\bf A}\vert\vert = \vert c\vert \cdot \vert\vert A\vert\vert$$

    (ii)

    $${\rm cond} ( c \cdot {\bf A}) = \vert c\vert \cdot {\rm cond} ({\bf A})$$

    (b)

    Let ${\bf A}$ be an $n\times n$ diagonal matrix with all its diagonal entries equal to $1/2$.

    (i) What is the value of $det( {\rm A})$?

    (ii) What is the value of ${\rm cond (A)}$?

62. Consider the linear system
    

    $$A x =b,$$

    $$A=\left(\begin{array}{cc} 1 & 1.1 0.9 & 1\end{array}\right),$$

    $$b = \left(\begin{array}{c} 1.11 1\end{array}\right).$$

    
    
    1. Solve this system by any method you like using exact arithmetic.
    2. Solve this system by computing an inverse of $A$ using two decimal digit machine arithmetic.
       Hint If
       $$A=\left(\begin{array}{cc} a & b c & d\end{array}\right),$$
       then
       $$A^{-1}=\frac{1}{a d - b c} \left(\begin{array}{cc} d & -b -c & a\end{array}\right).$$
       Also
       $$x= A^{-1}b.$$

    3. Now solve (9) by using LU factorization using two decimal digit machine arithmetic.
       
    4. Compare and explain the difference between results obtained in items 1, 2 and 3. What conclusion can you make about LU factorization and computing solution of (9) by using inverse of a matrix?

63. In this problem

    $$A = \left[ \begin{array}{rr} 1 & -2 \\ -2 & 3 \end{array}\right]$$
    (a) Find a vector $x$ such that $\vert\vert A x\vert\vert _\infty = \vert\vert A\vert\vert _\infty$.

    (b) Find a vector $x$ such that $\vert\vert A x\vert\vert _1 = \vert\vert A\vert\vert _1$

64. Consider the $A x = b$ problem with $\alpha>0$ and
    $$A = \left[ \begin{array}{rr} -1 & 1 \\ 0 & \alpha \end{a... ... \ b = \left[ \begin{array}{rr} 1 \\ 1 \end{array}\right]$$
    Suppose that the error ${\bf e} = {\bf x } - {\bf x_c}$ in computed solution is small, but nonzero. Here ${\bf x}$ is an exact solution, and ${\bf x}_c$ is a computed solution. For what values of $\alpha$, if any, the residual will be large?

    HINT For what values of $\alpha$, if any, the matrix $A$ will be ill-conditioned?

    HINT If

    $$A=\left(\begin{array}{cc} a & b c & d\end{array}\right),$$
    then
    $$A^{-1}=\frac{1}{a d - b c} \left(\begin{array}{cc} d & -b -c & a\end{array}\right).$$

65. The Kronecker delta (named after Leopold Kronecker) is a function of two variables, usually two integers, is defined as

    
    

    $$\delta^i_j =\left( \begin{array}{cc} 1 & {\rm if } i=j\\ 0 & {\rm if } i\ne j\\ \end{array}\right.$$ (7)

    
    

    Consider the $n\times n$ matrix $A$ defined as

    $$A = (a_{ij}), a_{ij} = i\cdot \delta^i_j.$$

    In other words, $A$ is a diagonal matrix with diagonal entries being equal to

    $$1, 2, 3, \dots (n-1), n.$$
    1. What is the one norm of this matix?
    2. What is the two norm of this matrix?
    3. What is the $\infty$ norm of this matrix?
    4. What is the Condition Number of this matrix?

66. For the matrix

    $${\bf A=}\left[ \begin{array}{rrr} 2 & -4 & 2 \\ 1 & 0 & 5 \\ 2 & -2 & 2 \end{array}\right]$$
    find the $LU$-factorization (show both $L$ and $U$ matrices explicitly).

67. Consider the system

    $${\bf A} \cdot x = b,$$ (8)

    where
    $${\bf A=}\left[ \begin{array}{rrr} 5 & 6 & 7 \\ 10 & 20 & 23 \\ 15 & 50 & 58 \end{array}\right]$$
    and
    $$b =\left[ \begin{array}{r} 6\\ 13\\ 23 \end{array}\right]$$

    or

    $${\bf A=}\left[ \begin{array}{rrr} 1 & 3 & 5 \\ 2 & 9 & 15 \\ 2 & 18 & 37 \end{array}\right]$$
    and
    $$b =\left[ \begin{array}{r} 22\\ 65\\ 149 \end{array}\right]$$

    (a) Find explicitly $LU$ factorization of ${\bf A}$.

    (b) Use this $LU$ decomposition to solve (9).

68. Consider the matrix
    $${\bf B=}\left[ \begin{array}{rrr} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 3 & 2 & 1 \end{array}\right]$$
    Calculate the inverse of this matrix $B^{-1}$ by representing the matrix as a product of two elementary Gauss elimination matrices.

69. In this problem $\alpha$ is a small positive number. Sketch the two lines in the $x,y$ plane, and describe how they change, including the point of intersection, as $\alpha$ approaches zero. Also, calculate the condition number for the matrix, and describe how it changes, when $\alpha$ approaches zero.

    1. $$x-y = -1, -x+ (1+\alpha) y =1.$$

    2. $$2 x + 4 y = 1, (1-\alpha)x+2 y = -1.$$

70. Prove that the one norm is the maximum absolute column sum; use $2\times 2$ matrices.
71. Consider
    

    $${\bf A}=\left(\begin{array}{ccc} 1 & 0 & 0 \\ 0 &-2&2\\ 0 & 2& -1\end{array}\right)$$ (9)

    
    

    a) Find the LU factorization of the given matrix

    b) Calculate the norms $\vert\vert A\vert\vert _2$, $\vert\vert A\vert\vert _\infty$, and $\vert\vert A\vert\vert _1$ for this matrix

    c) Calculate the condition number for the matrix A.

72. Consider
    

    $${\bf A=}\left( \begin{array}{cc} -1 & 1 \\ 2 & 2 \\ \end{array}\right)$$

    
    
    • Find all vectors satisfying $\vert\vert x\vert\vert _\infty=1$ and $\vert\vert{\bf A} x\vert\vert _\infty=\vert\vert{\bf A}\vert\vert _\infty$.
    • Find a vector satisfying $\vert\vert{\bf A} x\vert\vert _1=\vert\vert{\bf A}\vert\vert _1.$
    • Find a vector satisfying $\vert\vert{\bf A} x\vert\vert _2=\vert\vert{\bf A}\vert\vert _2.$
73. The $\infty$ norm of a vector is defined as a modulus of a maximum component of a vector. As we learned in class, matrix norms are defined through the vector norms as
    $$\vert\vert A\vert\vert _\infty = {\rm max} \frac{ \vert\vert A x\vert\vert _\infty}{\vert\vert x\vert\vert _\infty}.$$

    Use this definition of the matrix $\infty$ norm through the vector norm to proove that the $\infty$ norm of a matrix is a maximum absolute row sum.
    

    Complete the proof for $2\times 2$ matrices.

    b Extra credit 10% Prove this statement for general $n\times n$ matrices.

74. Consider the system
    

    $$\left[ \begin{array}{ll} 4 & 2 \\ 2+\varepsilon & 1+\varepsi... ...y}\right] =\left[ \begin{array}{l} 2 \\ 1 \end{array}\right] .$$ (10)

    
    

    where $\varepsilon$ is small. The system has two approximate solutions ${\bf\hat{x}=}[0,1]^{T}$ and ${\bf\tilde{x}=}[1-5\varepsilon ,-1]^{T}.$ Find the norms of the respective residuals. Which one is smaller? Find the condition number of the matrix. Explain, why you should not use residuals in this case to determine the quality of a solution.

    Hint: Find an exact solution to (11).

    Hint

    $$\left[ \begin{array}{rr} a & b \\ c & d \end{array}\right]... ...left[ \begin{array}{rr} d & -b \\ -c & a \end{array}\right]$$

75. Calculate an inverse of the following matrix:
    

    $${\bf A=}\left( \begin{array}{cccccc} 1 & 0 &0 &0 &0 &0 \\ 0 ... ... 0 & 0 &3 &0 &1 &0 \\ 0 & 0 &4 &0 &0 &1 \\ \end{array}\right)$$ (11)

    
    Calculate the inverse of this matrix, ${\bf A}^{-1}$.
76. Let a $40\times 40$ matrix ${\bf A}$ be factored as follows:
    

    $${\bf A=LU=}\left( \begin{array}{cccccc} 1 & & & & & \\ -1 & ... ...s & \vdots \\ & & & & 1 & 1 \\ & & & & & 1 \end{array}\right)$$ (12)

    
    where the blank spaces stand for zeros. Use the LU factorization to solve the system ${\bf Ax=[}0,1,-1,1,...,-1,1]^{T}.$

77. Consider the matrix
    

    $$A = \left( \begin{array}{cc} 1 & 1+\epsilon\\ 1-\epsilon & 1 \end{array}\right)$$

    
    
    1. What is the determinant of $A$?
    2. In floating point arithmetic, for what range of $\epsilon$ will the computed value of the determinant be nonzero
    3. What is the $LU$ factorization of $A$?
    4. In floating point arithmetic, for what value of $\epsilon$ will the computed value of $U$ be singular?
78. In a computer with no build in function for floating point divisions, one might instead use multiplication by the reciprocal of the divisor. Apply Newton's method to produce an iterative scheme to approximate the reciprocal of a number $y>0$, to solve the equation
    $$f(x)=\frac{1}{x}-y=0,$$
    given y. Considering intended application your scheme should not contain any divisions.

79. Consider the following system of equations:
    $$x^2+y^2=4, y = x^6.$$
    1. Sketch the two curves and explain where approximately the solutions are located
    2. Set up and explain the Newton method to find the solutions. Calculate the Jacobian $J$ and the RHS ${\bf f}$ of the Newton method.
    3. What would be the good starting point for your calculations?
    4. Write down in all details the system of equations to make the first iteration. Do not solve the resulting equations.

80. Let a $6\times 6$ matrix ${\bf A}$ be factored as follows:
    

    $${\bf A=} \left( \begin{array}{ccccccc} 1 & 1 & 1 & 1 &1 &1 \\... ...& 0 & 0 & 0 &1 &1 \\ 0 & 0 & 0 & 0 &0 &1\\ \end{array}\right)$$

    
    Using this factorization, solve for $x$ the following equation:
    

    $${\bf A x =} \left( \begin{array}{cccccc} 21 \\ 41 \\ 59 \\ 74 \\ 85 \\ 91 \\ \end{array}\right)$$

    
    

    Chapter FOUR

81. The Kronecker delta (named after Leopold Kronecker) is a function of two variables, usually two integers, is defined as

    
    

    $$\delta^i_j =\left( \begin{array}{cc} 1 & {\rm if } i=j\\ 0 & {\rm if } i\ne j\\ \end{array}\right.$$ (13)

    
    

    Consider the $n\times n$ matrix $A$ defined as

    $$A = (a_{ij}), a_{ij} = i\cdot \delta^i_j.$$

    In other words, $A$ is a diagonal matrix with diagonal entries being equal to

    $$1, 2, 3, \dots (n-1), n.$$
    1. Find eigenvalues of $A$.
    2. Find eigenvectors of $A$.
    3. To which eigenvector would a power iteractions converge? Explain, how to set up such power iterations.
    4. To which eigenvector would an inverse power iteraction converge? Explain, how to set up such power iterations.
    5. What algorithm would you use to find second largest eigenvector and corresponding eigenvalue? Please explain in details.

82. Let the $n\times n$ matrix $A$ have eigenvalues $\lambda_1\dots\lambda_n$, and eigenvectors $X_1\dots X_n$. Let the $n\times n$ matrix $B$ have eigenvalues $\mu_1\dots\mu_n$ and same eigenvectors $X_1\dots X_n$. What are eigenvectors and eigenvalues of the matrix $C$ given by
    $$C = 2 A^3+ 4 B^{-4}.$$

83. 
    

    $${\bf A}= \left(\begin{array}{ccc} 1 & 2 & -4\\ 3 &-2 & 2\\ 6 & 2 & 4 \end{array}\right)$$ (14)

    
    

    a) Calculate the Eigenvalues and Eigenvectors for the given matrix

    b) What Eigenvalue would the inverse power method converge to? Why?

    c) What Eigenvalue would the power method converge to? Why?

    d) Define $B = 2A - 3I$. For this matrix, what Eigenvalue would the power method converge to? Why?

84. Consider the $6\times 6$ matrix

    $$A = \begin{bmatrix} 5 & 0 & 0 & 0 & 1 & 0 \\ 0 & 5 & 0 & 0 & 0... ... 0 & 0 \\ 1 & 0 & 0 & 0 & 5 & 0 \\ 0 & 0 & 0 & 0 & 0 & 5\\ \end{bmatrix}$$
    1. Find Eigenvalues and Eigenvectors of this matrix
    2. Find LU decomposition of this matrix
    3. To what eigenvalue and eigenvector the power iteration will converge?
    4. To what eigenvalue and eigenvector the inverse power iteration will converge?

85. Suppose that ${\bf A}$ is a symmetric $4\times 4$ matrix with eigenvalues

    $$-4, 1, 2, 3.$$

    a) To which of these eigenvalues will the power method converge? Why

    b) To which of these eigenvalues will the inverse power iteration converge? Why?

    c) To what eigenvalue the power iteration method applied to the matrix

    $${\bf B}=2 {\bf A}+3 I$$
    will converge? Why?

86. Consider

    $$A=\left(\begin{array}{cc} 4 & 8 1 & 6\end{array}\right),$$

    (a) Find eigenvalues and eigenvectors of $A$.

    (b) Find eigenvalues and eigenvectors of

    $$B=\left(\begin{array}{cc} 5 & 8 1 & 7\end{array}\right)^3 + \left(\begin{array}{cc} 3 & 8 1 & 5\end{array}\right)^{-1}.$$

    Note that you do not have to calculate $B$ explicitly.

    Chapter FIVE

87. Given
    $$f(x) = x^5,$$
    on the interval $-1\le x\le 2$, use the points $x_1 = -1$, $x_2 = 0$ and $x_3 = 2$.

    a) Find the piecewise linear interpolation function

    b) find the quadratic interpolation function

88. Consider
    $s_1(x) = -2 + x + 6x^2 + 2x^3$ for $-1\le =\le 0$
    $s_2(x)$ for $0 \le x\le 1$.

    Solve for $s_2(x)$ so that the given function is a natural cubic spline from $-1\le x\le 1$.

89. Use the theorems we studied in class to calculate the maximum error in interpolating the function $\sin(t)$ by a polynomial of degree four using five equally spaced points on the interval $[0,2\pi]$.
90. Suppose you want to interpolate the function $\sin(t)$ by a polynomial of degree $N$ by using $N+1$ equally spaced points on the interval $[0,2\pi]$. How many points should you use so that the difference between the sine function and your interpolation is less that $10^{-16}$?

91. For a set of $N$ given data points $t_1, \dots t_n$, define the function
    $$\pi(t)= (t-t_1)(t-t_2)\dots (t-t_n).$$
    1. Show that
       $$\pi^\prime(t_j) = (t_j-t_1)(t_j-t_2)\dots (t_j-t_{j-1})(t_j-t_{j+1}) \dots (t_j-t_n).$$

    2. Show that the $j$'th Lagrange basis function can be expressed as
       $$L_j(t) = \frac{\pi(t)}{(t-t_j)\pi^\prime(t_j)}.$$

92. In general, is it possible to interpolate $n$ data points by a piecewise quadratic polynomial, with knots at a given data points, such that the interpolant is
    • once continuously differentiable?
    • twice continiously differentiable
    Explain your answer as best as you can.
93. What is the maximum number of points $n$ that can be interpolated by a piecewise quadratic polynomial that is twice continuously differentiable?

94. Consider the following data

    $$(0,1) ( 1,2) (2,9).$$
    1. Interpolate this data by a quadratic polynomial by using monomial interpolation
    2. Interpolate this data by using Lagrange interpolation
    3. Show that Lagrange interpolation reduces to monomial interpolation
95. The Gamma function $\Gamma(x)$ has the following known values:
    $$\Gamma(0.5)=\sqrt{\pi}, \Gamma(1)=1, \Gamma(1.5) = \sqrt{\pi}/2.$$
    Use quadratic interpolation to determine the value approximate value of $x$ such that $\Gamma(x)=1.5$. HINT: Instead of using the data $(0.5,\sqrt{\pi}), (1,1), (1.5, \sqrt{\pi}/2),$ you may find it easier to use the data $(\sqrt{\pi},0.5), (1,1), (\sqrt{\pi}/2, 1.5).$

96. Suppose that some measurements had produced the following data:

    $$(0; 5), (1;9), (2,15)$$

    (i)

    Write down second degree polynomial passing through all three points by using Lagrange interpolation

    (ii)

    Write down second degree polynomial passing through all three points by using Newton interpolation

    (iii)

    Show that the two polynomials obtained in (i) and (ii) are equivalent

97. Use appropriate Lagrange interpolating polynomial of to interpolate the following data:

    $$(0,-3), (1,0), (2,5), (3,12) .$$

    What is the degree of interpolating polynomial? There is a catch in this question.

98. Consider the following data:

    $$(0,3), (1,1), (2,3).$$
    1. Interpolate this data by a quadratic polynomial by using monomial interpolation
    2. Interpolate this data by using Lagrange interpolation
    3. Show that Lagrange interpolation reduces to monomial interpolation
    4. Interpolate this data by piece wise linear interpolation

99. Determine the parabola (interpolating polynomial of degree two) that interpolates the values of $\sin x$ for $x=0,\pi/2,\pi.$

100. Find the clamped cubic spline $s(x)$, which goes through the points
     $$(0,1), (1,3), (2,4)$$
     with the value of the first derivative being equal to $2$ and $3$ at the beginning and the end of the domain, i.e.
     $$s'(x=0)=2, {\rm and } s'(2)=3.$$

101. Find the clamped cubic spline $s(x)$, which goes through the points
     $$(0,1), (1,3), (2,5)$$
     with the value of the first derivative being equal to $2$ and $-2$ at the beginning and the end of the domain, i.e.
     $$s'(x=0)=2, {\rm and } s'(2)=-2.$$

     Consider the following function

     $$g(x) = \left[ \begin{array}{lll} x^3+1, & {\rm for }& 0\le x\... ...x^3+6 x^2 -6 x + 1 & {\rm for} &1\le x\le 2 \end{array}\right.$$
     Is $g(x)$ a cubic spline for $0\le x\le 2$? Make sure you justify your answer

102. Consider the logarithmic function $\ln(x)$ evaluated at the points 1,2 and 3:
     $$(1, \ln(1)), (2, \ln(2)), (3,\ln(3)).$$
     Write down the entries of the matrix and right hand side of the linear system that determines the coefficients for the cubic not-a-knot spline (variation: natural) interpolating these three points.

     HINT: not-a-knot spline requires that the third derivative is continuous at the first and last points. Do not solve this system.

103. Suppose you were to define a piece-wise quadratic spline that interpolates $n+1$ given values
     $$(x_1, y_1), (x_2, y_2), \dots (x_n, y_n), (x_{n+1}, y_{n+1}).$$

     Write down in general form $n$ quadratic polynomials that interpolate these $n+1$ points, such that the resulting piece wise quadratic polynomial has continuous first derivative. How many additional conditions are required to make a square system for the coefficients of this quadratic spline?

104. This problem considers the function
     

     $$g(x) = \begin{bmatrix} x^3-1, & {\rm if} &0\le x\le 1 \\ -x^3+6x^2-6x+1, & {\rm if} & 1\le x\le 2 \end{bmatrix}$$ (15)

     
     
     1. Is $g(x)$ a cubic spline for $0\le x\le 2$?
     2. If it is a spline, it is natural, clamped, or neither?
     Make sure to justify your answers.

105. This problem considers the function
     

     $$g(x) = \begin{bmatrix} 2+3x^2 + \alpha x^3, & {\rm if} &-1\le x\le 0 \\ 2+\beta x^2 -x^3, & {\rm if} & 0\le x\le 1 \end{bmatrix}$$ (16)

     
     
     1. For what values of $\alpha$ and $\beta$, if any, is $g(x)$ a cubil spline for $-1\le x\le 1$? These values are to be used for the rest of this problem.
     2. What were the data points that give rise to this cubic spline?
     3. for what values of $\alpha$ and $\beta$ is $g(x)$ a natural cubic spline?
     4. for what values of $\alpha$ and $\beta$ is $g(x)$ a clamped cubic spine?

106. Suppose you are given 4 point:

     $$(t_1,y_1), (t_2, y_2), (t_3, y_3), (t_4, y_4).$$
     • Is it possible to interpolate these points by piece-wise cubic polynomial with continuous first,second and third derivatives?
     • Is it possible to interpolate these points by piece-wise cubic polynomial with continuous first,second, third and fourth derivatives?
     Please explain your reasoning as accurately as you can.

107. a

     Suppose that you would like to obtain a quadratic spline that interpolates the function $\cos(x)$ between the nodes 0, $1$ and $2$.

     1. Write down the form of the spline interpolation function. How many coefficients need to be determined?
     2. Write down the conditions that the spline must satisfy, and the corresponding equations for the coefficients. Do not solve the resulting equations.
     3. Are there enough conditions? If not, what extra condition(s) would you recommend to make a best possible fit of $\cos(x)$?

     b Given a function on a discrete set of $n$ data points. Explain the difference between interpolation and approximation. What Is the difference between an interpolating polynomial of degree $n-1$ and an approximating polynomial of the same degree $n-1$?

108. Is it possible to interpolate three points

     $$(x_1,y_1), (x_2,y_2), (x_3, y_3)$$
     by a second order piece wise continious quadratic polynomial with continious first and second derivatives?

     Is it possible to interpolate four points

     $$(x_1,y_1), (x_2,y_2), (x_3, y_3),(x_4,y_4),$$
     by a second order piece wise continious quadratic polynomial with continious first and second derivatives?

109. Suppose that you would like to obtain a quadratic spline that interpolates the function $\cos(x)$ between the nodes $[0,1,2]$.

     1. Write down the form of the spline interpolation function. How many coefficients need to be determined?
     2. Write down the conditions that the spline must satisfy, and the corresponding equations for the coefficients. Do not solve the resulting equations.
     3. Are there enough conditions? If not, what extra condition(s) would you recommend?

110. Suppose that you are given 4 experimental points: $(t_1,y_1), (t_2,y_2), (t_3,y_3), (t_4, y_4)$.

     Is it possible to interpolate these 4 data points by piecewise quadratic polynomial with knots at these given data points, such that interpolant is

     1. Once continuously differentialble?
     2. Twice continuously differentialble?
     3. Three times continuously differentialble?

     In each case, if the answer is “yes” explain why, and outline the procedure to find the interpolating function (you may use short form of the equations, do not solve the resulting equations); if the answer is “no”, explain why.

111. In class we have studied cubic splines, i.e. interpolation by a piece wise cubic polynomial with continious first and second derivative. It is possible to also introduce quadratic spline, i.e. piece wise quadratic polynomial with continious first derivative. Such qudratic spline is the focus of this problem.q

     Consider the same data:

     $$(0,3), (1,1), (2,3).$$

     Interpolate this data by piece wise quadratic polynomial with continious first and second derivative at a middle point.

     Extra Credit, 30 percent Suppose that one additional point is added to the above data, so that there are four points.

     $$(0,3), (1,1), (2,3), (3,9).$$

     Is it possible to interpolate this data by piece wise quadratic interpolation with continious first and second derivatives at the interior points? Is it possible to do it in general?

     Chapter SIX

112. In class we have studied quadrature rules of the form
     $$\int\limits_a^b f(x) d x \simeq \sum\limits_{i=0}^{n}w_i f(x_i).$$
     It appears that sometimes it is advantageous to derive quadratures which also use the derivatives of the function, in addition to value of the function at selected points. Find the weights for the quadrature
     $$\int\limits_{-1}^1f(x) d x \simeq \omega_1 f(-1) + \omega_2 f''(0) + \omega_3 f(1).$$

     Chose the weights $\omega_1,\omega_2,\omega_3$ to maximize the precision of the quadrature. What is the order of the resulting quadrature?

     Derive the error term of this quadrature.

113. In class we have studied quadrature rules of the form

     $$\int\limits_a^b f(x) d x \simeq \sum\limits_{i=0}^{n}w_i f(x_i).$$
     It appears that sometimes it is advantageous to derive quadratures which also use the derivatives of the function, in addition to value of the function at selected points. Find the weights for the quadrature
     $$\int\limits_{-1}^1f(x) d x \simeq \omega_1 f(-1) + \omega_2 f'(-1) + \omega_3 f'(1)+\omega_4 f(1).$$
     Chose the weights $\omega_1,\omega_2,\omega_3, \omega_4$ to maximize the precision of the quadrature. What is the order of the resulting quadrature?

     HINT Solution of this problem will be much easier if you guess the relationship between $\omega_1$, $\omega_2$, $\omega_3$ and $\omega_4$.

     Derive the error term of this quadrature.

114. Consider the qudrature rule of the form

     $$\int\limits_{0}^1 f(x) d x \simeq a f(\frac{1}{2}) + b f(1).$$

     Choose $a$ and $b$ to maximize the accuracy of the resulting quadrature. Calculate the truncation error of the resulting quadrature.

     Is it more accurate or less accurate than Midpoint quadrature?

115. Given the points $x_n,f(x_n)$:

     $$(0,3), (1,1), (2,0), (4,-2), (6,1).$$

     a) Evaluate the integral of the function using the midpoint rule

     b) Evaluate the integral using Simpson's rule

     c) Evaluate the integral using the trapezoid rule

116. (a) Consider the integration rule of the form

     $$\int\limits_{0}^{1} f(x) d x \simeq a_1 f(\frac{1}{3})+ a_2 f(\frac{2}{3}).$$
     Choose $a_1$ and $a_2$ to maximise the precision of this quadrature rule 16 points

     (b) Calculate truncation error of this quadrature.

117. This problem concerns using numerical methods to calculate the integral

     $$I=\int\limits_0^1 x^4 d x.$$
     Note that the exact value is $I =\frac{1}{5}.$

     We are going to compare different ways to calculate this integral by using the value of the function $f(x) = x^5$ on only three points, $x = 0$, $x=\frac{1}{2}$ and $x=1$.

     1. Using the composite trapezoidal rule, and 2 subintervals, find an approximate value for the integral. What is the error?
     2. Using the Simpson rule on an $[0:1]$ interval find the approximate value of this integral. What is the error?
     3. out of two methods used above, which one gives more accurate answer, and why? Make sure you justify your answer.
     4. Extra Credit 10 percent Do the errors you obtained with Simpson and composite trapezoid above agree with the predictions given by the theorems we studied in class?

118. Let us denote
     $$I = \int\limits_{-1}^{1}\cos(x) d x.$$

     As you know, we can calculate the value of this integral analytically:

     $$\int\limits_{-1}^{1}\cos(x) d x = 2 \sin (1)\simeq 1.6829419696157930133.$$

     Calculate the value of this integral numerically by using

     1. Modpoint method
     2. Trapezoid method
     3. Simpson method
     4. Two point Gauss quadrature

     Compare the result of your calculations with the exact value. Which of these four methods give the most accurate result? Is this consistent with your expectations?

119. (a) Consider the integration rule of the form

     $$\int\limits_{0}^{1} f(x) d x \simeq a_1 f(\frac{1}{2})+ a_2 f(\frac{3}{4}).$$
     Choose $a_1$ and $a_2$ to maximise the precision of this quadrature rule 16 points

     (b) Calculate truncation error of this quadrature.

120. Find 3-point Gaussian rule for $% \int_{0}^{1}F(x)dx,$ if the standard 3-point Gaussian rule is given by

     $$\int_{-1}^{1}g(x)dx\cong \frac{1}{9}\left( 5g(-\sqrt{3/5})+8g(0)+5g(\sqrt{3/5})\right)$$
     (b) The trapezoid rule has the error estimate
     $$\int_{a}^{a+h}g(x)dx=\frac{h}{2}\left[ g(a)+g(a+h)\right] -\frac{1}{12}% h^{3}g^{\prime \prime }(s)$$
     where $a<s<a+h.$ If interval $[a,b]$ is divided into $n$ equal panels, show that the error of the composite trapezoid rule is bounded by
     $$\frac{(b-a)^{3}}{12n^{2}}\max_{a\leq x\leq b}\left\vert g^{\prime \prime }(s)\right\vert$$
     (c) Use the result in part (b) to determine the number of panels sufficient to approximate $\int_{0}^{1}\sin xdx$ within to $\frac{1}{3} 10^{-4}$ by using the composite trapezoid rule.

121. (a) (10 points) In the three point quadrature rule

     $$\int_{-1}^{1} f (x) d x = a_1 f(x_1) + a_2 f(x_2) + a_3 f(x_3),$$
     choose $a_1$, $a_2$, $a_3$, $x_1$, $x_2$ and $x_3$ to maximize the precision of the quadrature rule. (The result will be three-point Gauss quadrature.)

     (b) (5 points)What is the degree of the resulting scheme? Demonstrate this by showing the scheme correctly integrates a polynomial of that degree, and that it does not integrate correctly the polynomial of the degree of one order higher.

122. Find $a_{1},a_{2},a_{3},x_1,x_2,x_3$ in

     $$\int\limits_{-1}^1 f(x) d x = a_1 f(x_1)+ a_2 f(x_2) + a_3 f(x_3)$$
     to maximize the precision of the quadrature. Find the error term of this quadrature.
123. In class we have studied the two point Gauss quadrature
     $$\int\limits_{-1}^{1}f(x)\simeq f(-\frac{1}{\sqrt{3}})+f(\frac{1}{\sqrt{3}}).$$
     Calculate the error term for this quadrature.

     Hint Derivation is similar to calculation of the trapezoid error term we did in class. You will need to express $f(\pm\frac{1}{\sqrt{3}})$ via $f(0)$ and its derivatives.

124. In class we have studied two point Gauss quadrature. In this problem you are to derive one point Gauss quadrature.

     Consider the qudrature rule of the form

     $$\int\limits_{-1}^1 f(x) d x \simeq a f(z).$$

     Choose $a$ and $z$ to maximize the order (accuracy) of the resulting quadrature. What is the truncation order of this quadrature?

125. Suppose that you have a tabular data, that is to say that the function $f(x)$ is given only on the $n$ equidistant points $x_i$, $i=1\dots n$ such that $x_1 = 0$, $x_n=1$. Propose a way to numerically evaluate
     $$g(x) = \int\limits_0^x f(x) d x.$$

     Chapter SEVEN

126. Find an $O(k^2)$ approximation of $y'(t_j)$ that utilizes $y(t_j)$, $y(t_{j+3})$, and $y(t_{j-1})$.
127. You are producing a final project for your Master's Degree and need to solve Initial Value Problem numerically. You prefer to have accurate numerical solution. Out of Forward Euler, Backward Euler, Trapezoidal, Heun (RK2), and Runge-Kutta (RK4) method, which method would you choose and why?

128. Consider RK2 (Heun's) method:

     $$k_{1}=f(x_{k},y_{k});\;k_{2}=f(x_{k}+h,y_{k}+hk_{1});\;y_{k+1}=y_{k}+\frac{h}{2}(k_{1}+k_{2}).$$
     Show that this method is second order accurate, i.e. it finds exact solution to the initial value problem
     $$y'(x)=2 x, y(x=0)=0.$$

     This can be done, for example, by showing that if at step $k$ the numerical solution is

     $$y_k = x_k^2,$$
     then at step $k+1$ the numerical solution is equal to
     $$y_{k+1} = (x_k+h)^2,$$
     which agrees with exact analytically solution
     $$y(x)=x^2.$$

129. Derive an $O(k^2)$ finite difference approximation to $y'(t_k)$ that uses $y(t_{j+1})$, $y(t_{j-1})$ and $y(t_{j+2})$. Calculate the truncation error term of the resulting finite difference approximation.

130. Find approximation of the first derivative $f'(x)$ that uses $f(x)$, $f(x+h)$ and $f(x-3 h)$. What is the error term of your approximation?

131. For the equation $y^{\prime }=f(y)$ consider the following numerical method

     $$k_{1}=f(y_{k});\;k_{2}=f(y_{k}+hk_{1});\;y_{k+1}=y_{k}+\frac{h}{2}% (k_{1}+k_{2})$$
     (a) Is this method explicit or implicit? Is it one-step or muti-step?
     (b) Perform one step of the method for the equation $y^{\prime }=\lambda y.$
     (c) Find the order of the method.

132. Consider the following $n$-step method for solving $y^{\prime }=f(y)$

     $$y_{k+1}=y_{k}+af(y_{k-1})+bf(y_{k+1})%$$ (17)

     1. What is the ”number of steps” $n$ for this method? Is this method explicit or implicit?
     2. Determine $a$ and $b$, for which the method has the highest possible accuracy.
     3. Determine the order of the method of the highest possible accuracy in (18).
     4. Determine the order of the method of the highest possible accuracy in (18).

        SOLUTION Method of undetermined coefficients, $f(x)=1$ is satisfied automatically, $f(x)=x$ gives $a+b = h$, $f(x)=x^2$ gives $a-b=-h/2$. Solving equations we get $a= h/4, b=3/4 h;$ second order accurate

133. Determine whether the method
     $$y_{k+1}=y_{k}+hf(t_{k},y_{k})+\frac{h^{2}}{2}\left[ \frac{\partia... ...{\partial t}+f(t_{k},y_{k})\frac{\partial f(t_{k},y_{k}% )}{\partial y}\right]$$
     with $h=0.1$ is stable for the equation $y^{\prime}=\lambda y$ with $\lambda=-30$.

134. Suppose you want to solve numerically $y'(t)=e^{-y(t)} + t^5,$ for $0<t<1$ using 100 time steps (so, $k=0.01$). The method to be tried are (i) the Euler method (ii) the backward Euler method (iii) the trapezoidal method (iv) the RK2 (Heun) method (v) the RK4 method.

     (a) Which method do you expect to finish the calculation the fastests? Why?

     (b) Which would be the second fastest method? Why?

     (c) Which would be the most accurate method? Why?

     (d) If stability is a concern, which method would be the best? Why?

135. This is general question. It is sufficient to give an answer with out proof.

     Consider the following initial value problem

     $$y'(t) = f(t,y(t)), y(t=0)=y_0.$$

     The following algorithm is proposed for its numerical solution:

     $$y_{n+1} = y_n + \frac{h}{2}\left[ f(t_n,y_n)+f(t_{n+1}, y_{n+1})\right].$$
     1. Define the term stability for a numerical algorithm in the context of initial value problems for ODE's.
     2. Determine if the above algorithm is stable, and if it is, what restrictions if any is implied on the size of step size $h$ for stability.
     3. List one advantage and one disadvantage of the above algorithm over the Euler method.

136. Consider the following initial value problem:

     $$y'(t) = t e^{-3 t} - y, y(0)=1, 0\le t\le 1, {\rm with} h=0.5$$

     Using the Euler method with $\Delta t = 0.5$ calculate $y(0.5)$ and $y(1)$ 10 pt.

     Is the proposed method numerically stable for the propsoed time step? 2 pt

     Extra credit - 2 pt compare the result with the exact analytical solution.

137. computer the solution of

     $$\frac{d y} { d t} = e^{-2 y} - 4 t^3$$
     for $0\le t\le 1$ using 100 time steps (i.e. with $h=0.01$). The methods to be tried are
     1. The 2nd order Taylor method
     2. RK4
     3. Trapezoid method
     .

     Please answer the following questions:

     1. Which one would you expect to complete the calculation the fastest? Why?
     2. Which one would you expect to complete the calculation last Why?
     3. Which one you expect to be more accurate? Why?
     4. If stability is a concern, which meshod should be used? Why?

138. Suppose you want to solve numerically $y'(t)=e^{-y(t)} + t^5,$ for $0<t<1$ using 100 time steps (so, $k=0.01$). The method to be tried are (i) the Euler method (ii) the backward Euler method (iii) the trapezoidal method (iv) the RK2 (Heun) method (v) the RK4 method.

     (a) Which method do you expect to finish the calculation the fastests? Why?

     (b) Which would be the second fastest method? Why?

     (c) Which would be the most accurate method? Why?

     (d) If stability is a concern, which method would be the best? Why?

139. IsHeun's method

     $$k_{1}=f(t_{k},y_{k});\;k_{2}=f(t_{k}+h,y_{k}+hk_{1});\;y_{k+1}=y_{k}+\frac{h}{2}(k_{1}+k_{2}),$$
     stable for the equation $y^{\prime }=-20y$ with $h=0.1$?

140. Consider RK2 (Heun's) method:

     $$k_{1}=f(t_{k},y_{k});\;k_{2}=f(t_{k}+h,y_{k}+hk_{1});\;y_{k+1}=y_{k}+\frac{h}{2}(k_{1}+k_{2}).$$
     Show that this method is second order accurate, i.e. it finds exact solution to the initial value problem
     $$y'(x)=frac{x}{2}, y(x=0)=0.$$

     This can be done, for example, by showing that if at step $k$ the numerical solution is

     $$y_k = x_k^2,$$
     then at step $k+1$ the numerical solution is equal to
     $$y_{k+1} = (x_k+h)^2,$$
     which agrees with exact analytically solution
     $$y(x)=x^2.$$

141. Consider the following initial value problem:

     $$y'(x) = 2 x y , y(0)=1.$$
     Using Taylor second order scheme, calculate $y(0.1)$ with $\Delta x= 0.1$ (i.e. calculate one time step).

     ( 4 points) Compare the result with the exact analytical solution.

142. State whether the following methods are (i) explicit or implicit (ii) single step or multi-step (iii) selfstarting or not. Cross out wrong statements and underline correct ones:
     $$y_{k+1} = y_k + \frac{h}{24}(55 y'_k - 59 y'_{k-1}- 9 y'_{k-3}),$$

     (i)explicit/implicit (ii)single step/multi-step (iii)selfstarting/not selfstarting.

     $$y_{k+1}=\frac{1}{11}(18 y_k - 9 y_{k-1} + 2 y_{k-2}) + \frac{6 h}{11}y'_{k+1}$$

     (i)explicit/implicit (ii)single step/multi-step (iii)selfstarting/not selfstarting.

     $$y_{k+1} = y_k + \frac{h}{2} (y'_{k}+ y'_{k+1})$$

     (i)explicit/implicit (ii)single step/multi-step (iii)selfstarting/not selfstarting.

143. The Bernoulli equation is
     $$y'(t)+y^3(t)=\frac{y(t)}{1+t}.$$
     1. If the Forward Euler method is used to solve this equation, what is the resulting finite difference equation (i.e. equation expressing $y_{k+1}$ through $y_k$)?
     2. If the trapezoid method is used to solve this equation, what is the resulting finite difference equation?
     3. If the RK2 method is used, what is the resulting finite difference equation?
     4. If the RK4 method is used, what is the resulting finite difference equation?

144. Consider the fourth order RK method:
     

     $$y_{n+1} = y_n + \frac{1}{6}(K_1+2K_2 + 2K_3 + K_4),$$ (18)

     $$t_{n+1} = x_n + h,$$ (19)

     $$K_1 = h f(x_n, y_n),$$ (20)

     $$K_2 = h f(x_n + \frac{1}{2}h, y_n+ \frac{1}{2}K_1),$$ (21)

     $$K_3 = h f(x_n+\frac{1}{2}h, y_n+\frac{1}{2}K_2),$$ (22)

     $$K_4 = h f(x_n+h, y_n+K_3).$$ (23)

     
     

     Apply this RK4 method for solving the equation

     $$y'(x) = 4 x^3,$$
     with initial condition
     $$y(x=0)=0,$$
     and show that the RK4 method is indeed at least fourth order accurate. This can be done, for example, by showing that if at step $k$ the numerical solution is
     $$y_k = x_k^4,$$
     then at step $k+1$ the numerical solution is equal to
     $$y_{k+1} = (x_k+h)^4,$$
     which agrees with exact analytically solution
     $$y(x)=x^4.$$

145. Consider the fourth order RK method:
     

     $$y_{n+1} = y_n + \frac{1}{6}(K_1+2K_2 + 2K_3 + K_4),$$ (24)

     $$t_{n+1} = t_n + h,$$ (25)

     $$K_1 = h f(t_n, y_n),$$ (26)

     $$K_2 = h f(t_n + \frac{1}{2}h, y_n+ \frac{1}{2}K_1),$$ (27)

     $$K_3 = h f(t_n+\frac{1}{2}h, y_n+\frac{1}{2}K_2),$$ (28)

     $$K_4 = h f(t_n+h, y_n+K_3).$$ (29)

     
     

     Apply this RK4 method for solving the equation

     $$y'(x) = y (x),$$
     and show that this method is indeed fourth order accurate. This can be done, for example, by computing an amplification factor and comparing it to the analytic value $e^h$.

     Chapter EIGHT

146. Set up the linear least squares problem for fitting the model
     $f(t,\mathbf{x})=x_{1}t+x_{2}e^{-t}$ to the four data points $(1,2)$, $(2,3)$, $(3,5)$, $(4,3)$.

147. Set up and solve the linear least squares system

     $$A x \simeq b$$
     for the fitting the model function
     $$f(t,x) = x_1 t + x_2 e^t, x=(x_1,x_2)^T$$
     to the three data points
     $$(1,2), (2,3), (3,5)$$

148. (a) Suppose you would like to fit the data points

     $$(-1,0), (0,1) {\rm and} (1,2)$$
     by the fitting function
     $$y(x) = a \cos(x) + b x^2.$$
     Find $a$ and $b$ by setting up a linear (overdetermined) least square problem and solving it.

     (b) Also calculate the residual.

149. Suppose you measure $x$ as a function of $t$ and you get the following:

     $t$	$x(t)$
     0	2
     1	1
     2	-2
     3	-1

     Suppose you would like to fit this data by

     $$x(t) = a \sin \left(\frac{\pi t}{2}\right) +b \cos \left(\frac{\pi t}{2}\right)$$
     Find $a$ and $b$ by setting up a linear (overdetermined) least square problem and solving it. Also calculate the residal.

150. Consider the data

     $$(1,2), (2, 3), (3, 4)$$

     Apporximate this data by a constant, i.e. find $x$ such that

     $$y(t) = x,$$

     is a good fit for this data.

     1. Use least square method. As we have shown in class the least square method minimizes the square of the second norm of a residual, i.e. $\vert\vert r\vert\vert^2_2$, where $r= (A x - b) .$
     2. Now minimize the fourth power of the fourth norm of a residual.
     3. Compare the results and explain the difference.

151. Suppose that an experiment produced the following data:
     $$(1,3), (2,2).$$
     You are to fit this data by using the linear fit
     $$y(t) = x \cdot t.$$

     a Calculate the value of $x$ which minimized the square of the second norm $\vert\vert r\vert\vert^2_2$ of the residual $r=A x - b.$

     b Calculate $r$ and $A x$. Sketch ${\rm Span}(A)$, $A x$, $b$ and $r$. Verify that $r\perp A x$. Is it so on your graph?

     c Extra-credit, 5 points Obtain equation for $x$ that minimizes $\vert\vert r\vert\vert^4_4$ instead of traditional $\vert r\vert^2_2$. Do not solve the resulting equation. What are the advantages and disadvantages of using $\vert\vert r\vert\vert^4_4$ instead of $\vert\vert r\vert\vert^2_2$?

152. Suppose that an experiment produced the following data:

     $$(1,3), (2,2).$$
     You are to fit this data by using the linear fit
     $$y(t) = x \cdot t.$$

     a Calculate the value of $x$ which minimized the square of the second norm $\vert\vert r\vert\vert^2_2$ of the residual $r=A x - b.$

     b Calculate $r$ and $A x$. Sketch ${\rm Span}(A)$, $A x$, $b$ and $r$. Verify that $r\perp A x$. Is it so on your graph?

     c Extra-credit, 5 points Obtain equation for $x$ that minimizes $\vert\vert r\vert\vert^4_4$ instead of traditional $\vert r\vert^2_2$. Do not solve the resulting equation. What are the advantages and disadvantages of using $\vert\vert r\vert\vert^4_4$ instead of $\vert\vert r\vert\vert^2_2$?

153. Let A be the $5\times 3$ identity matrix,
     $$A= \left(\begin{array}{ccc} 1 & 0 &0 \\ 0& 1& 0\\ 0& 0& 1\\ 0& 0& 0\\ 0& 0& 0 \end{array}\right).$$
     Let $b$ the vector
     $$b= \left(\begin{array}{c} b_1 \\ b_2 \\ b_3 \\ b_4 \\ b_5 \end{array}\right).$$

     Find the least squares solution of

     $$A x \tilde{=}b,$$
     and calculate the residual and its 2-norm.

154. Let A be the $m\times n$ identity matrix
     

     $$A=(a_{ij}), i = 1..m, j=1..n, \ a_{ij}=\left[\begin{array}{cc} 1 & i=j, \\ 0 & i\ne j. \end{array}\right.$$ (30)

     
     Furthermore, let
     $$b=[b_1, b_2, \dots, b_m]^{T}.$$
     Find the least squares solution of
     $$A x \tilde{=}b,$$
     and calculate the residual and its 2-norm.