% vim: set ts=2 sw=2 et tw=80: \documentclass[12pt,a4paper]{article} \usepackage[utf8]{inputenc} \usepackage[margin=2cm]{geometry} \usepackage{amstext} \usepackage{amsmath} \usepackage{array} \newcommand{\lra}{\Leftrightarrow} \title{Howework 5 -- Introduction to Computational Science} \author{Claudio Maggioni} \begin{document} \maketitle \section*{Question 1} Given the definition of degree of exactness being the highest polynomial degree $n$ at which a quadrature, for every polynomial of degree $n$, produces exactly the same polynomial, these are the proofs. \subsection*{Midpoint rule} All polynomials of degree 1 can be expressed as: \[p_1(x) = a_1 \cdot x + a_0\] Therefore their integral is: \[\int_0^1 a_1 \cdot x + a_0 dx = \frac{a_1}{2} + a_0\] The midpoint rule for $p_1(x)$ is \[f\left(\frac{1}{2}\right) \cdot 1 = \frac{a_1}{2} + a_0 = \int_0^1 a_1 \cdot x + a_0 dx\] Therefore the midpoint rule has a degree of exactness of at least 1. It is easy to show that the degree of exactness is not higher than 1 by considering the degree 2 polynomial $x^2$, which has an integral in $[0, 1]$ of $\frac{1}{3}$ but a midpoint rule quadrature of $\frac{1}{4}$. \subsection*{Trapezoidal rule} The proof is similar to the one for the midpoint rule, but with this quadrature for degree 1 polynomials: \[\frac{f(0)}{2} + \frac{f(1)}{2} = \frac{a_0 + a_1 + a_0}{2} = \frac{a_1}{2} + a_0\] Which is again equal to the general integral for these polynomials. Again $x^2$ is a degree 2 polynomial with integral $\frac{1}{3}$ but a midpoint quadrature of $\frac{0 + 1}{2} = \frac{1}{2}$, thus bounding the degree of exactness to 1. \subsection*{Simpson rule} The proof is again similar, but for degree 3 polynomials which can all be written as: \[p_3(x) = a_3 x^3 + a_2 x^2 + a_1 x + a_0\] The integral is: \[\int_0^1p_3(x) dx = \frac{a_3}{4} + \frac{a_2}{3} + \frac{a_1}{2} + a_0\] The Simpson rule gives: \[\frac{1}{6} \cdot f(0) + \frac{4}{6}\cdot f\left(\frac{1}{2}\right) + \frac{1}{6} \cdot f(1) = \frac{1}{6} a_0 + \frac{4}{6} \left(\frac{a_3}{8} + \frac{a_2}{4} + \frac{a_1}{2} + a_0\right) + \]\[\frac{1}{6} \left(a_3 + a_2 + a_1 + a_0\right) = \frac{a_3}{4} + \frac{a_2}{3} + \frac{a_1}{2} + a_0 = \int_0^1 p_3(x)dx\] Which tells us that the degree of exactness is at least 1. We can bound the degree of exactness to 3 with the 4th degree polynomial $x^4$ which has integral in $[0, 1]$ of $\frac{1}{5}$ but has a quadrature of $\frac{1}{6} \cdot 0 + \frac{2}{3} \cdot \frac{1}{16} + \frac{1}{6} \cdot 1 = \frac{5}{24}$. \section*{Question 2} The algebraic solution is: \[\int_0^1 1 - 4(x - 0.5)^2 dx = 1 - 4 \cdot \int_0^1 x^2 - x + \frac14 = 1 - 4 \left(\frac{4-6+3}{12}\right) = 1 - \frac13 = \frac23\] The solution using quadrature is: \[Q = \frac{1}{2} (f(0) + f(1)) = \frac{1}{2}(0 + 0) = 0 \qquad (x, h) = \left(\frac{1}{2}, \frac{1}{2}\right) \qquad \epsilon = \frac{1}{10}\] \[E\left(\frac{1}{2}, \frac12\right) = f\left(\frac12\right) - \frac12\left(f(0) + f(1)\right) = 1 > \frac1{10} \qquad Q = 0 + \frac12 \cdot 1 = \frac12\] \[E\left(\frac{1}{4}, \frac14\right) = f\left(\frac14\right) - \frac12\left(f(0) + f\left(\frac12\right)\right) = \frac34 - \frac12 = \frac14 > \frac1{10} \qquad Q = \frac12 + \frac14 \cdot \frac14 = \frac9{16}\] \[E\left(\frac{3}{4}, \frac14\right) = f\left(\frac34\right) - \frac12\left(f\left(\frac12\right) + f(1)\right) = \frac14 > \frac1{10} \qquad Q = \frac9{16} + \frac14 \cdot \frac14 = \frac{10}{16}\] \[E\left(\frac18, \frac18\right) = f\left(\frac18\right) - \frac12\left(f\left(0\right) + f\left(\frac14\right)\right) = \frac7{16} - \frac12 \cdot \frac34 = \frac1{16} < \frac1{10}\] \[E\left(\frac38, \frac18\right) = f\left(\frac38\right) - \frac12\left(f\left(\frac14\right) + f\left(\frac12\right)\right) = \frac{15}{16} - \frac12 \cdot \frac74 = \frac1{16} < \frac1{10}\] \[E\left(\frac58, \frac18\right) = f\left(\frac58\right) - \frac12\left(f\left(\frac12\right) + f\left(\frac34\right)\right) = \frac{15}{16} - \frac12 \cdot \frac74 = \frac1{16} < \frac1{10}\] \[E\left(\frac78, \frac18\right) = f\left(\frac78\right) - \frac12\left(f\left(\frac34\right) + f\left(1\right)\right) = \frac7{16} - \frac12 \cdot \frac34 = \frac1{16} < \frac1{10}\] Thus the solution using quadrature is $\frac{5}{8}$. \section*{Question 4} \[\begin{bmatrix} x_0^2 & x_0 & 1 \\x_1^2 & x_1 & 1 \\x_2^2 & x_2 & 1 \\x_3^2 & x_3 & 1 \end{bmatrix} \begin{bmatrix}a \\b\\c\\\end{bmatrix} = \begin{bmatrix} y_0 \\y_1\\y_2\\y_3\\\end{bmatrix}\] \[\begin{bmatrix} x_0^2 & x_1^2 & x_2^2 & x_3^2 \\ x_0 & x_1 & x_2 & x_3 \\ 1&1&1&1\end{bmatrix} \begin{bmatrix} x_0^2 & x_0 & 1 \\x_1^2 & x_1 & 1 \\x_2^2 & x_2 & 1 \\x_3^2 & x_3 & 1 \end{bmatrix} \begin{bmatrix}a \\b\\c\\\end{bmatrix} = \begin{bmatrix} x_0^2 & x_1^2 & x_2^2 & x_3^2 \\ x_0 & x_1 & x_2 & x_3 \\ 1&1&1&1\end{bmatrix} \begin{bmatrix} y_0 \\y_1\\y_2\\y_3\\\end{bmatrix}\] \[\begin{bmatrix}18&8&6\\8&6&2\\6&2&4\\\end{bmatrix}\begin{bmatrix}a\\b\\c\\\end{bmatrix}=\begin{bmatrix}2\\0\\2\\\end{bmatrix}\] We now use Gaussian \textit{ellimination} to solve the system: \[ \begin{array}{@{}ccc|c@{}} 18&8&6&2\\ 8&6&2&0\\ 6&2&4&2\\ \end{array} \qquad \begin{array}{@{}ccc|c@{}} 1&\frac49 &\frac13 & \frac19\\ 8& 6& 2 &0\\ 6 &2 &4 &2\\ \end{array} \qquad \begin{array}{@{}ccc|c@{}} 1& \frac49& \frac13& \frac19\\ 0& \frac{22}9& \frac{-2}3& \frac{-8}9\\ 0& \frac{-2}3& 2& \frac43\\ \end{array} \qquad \begin{array}{@{}ccc|c@{}} 1& \frac49& \frac13& \frac19\\ 0 &1 &\frac{-3}{11} & \frac{-4}{11}\\ 0 & \frac{-2}{3} & 2 & \frac43\\ \end{array} \]\[ \begin{array}{@{}ccc|c@{}} 1& 0& \frac5{11} &\frac3{11}\\ 0 &1 &\frac{-3}{11}&\frac{-4}{11}\\ 0 &0 &\frac{20}{11}&\frac{12}{11}\\ \end{array} \qquad \begin{array}{@{}ccc|c@{}} 1& 0 &\frac5{11} & \frac{3}{11}\\ 0 &1 & \frac{-3}{11} & \frac{-4}{11}\\ 0& 0& 1 &\frac35\\ \end{array} \qquad \begin{array}{@{}ccc|c@{}} 1 &0 &0 &0\\ 0& 1 &0 &\frac{-1}5\\ 0& 0& 1 &\frac35\\ \end{array} \qquad \begin{bmatrix}a\\b\\c\\\end{bmatrix}=\begin{bmatrix}0\\-\frac15\\\frac35\\\end{bmatrix} \] \section*{Question 5} \[\begin{bmatrix}1&0\\0&1\\-1&0\\0&-1\\1&0\\\end{bmatrix}\begin{bmatrix}a\\b\end{bmatrix} = \begin{bmatrix}\frac32\\2\\-\frac12\\-2\\1\end{bmatrix}\] \[\begin{bmatrix}1&0&-1&0&1\\0&1&0&-1&0\end{bmatrix}\begin{bmatrix}1&0\\0&1\\-1&0\\0&-1\\1&0\\\end{bmatrix}\begin{bmatrix}a\\b\end{bmatrix} = \begin{bmatrix}1&0&-1&0&1\\0&1&0&-1&0\end{bmatrix}\begin{bmatrix}\frac32\\2\\-\frac12\\-2\\1\end{bmatrix}\] \[\begin{bmatrix}3&0\\0&2\end{bmatrix}\begin{bmatrix}a\\b\end{bmatrix} = \begin{bmatrix}3\\2\end{bmatrix} \qquad \begin{bmatrix}a\\b\end{bmatrix} = \begin{bmatrix}1\\1\end{bmatrix}\] \end{document}