diff --git a/Lectures_my/NumMet/Lecture5/mchrzasz.aux b/Lectures_my/NumMet/Lecture5/mchrzasz.aux index 28389db..8f14db5 100644 --- a/Lectures_my/NumMet/Lecture5/mchrzasz.aux +++ b/Lectures_my/NumMet/Lecture5/mchrzasz.aux @@ -93,8 +93,56 @@ \@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}}} +\HyPL@Entry{11<>} +\pgfsyspdfmark {pgfid44}{23867907}{17900937} +\@writefile{nav}{\headcommand {\slideentry {0}{0}{12}{12/12}{}{0}}} +\@writefile{nav}{\headcommand {\beamer@framepages {12}{12}}} +\pgfsyspdfmark {pgfid45}{0}{0} +\pgfsyspdfmark {pgfid46}{0}{0} +\HyPL@Entry{12<>} +\pgfsyspdfmark {pgfid47}{23867907}{17900937} +\@writefile{nav}{\headcommand {\slideentry {0}{0}{13}{13/13}{}{0}}} +\@writefile{nav}{\headcommand {\beamer@framepages {13}{13}}} +\pgfsyspdfmark {pgfid48}{0}{0} +\pgfsyspdfmark {pgfid49}{0}{0} +\HyPL@Entry{13<>} +\pgfsyspdfmark {pgfid50}{23867907}{17900937} +\@writefile{nav}{\headcommand {\slideentry {0}{0}{14}{14/14}{}{0}}} +\@writefile{nav}{\headcommand {\beamer@framepages {14}{14}}} +\pgfsyspdfmark {pgfid51}{0}{0} +\pgfsyspdfmark {pgfid52}{0}{0} +\HyPL@Entry{14<>} +\pgfsyspdfmark {pgfid53}{23867907}{17900937} +\@writefile{nav}{\headcommand {\slideentry {0}{0}{15}{15/15}{}{0}}} +\@writefile{nav}{\headcommand {\beamer@framepages {15}{15}}} +\pgfsyspdfmark {pgfid54}{0}{0} +\pgfsyspdfmark {pgfid55}{0}{0} +\HyPL@Entry{15<>} +\pgfsyspdfmark {pgfid56}{23867907}{17900937} +\@writefile{nav}{\headcommand {\slideentry {0}{0}{16}{16/16}{}{0}}} +\@writefile{nav}{\headcommand {\beamer@framepages {16}{16}}} +\pgfsyspdfmark {pgfid57}{0}{0} +\pgfsyspdfmark {pgfid58}{0}{0} +\HyPL@Entry{16<>} +\pgfsyspdfmark {pgfid59}{23867907}{17900937} +\@writefile{nav}{\headcommand {\slideentry {0}{0}{17}{17/17}{}{0}}} +\@writefile{nav}{\headcommand {\beamer@framepages {17}{17}}} +\pgfsyspdfmark {pgfid60}{0}{0} +\pgfsyspdfmark {pgfid61}{0}{0} +\HyPL@Entry{17<>} +\pgfsyspdfmark {pgfid62}{23867907}{17900937} +\@writefile{nav}{\headcommand {\slideentry {0}{0}{18}{18/18}{}{0}}} +\@writefile{nav}{\headcommand {\beamer@framepages {18}{18}}} +\pgfsyspdfmark {pgfid63}{0}{0} +\pgfsyspdfmark {pgfid64}{0}{0} +\HyPL@Entry{18<>} +\pgfsyspdfmark {pgfid65}{23867907}{17900937} +\@writefile{nav}{\headcommand {\slideentry {0}{0}{19}{19/19}{}{0}}} +\@writefile{nav}{\headcommand {\beamer@framepages {19}{19}}} +\pgfsyspdfmark {pgfid66}{0}{0} +\pgfsyspdfmark {pgfid67}{0}{0} +\@writefile{nav}{\headcommand {\beamer@partpages {1}{19}}} +\@writefile{nav}{\headcommand {\beamer@subsectionpages {1}{19}}} +\@writefile{nav}{\headcommand {\beamer@sectionpages {1}{19}}} +\@writefile{nav}{\headcommand {\beamer@documentpages {19}}} +\@writefile{nav}{\headcommand {\def \inserttotalframenumber {18}}} diff --git a/Lectures_my/NumMet/Lecture5/mchrzasz.log b/Lectures_my/NumMet/Lecture5/mchrzasz.log index 85dfbfe..79791ea 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) 16 SEP 2016 15:04 +This is XeTeX, Version 3.1415926-2.5-0.9999.3 (TeX Live 2013/Debian) (format=xelatex 2015.4.1) 18 SEP 2016 14:43 entering extended mode restricted \write18 enabled. %&-line parsing enabled. @@ -2923,7 +2923,6 @@ [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 [] @@ -2945,6 +2944,181 @@ [11 ] +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: +................................................. + +[12 + +] +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: +................................................. + +[13 + +] +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: +................................................. + +[14 + +] +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: +................................................. + +[15 + +] +LaTeX Font Info: External font `plex10' loaded for size +(Font) <9> on input line 626. + +Overfull \vbox (7.86516pt too high) detected at line 626 + [] + +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: +................................................. + +[16 + +] +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: +................................................. + +[17 + +] +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: +................................................. + +[18 + +] +\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: +................................................. + +[19 + +] \tf@nav=\write10 \openout10 = `mchrzasz.nav'. @@ -2954,23 +3128,23 @@ \tf@snm=\write12 \openout12 = `mchrzasz.snm'. -Package atveryend Info: Empty hook `BeforeClearDocument' on input line 473. -Package atveryend Info: Empty hook `AfterLastShipout' on input line 473. +Package atveryend Info: Empty hook `BeforeClearDocument' on input line 680. +Package atveryend Info: Empty hook `AfterLastShipout' on input line 680. (./mchrzasz.aux) -Package atveryend Info: Empty hook `AtVeryEndDocument' on input line 473. -Package atveryend Info: Empty hook `AtEndAfterFileList' on input line 473. +Package atveryend Info: Empty hook `AtVeryEndDocument' on input line 680. +Package atveryend Info: Empty hook `AtEndAfterFileList' on input line 680. Package logreq Info: Writing requests to 'mchrzasz.run.xml'. \openout1 = `mchrzasz.run.xml'. -Package atveryend Info: Empty hook `AtVeryVeryEnd' on input line 473. +Package atveryend Info: Empty hook `AtVeryVeryEnd' on input line 680. ) Here is how much of TeX's memory you used: - 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 + 48417 strings out of 493918 + 951770 string characters out of 6150564 + 1294951 words of memory out of 5000000 + 50705 multiletter control sequences out of 15000+600000 + 33281 words of font info for 136 fonts, out of 8000000 for 9000 1144 hyphenation exceptions out of 8191 - 61i,21n,73p,10479b,1450s stack positions out of 5000i,500n,10000p,200000b,80000s + 61i,21n,73p,10479b,1474s stack positions out of 5000i,500n,10000p,200000b,80000s -Output written on mchrzasz.pdf (11 pages). +Output written on mchrzasz.pdf (19 pages). diff --git a/Lectures_my/NumMet/Lecture5/mchrzasz.nav b/Lectures_my/NumMet/Lecture5/mchrzasz.nav index 7f72c1d..cfbea79 100644 --- a/Lectures_my/NumMet/Lecture5/mchrzasz.nav +++ b/Lectures_my/NumMet/Lecture5/mchrzasz.nav @@ -22,8 +22,24 @@ \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}} +\headcommand {\slideentry {0}{0}{12}{12/12}{}{0}} +\headcommand {\beamer@framepages {12}{12}} +\headcommand {\slideentry {0}{0}{13}{13/13}{}{0}} +\headcommand {\beamer@framepages {13}{13}} +\headcommand {\slideentry {0}{0}{14}{14/14}{}{0}} +\headcommand {\beamer@framepages {14}{14}} +\headcommand {\slideentry {0}{0}{15}{15/15}{}{0}} +\headcommand {\beamer@framepages {15}{15}} +\headcommand {\slideentry {0}{0}{16}{16/16}{}{0}} +\headcommand {\beamer@framepages {16}{16}} +\headcommand {\slideentry {0}{0}{17}{17/17}{}{0}} +\headcommand {\beamer@framepages {17}{17}} +\headcommand {\slideentry {0}{0}{18}{18/18}{}{0}} +\headcommand {\beamer@framepages {18}{18}} +\headcommand {\slideentry {0}{0}{19}{19/19}{}{0}} +\headcommand {\beamer@framepages {19}{19}} +\headcommand {\beamer@partpages {1}{19}} +\headcommand {\beamer@subsectionpages {1}{19}} +\headcommand {\beamer@sectionpages {1}{19}} +\headcommand {\beamer@documentpages {19}} +\headcommand {\def \inserttotalframenumber {18}} diff --git a/Lectures_my/NumMet/Lecture5/mchrzasz.pdf b/Lectures_my/NumMet/Lecture5/mchrzasz.pdf deleted file mode 100644 index d42ceb3..0000000 --- a/Lectures_my/NumMet/Lecture5/mchrzasz.pdf +++ /dev/null Binary files differ diff --git a/Lectures_my/NumMet/Lecture5/mchrzasz.synctex.gz b/Lectures_my/NumMet/Lecture5/mchrzasz.synctex.gz index 2af2a4f..6495ee4 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 1e04770..ffb0471 100644 --- a/Lectures_my/NumMet/Lecture5/mchrzasz.tex +++ b/Lectures_my/NumMet/Lecture5/mchrzasz.tex @@ -454,6 +454,213 @@ +\begin{frame}\frametitle{Exact methods: modified Gauss method} +\begin{small} + +\ARROW The biggest disadvantage of Gauss method is the fact that we can have zero elements :( \\ +\ARROW The modified method fixes this problem :)\\ +\ARROW The modification is as follows: +\begin{itemize} +\item In each step before we do the elimination we look for main element: +\begin{align*} +\vert a_{mk}^{\vert k \vert } = \max \lbrace \vert a_{jk}^{\vert k \vert} : j=k, k+1,..., n \rbrace +\end{align*} +\item We exchange the rows $m$ and $k$. +\item We do the standard elimination. +\end{itemize} + +\end{small} +\end{frame} + + + +\begin{frame}\frametitle{Exact methods: Jordan elimination method} +\begin{small} + + +\ARROW The Jordan elimination method is similar to Guass method but the idea is to transform the matrix from $Ax =b$ to $I x = b^{\lfloor n+1 \rfloor}$. +\begin{enumerate} +\item We start from eliminating the as in Gauss method in the first row. +\item When we move to the second row we eliminate the $x_2$ element also from the first raw. +\item The third raw we eliminate the first and second raw. +\item We repeat this $n$ times. +\end{enumerate} +\ARROW After this we will get new system $I x = b^{\lfloor n+1 \rfloor}$. \\ +\ARROW The $b^{\lfloor n+1 \rfloor}$ is already the solution! No need to do more. + +\end{small} +\end{frame} + + +\begin{frame}\frametitle{Exact methods: LU method} +\begin{small} + + +\ARROW The most popular of the exact methods is so-called LU method.\\ +\ARROW The idea is very simple; we represent the matrix in a form: +\begin{align*} +A = & \begin{pmatrix} +a_{11} & a_{12} & a_{13} & ... & a_{1n} \\ +a_{21} & a_{22} & a_{23} & ... & a_{2n} \\ +a_{31} & a_{32} & a_{33} & ... & a_{2n} \\ + & & ... & & \\ + _{n1} & a_{n2} & a_{n3} & ... & a_{nn} \\ +\end{pmatrix} = \\ & \begin{pmatrix} +1 & 0 & 0 & ... & 0 \\ +l_{21} & 1 & 0 & ... & 0 \\ +l_{31} & l_{32} & 1 & ... &0 & \\ + & & ... & & \\ +l_{n1} & l_{n2} & l_{n3} & ... & l_{nn}\\ +\end{pmatrix} \cdot +\begin{pmatrix} +u_{11} & u{12} & u_{13} & ... & u_{1n} \\ +0 & u{22} & u_{23} & ... & u_{2n} \\ +0 & 0 & u_{33} & ... & u_{3n} \\ + & & ... & & \\ +0 & 0 & 0 & ... & u_{nn} +\end{pmatrix} = L \cdot U +\end{align*} +\ARROW After this decomposition we need to solve: +\begin{align*} +\begin{cases} +L y & =b\\ +U x & =y +\end{cases} +\end{align*} + +\end{small} +\end{frame} + +\begin{frame}\frametitle{Exact methods: LU method, algorithms} +\begin{small} +\ARROW We solve the following matrix: $A^{\lfloor 1 \rfloor} x = b^{\lfloor1 \rfloor}$\\ +\ARROW We start by preparing the matrix $L^{\lfloor 1 \rfloor}$: +\begin{align*} +L^{\lfloor 1 \rfloor }=\begin{pmatrix} +1 & 0 & 0 & ... & 0 \\ +-l_{21} & 1 & 0 & ... & 0\\ +-l_{31} & 0 & 1 & ... & 0\\ +& & ... & & \\ +-l_{n1} & 0 & 0 & ... & 1 +\end{pmatrix} +\end{align*} +where the $l_{i1}$ are defined: +\begin{align*} +l_{i1} = \frac{a_{i1}^{\lfloor 1 \rfloor}}{a_{11}^{\lfloor 1 \rfloor}} +\end{align*} +\ARROW Now we take our base equation by $L^{\lfloor 1 \rfloor }$: +\begin{align*} +L^{\lfloor 1 \rfloor } A^{\lfloor 1 \rfloor } x = L^{\lfloor 1 \rfloor } b^{\lfloor1 \rfloor} +\end{align*} +\ARROW We get the a new system: +\begin{align*} +A^{\lfloor 2 \rfloor} x = b^{\lfloor2 \rfloor}~~~~~~~~\Leftrightarrow~~~~~~~~~~L^{\lfloor 1 \rfloor } A^{\lfloor 1 \rfloor } x = L^{\lfloor 1 \rfloor } b^{\lfloor1 \rfloor} +\end{align*} + +\end{small} +\end{frame} + +\begin{frame}\frametitle{Exact methods: LU method, algorithms} +\begin{small} +\ARROW In the second step we construct the $L^{\lfloor 2 \rfloor}$ in the form: +\begin{align*} +L^{\lfloor 2 \rfloor}=\begin{pmatrix} +1 & 0 & 0 & ... & 0 \\ +0 & 1 & 0 & ... & 0\\ +0 & -l_{32} & 1 & ... & 0\\ +& & ... & & \\ +0 & -l_{n2} & 0 & ... & 1 +\end{pmatrix} +\end{align*} +where : +\begin{align*} +l_{i2} = \frac{a_{i2}^{\lfloor 2 \rfloor}}{a_{22}^{\lfloor 2 \rfloor}} +\end{align*} + +\ARROW Now we take the $A^{\lfloor 2 \rfloor} x = b^{\lfloor2 \rfloor}$ and multiply it by $L^{\lfloor 2 \rfloor}$: +\begin{align*} +L^{\lfloor 2 \rfloor } A^{\lfloor 2 \rfloor } x = L^{\lfloor 2 \rfloor } b^{\lfloor2 \rfloor} +\end{align*} +\ARROW We get the a new system: +\begin{align*} +A^{\lfloor 3 \rfloor} x = b^{\lfloor3 \rfloor}~~~~~~~~\Leftrightarrow~~~~~~~~~L^{\lfloor 2 \rfloor } L^{\lfloor 1 \rfloor } A^{\lfloor 1 \rfloor } x = L^{\lfloor 2 \rfloor } L^{\lfloor 1 \rfloor } b^{\lfloor1 \rfloor} +\end{align*} + +\end{small} +\end{frame} + + +\begin{frame}\frametitle{Exact methods: LU method, algorithms} +\begin{small} + +\ARROW Now the we repeat the above steps $n-1$ times after which we get: +\begin{align*} +& L^{\lfloor n-1 \rfloor } L^{\lfloor n-2 \rfloor } ... L^{\lfloor 2 \rfloor } L^{\lfloor 1 \rfloor } A^{\lfloor 1 \rfloor } = A^{\lfloor n \rfloor } = U\\ +& L^{\lfloor n-1 \rfloor } L^{\lfloor n-2 \rfloor } ... L^{\lfloor 2 \rfloor } L^{\lfloor 1 \rfloor } b^{\lfloor1 \rfloor} = b^{\lfloor n \rfloor} +\end{align*} +\ARROW From the above we can calculate: +\begin{align*} +A^{\lfloor 1 \rfloor } = \left( L^{\lfloor 1 \rfloor } \right)^{-1} \left( L^{\lfloor 2 \rfloor } \right)^{-1} ... \left( L^{\lfloor n-1 \rfloor } \right)^{-1} A^{\lfloor n \rfloor } +\end{align*} +\ARROW So the matrix $L$ we search for is: +\begin{align*} +L= \left( L^{\lfloor 1 \rfloor } \right)^{-1} \left( L^{\lfloor 2 \rfloor } \right)^{-1} ... \left( L^{\lfloor n-1 \rfloor } \right)^{-1} +\end{align*} +\ARROW The $\left( L^{\lfloor k \rfloor } \right)^{-1}$ can be easy calculated: +\begin{footnotesize} +\begin{align*} +\left( L^{\lfloor k \rfloor } \right)^{-1} = \begin{pmatrix} +1 & 0 & ... & 0 & ... & 0 \\ +0 & 1 & ... & 0 & ... & 0 \\ +& & & ... & & \\ +0 & 0 & ... & 1 & ... & 0 \\ +0 & 0 & ... & l_{k+1 k} & ... & 0 \\ +0 & 0 & ... & l_{k+2 k} & ... & 0 \\ +& & & ... & & \\ +0 & 0 & ... & l_{n k} & ... & 1 \\ +\end{pmatrix} +\end{align*} +\end{footnotesize} + +\end{small} +\end{frame} + + + +\begin{frame}\frametitle{Exact methods: LU method, algorithms} +\begin{small} + +\ARROW Now the only thing left is to solve the simple linear system: +\begin{align*} +\begin{cases} +L y & =b\\ +U x & =y +\end{cases} +\end{align*} +\ARROW Because of the triangular matrix the solution is straightforward: +\begin{align*} +y_1=\frac{b_1}{L_11},~~~~~~~~~y_i=\frac{b_1 - \sum_{j=1^{i-1}} L_{ij} y_j }{L_{ii}}~~{ i\geq 2} +\end{align*} + +\end{small} +\end{frame} + + +\begin{frame}\frametitle{Summary} +\begin{small} + +\ARROW This lecture we learn the exact methods of solving linear equation system.\\ +\ARROW The three most popular one are: Gauss, Jordan, LU.\\ +\ARROW By default the LU method should be used.\\ +\ARROW And remember: be sure the system is well conditioned! + + +\end{small} +\end{frame} + + + + \backupbegin