Temat: „ Czego nauczyłaś się na przedmiocie metody numeryczne?”

Analiza numeryczna zajmuje się tworzeniem, badaniem i analizą algorytmów. Zadaniem jej jest otrzymanie rozwiązań numerycznych zadań matematycznych. W jednej z książek spotkałam się z określeniem analizy numerycznej, jako matematyki obliczeń naukowych.

Postanowiłam, że w pracy przedstawię w rozdziałach tematy z tych zagadnień, które spotkały się z moim zainteresowaniem.

Liczby rzeczywiste i maszynowe.

Aby liczba była liczbą maszynową, musi spełniać pewne warunki. Dlatego nie każda liczba rzeczywista x jest liczba maszynową. Liczbę niebędącą liczbą maszynową można zastąpić jakąś bliską liczbą maszynową. Można ją wybrać na kilka sposobów.

W książce Kincaid’a i Cheney ’a pt. „Analiza numeryczna” jest napisane:

„ Załóżmy, że nasze x>0 oraz x =q×2^m, gdzie 1<q<2, zatem:

x=(1.a₁…)₂×2^m.

Nasze a_i przyjmują wartości 0 albo 1. Jeśli mantysy liczb maszynowych mają t bitów po kropce, to bliska względem x taka liczba powstaje przez odrzucenie zbędnych bitów a_t+1,…. Taką operację nazywamy obcięciem. Następnie otrzymujemy poniższy wzór:

x_-=(1.a₁…a_t)₂×2^m,

Zwróćmy uwagę na to, że x_-≤x. Inna bliska liczba maszynowa, która znajduje się na prawo od x, powstaje przez zaokrąglenie w górę. Wtedy niepotrzebne bity odrzucamy i do q dodajemy jedynkę na ostatniej wolnej pozycji. W ten sposób otrzymamy poniższy wzór:

x₊=[(1.a₁…a_t)₂+2^-t]× 2^m.

Na końcu otrzymujemy, że:

x₊-x_-=2^m-t.

Najbliższą dla x liczbą maszynową oznaczmy ją, jako fl(x), jest bliższa jej z liczb x_- lub x₊. Jeśli jako bliższą liczbę wybraliśmy fl(x)=x_-, to mamy :

|x-fl(x)|≤$\frac{1}{2}$ |x₊ - x_-|= 2^m-t-1

Analogiczny wzór mamy dla fl(x) =x₊. Dla obu przypadków szacujemy podobny błąd względny reprezentacji maszynowej liczby x. Wygląda on następująco:

$$\frac{|x - fl\left( x \right)|}{|x|} \leq \frac{2^{m - t - 1}}{q2^{m}} = \frac{1}{q}2^{- t - 1} \leq 2^{- t - 1}''$$

Wykorzystajmy zdobyte wiadomości w praktyce, rozwiązują poniższe zadanie.

Zadanie

Jaka jest postać dwójkowa liczby x= $\frac{4}{5}$ w przykładowej arytmetyce, w której t=23? Znajdź błąd względny i bezwzględny.

Rozwiązanie:

x= $\frac{4}{5}$=0.110(0110)=1.10(0110)×2^-1

Dla liczby x wyznaczamy bliskie liczby maszynowe:

x_-=1.10(0110)…0×2^-1 (gdzie na 23 miejscu znajduje się 0)

x₊=1.10(0110)…1×2^-1 (gdzie na 23 miejscu znajduje się 1)

Obliczmy teraz różnice:

Oznaczmy sobie x_-=s i x₊=k

|x₊-x_-|=2^-24

x-x_-=1.10(0110) ×2^-1-s= $\frac{4}{5} \times$2^-24

x₊-x=x₊-x_- -(x-x_-)=2^-24-$\ \frac{4}{5} \times$2^-24 =$\ \frac{1}{5} \times$2^-24

Zatem nasz błąd bezwzględny wynosi: $\frac{1}{5} \times$2^-24, czyli ostatecznie: |x-fl(x)|=$\frac{1}{5} \times$2^-24.

Policzmy teraz błąd względny:

$$\frac{|x - fl\left( x \right)|}{|x|} = \frac{\frac{1}{5} \times 2^{- 24}}{\frac{4}{5}} = 2^{- 25}$$

Interpolacja wielomianowa

Do wyjaśnienia zagadnienia posłużę się zadaniem, które znalazłam w książce „Analiza numeryczna”: ” Znaleźć wielomian p najniższego stopnia taki, że dla danych n + 1 punktów (x_i, y_i) jest p(x_i) = y_i dla 0 ≤ i ≤ n.

Wtedy mówimy, że ten wielomian interpoluje wartości y_k w węzłach x_k. Jeśli są to wartości pewnej funkcji f, to mówimy, że p interpoluje f. Omawiając zadania interpolacji wielomianowej, symbolem $\prod_{}^{}n$, zbiór wszystkich wielomianów maksymalnie stopnia n.”

Postanowiłam także wykorzystać twierdzenie i dowód z książki Kincaid’a i Cheney ‘a:

Twierdzenie

Jeśli liczby x₀, …,x_n są parami różne , to istnieje dokładnie jeden wielomian p_nnależący do $\prod_{}^{}n$, taki, że

p_n(x_i) = y_i

dla 0 ≤ i ≤ n.

Dowód

Udowodnimy najpierw jednoznaczność tego wielomianu. Przypuśćmy, że dwa wielomiany p_n, q_n, z klasy $\prod_{}^{}n$, spełniają powyższe warunki. Wtedy ich różnica p_n − q_n znika w n+1 punktach x_i. Ponieważ jednak wielomian z $\prod_{}^{}n$, nieznikający tożsamościowo ma, co najwyżej n zer, więc te wielomiany są tożsamością.

Istnienie wielomianu sprawdzamy przez indukcję. Dla n=0 jest oczywiste, że warunek jest spełniony. Wiedząc, ze dla pewnego k naturalnego istnieje wielomian p_k − 1 należący do $\prod_{}^{}{}_{k - 1}$, taki, że ∖np_k − 1(x_i) = y_i dla 0 ≤ i ≤ k − 1, próbujemy wyrazić p_k w postaci:

p_k(x) = p_k − 1(x) + c(x−x₀)(x−x₁)…(x−x_k − 1).

Dla każdej stałej c stopień tego wielomianu nie przewyższa k. Jest też oczywistością, że p_k spełnia warunki interpolacyjne dla 0 ≤ i ≤ k − 1. Pozostaje wyznaczyć c tak, żeby było również p_k(x_k) = y_k. Tak jest, gdy:

p_k − 1(x_k) + c(x_k−x₀)(x_k−x₁)…(x_k−x_k − 1) = y_k,

A stąd można obliczyć c.

Zadanie

Rozwiąż metodą Lagrange’a.

x	0	1	2
f(x)	3	4	5

Do rozwiązania naszego zadania, potrzebny będzie nam następujący wzór:

$$w\left( x \right) = \sum_{k = 0}^{n}y_{k}\frac{\ \prod_{j = 0,j \neq k}^{n}{(x - x_{\text{j\ \ }})}}{\prod_{j = 0,j \neq k}^{n}{(x_{k}} - x_{\text{j\ }})}$$

$w\left( x \right) = 3 \times \frac{\left( x - 1 \right)\left( x - 2 \right)}{\left( 0 - 1 \right)\left( 0 - 2 \right)}$+ 4 $\times \frac{\left( x - 0 \right)\left( x - 2 \right)}{\left( 1 - 0 \right)\left( 1 - 2 \right)}$ +5$\times \frac{\left( x - 0 \right)\left( x - 1 \right)}{\left( 2 - 0 \right)\left( 2 - 1 \right)}$

$$w\left( x \right) = \frac{1}{2}\{ 3 \times \left( x - 1 \right)\left( x - 2 \right) + 5x\left( x - 1 \right) - 8x\left( x - 2 \right)\}$$

$$w\left( x \right) = \frac{1}{2}(2x + 6)$$

Można sprawdzić czy wyliczenia się zgadzają, wstawiając do w(x) wartości x.

$$w\left( 0 \right) = \frac{6}{2} = 3$$

$$w\left( 1 \right) = \frac{8}{2} = 4$$

$$w\left( 2 \right) = \frac{10}{2} = 5$$

Metoda Newtona (metoda stycznej)

Wyjaśnienie powyższej metody oraz szereg twierdzeń, można znaleźć w książce „Analiza numeryczna”:

„Niech będzie dana funkcja f, której zera wyznaczamy numerycznie. Załóżmy sobie, że r jest takim naszym zerem, z kolei x jego przybliżeniem. Jeśli istnieje druga pochodna f, wtedy:

0 = f(r) = f(x+h) = f(x) + hf^′(x) + O(h²),

Niech h = r − x. Dla x znajdującego się blisko r, pomijamy O(h²). Wtedy wyliczając h otrzymamy:

$$h = \frac{- f(x)}{f^{'}(x)}$$

Z kolei dla x, który jest przybliżeniem r, $x - \ \frac{f(x)}{f^{'}(x)}$, powinno być lepszym przybliżeniem zera. Zatem metoda Newtona zaczyna od przybliżenia x₀ zera r i polega na rekurencyjnym stosowaniu wzoru:

$$x_{n + 1} = x_{n} - \ \frac{f(x_{n})}{f^{'}(x_{n})}$$

gdzie n ≥ 0.

Twierdzenie

Niech r będzie zerem pojedynczym funkcji f i niech jego druga pochodna będzie ciągła. Wtedy istnieje takie otoczenie punktu r i taka stała C, że jeśli metoda startuje z tego otoczenia, to kolejne punkty są coraz bliższe r i takie, że

|x_n + 1 − r|≤|C(x_n−r)²|

gdzie n ≥ 0,    e_n = (x_n−r) jest błędem.

Twierdzenie

Jeśli f należy do C²(R), jest rosnąca, wypukła i ma zero, to jest ono jedyne, a metoda Newtona daje ciąg do niego zbieżny dla dowolnego punktu początkowego.

Dowód

Wiemy, że funkcja f jest wypukła, jeśli druga jej pochodna jest większa od zera dla każdego x. Ponieważ funkcja ta, jest tez rosnąca, wiec jej pierwsza pochodna jest większa od zera w R. Zatem (x_n + 1−r)>0, x_n > r dla n ≥ 0. Wiemy także, żef(x_n) > f(r) = 0. Dlatego x_n + 1 − r < x_n − r. Zatem ciągi {e_n} , {x_n} są malejące i ograniczone z dołu (odpowiednio przez 0 i r). Dzięki temu granice e^* = e_n,   x^*=x_n istnieją. Czyli

$e^{*} = e^{*} - \frac{{f(x}^{*})}{f^{'}(x^{*})}$, zatem $f\left( x^{*} \right) = 0\ i\ x^{*} = r."$

Zadanie

∖n

f(x) = x² − 15

x² − 15 = 0

Wyliczamy h(x) ze wzoru:

$$h = \frac{- f(x)}{f^{'}(x)}$$

$$h\left( x \right) = \frac{- x^{2} + 15}{2x}$$

Następnie korzystając z poniższego wzoru wyliczamy kolejne wyrazy ciągu:

$$x_{n + 1} = x_{n} - \ \frac{x_{n}^{2\ } + 15}{2x_{n}}$$

Ustalmy, że x₀=3, bo $3 < \sqrt{15} < 4$.

$$x_{1} = \frac{x_{0}}{2} + \frac{15}{2x_{0}}$$

x₁ = 4

$$x_{2} = \frac{33}{8} = 4\frac{1}{8}$$

Metoda bisekcji (połowienia przedziału)

Do wyjaśnienia metody posłużę się twierdzeniami z wcześniej wskazanej książki.

Twierdzenie

Jeśli f jest funkcją ciągłą w przedziale [a, b] i f(a)f(b)<0, czyli zmieniony jest znak f w [a,b], to funkcja musi mieć zero w (a,b).

Powyższe twierdzenie wynika z własności Darboux dla funkcji ciągłych. Odgrywa ważną rolę w metodzie połowienie przedziału, ponieważ bazuje na jego własnościach.

Jeśli f(a) f(b) <0, wtedy obliczamy wartość $c = \frac{1}{2}$(a + b). Następnie musimy sprawdzić czy nasze f(a) f(b) są nadal mniejsze od 0. Gdy warunki te zostają spełnione, to f ma zero w [a, c] i w miejsce a wstawiamy c. Nowo powstały przedział [a, b] jest dwa razy krótszy od poprzedniego, posiada zero funkcji f i dlatego możemy powtórzyć całość.

Twierdzenie

Jeżeli przedziały [a₀,b₀], [a_1,b₁],…są tworzone metodą bisekcji to granice a_n i b_n istnieją, są identyczne i równe zeru funkcji f.

Jeżeli:

r = c_n gdzie $\text{\ \ \ \ \ \ \ }c_{n} = \frac{1}{2}$(a_n + b_n) (*)

Wtedy:

|r − c_n|≤2^{−(n + 1)}(b₀-a₀) (**)

Zadanie

Niech metoda bisekcji startuje od przedziału [50,80]. Ile razy musimy wykonać metodę bisekcji, aby otrzymać wynik z błędem względnym naszego obliczenia mniejszym niż 10⁻²⁰?

Rozwiązanie:

Wiemy, że a₀ = 50,  b₀ = 80.

Skorzystajmy ze wzoru (*) do obliczenia c₀, zatem jego wartość wynosi:

$c_{0} = \frac{(80 - 50)}{2}$_{= 15}

Z treści zadania wartość błędu względnego ma być mniejsza od 10⁻²⁰, więc:

$$\frac{|r - c_{n}|}{|r|}{< 10}^{- 20}$$

|r−c_n|<10⁻²⁰|r|

Teraz w wartość po lewej stronie wstawiamy (**), czyli:

2⁻⁽ⁿ⁺¹⁾(80 − 50) <10⁻²⁰|r|

$$\frac{30}{2^{n + 1}} < \frac{|r|}{10^{20}}$$

Przyjmijmy, że r jest początkiem przedziału, zatem r =50.

$$\frac{30}{2^{n + 1}} < \frac{50}{10^{20}}$$

Po wykonaniu kilku prostych przekształceń mamy:

$$n + 1 > \operatorname{}\frac{10^{20}30}{50}$$

n > 2010 + 30 − 50 − 1

Funkcja wielomianowa

Funkcja wielomianowa jest dana w postaci:

P(n) = a_nxⁿ + … + a₁x + a₀ (***)

Po raz kolejny wykorzystam twierdzenia z podręcznika, do wyjaśnienia zagadnień, które okażą się pomocne do rozwiązania zadań.

Twierdzenie

Każdy wielomian różny od stałej ma, co najmniej jeden pierwiastek w ciele C liczb zespolonych.

Twierdzenie

Wielomian stopnia n ma dokładnie n pierwiastków na płaszczyźnie zespolonej, gdy każdy z nich jest liczony tule razy ile wynosi jego krotność.

Twierdzenie

Wszystkie pierwiastki wielomianu (***) leżą w kole otwartym o środku w punkcie 0 płaszczyzny zespolonej i promieniu

g = 1 + |a_n|⁻¹|a_k|

Dowód

Niech c =|a_k|, stąd c|a_n|⁻¹=g − 1. Jeśli c=0, to twierdzenie jest prawdziwe. W przeciwnym wypadku jest g > 1 i dla |z|≤g mamy nierówność

$$\left| p\left( z \right) \right| \geq \left| a_{n}z^{n} \right| - \left| a_{n - 1}z^{n - 1} + \ldots + a_{0} \right| \geq \left| a_{n}z^{n} \right| - c\sum_{k = 0}^{n - 1}{{|z|}^{k} >}$$

>|a_nzⁿ| − c|z|ⁿ(|z|−1)⁻¹ = |a_nzⁿ|[1 − c|a_n|⁻¹(|z|−1)⁻¹]≥

≥|a_nzⁿ|[1−c|a_n|⁻¹(g−1)⁻¹] = 0.

Zadanie

Oblicz promień koła na płaszczyźnie zespolonej o środku w punkcie (0,0) dla poniższego wielomianu:

P(z) = z³+2z-1

Rozwiązanie:

Wstawiamy do wzoru:

g = 1 + |a₃|⁻¹|a_k|=3

Twierdzenie

Jeśli wszystkie pierwiastki wielomianu s leżą w kole |z| ≤ g, to wszystkie niezerowe pierwiastki wielomianu p leżą poza kołem|z| < g⁻¹.

Zadanie

Znaleźć koło o środku w punkcie (0,0), w którym wielomian nie ma żadnego pierwiastka. Do zbudowania nowego wielomianu, skorzystaj ze wzoru na wielomian odwrotny dla poniższego wielomianu:

P(z) = z³+2z-1

Rozwiązanie:

Wzór na wielomian odwrotny wygląda następująco:

S(z) = a₀xⁿ + … + a_n − 1x + a_n

S(z) = −z³+2z+1

Promień dla wielomianu odwrotnego wynosi tyle samo, czyli:

g = 1 + |a₃|⁻¹|a_k| = 3

|z|<g⁻¹

$$\frac{1}{3} < |z| < 3$$

Wniosek: Otrzymane pierwiastki wielomianu P(z) leżą poza kołem.

Rozkład LU

Niech dana będzie macierz A o wymiarach n×n. Macierz A można rozłożyć na iloczyn dwóch macierzy.

Zatem:

A=LU

gdzie:

L- macierz trójkątna dolna

U- macierz trójkątna górna

Rys. Źródło Wikipedia

Zadanie

Rozłóż na macierz LU

$$\begin{bmatrix} 5 & 0 \\ 0 & 4 \\ \end{bmatrix}$$

Rozwiązanie:

Do znalezienia rozkładu LU, musimy posłużyć się następującym algorytmem, który był omawiany na ćwiczeniach u mgr Marka Szczepańskiego:

For k=1 to n do

WYBRAĆ WARTOŚĆ NIEZEROWĄ DLA l_kk LUB u_kk

WYLICZYĆ DRUGĄ ZE WZORU

$$l_{\text{kk}}u_{\text{kk}} = a_{\text{kk}} - \sum_{s = 1}^{k - 1}{u_{\text{sk}}l_{\text{ks}}}$$

For j=k+1 to n

$$u_{\text{kj}} = (a_{\text{kj}} - \sum_{s = 1}^{k - 1}{l_{\text{ks}}u_{\text{sj}})/l_{\text{kk}}}$$

$$l_{\text{jk}} = (a_{\text{jk}} - \sum_{s = 1}^{k - 1}{l_{\text{js}}u_{\text{sk}})/u_{\text{kk}}}$$

End do

End do

Wybierzmy, jako pierwsza niezerową wartość dla l₁₁ liczbę 5, a pozostałe wartości wyliczamy, korzystając z algorytmu.

5u₁₁ = a₁₁ = 5

u₁₁ = 1

$$l_{21} = \frac{a_{21}}{u_{11}} = 0$$

Wybierzmy teraz dla l₂₂ wartość 2, zatem:

$u_{12} = \frac{a_{12}}{l_{22}}$ =0

$$u_{22} = \frac{a_{22} - l_{21}u_{12}}{l_{22}} = 2$$

Zatem nasz rozkład LU wygląda następująco:

L= $\begin{bmatrix} 5 & 0 \\ 0 & 2 \\ \end{bmatrix}$

U=$\begin{bmatrix} 1 & 0 \\ 0 & 2 \\ \end{bmatrix}$

Możemy sprawdzić, czy otrzymany wynik jest prawidłowy wymnażając macierze L i U.

Bibliografia:

1. David Kincaid, Ward Cheney „Analiza numeryczna”.

2. Notatki z ćwiczeń u mgr. Marka Szczepańskiego.

3. Wikipedia.