diff --git a/Lectures_my/NumMet/Lecture5/mchrzasz.aux b/Lectures_my/NumMet/Lecture5/mchrzasz.aux index dc9b06f..28389db 100644 --- a/Lectures_my/NumMet/Lecture5/mchrzasz.aux +++ b/Lectures_my/NumMet/Lecture5/mchrzasz.aux @@ -46,19 +46,55 @@ \pgfsyspdfmark {pgfid9}{0}{0} \pgfsyspdfmark {pgfid10}{0}{0} \HyPL@Entry{3<>} -\pgfsyspdfmark {pgfid11}{23867907}{17900937} +\pgfsyspdfmark {pgfid14}{23867907}{17900937} \@writefile{nav}{\headcommand {\slideentry {0}{0}{4}{4/4}{}{0}}} \@writefile{nav}{\headcommand {\beamer@framepages {4}{4}}} -\pgfsyspdfmark {pgfid12}{0}{0} -\pgfsyspdfmark {pgfid13}{0}{0} -\HyPL@Entry{4<>} -\pgfsyspdfmark {pgfid14}{23867907}{17900937} -\@writefile{nav}{\headcommand {\slideentry {0}{0}{5}{5/5}{}{0}}} -\@writefile{nav}{\headcommand {\beamer@framepages {5}{5}}} \pgfsyspdfmark {pgfid15}{0}{0} \pgfsyspdfmark {pgfid16}{0}{0} -\@writefile{nav}{\headcommand {\beamer@partpages {1}{5}}} -\@writefile{nav}{\headcommand {\beamer@subsectionpages {1}{5}}} -\@writefile{nav}{\headcommand {\beamer@sectionpages {1}{5}}} -\@writefile{nav}{\headcommand {\beamer@documentpages {5}}} -\@writefile{nav}{\headcommand {\def \inserttotalframenumber {4}}} +\HyPL@Entry{4<>} +\pgfsyspdfmark {pgfid17}{23867907}{17900937} +\@writefile{nav}{\headcommand {\slideentry {0}{0}{5}{5/5}{}{0}}} +\@writefile{nav}{\headcommand {\beamer@framepages {5}{5}}} +\pgfsyspdfmark {pgfid18}{0}{0} +\pgfsyspdfmark {pgfid19}{0}{0} +\HyPL@Entry{5<>} +\pgfsyspdfmark {pgfid20}{23867907}{17900937} +\@writefile{nav}{\headcommand {\slideentry {0}{0}{6}{6/6}{}{0}}} +\@writefile{nav}{\headcommand {\beamer@framepages {6}{6}}} +\pgfsyspdfmark {pgfid21}{0}{0} +\pgfsyspdfmark {pgfid22}{0}{0} +\HyPL@Entry{6<>} +\pgfsyspdfmark {pgfid23}{23867907}{17900937} +\@writefile{nav}{\headcommand {\slideentry {0}{0}{7}{7/7}{}{0}}} +\@writefile{nav}{\headcommand {\beamer@framepages {7}{7}}} +\pgfsyspdfmark {pgfid24}{0}{0} +\pgfsyspdfmark {pgfid25}{0}{0} +\HyPL@Entry{7<>} +\pgfsyspdfmark {pgfid26}{23867907}{17900937} +\@writefile{nav}{\headcommand {\slideentry {0}{0}{8}{8/8}{}{0}}} +\@writefile{nav}{\headcommand {\beamer@framepages {8}{8}}} +\pgfsyspdfmark {pgfid27}{0}{0} +\pgfsyspdfmark {pgfid28}{0}{0} +\HyPL@Entry{8<>} +\pgfsyspdfmark {pgfid29}{23867907}{17900937} +\@writefile{nav}{\headcommand {\slideentry {0}{0}{9}{9/9}{}{0}}} +\@writefile{nav}{\headcommand {\beamer@framepages {9}{9}}} +\pgfsyspdfmark {pgfid30}{0}{0} +\pgfsyspdfmark {pgfid31}{0}{0} +\HyPL@Entry{9<>} +\pgfsyspdfmark {pgfid38}{23867907}{17900937} +\@writefile{nav}{\headcommand {\slideentry {0}{0}{10}{10/10}{}{0}}} +\@writefile{nav}{\headcommand {\beamer@framepages {10}{10}}} +\pgfsyspdfmark {pgfid39}{0}{0} +\pgfsyspdfmark {pgfid40}{0}{0} +\HyPL@Entry{10<>} +\pgfsyspdfmark {pgfid41}{23867907}{17900937} +\@writefile{nav}{\headcommand {\slideentry {0}{0}{11}{11/11}{}{0}}} +\@writefile{nav}{\headcommand {\beamer@framepages {11}{11}}} +\pgfsyspdfmark {pgfid42}{0}{0} +\pgfsyspdfmark {pgfid43}{0}{0} +\@writefile{nav}{\headcommand {\beamer@partpages {1}{11}}} +\@writefile{nav}{\headcommand {\beamer@subsectionpages {1}{11}}} +\@writefile{nav}{\headcommand {\beamer@sectionpages {1}{11}}} +\@writefile{nav}{\headcommand {\beamer@documentpages {11}}} +\@writefile{nav}{\headcommand {\def \inserttotalframenumber {10}}} diff --git a/Lectures_my/NumMet/Lecture5/mchrzasz.log b/Lectures_my/NumMet/Lecture5/mchrzasz.log index 4dc5e0a..85dfbfe 100644 --- a/Lectures_my/NumMet/Lecture5/mchrzasz.log +++ b/Lectures_my/NumMet/Lecture5/mchrzasz.log @@ -1,4 +1,4 @@ -This is XeTeX, Version 3.1415926-2.5-0.9999.3 (TeX Live 2013/Debian) (format=xelatex 2015.4.1) 15 SEP 2016 19:51 +This is XeTeX, Version 3.1415926-2.5-0.9999.3 (TeX Live 2013/Debian) (format=xelatex 2015.4.1) 16 SEP 2016 15:04 entering extended mode restricted \write18 enabled. %&-line parsing enabled. @@ -2789,9 +2789,12 @@ [4 ] -\c@framenumberappendix=\count443 +Overfull \hbox (22.23553pt too wide) in paragraph at lines 336--336 +[] + [] + File: images/BG_lower.png Graphic file (type QTm) - + Overfull \vbox (19.18185pt too high) has occurred while \output is active [] ................................................. @@ -2811,6 +2814,137 @@ [5 ] +File: images/BG_lower.png Graphic file (type QTm) + +Overfull \vbox (19.18185pt too high) has occurred while \output is active [] + +................................................. +. fontspec info: "no-scripts" +. +. Font Trebuchet MS does not contain any OpenType `Script' information. +................................................. +................................................. +. fontspec info: "defining-font" +. +. Font family 'TrebuchetMS(0)' created for font 'Trebuchet MS' with options +. [Mapping=tex-text,]. +. +. This font family consists of the following shapes: +................................................. + +[6 + +] +Overfull \hbox (22.23553pt too wide) in paragraph at lines 381--381 +[] + [] + +File: images/BG_lower.png Graphic file (type QTm) + +Overfull \vbox (19.18185pt too high) has occurred while \output is active [] + +................................................. +. fontspec info: "no-scripts" +. +. Font Trebuchet MS does not contain any OpenType `Script' information. +................................................. +................................................. +. fontspec info: "defining-font" +. +. Font family 'TrebuchetMS(0)' created for font 'Trebuchet MS' with options +. [Mapping=tex-text,]. +. +. This font family consists of the following shapes: +................................................. + +[7 + +] +File: images/BG_lower.png Graphic file (type QTm) + +Overfull \vbox (19.18185pt too high) has occurred while \output is active [] + +................................................. +. fontspec info: "no-scripts" +. +. Font Trebuchet MS does not contain any OpenType `Script' information. +................................................. +................................................. +. fontspec info: "defining-font" +. +. Font family 'TrebuchetMS(0)' created for font 'Trebuchet MS' with options +. [Mapping=tex-text,]. +. +. This font family consists of the following shapes: +................................................. + +[8 + +] +File: images/BG_lower.png Graphic file (type QTm) + +Overfull \vbox (19.18185pt too high) has occurred while \output is active [] + +................................................. +. fontspec info: "no-scripts" +. +. Font Trebuchet MS does not contain any OpenType `Script' information. +................................................. +................................................. +. fontspec info: "defining-font" +. +. Font family 'TrebuchetMS(0)' created for font 'Trebuchet MS' with options +. [Mapping=tex-text,]. +. +. This font family consists of the following shapes: +................................................. + +[9 + +] +File: images/BG_lower.png Graphic file (type QTm) + +Overfull \vbox (19.18185pt too high) has occurred while \output is active [] + +................................................. +. fontspec info: "no-scripts" +. +. Font Trebuchet MS does not contain any OpenType `Script' information. +................................................. +................................................. +. fontspec info: "defining-font" +. +. Font family 'TrebuchetMS(0)' created for font 'Trebuchet MS' with options +. [Mapping=tex-text,]. +. +. This font family consists of the following shapes: +................................................. + +[10 + +] +\c@framenumberappendix=\count443 +File: images/BG_lower.png Graphic file (type QTm) + +Overfull \vbox (19.18185pt too high) has occurred while \output is active [] + +................................................. +. fontspec info: "no-scripts" +. +. Font Trebuchet MS does not contain any OpenType `Script' information. +................................................. +................................................. +. fontspec info: "defining-font" +. +. Font family 'TrebuchetMS(0)' created for font 'Trebuchet MS' with options +. [Mapping=tex-text,]. +. +. This font family consists of the following shapes: +................................................. + +[11 + +] \tf@nav=\write10 \openout10 = `mchrzasz.nav'. @@ -2820,23 +2954,23 @@ \tf@snm=\write12 \openout12 = `mchrzasz.snm'. -Package atveryend Info: Empty hook `BeforeClearDocument' on input line 317. -Package atveryend Info: Empty hook `AfterLastShipout' on input line 317. +Package atveryend Info: Empty hook `BeforeClearDocument' on input line 473. +Package atveryend Info: Empty hook `AfterLastShipout' on input line 473. (./mchrzasz.aux) -Package atveryend Info: Empty hook `AtVeryEndDocument' on input line 317. -Package atveryend Info: Empty hook `AtEndAfterFileList' on input line 317. +Package atveryend Info: Empty hook `AtVeryEndDocument' on input line 473. +Package atveryend Info: Empty hook `AtEndAfterFileList' on input line 473. Package logreq Info: Writing requests to 'mchrzasz.run.xml'. \openout1 = `mchrzasz.run.xml'. -Package atveryend Info: Empty hook `AtVeryVeryEnd' on input line 317. +Package atveryend Info: Empty hook `AtVeryVeryEnd' on input line 473. ) Here is how much of TeX's memory you used: - 48224 strings out of 493918 - 946991 string characters out of 6150564 - 1284926 words of memory out of 5000000 - 50521 multiletter control sequences out of 15000+600000 - 29364 words of font info for 122 fonts, out of 8000000 for 9000 + 48315 strings out of 493918 + 949535 string characters out of 6150564 + 1291951 words of memory out of 5000000 + 50611 multiletter control sequences out of 15000+600000 + 29372 words of font info for 123 fonts, out of 8000000 for 9000 1144 hyphenation exceptions out of 8191 - 61i,17n,73p,10479b,1432s stack positions out of 5000i,500n,10000p,200000b,80000s + 61i,21n,73p,10479b,1450s stack positions out of 5000i,500n,10000p,200000b,80000s -Output written on mchrzasz.pdf (5 pages). +Output written on mchrzasz.pdf (11 pages). diff --git a/Lectures_my/NumMet/Lecture5/mchrzasz.nav b/Lectures_my/NumMet/Lecture5/mchrzasz.nav index 84d00f5..7f72c1d 100644 --- a/Lectures_my/NumMet/Lecture5/mchrzasz.nav +++ b/Lectures_my/NumMet/Lecture5/mchrzasz.nav @@ -10,8 +10,20 @@ \headcommand {\beamer@framepages {4}{4}} \headcommand {\slideentry {0}{0}{5}{5/5}{}{0}} \headcommand {\beamer@framepages {5}{5}} -\headcommand {\beamer@partpages {1}{5}} -\headcommand {\beamer@subsectionpages {1}{5}} -\headcommand {\beamer@sectionpages {1}{5}} -\headcommand {\beamer@documentpages {5}} -\headcommand {\def \inserttotalframenumber {4}} +\headcommand {\slideentry {0}{0}{6}{6/6}{}{0}} +\headcommand {\beamer@framepages {6}{6}} +\headcommand {\slideentry {0}{0}{7}{7/7}{}{0}} +\headcommand {\beamer@framepages {7}{7}} +\headcommand {\slideentry {0}{0}{8}{8/8}{}{0}} +\headcommand {\beamer@framepages {8}{8}} +\headcommand {\slideentry {0}{0}{9}{9/9}{}{0}} +\headcommand {\beamer@framepages {9}{9}} +\headcommand {\slideentry {0}{0}{10}{10/10}{}{0}} +\headcommand {\beamer@framepages {10}{10}} +\headcommand {\slideentry {0}{0}{11}{11/11}{}{0}} +\headcommand {\beamer@framepages {11}{11}} +\headcommand {\beamer@partpages {1}{11}} +\headcommand {\beamer@subsectionpages {1}{11}} +\headcommand {\beamer@sectionpages {1}{11}} +\headcommand {\beamer@documentpages {11}} +\headcommand {\def \inserttotalframenumber {10}} diff --git a/Lectures_my/NumMet/Lecture5/mchrzasz.pdf b/Lectures_my/NumMet/Lecture5/mchrzasz.pdf index 61d722f..d42ceb3 100644 --- a/Lectures_my/NumMet/Lecture5/mchrzasz.pdf +++ b/Lectures_my/NumMet/Lecture5/mchrzasz.pdf Binary files differ diff --git a/Lectures_my/NumMet/Lecture5/mchrzasz.synctex.gz b/Lectures_my/NumMet/Lecture5/mchrzasz.synctex.gz index 5416ac4..2af2a4f 100644 --- a/Lectures_my/NumMet/Lecture5/mchrzasz.synctex.gz +++ b/Lectures_my/NumMet/Lecture5/mchrzasz.synctex.gz Binary files differ diff --git a/Lectures_my/NumMet/Lecture5/mchrzasz.tex b/Lectures_my/NumMet/Lecture5/mchrzasz.tex index 7a7029b..1e04770 100644 --- a/Lectures_my/NumMet/Lecture5/mchrzasz.tex +++ b/Lectures_my/NumMet/Lecture5/mchrzasz.tex @@ -206,7 +206,7 @@ \author{ {\fontspec{Trebuchet MS}Marcin Chrz\k{a}szcz, Danny van Dyk} (UZH)} \institute{UZH} -\title[Linear equation systems I]{Linear equation systems I} +\title[Linear equation systems: exact methods]{Linear equation systems:exact methods} \date{21 September 2016} @@ -220,7 +220,7 @@ \begin{center} \begin{columns} \begin{column}{0.9\textwidth} - \flushright\fontspec{Trebuchet MS}\bfseries \Huge {Linear equation \\systems I} + \flushright\fontspec{Trebuchet MS}\bfseries \Huge {Linear equation systems: exact methods} \end{column} \begin{column}{0.2\textwidth} %\includegraphics[width=\textwidth]{SHiP-2} @@ -290,13 +290,172 @@ \Vert A \Vert_2 &= \sqrt{\rho(A^T A)}\\ \rho(M) &= \max \lbrace \vert\lambda_i \vert: \det{M- \lambda I} =0,~i=1,...n \rbrace \end{align*} +where $\rho(M)$ - spectral radios of $M$ matrix, $I$ unit matrix, $\lambda_i$ eigenvalues of $M$.\\ +\ARROW Row norm: +\begin{align*} +\Vert A \Vert_{\infty} &= \max_{1 \leq i \leq n} \sum_{j=1}^n \vert a_{i,j} \vert, +\end{align*} +\begin{exampleblock}{Digression:} +\ARROWR Calculation of the matrix norms are not a simple process at all. There are certain class of matrices that make the calculations easier.\\ +\ARROWR The spectral norm can be also defined: +\begin{align*} +cond_2(A) = \frac{\max_{1\leq i \leq n}\vert \lambda_i \vert }{\min_{1\leq i \leq n}\vert \lambda_i \vert }, +\end{align*} +\end{exampleblock} + +\end{small} +\end{frame} + + +\begin{frame}\frametitle{Example, ill-conditioned matrix} +\begin{small} +\ARROW The text-book example of wrongly conditioned matrix is the Hilbert matrix: +\begin{align*} +h_{i,j} = \frac{1}{i+j-1} +\end{align*} +\ARROWR Example: +\begin{align*} +h_{i,j}^{4 \times 4} = \begin{pmatrix} +1 & \frac{1}{2} & \frac{1}{3} & \frac{1}{4} \\ +\frac{1}{2} & \frac{1}{3} & \frac{1}{4} & \frac{1}{5} \\ +\frac{1}{3} & \frac{1}{4} & \frac{1}{5} & \frac{1}{6}\\ +\frac{1}{4} & \frac{1}{5} & \frac{1}{6} & \frac{1}{7} +\end{pmatrix} +\end{align*} +\ARROW The condition of this matrix: +\begin{align*} +cond(A)=\mathcal{O}\left(\frac{e^{3.52N}}{\sqrt{N}}\right) +\end{align*} +\ARROW For $8 \times 8$ matrix we get: +\begin{align*} +cond_1(A)=3.387\cdot 10^{10},~~~cond_2(A)=1.526\cdot 10^{10},~~~~~cond_{\infty}(A)=3.387\cdot 10^{10} +\end{align*} +\ARROW Clearly large numbers ;) +\end{small} +\end{frame} + +\begin{frame}\frametitle{Exact methods: Cramer method} +\begin{small} +\ARROW If $\det{A} \neq 0$ then the solutions are given by: +\begin{align*} +x_i =\frac{\det{A_i}}{\det{A}} +\end{align*} +\ARROW So calculate the solutions one needs to calculate $n+1$ determinants. To calculate each determinate one needs $(n-1)n!$ multiplications. \\ +\ARROW Putting it all together one needs $(n+1)(n-1)n! = n^{n+2}$ \\ +\ARROW Brutal force but works ;) \end{small} \end{frame} + + + +\begin{frame}\frametitle{Example, ill-conditioned matrix} +\begin{small} +\ARROW The text-book example of wrongly conditioned matrix is the Hilbert matrix: +\begin{align*} +h_{i,j} = \frac{1}{i+j-1} +\end{align*} +\ARROWR Example: +\begin{align*} +h_{i,j}^{4 \times 4} = \begin{pmatrix} +1 & \frac{1}{2} & \frac{1}{3} & \frac{1}{4} \\ +\frac{1}{2} & \frac{1}{3} & \frac{1}{4} & \frac{1}{5} \\ +\frac{1}{3} & \frac{1}{4} & \frac{1}{5} & \frac{1}{6}\\ +\frac{1}{4} & \frac{1}{5} & \frac{1}{6} & \frac{1}{7} +\end{pmatrix} +\end{align*} +\ARROW The condition of this matrix: +\begin{align*} +cond(A)=\mathcal{O}\left(\frac{e^{3.52N}}{\sqrt{N}}\right) +\end{align*} +\ARROW For $8 \times 8$ matrix we get: +\begin{align*} +cond_1(A)=3.387\cdot 10^{10},~~~cond_2(A)=1.526\cdot 10^{10},~~~~~cond_{\infty}(A)=3.387\cdot 10^{10} +\end{align*} +\ARROW Clearly large numbers ;) +\end{small} +\end{frame} + +\begin{frame}\frametitle{Exact methods: Cramer method} +\begin{small} +\ARROW If $\det{A} \neq 0$ then the solutions are given by: +\begin{align*} +x_i =\frac{\det{A_i}}{\det{A}} +\end{align*} +\ARROW So calculate the solutions one needs to calculate $n+1$ determinants. To calculate each determinate one needs $(n-1)n!$ multiplications. \\ +\ARROW Putting it all together one needs $(n+1)(n-1)n! = n^{n+2}$ \\ +\ARROW Brutal force but works ;) + + +\end{small} +\end{frame} + + + + + +\begin{frame}\frametitle{Exact methods: Gauss method} +\begin{small} + +\ARROW The idea besides the Gauss method is simple: transform the $A x =b$ to get the equvalent matrix $A^{\left[n\right]} x = b^{\left[n\right]}$ where $A^{\left[n\right]}$ is triangular matrix: +\begin{align*} +A^{\left[n\right]} = \begin{pmatrix} +a^{\left[n\right]}_{11} & a^{\left[n\right]_{12}} & ... & a^{\left[n\right]}_{1n}\\ +0 & a^{\left[n\right]}_{22} & ... & a^{\left[n\right]}_{2n} \\ +...\\ +0 & 0 & ... & a^{\left[n\right]}_{nn} \\ +\end{pmatrix} +\end{align*} +\ARROWR The algorithm: +\ARROW To do so we calculate the: $d^{\left[1\right]}_{i,1}=\frac{a^{\left[1\right]}_{i1}}{a^{\left[1\right]}_{11}}$ \\ +\ARROW The first row multiplied by the $d^{\left[1\right]}_{i,1}$ we subtract from the $i^{th}$ row. +\ARROW After this we get: + +\begin{align*} +\begin{pmatrix} +a^{\left[ 1 \right]}_{11} & a^{\left[ 1 \right]_{12}} & ... & a^{\left[ 1 \right]}_{1n}\\ +0 & a^{\left[ 1 \right]}_{22} & ... & a^{\left[ 1 \right]}_{2n} \\ +...\\ +0 & a^{\left[ 1 \right]}_{n2} & ... & a^{\left[ 1 \right]}_{nn} \\ +\end{pmatrix} \overrightarrow{x}= +\begin{pmatrix} +b^{\left[ 1 \right]}_{1} \\ +b^{\left[ 1 \right]}_{1} \\ +... \\ +b^{\left[ 1 \right]}_{1} \\ +\end{pmatrix} +\end{align*} + +\end{small} +\end{frame} + + + +\begin{frame}\frametitle{Exact methods: Gauss method 2} +\begin{small} + +\ARROW Now one needs to repeat the above n times moving each time row down. +\begin{alertblock}{Cons:} +\ARROW The algoright can be stooped if you divide by zero.\\ +\ARROW The method is very efficient to accumulate numerical errors. +\end{alertblock} + +\begin{exampleblock}{Pros:} +\ARROWR The number of needed floating point operations is less then Cramer.\\ +\ARROWR Example for 15 equations: $1345$ vs $5 \cdot 10^{12}$. +\end{exampleblock} + +\end{small} +\end{frame} + + + + + \backupbegin \begin{frame}\frametitle{Backup} @@ -310,8 +469,5 @@ - - - \backupend \end{document}