Уражнения 6

Тука сложи заглавие


страницата се нуждае от дописване/преглеждане


a = x_0 < x_1 < … < x_n = b
"Начупена линия" I(f; x) = \Sigma_{k=0}^n c_K |x - x_k|

c_0 = 1/2 ((f(x_0) + f(x_n))/(x_n - x_0) + f[x_1, x_1])
c_n = 1/2 ((f(x_0) + f(x_n))/(x_n - x_0) - f[x_{n-1}, x_n])
c_k = 1/2 ((f[x_k, x_{k+1}] - f[x_{k-1}, x_k]), k = 1, 2, …, n

[a,b] = [0,1]
f(x) = sqrt(x)

a) x_k = k/n, k = 0, 1, …, n
б) x_k = (k/n)^4, k = 0, 1, …, n

Сега, на Mathematica:

n = 10; Do[x[k] = k/n, {k, 0, n}]; f[t_] := Sqrt[t];
c[0] = ((f[x[0]] + f[x[n]])/(x[n] - x[0]) + (f[x[1]] - f[x[0]])/(x[1] - x[0]))/2;
c[n] = ((f[x[0]] + f[x[n]])/(x[n] - x[0]) - (f[x[n]] - f[x[n - 1]])/(x[n] - x[n - 1]))/2;
Do[c[k] = ((f[x[k + 1]] - f[x[k]])/(x[k + 1] - x[k]) - (f[x[k]] - f[x[k - 1]])/(x[k] - x[k - 1]))/2, {k, 1, n - 1}];
I1[t_] := Sum[c[k] Abs[t - x[k]], {k, 0, n}];
Plot[{f[t], I1[t]}, {t, 0, 1}]
Plot[f[t] - I1[t], {t, 0, 1}, PlotRange -> All]

Най-голямата грешка е в първия интервал, като тя прогресивно намалява. Порядъкът е около 0.08 . С n = 20, грешката
пада до около 0.055 .

За втората формула, задаваме x[i] като (k/n)^4:

n = 10; Do[x[k] = (k/n)^4, {k, 0, n}]; f[t_] := Sqrt[t];
c[0] = ((f[x[0]] + f[x[n]])/(x[n] - x[0]) + (f[x[1]] - f[x[0]])/(x[1] - x[0]))/2;
c[n] = ((f[x[0]] + f[x[n]])/(x[n] - x[0]) - (f[x[n]] - f[x[n - 1]])/(x[n] - x[n - 1]))/2;
Do[c[k] = ((f[x[k + 1]] - f[x[k]])/(x[k + 1] - x[k]) - (f[x[k]] - f[x[k - 1]])/(x[k] - x[k - 1]))/2, {k, 1, n - 1}];
I1[t_] := Sum[c[k] Abs[t - x[k]], {k, 0, n}];
Plot[{f[t], I1[t]}, {t, 0, 1}]
Plot[f[t] - I1[t], {t, 0, 1}, PlotRange -> All]

тук, за 10 възела имаме грешка от порядък 0.005, а за 20 - 0.0012, т. е. грешката пада около 4 точки.
Сега ще обосновем защо се получава така.

Аналитична обосновка: Нека x \in (x_i, x_{i+1}). Тогава
\phi(x) = f(x) - I_1(f;x) = sqrt(x) - ((x_{i+1} - x) / (x_{i+1} - x_i) sqrt(x_i) + (x - x_i)/(x_{i+1} - x_i) sqrt(x_{i+1}).
В интервала (x_i, x_{i+1}) това е "арка"/дъга. /* дъгата е горното */


-
- -
—* - |
— | - |
— -* |
/ - | |
/- | |
| | |
||___|
x_i x_i^* x_{i+1}

\phi'(x) = 1/(2sqrt(x)) - (sqrt(x_{i+1}) - sqrt(x_i))/(x_{i+1} - sqrt(x)) = 1/(2sqrt(x)) - 1/(sqrt(x_{i+1}) + sqrt(x_i)) = 0
Производната на \phi(x) се анулира в точката x_i^* - там имаме най-голяма грешка.
sqrt(x_i^*) = (sqrt(x_i) + sqrt(x_{i+1}))/2
\Phi(x_i^*) = (sqrt(x_i) + sqrt(x_{i+1}))/2 -
((sqrt(x_{i+1}) - sqrt(x_i))/(x_{i+1} - x_i)((sqrt(x_i) +
sqrt(x_{i+1})/2)^2 + (x_{i+1}sqrt(x_i) - x_i sqrt(x_{i+1})/(x_{i+1} - x_i)) =
(sqrt(x_i) + sqrt(x_{i+1}))/2 - (sqrt(x_i) + sqrt(x_{i+1})/4 -
(sqrt(x_i)sqrt(x_{i+1})(sqrt(x_{i+1}) - sqrt(x_i)))/((sqrt(x_{i+1}) - sqrt(x_i)))((sqrt(x_{i+1}) + sqrt(x_i)))) =
(sqrt(x_i) + sqrt(x_{i+1}))/4 - (sqrt(x_i)sqrt(x_{i+1}))/(sqrt(x_{i+1} + sqrt(x_i)) =

(sqrt(x_i)sqrt(x_{i+1}))/(sqrt(x_{i+1} + sqrt(x_i)) =

((sqrt(x_i) + sqrt(x_{i+1}))^2 - 4sqrt(x_i)sqrt(x_{i+1})/(4(sqrt(x_i) + sqrt(x_{i+1})))

Така, след рационализация, максималната грешка в интервала [x_i, x_{i+1}] е (sqrt(x_{i+1}) - sqrt(x_i))^3/(4(x_{i+1} - x_i))

1) При x_i = i/n,
(sqrt(x_{i+1}) - sqrt(x_i))^3/(4(x_{i+1} - x_i)) =
(sqrt(x_{i+1}) - sqrt(x_i))^3/(4sqrt(n)) \le 1/(4sqrt(n)) -> 0 при n -> \inf, както 1\sqrt(n\).

2) При x_i = (i/n)^4:

(((i+1)/n)^2 - (i/n)^2)^3/(4(((i+1)/n)^4 - (i/n)^ 4)) = (((i+1)/n)^2 - (i/n)^2)^2/(4(((i+1)/n)^2 + (i/n)^ 2))
/* Опростяваме чрез формулата сбор по разлика */
= 1/(4n^2) (2i+1)^2/((i+1)^2 + i^2) = 1/(4n^2) (4i^2+4i+2-1)/(2i^2 + 2i + 1) = 1/(4n^2) (2 - 1/(2i^2 + 2i + 1))
/* Това, полученото, расте при растящо i (но расте бавно - както видяхме, арките са почти еднакво високи) */
< 1/2n^2 -> 0 при n -> \inf, както 1/n^2.
Това обяснява защо, при удвояване на възлите, грешката намаля приблизително 4 пъти.
Така се обясняват аналитично получените от визуализацията резултати. За конкретната функция, изборът на възлите е важен.
Обяснение с "думи": функцията sqrt(x) расте най-бързо в началото, тъй като производната ‘и
(sqrt(x))’ = 1/(2sqrt(x)) се държи по същия начин. Затова е хубаво в началото да имаме много възли.

Неща, свързани със сходимост (нещо от миналия път):

a = x_0 < x_1 < … < x_n = b
Доказахме ей такава оценка:
|f(x) - I_1(f;x)| \le \omega(f; \Delta), където \omega е модулът на непрекъснатост на функцията:
\omega(f; \delta) = sup{|f(x) - f(y)|: x,y \in [a,b], |x-y| \le \delta}

Ще решим следната задача:
Задача. Нека [a,b] = [0,1], x_k = k/n за k = 0, 1, …, n. Ако f /in C^1[0,1] (съществува първа производна) и
|f'(x)| \le M = const, \Each x \in [0,1], да се докаже, че за всяко x \in [0,1] е изпълнено:
|f(x) - I_1(f;x)| \le M/n, \Each n, и клони към 0 при n -> 0, както 1/n .
Каква е причината? f(x) = sqrt(x), f'(x) = 1/(2sqrt(x)) -> +\inf при x -> 0.

Ще използваме едно свойство.
Свойство на модула на непрекъснатост:
Ако f' съществува в (a,b) и |f'(x)| \le M в [a,b], тогава \omega(f;\delta) \le M\delta , M = const.

Доказателство на свойството: За \Each x,y \in [a,b], f(x) - f(y) = f'(\xi).(x-y) - теорема на Лагранж за крайни нараствания.
|f(x) - f(y)| = |f'(\xi)|.|x-y| \le M.|x-y| \le M\delta
Така M\delta е горна граница за множеството {|f(x) - f(y)|, x, y \in [a,b], |x - y| \le \delta}
Но \omega(f;\delta) е точна горна граница за същото множество. Следователно \omega(f;\delta) \le M\delta .

Решение на задачата: Имаме
|f(x) - I_1(f;x)| \le \omega(f;\Delta) = \omega(f; 1/n)
Съгласно свойството: |f(x) - I_1(f;x)| \le M.(1/n) = M/n - задачата е решена. (Безпардонно!)

Така, ако функцията има първа производна, скоростта на (?намаляване на грешката??) е 1/n. Ами ако има и втора?

Задача. Нека [a,b] = [0,1], x_k = k/n за k = 0, 1, …, n. Ако f /in C^2[0,1], да се докаже: съществува константа
C > 0, независеща от n, такава, че |f(x) - I_1(f;x)| \le C/\n^2 .

Решение: Нека x \in [x_i, x_{i+1}]. Тогава I_1(f;x) \equiv L_1(f;x) - полиномът на Лагранж, интерполиращ f в точките
x_i и x_{i+1}. От теорията знаем: f(x) - L_1(f;x) = f''(\xi)/2 (x - x_i)(x - x_{i+1})
|f(x) - L_1(f;x)| \le (max_{x \in [0,1]}|f''(x)|)/2 (x - x_i)(x_{i+1} - x)

Ако max_{x \in [0,1]}|f''(x)| = M, тогава |f(x) - I_1(f;x)| \le M/2 (x - x_i)(x_{i+1} - x_ \le M/2 ((x_{i+1} - x_i)/2)^2
= M/8 . 1/n^2 . Така C = M/8 върши работа.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License