---
# System prepended metadata

title: Lista 4
tags: [Analiza Numeryczna (L)]

---

###### tags: `Analiza Numeryczna (L)`
# Lista 4

## 1
:::info
Niech $[a_0, b_0]$, $[a_1, b_1]$, . . będzie ciągiem przedziałów zbudowanym za pomocą metody bisekcji zastosowanej do lokalizacji zer funkcji $f$ ciągłej w przedziale $[a_0, b_0]$, niech ponadto $m_{n+1} := \frac12(a_n + b_n)$, $α = \lim_{n→∞} m_n$ oraz $e_n := α − m_{n+1}$.
:::
### a)

$[a_{n+1},b_{n+1}] =
  \begin{cases}
    [\frac{a_n}{2},b_n]       & \quad \text{dla } \alpha\in [\frac{a_n}{2},b_n] \\
    [a_n,\frac{b_n}{2}]   & \quad \text{w p.p. }
  \end{cases}$

A wiemy, że $[a_n,b_n]\supset [\frac{a_n}{2},b_n]$ oraz $[a_n,b_n]\supset [a_n,\frac{b_n}{2}]$ więc z tego wynika, że $[a_n,b_n]\supset[a_{n+1},b_{n+1}]$

co należało udowodnić.

### b)
Teza: Długość przedziału wynosi $\frac{b_0 - a_0}{2^n}$
Dowód przeprowadzę przez indukcję.
$1^\circ$ dla n=0
$\frac{b_0 - a_0}{2^0} = b_0-a_0$
$1^\circ$ Załóżmy, że długość przedziału $[a_n,b_n]$ wyraża się wzorem $n=\frac{b_0 - a_0}{2^n}$ Wtedy dla n+1
$długość[a_{n+1},b_{n+1}] = \frac{1}{2}\times długość[a_n,b_n] = \frac{1}{2}\times \frac{b_0 - a_0}{2^n} = \frac{b_0-a_0}{2^{n+1}}$
Na podstawie indukcji pokazałem, że długość przedziału $[a_n,b_n]$ Wyraża się wzorem $\frac{b_0 - a_0}{2^n}$.

### c)

$|e_n| = |\alpha - m_{n+1}| = |\alpha - \frac{1}{2}(a_n+b_n)|$ Możemy zauważyć, że $\alpha\in[a_n,b_n]$ więc podana rożnica będzie największa dla $\alpha = a_n$ lub $\alpha = b_n$ w obu przypadkach po podstawieniu za $\alpha$ otrzymamy $|e_n| = |\frac{b_n-a_n}{2}| = |\frac{b_n}{2} - \frac{a_n}{2}|$ Zauważmy, że jest to długość odcinka, która wynosi (z podpunktu b) $|\frac{b_0-a_0}{2^{n+1}}|$, a $|\frac{b_0-a_0}{2^{n+1}}| = P$ Czyli w przypadku największego $|e_n|$ zachodzi równość, z czego wynika, że dla każdego n zachodzi $|e_n|\leq|\frac{b_0-a_0}{2^{n+1}}|$
Co należało udowodnić.
### d)
Wiemy, że miejsce zerowe funkcji $f\in[a_0,b_0]$. Załóżmy, że miesjce zerowe $\alpha = b_0$. Wtedy przy kolejnych podziałach odcinka będziemy brać zawsze "drugą" połowę i nie będziemy zmieniać $b_0$, co za tym idzie będziemy zawsze zwiększać $a$ więc zachodzi nierówność $a_0<a_1<a_2<...$
## 2

Korzystając z poprzedniego zadania
$\epsilon_n < \epsilon$
$\epsilon_n  = |\alpha - m_{m+1}| \leq 2^{-n-1}(b_0-a_0)$
$\frac{b_0-a_0}{2^{n+1}} < \epsilon$
$\frac{b_0-a_0}{\epsilon} < 2^{n+1}$ Obie strony są dodatnie, więc mogę nałożyć $log_2$
$log_2(\frac{b_0-a_0}{\epsilon}) < n+1$
$log_2(\frac{b_0-a_0}{\epsilon}) - 1 < n$
$log_2(\frac{b_0-a_0}{\epsilon}) - log_22 < n$
$log_2(\frac{b_0-a_0}{2\epsilon}) < n$
Aby ta nierówność była prawdziwa trzeba wykonać conajmniej $log_2(\frac{b_0-a_0}{2\epsilon})$ kroków, czyli co najmniej $\lfloor log_2(\frac{b_0-a_0}{2\epsilon})\rfloor + 1$
## 3
```java=
import static java.lang.Math.pow;

public class Main {
    public static double L41function(double x){
        return x - 0.49d;
    }
    public static void L41(){

        double start = 0d;
        double end = 1d;
        double mid, result, fault;

        for (int i=0; i<=5; i++){

            mid = (start + end)/2d;
            result = L41function(mid);
            fault = pow(2,-i-1);

            if (i>0)
                System.out.println("Dla n=" + i + " przybliżona wartość miejsca zerowego:" + mid + ". Błąd: |e_n| <= " + fault);

            if (result == 0)
                System.out.println("Miejsce zerowe a = " + result);

            if (result < 0)
                start = mid;
            else
                end = mid;
        }
    }

    public static void main(String args[]){
        L41();
    }
}
```
![](https://i.imgur.com/7C4oGpj.png)


Dla każdego kolejnego n funkcja wyznacza coraz to lepsze przybliżenie miejsca zerowego. Szacowany błąd z każdym nowym przybliżeniem maleje dwukrotnie, co daje nam coraz to lepszy wynik.
## 4
![](https://i.imgur.com/YjfBRbq.png)
Po naszkicowaniu wykresów ze wskazówki możemy zauważyć, że funkcja $f(x) =x^22−2cos(3x+ 1)$ ma 2 miejsca zerowe oraz, że znajdują się one kolejno w przedziale $x_1\in[-1,0]$, $x_2\in[0,1]$
Sprawdzamy znaki wartości w tych punktach:
$f(-1) =$ dodatnia wartość
$f(0) =$ ujemna wartość
$f(1) =$ dodatnia wartość
Po podstawieniu do wzoru z zadania 2, musimy wykonać w obu przypadkach obliczenia do n = 16.
## 5
### a)
$\frac{1}{R} = x$
$\frac{1}{x} = R$
$\frac{1}{x}- R = 0$
Dla $f(x) = \frac{1}{x} - R$
Chcemy znaleźć miejsce zerowe tej funkcji (Jest to $\frac{1}{R}$)
$f'(x) = -\frac{1}{x^2}$
Więc z metody Newtona $x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} = x_n - \frac{\frac{1}{x_n} - R}{\frac{-1}{x_n^2}} = x_n - \frac{\frac{1}{x_n} - R}{\frac{-1}{x_n^2}} = x_n + \frac{\frac{1}{x_n} - R}{\frac{1}{x_n^2}} = x_n + (\frac{1}{x_n} - R)\times x_n^2 =$
$=x_n + x_n - Rx_n^2 = 2x_n - Rx_n^2 = x_n(2-Rx_n)$
### b)
![](https://i.imgur.com/QXZ91kC.png)
### c)
$x_{n+1} < 0 \iff x_n > 0$ oraz $2 - x_nR < 0$ LUB $x_n < 0$ oraz $2 - x_nR > 0$
$1^\circ$ $x_n > 0$ oraz $2 - x_nR < 0$
$x_nR > 2$
**$x_n > \frac{2}{R}$**
$2^\circ$ $x_n < 0$ oraz $2 - x_nR > 0$
$x_nR < 2$
$x_n < \frac{2}{R}$
Czyli $x_n <0$

**Odp $x_n < 0$ lub $x_n > \frac{2}{R}$**
### d)
Załóżmy, że $x_n < 0$
Wtedy $x_{n+1} =x_n(2-x_nR)$
(x_n < 0, R > 0)
$x_n(2-x_nR) < x_n(2) = 2\times x_n$
$x_{n+1} < 2\times x_n < x_n$
Czyli $x_{n+1} < x_n$
Co nalezało udowodnić.
### e)
$x_{n+1} > 0$ oraz $x_n < \frac{1}{R}$

**1$^\circ$ $x_{n+1} > 0$**

$x_{n+1} = x_n(2-x_nR) > 0$
Rozwiążmy równanie $x_n(2-x_nR) = 0$
Wtedy $x_n = 0$ LUB $2-x_nR = 0$
Czyli $x_n=0$ LUB $x_n = \frac{2}{R}$
Wracając do nierównośći, $x_n(2-x_nR) > 0 \iff x_n\in(0,\frac{2}{R})$

**2$^\circ$ $x_{n+1} < \frac{1}{R}$**
$x_{n+1} = x_n(2-x_nR)$
$x_n(2-x_nR)< \frac{1}{R}$ / $\times R$ (R dodatnie)
$x_nR(2-x_nR)< 1$ / $-1$
$x_nR(2-x_nR) - 1 < 0$
$x_nR(2-x_nR - \frac{1}{x_nR}) < 0$ / $\times x_n$ ($x_n$ dodatnie)
$x_nR(2x_n-x_n^2R - \frac{1}{R}) < 0$ $\times \frac{-1}{R^2}$
$x_n(x_n^2 - \frac{2x_n}{R} + \frac{1}{R^2}) > 0$
$x_n(x_n - \frac{1}{R})^2 > 0$
Czyli $x_n\in (0,+\infty)$ \ {$\frac{1}{R}$}

Czyli, aby $x_{n+1}\in(0,\frac{1}{R})$ to $x_n\in(0,\frac{2}{R})$ \ {$\frac{1}{R}$}

### f)
Załóżmy, że $x_n\in(0,R^{-1})$ Pokażę, że $x_{n+1} > x_n$ oraz $x_{n+1} < R^{-1}$

**1$^\circ$ $x_{n+1} > x_n$**

$x_{n+1} = x_n(2-x_nR)$


$x_n < \frac{1}{R}$ (Z założenia prawdziwe, rozpatrujemy tylko dodatnie $x_n$)
$x_nR < 1$
$-x_nR > -1$
$2-x_nR > 1$ \ $\times x_n$ ($x_n dodatnie$)
$x_n(2-x_nR) > x_n$

**2$^\circ$ $x_{n+1} < R^{-1}$**

$(x_n+\frac{1}{R})^2>0$ (Z założenia prawdziwie)
$x_n^2 - 2\frac{x_n}{R} +\frac{1}{R^2} > 0$
$x_n^2 - 2\frac{x_n}{R} +\frac{1}{R^2} > 0$ / $\times R$ (R dodatnie)
$x_n^2R - 2x_n +\frac{1}{R} > 0$ / $\times-1$
$2x_n-x_n^2R -  \frac{1}{R} < 0$
$x_n(2-x_nR -  \frac{1}{x_nR}) < 0$
$x_n(2-x_nR) -  \frac{1}{R} < 0$
$x_n(2-x_nR) < \frac{1}{R}$

### g)
Załóżmy nie wprost, że $\lim\limits_{x \to \infty} x_n \neq \frac{1}{R}$
Wtedy rozpatrzmy 2 przypadki.

**1$^\circ$ $\lim\limits_{x \to \infty} x_n > \frac{1}{R}$**
Sprzeczność, ponieważ maksymalną wartość jaką mogą osiągnąć elementy $x_n$ wynoszą $\frac{1}{R}$ (Z podpunktu f)
**2$^\circ$ $\lim\limits_{x \to \infty} x_n < \frac{1}{R}$**
Weźmy takie g, że $\lim\limits_{x \to \infty} x_n  = g$ oraz z założenia g < $\frac{1}{R}$
Weźmy małe $\epsilon > 0$ takie , że $x_n = |g - \epsilon| = g - \epsilon$
Wtedy $x_{n+1} = x_n(2 - x_n\times R) = x_n \times (2-(g-\epsilon)\times R) = x_n\times(1 + \alpha)$ Gdzie $\alpha >\frac{1}{R} - g$ Możemy zauważyć, że kolejny element będzie zawsze przemnożony przez coś co jest >1, co pokazuje, że po pewnym czasie przekroczymy $g$ i dostaniemy liczbę większą, co pokazuje, że ciąg $x_n$ na pewno nie dąży do g.

Co kończy dowód.
Zbieżne jest dla liczby $x_0\in(0,\frac{2}{R})$
### h)
KOD

## 6
:::info
Stosując metodę Newtona, zaproponuj algorytm numerycznego obliczania $\frac1{\sqrt a}\space (a >0)$ bez wykonywania dzieleń. Opracowaną metodę sprawdź eksperymentalnie, w tym zbadaj m.in. jak warto dobierać $x_0$ oraz ile średnio iteracji wystarczy do osiągnięcia satysfakcjonujących wyników.
:::
$\frac{1}{\sqrt{a}} = x$
$\frac{1}{x} = \sqrt{a}$
$\frac{1}{x^2} = a$
$\frac{1}{x^2} - a = 0$
Dla $f(x) = \frac{1}{x^2} - a$
$f'(x) = -\frac{2}{x^3}$
$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} = x_n - \frac{\frac{1}{x_n^2} - a}{-\frac{2}{x_n^3}} = x_n + \frac{x_n - ax_n^3}{2} = \frac{x_n}{2}(3 - ax_n^2)$

$\Phi(x) =\frac{3}{2}x - \frac{ax^3}{2}$
$\Phi'(x) =\frac{3}{2} - \frac{3ax^2}{2}$
Zbieżne, gdy:
**$1^\circ$** $\Phi(\alpha) = \alpha$
$\Phi(\frac{1}{\sqrt{a}}) = \frac{3}{2\sqrt{a}} - \frac{a}{a\sqrt{a}} = \frac{3}{2\sqrt{a}} - \frac{1}{\sqrt{a}} = \frac{1}{\sqrt{a}}$
**$2^\circ$** $|\Phi'(x)| < 1$
$|\Phi'(x)| < 1$
$|\frac{3}{2} - \frac{3ax^2}{2}| < 1$
$|1 - ax^2| < \frac{2}{3}$
$|ax^2 - 1| < \frac{2}{3}$
$-\frac{2}{3} < ax^2 - 1 < \frac{2}{3}$
$\frac{1}{3} < ax^2 < \frac{5}{3}$
$\frac{1}{3a} < x^2 < \frac{5}{3a}$
$\frac{1}{\sqrt{3a}} < x < \frac{\sqrt{5}}{\sqrt{3a}}$
Zbieżne dla $x\in (\frac{1}{\sqrt{3a}},\frac{\sqrt{5}}{\sqrt{3a}}$

Im bliżej dobierzemy wartość $\frac{1}{\sqrt{a}}$ tym bliżej będziemy wyniku.

## 7

**Niech będziea=m2c, gdziecjest liczbą całkowitą, am–ułamkiem z przedziału[12,1). Zaproponuj efektywną metodę obliczania√a, otrzymanąprzez zastosowanie metody Newtona do wyznaczania zera pewnej funkcjif.Ustaleksperymentalniedla jakich wartościx0metoda jest zbieżna**

$\sqrt{m\times2^{c}} =
  \begin{cases}
    \sqrt{m}\times2^{k}       & \quad \text{dla } c \text{ parzystego takiego, że c = 2k}\\
    \sqrt{2m}\times2^{k}  & \quad \text{dla } c \text{ nieparzystego takiego, że c = 2k + 1}
  \end{cases}$

Wiemy, że $m\in[\frac{1}{2},1)$
Czyli zawężyliśmy problem wyszukiwania pierwiastka do przedziału $[\frac{1}{2},1)$ dla n parzystego oraz do $[\frac{\sqrt{2}}{2},\sqrt{2})$ dla c nieparzystego.
Czyli musimy napisać skuteczny algorytm obliczania pierwiastka z liczby, która jest z przedziału $[\frac{1}{2},\sqrt{2})$

**Wzór funkcji**
$\sqrt{a} = x$
$a = x^2$
$x^2-a = 0$
$f(x) = x^2-a$
$f'(x) = 2x$

$x_{n+1} = x_n - \frac{x_n^2-a}{2x_n} = x_n - \frac{x_n}{2} + \frac{a}{2x_n} =\frac{x_n}{2} + \frac{a}{2x_n} = \frac{1}{2}(x_n + \frac{a}{x_n})$

$\Phi(x) = \frac{1}{2}(x + \frac{a}{x}) = \frac{x}{2} + \frac{a}{2x}$

$\Phi'(x) = \frac{1}{2} - \frac{a}{2x^2}$

Zbieżność:

**$1^\circ$** $\Phi(\alpha) = \alpha$
$\Phi(\sqrt{a}) = \frac{\sqrt{a}}{2} + \frac{a}{2\sqrt{a}} = \frac{\sqrt{a}}{2} + \frac{\sqrt{a}}{2} = \sqrt{a}$

**$2^\circ$** $|\Phi'(x)| < 1$
$|\frac{1}{2} - \frac{a}{2x^2}| < 1$
$|1 - \frac{a}{x^2}| < 2$
$|\frac{a}{x^2} - 1| < 2$
$-2 < \frac{a}{x^2} - 1 < 2$
$-1 < \frac{a}{x^2} < 3$
$\frac{-1}{a} < \frac{1}{x^2} < \frac{3}{a}$
$0 < \frac{1}{x^2} < \frac{3}{a}$
$x^2 > \frac{a}{3}$
$x > \frac{\sqrt{3a}}{3}$
Wiemy, że nasz pierwiastek, którego szukamy jest z przedziału $[\frac{1}{2},\sqrt{2})$

<br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br>