Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- \documentclass[]{article}
- \usepackage{amsmath}
- \usepackage{listings}
- \usepackage{color}
- \usepackage{longtable}
- \usepackage{pgfplots}
- \pgfplotsset{width=15cm,compat=1.9}
- \usepackage[T1]{fontenc}
- \usepackage[polish]{babel}
- \usepackage[utf8]{inputenc}
- \usepackage{lmodern}
- \selectlanguage{polish}
- \definecolor{codegreen}{rgb}{0,0.6,0}
- \definecolor{codeblue}{rgb}{0,0,0.6}
- \definecolor{codegray}{rgb}{0.5,0.5,0.5}
- \definecolor{codepurple}{rgb}{0.58,0,0.82}
- \definecolor{backcolour}{rgb}{0.95,0.95,0.92}
- \lstdefinestyle{mystyle}{
- commentstyle=\color{codegreen},
- keywordstyle=\color{magenta},
- keywordstyle=[2]\color{codeblue},
- numberstyle=\tiny\color{codegray},
- stringstyle=\color{codepurple},
- basicstyle=\footnotesize,
- breakatwhitespace=false,
- breaklines=true,
- captionpos=b,
- keepspaces=true,
- numbers=left,
- numbersep=5pt,
- showspaces=false,
- showstringspaces=false,
- showtabs=false,
- tabsize=2,
- keywords=[2]{zesp},
- }
- \lstset{style=mystyle}
- \usepackage{geometry}
- \usepackage{bbold}
- \newgeometry{tmargin=3cm, lmargin=3cm, rmargin=3cm}
- %opening
- \title{Metody numeryczne}
- \author{Wojciech Chrobak}
- \begin{document}
- \maketitle
- \section*{Zadanie 6 - obowiązkowe}
- \subsection*{Metoda Laguerre'a}
- Metoda Laguerre'a jest metodą numerycznego poszukiwania \textbf{miejsc zerowych wielomianów}.\\
- W wypadku ogólnym:
- \begin{itemize}
- \item metoda jest zbieżna sześciennie do wszystkich pojedynczych miejsc zerowych (rzeczywistych i zespolonych)
- \item metoda jest zbieżna liniowo do wielokrotnych miejsc zerowych
- \item przypadki braku zbieżności są bardzo rzadkie; w nielicznych przypadkach, w których metodzie grozi stagnacja, można ją przerwać wykonując jeden-dwa kroki metodą Newtona, a potem powrócić do metody Laguerre'a
- \item metoda jest podobna do metody opartej o rozwinięcie w szereg Taylora do drugiego rzędu ale jest lepsza, gdyż uwzględnia stopień wielomianu
- \item metoda wymaga obliczania drugiej pochodnej, ale w wypadku wielomianów jest to bardzo proste
- \item metoda nawet dla rzeczywistych punktów początkowych może prowadzić do zespolonych miejsc zerowych. Jednak z uwagi na specyfikę wielomianów, nie ma sensu upieranie się przy operowaniu na liczbach rzeczywistych
- \end{itemize}
- \subsubsection*{Algorytm}
- Metoda Laguerre'a znalezienia jednego pierwiastka wielomianu $P(x)$ stopnia $n$ jest następująca:
- \begin{itemize}
- \item wybierz dowolny zespolony punkt startowy $x_0$
- \item dla $k = 0, 1, 2, ...$
- \begin{itemize}
- \item jeśli $P(x_k)$ bardzo małe, przerwij pętle
- \item wylicz $$G = \frac{P'(x_k)}{P(x_k)}$$
- \item wylicz $$H = G^2 - \frac{P''(x_k)}{P(x_k)}$$
- \item wylicz $$a = \frac{n}{G \pm \sqrt{(n-1)(nH-G^2)}}$$ znak wybierany jest w ten sposób aby mianownik miał większy moduł dla uniknięcia utraty cyfr znaczących
- \item przypisz $x_{k+1} = x_k - a$
- \end{itemize}
- \item powtarzaj dotąd aż $a$ stanie się dostatecznie małe lub będzie osiągnięta maksymalna ilość iteracji
- \end{itemize}
- \subsubsection*{Strategia postępowania}
- W ten sposób dostaliśmy \textbf{przybliżenie} miejsca zerowego $\overline{z}_{k+1}$ wielomianu $P_{n-k}$
- W celu \textbf{wygładzenia} tego miejsca zerowego, liczby $\overline{z}_{k+1}$ używamy jako warunku początkowego dla metody Laguerre'a zastosowanej do pełnego wielomianu $P_n(z)$. Spodziewamy się, że w ciągu kilku iteracji znajdziemy miejsce zerowe $z_{k+1}$.
- \textbf{Faktoryzujemy} wielomian $P_{n-k}(z)$, to znaczy obliczamy $P_{n-k}(z) = (z-z_{k+1})P_{n-k-1}(z)$.
- Postępujemy tak dopóki nie dojdziemy do wielomianu stopnia 2, któego pierwiastki obliczamy według znanego wzoru.
- \subsection*{Kod}
- \lstinputlisting[language=C++]{../main.cpp}
- \subsection*{Wynik}
- \[
- 243z^7 - 486z^6+783z^5-990z^4+558z^3-28z^2-72z+16=0
- \]
- \begin{center}
- \textbf{Miejsca zerowe:} ($\Re, \Im$)
- \end{center}
- \[
- (0.66599495,0.00000000)
- \]
- \[
- (0.66700240,-0.00058032)
- \]
- \[
- (0.33333334,0.00000000)
- \]
- \[
- (0.66700265,0.00058032)
- \]
- \[
- (-0.33333333,0.00000000)
- \]
- \[
- (0.00000000,1.41421356)
- \]
- \[
- (0.00000000,-1.41421356)
- \]
- \[
- z^{10}+z^9+3z^8+2z^7-z^6-3z^5-11z^4-8z^3-12z^2-4z-4=0
- \]
- \begin{center}
- \textbf{Miejsca zerowe:} ($\Re, \Im$)
- \end{center}
- \[
- (0.00001593,-0.99997605)
- \]
- \[
- (0.00001105,0.99997767)
- \]
- \[
- (-0.00001104,1.00002233)
- \]
- \[
- (-0.50000000,-0.86602540)
- \]
- \[
- (0.00000000,-1.41421356)
- \]
- \[
- (-0.50000000,0.86602540)
- \]
- \[
- (-0.00001593,-1.00002395)
- \]
- \[
- (1.41421356,0.00000000)
- \]
- \[
- (0.00000000,1.41421356)
- \]
- \[
- (-1.41421356,0.00000000)
- \]
- \[
- z^4+iz^3-z^2-iz+1=0
- \]
- \begin{center}
- \textbf{Miejsca zerowe:} ($\Re, \Im$)
- \end{center}
- \[
- (0.95105652,0.30901699)
- \]
- \[
- (0.58778525,-0.80901699)
- \]
- \[
- (-0.95105652,0.30901699)
- \]
- \[
- (-0.58778525,-0.80901699)
- \]
- \end{document}
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement