571 lines
16 KiB
Plaintext
571 lines
16 KiB
Plaintext
|
{
|
||
|
|
"cells": [
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"id": "4cc6c96f",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"# Ćwiczenia 3"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"id": "1276423e",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"***TEMAT:*** przestrzenie metryczne"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"id": "a92c3fcc",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"## Przykłady metryk"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"id": "cd1dc617",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"### Definicja (metryka) \n",
|
||
|
|
"Jeżeli w niepustym zbiorze $X$ dla każdych dwóch elementów $x,y$ tego zbioru przyporządkowano liczbę nieujemną $d(x,y)$ taką, że\n",
|
||
|
|
"\n",
|
||
|
|
"1. $\\quad d(x,y)=0 \\ \\Longleftrightarrow \\ x=y$,\n",
|
||
|
|
"\n",
|
||
|
|
"2. $\\quad d(x,y)=d(y,x)$,\n",
|
||
|
|
"\n",
|
||
|
|
"3. $\\quad d(x,y)\\le d(x,z)+d(z,y)$ dla każdego $z\\in X$,\n",
|
||
|
|
"\n",
|
||
|
|
"to $d$ nazywamy odległością albo metryką, a parę $(X,d)$ przestrzenią metryczną."
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"id": "fd37d0aa",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"#### Zadanie 1 \n",
|
||
|
|
"Niech $X$ będzie zbiorem niepustym. Pokaż, że wzór\n",
|
||
|
|
"$$\n",
|
||
|
|
"d(x,y)=\\begin{cases}\n",
|
||
|
|
"1, & x\\not=y\\\\\n",
|
||
|
|
"0, & x=y\n",
|
||
|
|
"\\end{cases}\n",
|
||
|
|
"$$\n",
|
||
|
|
"definiuje metrykę na $X$.\n",
|
||
|
|
"\n",
|
||
|
|
"___Uwaga:___ metrykę $d$ nazywamy metryką dyskretną. Zadanie to pokazuje, że na każdym niepustym zbiorze jest ___jakaś___ metryka."
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"id": "bdfd11a6",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"##### Rozwiązanie:\n",
|
||
|
|
"Jest absolutnie jasne, że funkcja $d$ spełnia pierwszy i drugi warunek narzucany na metrykę.\n",
|
||
|
|
"Niech teraz $x,y,z\\in X$ będą dowolne. Jeśli\n",
|
||
|
|
"\n",
|
||
|
|
"$$\n",
|
||
|
|
"d(x,z)+d(z,y)=0,\n",
|
||
|
|
"$$\n",
|
||
|
|
"to \n",
|
||
|
|
"$$x=y=z \\quad\\text{ a zatem }\\quad d(x,y)=0.$$\n",
|
||
|
|
"Jeśli \n",
|
||
|
|
"\n",
|
||
|
|
"$$\n",
|
||
|
|
"d(x,z)+d(z,y)>0, \\quad \\text{to}\\quad d(x,z)+d(z,y)\\geq 1 \n",
|
||
|
|
"$$\n",
|
||
|
|
"\n",
|
||
|
|
"a zatem \n",
|
||
|
|
"\n",
|
||
|
|
"$$\n",
|
||
|
|
"d(x,y)\\leq 1\\leq d(x,z)+d(z,y).\n",
|
||
|
|
"$$\n",
|
||
|
|
"To pokazuje, że $d$ jest metryką."
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"id": "22ba9f05",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"#### Zadanie 2\n",
|
||
|
|
"__Metryka Hamminga__\n",
|
||
|
|
"\n",
|
||
|
|
"Niech $a = (a_1, a_2, ... , a_n)$, $b = (b_1, b_2, ... , b_n)$, \n",
|
||
|
|
"będą ciągami binarnymi długości $n$. Niech \n",
|
||
|
|
"$$\n",
|
||
|
|
"d_{HM}(a,b) = \\sum_{i=1}^n [ a_i (1 - b_i) + b_i (1-a_i)] .\n",
|
||
|
|
"$$\n",
|
||
|
|
"\n",
|
||
|
|
"1. Jaka jest interpretacja liczby $d_{HM} (a,b)$?\n",
|
||
|
|
"2. Pokaż, że $d_{HM}$ jest metryką na zbiorze wszystkich ciągów binarnych długości $n$. "
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"id": "ac327544",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"##### Rozwiązanie:\n",
|
||
|
|
"1. Łatwo zauważyć, że $d_{HM} (a,b)$ to liczba pozycji na których ciągi $a$ oraz $b$ się różnią.\n",
|
||
|
|
"2. Niech $d$ będzie metryką dyskretną na zbiorze $\\{0,1\\}$.\n",
|
||
|
|
"Widzimy, że \n",
|
||
|
|
"\n",
|
||
|
|
"$$\n",
|
||
|
|
"d_{HM}(a,b) = \\sum_{i=1}^n d(a_i,b_i). \n",
|
||
|
|
"$$\n",
|
||
|
|
"\n",
|
||
|
|
"Jest jasne, że funkcja $d_{HM}(a,b)$ spełnia pierwszy i drugi warunek narzucany na metrykę.\n",
|
||
|
|
"Niech teraz $a = (a_1, a_2, ... , a_n)$, $b = (b_1, b_2, ... , b_n)$, $c = (c_1, c_2, ... , c_n)$\n",
|
||
|
|
"będą dowolne.\n",
|
||
|
|
"Mamy (korzystając z poprzedniego zadania), że \n",
|
||
|
|
"\n",
|
||
|
|
"$$\n",
|
||
|
|
"d_{HM}(a,b) = \\sum_{i=1}^n d(a_i,b_i)\\leq \\sum_{i=1}^n (d(a_i,c_i)+d(c_i,b_i))=d_{HM}(a,b)+d_{HM}(b,c).\n",
|
||
|
|
"$$\n",
|
||
|
|
"To pokazuje, że $d_{HM}$ jest metryką."
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"id": "b375c3ed",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"#### Zadanie 3\n",
|
||
|
|
" __Metryka Levenshteina__ \n",
|
||
|
|
" \n",
|
||
|
|
"Jest to metryka w przestrzeni ciągów znaków, zdefiniowana następująco - działaniem prostym na napisie nazwiemy: \n",
|
||
|
|
">* wstawienie nowego znaku do napisu\n",
|
||
|
|
">* usunięcie znaku z napisu \n",
|
||
|
|
">* zamianę znaku w napisie na inny znak. \n",
|
||
|
|
"\n",
|
||
|
|
"Odległością pomiędzy dwoma napisami jest najmniejsza liczba działań prostych, przeprowadzających jeden napis na drugi.\n",
|
||
|
|
"\n",
|
||
|
|
"1. Uzasadnij, że metryka Levenshteina jest w istocie metryką na zbiorze wszyskich skończonych ciągów znaków.\n",
|
||
|
|
"2. Przeanalizuj poniższy kod (zadanie domowe) i przetestuj go dla kilku par ciągów znaków.\n",
|
||
|
|
"\n",
|
||
|
|
"___Uwaga:___ więcej informacji można znaleźć tutaj: https://www.geeksforgeeks.org/introduction-to-levenshtein-distance/"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"execution_count": 1,
|
||
|
|
"id": "a628dda8",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"name": "stdout",
|
||
|
|
"output_type": "stream",
|
||
|
|
"text": [
|
||
|
|
"Levenshtein Distance: 1\n"
|
||
|
|
]
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"source": [
|
||
|
|
"def levenshteinRecursive(str1, str2, m, n):\n",
|
||
|
|
" # str1 is empty\n",
|
||
|
|
" if m == 0:\n",
|
||
|
|
" return n\n",
|
||
|
|
" # str2 is empty\n",
|
||
|
|
" if n == 0:\n",
|
||
|
|
" return m\n",
|
||
|
|
" if str1[m - 1] == str2[n - 1]:\n",
|
||
|
|
" return levenshteinRecursive(str1, str2, m - 1, n - 1)\n",
|
||
|
|
" return 1 + min(\n",
|
||
|
|
" # Insert \n",
|
||
|
|
" levenshteinRecursive(str1, str2, m, n - 1),\n",
|
||
|
|
" min(\n",
|
||
|
|
" # Remove\n",
|
||
|
|
" levenshteinRecursive(str1, str2, m - 1, n),\n",
|
||
|
|
" # Replace\n",
|
||
|
|
" levenshteinRecursive(str1, str2, m - 1, n - 1))\n",
|
||
|
|
" )\n",
|
||
|
|
" \n",
|
||
|
|
"# Drivers code\n",
|
||
|
|
"str1 = \"adam\"\n",
|
||
|
|
"str2 = \"adaś\"\n",
|
||
|
|
"distance = levenshteinRecursive(str1, str2, len(str1), len(str2))\n",
|
||
|
|
"print(\"Levenshtein Distance:\", distance)"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"id": "685970d0",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"##### Rozwiązanie:\n",
|
||
|
|
"Jest jasne, że metryka Levenshteina spełnia pierwszy i drugi warunek nakładany na metrykę.\n",
|
||
|
|
"Niech $x,y,z$ będą dowolnymi napisami. Zauważmy, że aby za pomocą działań prostych zamieć $x$ na $z$ możemy najpierw zamienić $x$ na $y$ a potem $y$ na $z$. Oczywiście nie musi to być optymalne podejście.\n",
|
||
|
|
"Zatem \n",
|
||
|
|
"$$\n",
|
||
|
|
"d(x,z)\\leq d(x,y)+d(y,z).\n",
|
||
|
|
"$$"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"id": "6c20d350",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"#### Zadanie 4\n",
|
||
|
|
"Niech $C([0,1])$ oznacza zbiór wszystkich funkcji ciągłych (o wartościach rzeczywistych bądź zespolnych) określonych na $[0,1]$.\n",
|
||
|
|
"Pokaż, że wzór \n",
|
||
|
|
"\n",
|
||
|
|
"$$\n",
|
||
|
|
"d_\\infty(f,g)=\\max_{x\\in[0,1]} |f(x)-g(x)|\n",
|
||
|
|
"$$\n",
|
||
|
|
"definiuje metrykę na $C([0,1])$. Oblicz $d_\\infty(f,g)$ dla $f(x)=x$ i $g(x)=1-x$."
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"id": "2eace208",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"##### Rozwiązanie:\n",
|
||
|
|
"1. Jeśli $d_\\infty(f,g)=0$, to $f(x)=g(x)$ dla wszystkich $x\\in [0,1]$. Zatem $f=g$.\n",
|
||
|
|
"2. Jest jasne, że $d_\\infty(f,g)=d_\\infty(g,f)$.\n",
|
||
|
|
"3. Niech $f,g,h$ będą funkcjami ciągłymi na $[0,1]$. Mamy\n",
|
||
|
|
"\n",
|
||
|
|
"$$\n",
|
||
|
|
"\\begin{align}\n",
|
||
|
|
"d_\\infty(f,h)&=\\max_{x\\in[0,1]} |f(x)-h(x)|=\\max_{x\\in[0,1]}|f(x)-g(x)+g(x)-h(x)|\\\\\n",
|
||
|
|
"&\\leq \\max_{x\\in[0,1]} \\left(|f(x)-g(x)|+|h(x)-g(x)|\\right)\n",
|
||
|
|
"\\leq \\max_{x\\in[0,1]} |f(x)-g(x)|+\\max_{x\\in[0,1]} |h(x)-g(x)|\\\\\n",
|
||
|
|
"&=d_\\infty(f,g)+d_\\infty(g,h)\n",
|
||
|
|
"\\end{align}\n",
|
||
|
|
"$$\n",
|
||
|
|
"\n",
|
||
|
|
"Dla funkcji $f$ oraz $g$ takich jak w zadaniu mamy:\n",
|
||
|
|
"\n",
|
||
|
|
"$$\n",
|
||
|
|
"d(f,g)=\\max_{x\\in[0,1]}|f(x)-g(x)|=\\max_{x\\in[0,1]}|2x-1|=1.\n",
|
||
|
|
"$$"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"id": "449e2c7d",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"#### Zadanie 5\n",
|
||
|
|
"\n",
|
||
|
|
"Niech $C([0,1])$ oznacza zbiór wszystkich funkcji ciągłych (o wartościach rzeczywistych bądź zespolnych) określonych na $[0,1]$.\n",
|
||
|
|
"Pokaż, że wzór\n",
|
||
|
|
"\n",
|
||
|
|
"$$\n",
|
||
|
|
"d_1(f,g)=\\int_0^1|f(x)-g(x)|dx\n",
|
||
|
|
"$$\n",
|
||
|
|
"definiuje metrykę na $C([0,1])$. Oblicz $d_1(f,g)$ dla $f(x)=x$ i $g(x)=1-x$."
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"id": "5f8b9115",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"##### Rozwiązanie: \n",
|
||
|
|
"\n",
|
||
|
|
"1. Jeśli $d_1(f,g)=0$, to jest jasne, że $f(x)=g(x)$ dla $x\\in [0,1]$, a zatem $f=g$.\n",
|
||
|
|
"2. Jest oczywiste, że $d_1(f,g)=d_1(g,f)$.\n",
|
||
|
|
"3. Dla $f,g,h\\in C([0,1])$ mamy\n",
|
||
|
|
"\n",
|
||
|
|
"$$\n",
|
||
|
|
"\\begin{align}\n",
|
||
|
|
"d_1(f,g)=&\\int_0^1|f(x)-g(x)|dx=\\int_0^1|f(x)-h(x)+h(x)-g(x)|dx\\\\\n",
|
||
|
|
"\\leq & \\int_0^1|f(x)-h(x)|dx+\\int_0^1|h(x)-g(x)|dx\\\\\n",
|
||
|
|
"=& d_1(f,h)+d_1(h,g).\n",
|
||
|
|
"\\end{align}\n",
|
||
|
|
"$$\n",
|
||
|
|
"\n",
|
||
|
|
"Dla $f$ oraz $g$ takich jak w zadaniu mamy (pamiętajmy o geometrycznej intepretacji całki jako polu)\n",
|
||
|
|
"\n",
|
||
|
|
"$$\n",
|
||
|
|
"d_1(f,g)=\\int_0^1|2x-1|dx=1/2.\n",
|
||
|
|
"$$"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"id": "116d122b",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"___Uwaga!!!___ \n",
|
||
|
|
"W zastosowaniach dużo ważniejsza jest metryka \n",
|
||
|
|
"$$\n",
|
||
|
|
"d_2(f,g)=\\left(\\int_0^1|f(x)-g(x)|^2dx\\right)^{\\frac 12}.\n",
|
||
|
|
"$$"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"id": "db9b72e9",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"## Zbieżność w przestrzeniach metrycznych"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"id": "2b0d9d62",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"### Definicja (zbieżność w przestrzeni metrycznej)\n",
|
||
|
|
"\n",
|
||
|
|
"Mówimy, że ciąg $(x_n)$ punktów $x_n\\in X$ jest zbieżny do punktu $x\\in X$ gdy\n",
|
||
|
|
"\n",
|
||
|
|
"$$\n",
|
||
|
|
"d(x_n,x)\\longrightarrow 0 \\quad\\quad\\text {dla}\\quad n\\to\\infty .\n",
|
||
|
|
"$$"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"id": "00ccd3cd",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"#### Zadanie 6\n",
|
||
|
|
"\n",
|
||
|
|
"W $\\mathbb{R}^n$ odległość Euklidesowa jest określona wzorem\n",
|
||
|
|
"\n",
|
||
|
|
"$$\n",
|
||
|
|
"d((x_1,\\ldots, x_n),(y_1,\\ldots, y_n))=\\sqrt{\\sum_{i=1}^n(x_i-y_i)^2}.\n",
|
||
|
|
"$$\n",
|
||
|
|
"1. Jaka jest granica ciągu $\\left(\\frac{1}{n},2+\\frac{1}{n^2}\\right)$ w $\\mathbb{R}^2$?\n",
|
||
|
|
"2. Postaw hipotezę o tym jak badać zbieżność ciągów w $\\mathbb{R}^n$."
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"id": "8c47f547",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"##### Rozwiązanie:\n",
|
||
|
|
"\n",
|
||
|
|
"1. Pokażemy, że granicą ciągu $\\left(\\frac{1}{n},2+\\frac{1}{n^2}\\right)$ jest $(0,2)$.\n",
|
||
|
|
"mamy\n",
|
||
|
|
"\n",
|
||
|
|
"$$\n",
|
||
|
|
"d\\left(\\left(\\frac{1}{n},2+\\frac{1}{n^2}\\right),(0,2)\\right)=\\sqrt{\\frac{1}{n^2}+\\frac{1}{n^4}}\\xrightarrow{n\\to\\infty} 0.\n",
|
||
|
|
"$$\n",
|
||
|
|
"\n",
|
||
|
|
"2. Prawdziwy jest następujący fakt:\n",
|
||
|
|
"> Ciąg $((x^k_1,\\ldots, x^k_n))_{k\\in\\mathbb{N}}$ jest zbieżny do $(x^0_1,\\ldots, x^0_n)$ w $\\mathbb{R}^n$ z metryką Euklidesową wtedy i tylko wtedy, gdy dla każdego $1\\leq i\\leq n$ ciąg liczbowy $(x^k_i)_{k\\in\\mathbb{N}}$ jest zbieżny do $x^0_i$. \n",
|
||
|
|
"\n",
|
||
|
|
"Wynika on bardzo łatwo z nierówności\n",
|
||
|
|
"\n",
|
||
|
|
"$$\n",
|
||
|
|
"\\max_{1\\leq i\\leq n}|x^k_i-x^0_i|\\leq\\sqrt{\\sum_{i=1}^n(x^k_i-x^0_i)^2}\\leq \\sum_{i=1}^n|x^k_i-x^0_i|.\n",
|
||
|
|
"$$\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"id": "1b40f968",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"#### Zadanie 7\n",
|
||
|
|
"1. Pokaż, że jeśli ciąg $(f_n)$ jest zbieżny do $f$ w $C([0,1])$ z metryką $d_\\infty$, to jest zbieżny do jest zbieżny do $f$ w przestrzeni $C([0,1])$ z metryką $d_1$.\n",
|
||
|
|
"2. Niech $f_n(x)=x^n$ i $f(x)=0$. Zbadaj zbieżność tego ciągu do $f$ w przestrzeni $C([0,1])$ z metryką $d_1$ i w przestrzeni $C([0,1])$ z metryką $d_\\infty$."
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"id": "95c73b26",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"##### Rozwiązanie:\n",
|
||
|
|
"1. Dla dowolnych funkcji $f_n$ oraz $f$ mamy\n",
|
||
|
|
"\n",
|
||
|
|
"$$\n",
|
||
|
|
"d_1(f_n,f)=\\int_0^1|f_n(x)-f(x)|dx\\leq \\int_0^1\\max_{x\\in[0,1]}|f(x)-g(x)|dx=\\max_{x\\in[0,1]}|f(x)-g(x)|=d_\\infty(f_n,f).\n",
|
||
|
|
"$$\n",
|
||
|
|
"\n",
|
||
|
|
"Zatem jeśli ciąg $d_\\infty(f_n,f)$ dąży do zera, to ciąg $d_1(f_n,f)$ dąży do zera.\n",
|
||
|
|
"\n",
|
||
|
|
"2. Mamy\n",
|
||
|
|
"\n",
|
||
|
|
"$$\n",
|
||
|
|
"d_\\infty(f_n,f)=\\max_{x\\in [0,1]}|x^n|=1.\n",
|
||
|
|
"$$\n",
|
||
|
|
"\n",
|
||
|
|
"Zatem ciąg $(f_n)$ nie jest zbieżny do $f$ w przestrzeni $C([0,1])$ z metryką $d_\\infty$.\n",
|
||
|
|
"\n",
|
||
|
|
"Ponadto\n",
|
||
|
|
"\n",
|
||
|
|
"$$\n",
|
||
|
|
"d_1(f_n,f)=\\int_0^1x^ndx=\\frac{1}{n+1}\\xrightarrow{n\\to\\infty}0.\n",
|
||
|
|
"$$\n",
|
||
|
|
"\n",
|
||
|
|
"Zatem ciąg $(f_n)$ jest zbieżny do $f$ w przestrzeni $C([0,1])$ z metryką $d_1$.\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"id": "9d02362d",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"## Twierdzenie Banacha o punkcie stałym"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"id": "a99122b5",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"### Definicja (kontrakcja)\n",
|
||
|
|
"\n",
|
||
|
|
"Odwzorowanie $T:X \\to X$ przestrzeni metrycznej $(X,d)$ w siebie nazywamy __kontrakcją__ lub odwzorowaniem zwężającym, gdy istnieje taka liczba $L$, spełniająca nierówności $0<L<1$, że dla każdych $x,y\\in X$ zachodzi nierówność\n",
|
||
|
|
"\n",
|
||
|
|
"$$\n",
|
||
|
|
"d(T(x),T(y))\\leq L d(x,y) . \n",
|
||
|
|
"$$"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"id": "e22bab88",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"### Twierdzenie (Banacha o punkcie stałym).\n",
|
||
|
|
"\n",
|
||
|
|
"> __Twierdzenie.__ Niech $X$ będzie przestrzenią metryczną zupełną. Jeżeli odwzorowanie $T:X\\to X$ jest kontrakcją ze stałą $L < 1$, to istnieje dokładnie jeden punkt stały $x_0$ tego odwzorowania. Ponadto punkt ten można otrzymać jako granicę ciągu $(x_n)$ określonego w następujący sposób: $x_1$ jest dowolnym punktem z przestrzeni $X$, a $x_{n+1}=T(x_n)$ dla $n=1,2,\\ldots$.\n",
|
||
|
|
"\n",
|
||
|
|
"> Co więcej: prawdziwa jest również następująca nierówność\n",
|
||
|
|
"\n",
|
||
|
|
"$$\n",
|
||
|
|
" d(x_n,x_0) \\leq \\frac{L^{n-1}}{1-L} \\cdot d(x_2,x_1) .\n",
|
||
|
|
"$$"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"id": "944460ca",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"#### Zadanie 8\n",
|
||
|
|
"\n",
|
||
|
|
"Pokażemy, że równanie \n",
|
||
|
|
"\n",
|
||
|
|
"$$\n",
|
||
|
|
"x^{10}+11x-11=0\n",
|
||
|
|
"$$\n",
|
||
|
|
"\n",
|
||
|
|
"ma dokładnie jedno rozwiązanie w przedziale $[0,1]$."
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"id": "82b6291d",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"##### Rozwiązanie:\n",
|
||
|
|
"Nasze równanie jest równoważne równaniu\n",
|
||
|
|
"\n",
|
||
|
|
"$$\n",
|
||
|
|
"x=1-\\frac{x^{10}}{11}.\n",
|
||
|
|
"$$\n",
|
||
|
|
"\n",
|
||
|
|
"Niech \n",
|
||
|
|
"\n",
|
||
|
|
"$$\n",
|
||
|
|
"f(x)=1-\\frac{x^{10}}{11}.\n",
|
||
|
|
"$$\n",
|
||
|
|
"1. Jest jasne, że funkcja $f$ przekształca odcinek $[0,1]$ w odcinek $[0,1]$.\n",
|
||
|
|
"2. Ponieważ $f'(x)=\\frac{10}{11}x^{9}$, to dla $x\\in [0,1]$ mamy, że $|f'(x)|\\leq \\frac{10}{11}$.\n",
|
||
|
|
"Z twierdzenia o wartości średniej wynika zatem, że $f$ jest kontrakcją ze stałą $L=\\frac{10}{11}$.\n",
|
||
|
|
"3. Na mocy Twierdzenia Banacha $f$ ma dokładnie jeden punkt stały w $[0,1]$. "
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"execution_count": 2,
|
||
|
|
"id": "85cafa96",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"name": "stdout",
|
||
|
|
"output_type": "stream",
|
||
|
|
"text": [
|
||
|
|
"The 100000-th iterate of 0.5 under f is: 0.9471695279677836\n"
|
||
|
|
]
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"source": [
|
||
|
|
"def f(x):\n",
|
||
|
|
" return 1 - (x ** 10) / 11\n",
|
||
|
|
"\n",
|
||
|
|
"def nth_iterate(x, n):\n",
|
||
|
|
" for _ in range(n):\n",
|
||
|
|
" x = f(x)\n",
|
||
|
|
" return x\n",
|
||
|
|
"\n",
|
||
|
|
"# Example usage:\n",
|
||
|
|
"x_initial = 0.5 # initial value of x in [0, 1]\n",
|
||
|
|
"n = 100000 # number of iterations\n",
|
||
|
|
"result = nth_iterate(x_initial, n)\n",
|
||
|
|
"print(f\"The {n}-th iterate of {x_initial} under f is: {result}\")\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"execution_count": 3,
|
||
|
|
"id": "4128d41e",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"data": {
|
||
|
|
"text/plain": [
|
||
|
|
"True"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
"execution_count": 3,
|
||
|
|
"metadata": {},
|
||
|
|
"output_type": "execute_result"
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"source": [
|
||
|
|
"f(0.9471695279677836) == 0.9471695279677836"
|
||
|
|
]
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"metadata": {
|
||
|
|
"kernelspec": {
|
||
|
|
"display_name": "Python 3 (ipykernel)",
|
||
|
|
"language": "python",
|
||
|
|
"name": "python3"
|
||
|
|
},
|
||
|
|
"language_info": {
|
||
|
|
"codemirror_mode": {
|
||
|
|
"name": "ipython",
|
||
|
|
"version": 3
|
||
|
|
},
|
||
|
|
"file_extension": ".py",
|
||
|
|
"mimetype": "text/x-python",
|
||
|
|
"name": "python",
|
||
|
|
"nbconvert_exporter": "python",
|
||
|
|
"pygments_lexer": "ipython3",
|
||
|
|
"version": "3.12.4"
|
||
|
|
},
|
||
|
|
"toc": {
|
||
|
|
"base_numbering": 1,
|
||
|
|
"nav_menu": {},
|
||
|
|
"number_sections": false,
|
||
|
|
"sideBar": true,
|
||
|
|
"skip_h1_title": false,
|
||
|
|
"title_cell": "Table of Contents",
|
||
|
|
"title_sidebar": "Contents",
|
||
|
|
"toc_cell": false,
|
||
|
|
"toc_position": {},
|
||
|
|
"toc_section_display": true,
|
||
|
|
"toc_window_display": true
|
||
|
|
}
|
||
|
|
},
|
||
|
|
"nbformat": 4,
|
||
|
|
"nbformat_minor": 5
|
||
|
|
}
|