Упражнение 3

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


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


$L_n(f;x) = f(x_0) + \underset {k=0} {\overset n \sum}} f[x_0,...,x_k](x - x_0)...(x - x_k)$
$[-1, 1], x_k = cos \cfrac {(2k + 1)\pi} {2n + 2}, k = 0, 1, ... , n$

$f[x_i] = f(x_i) ; f[x_0, ..., x_k] = \cfrac {f[x_1, ..., x_k] - f[x_0, ..., x_{k-1}]} {x_k - x_0}$

С $a_{kj}$ ще означаваме разделената разлика $f[x_j, ..., x_{j+k}]$.

n = 5;
f[t_] := 1/(1 + t^2);
Do[x[k] = Cos[(2 k + 1) Pi/(2 n + 2)], {k, 0, n}];

(*Разделените разлики:*)
Do[a[k, 0] = f[x[k]], {k, 0, n}];
Do[a[0, k] = f[x[k]], {k, 0, n}];

(*Попълваме РР от ред 1 до n,като за всяка РР в отделен цикъл \
смятаме:*)
Do[Do[a[k, j] = (a[k - 1, j + 1] - a[k - 1, j])/(x[j + k] - x[j]), {j,
     0, n - k}], {k, 1, n}];
L[t_] := a[0, 0] + 
   Sum[a[k, 0] Product[t - x[j], {j, 0, k - 1}], {k, 1, n}];

Plot[{f[t], L[t]}, {t, -1, 1}]
Plot[f[t] - L[t], {t, -1, 1}]

Да се опита и с n = 10. Ще върви доста по-бавно.
Следващия път ще модифицираме програмата, за да работи и за съвпадащи възли - интерполационна задача на Ермит. Там ще се проверява дали най-малкият и най-големият възел съвпадат.

Сега, две задачи за контролното:

Задача 1.

Като използвате интерполационната формула на Лагранж, докажете тъждествата:

(1)
\begin{eqnarray} \underset {k=0} {\overset n \sum} (-1)^{n+k} \binom n k \binom m n .\frac 1 {m - k} = \frac 1 {m - n}, \forall m > n \ge 0 \\ \underset {k=0} {\overset n \sum} (-1)^{n+k} \binom n k \binom m n .\frac k {m - k} = \frac m {m - n}, \forall m > n \ge 0 \end{eqnarray}

За целта ще [?] (в долните формули има нещо адски съмнително, някой да ги прегледа!):

(2)
\begin{eqnarray} && x_k = k, k = 0, 1, \dots, n \left \\ && L_n(f; k) = \underset {k=0} {\overset n \sum} \cfrac {\omega(x)} {(x - x_k) \omega'(x_k)} f(x_k) = \cfrac {x(x - 1)...(x - k + 1)(x - k - 1) ... (x - n)} {k (k - 1) ... 1 . (-1)(-2)...(-(n- k ))} \end{eqnarray}

В знаменателя имаме: $k! (n - k)! (-1)^{n - k}$

(3)
\begin{eqnarray} L_n(f; m) &=& \underset {k=0} {\overset n \sum} (-1)^{n-k} \cfrac 1 {k! (n - k)!} \cfrac {m(m - 1) ... (m - n)} {(m-k)} f(k) = \\ &=& \underset {k=0} {\overset n \sum} (-1)^{n - k} \binom n k \cfrac {m(m - 1) ... (m - n + 1)(m - n)} {n! (m - k)} f(k) = \\ &=& \underset {k=0} {\overset n \sum} (-1)^{n - k} \binom n k \binom m n \cfrac {m - n} {m - k} f(k) \end{eqnarray}

За първата формула:
При $f(x) \equiv 1, f(k) = 1, \forall k, L_n(f;m) \equiv f(m) \equiv 1$,
$1 = \underset {k=0} {\overset n \sum} (-1)^{n - k} \binom n k \binom m n \cfrac {m - n} {m - k} = 1$ | : (m - n) (това може би означава "съкращаваме на (m - n) ?)

За втората формула:
При $f(x) \equiv x && f(x) \ge 1, L_n(f;m) \equiv f(m) \equiv m$,
$\underset {k=0} {\overset n \sum} (-1)^{n - k} \binom n k) \binom m n) \cfrac {m - n} {m - k}.k = m$ | : (m-n)

Крайни разлики

$f_0, \dots, f_n, \dots$
$\delta^0 f_i := f_i$
$\delta^k f_i = \delta^{k-1} f_{i+1} - \delta^{k-1} f_i, k = 1, 2, \dots$

Когато $f_i = f(x_i)$ и $x_i = x_9 + i.h, i = 9, ..., n$ (равноотдалечени), $f[x_0, ..., x_n] = \cfrac {\delta^n(f_0)} {n! h^n}$
$\delta^n f_i = \underset {k=0} {\overset n \sum}(-1)^{n-k} \binom n k) f_{i+k}$

Ако $f \in \Pi_{n-1}$ , тогава $\delta^n f_i = 0$
Ако $f \in \Pi_n$, тогава $\delta^n f_i = n! h^n$ . (коефициентът пред x^n във f(x) )

Задача 2.

Като се използват свойствата на кройните разлики, да се докажат следните две тъждества:
а) $\underset {k=0} {\overset n \sum} (-1)^{n - k} \binom n k .k^m = {0, m = 0, 1, ..., n-1 ; n!, m = n}$
б) $\underset {k=0} {\overset n \sum} (-1)^{n - k} \binom n k \binom {m + k} l = 0, \forall m, l = 0, 1, ..., n - 1$

а) Лявата страна е крайна разлика от $f(x) = x^m$ при $x_k = k, k = 0, 1, \dots, n ; \delta^n f_0 = {0, m < n; n!, m = n}$

б) Лявата страна е разделената разлика от ред n от $f(x) = \binom {m + k} l = \cfrac {(m + k)(m + k - 1) \dots (m + k - k + 1)} {l!}$, което е полином на k от степен l < n.

Задачи с Поповичу-Стефенсон

Формулата на Поповичу-Стефенсон (от по-предишната лекция):

(4)
\begin{align} (f.g)[x_0, ..., x_n] = \Sigma_{k=0}^n f[x_0, ..., x_k].g[x_k, ..., x_n] \end{align}

Задача 1: Нека $f(x) = \cfrac 1 x$, и $x_0 . x_1 . \dots . x_n != 0 , n \in \mathbb N$. Да се намери $f[x_0, ..., x_n]$.
Използваме формулата и нека g(x) = x. Тогава f.g = 1.
$f.g[x_0, ..., x_n] = 0$, от една страна. От друга, $f.g[x_0, ..., x_n] = \underset {k=0} {\overset n \sum} f[x_0, ..., x_k].g[x_k, ..., x_n]$ . Тази сума има две ненулеви събираеми: k = n - 1, k = n :

(5)
\begin{eqnarray} && f[x_0, ..., x_{n-1}].g[x_{n-1}, x_n] + f[x_0,, ..., x_n].g[x_n] \\ && g[x_n] = x_n \Rightarrow f[x_0, ..., x_n] = \frac {-1} {x_n} f[x_0, \dots, x_{n-1}] = \dots = \cfrac {(-1)^n} {x_n} .x_{n-1}...x_1 . f[x_0] = \cfrac {(-1)^n} {x_0 \dots x_n} \end{eqnarray}

Същата задача, за $f(x) = \cfrac 1 {x^2}$

[TODO: below the line]


Нека g(x) = x, f.g = 1/x => (-1)^n/x_0…x_n = f.g[x_0, …, x_n] = f[x_0, …, x_n].x_n + f[x_0, …, x_n-1]
f[x_0, …, x_n] = (-1)^n / x_0x_1…x_n . 1/x_n - 1/x_n f[x_0, …, x_{n-1}].

Пишем сега същата формула с n-1 вместо n.
f[x_0, …, x_{n-1}] = (-1)^{n-1} / x_0x_1…x_{n-1} . 1/x_{n-1} - 1/x_{n-1} f[x_0, …, x_{n-2}].

Умножаваме двете страни с (-1)/x_n:
f[x_0, …, x_n}] = (-1)^n / x_0x_1…x_{n-1}x_n . (1/x_{n-1} + 1/x_n) + (-1)^2/x_{n-1}x_n f[x_0, …, x_{n-2}].

Предполагаме, че разделената разлика е f[x_0, …, x_n] = (-1)^n/x_1…x_n . (1/x_0 + … + 1/x_n).
Ако е вярно за n = 1, можем да използваме индукция.

n = 1. (1/x^2)[x_0,x_1] = (1/(x_1)^2 - 1/(x_0)^2) / (x_1 - x_0) = (x_0^2 - x_1^2) / x_0^2.x_1^2.(x_1 - x_0) =
-(x_0 + x_1)/x_0^2.x_1^2 = (-1)/x_0x_1 (1/x_0 + 1/x_1). Вярно е.

Допускаме, че формулата е вярна за n-1. За n:

f[x_0, …, x_n] = (-1)^n/x_0.x_1.\dots.x_n .1/x_n - 1/x_n.(-1)^{n-1}/x_0.x_1.\dots.x_{n-1} .(1/x_0 + … + 1/x_{n-1})
= (-1)^n/x_0x_1…x_n (\Sigma_{k=0}^n 1/x_k) - формулата е вярна и за n.

Приложение на формулата на Нютон за намиране сумите настепените на първите n числа.

\Sigma_{k=1}^n k = n(n+1)/2
\Sigma_{k=1}^n k^2 = n(n+1)(2n+1)/6
\Sigma_{k=1}^n (2k-1) = n^2

\Sigma_{k=1}^n (2k-1)^2 = ?
\Sigma_{k=1}^n (2k-1)^3 = ?

Задача 2. Да се намери S(n) = \Sigma_{k=1}^n k^3

Правим си таблицата:

x_i S[x_i] S[x_i,x_{i+1}] S[.,.,.] S[.,.,.,.] РР от ред 5


0 0 1 7/2 2 1/4 0
1 1 8 11/2 3 1/4 0
2 9 27 \dots \dots
3 36 \dots 1/4 0
\dots \dots \dots \dots n-1
n-2 S(n-2) (n-1)^3 (n^2-3n+2)/2
n-1 S(n-1) n^3
n S(n)

//Буфер: (3k^2 - 3k + 1 - 3(k-1)^2 - 3(k-1) - 1) / 6 = (6k - 6)/6 = k-1

Взимаме първите числа:
S(n) = 0 + 1.(n-0) + 7/2 n(n-1) + 2n(n-1)(n-2) + 1/4 n(n-1)(n-2)(n-3) = n/4((n-1)(n-2)(n-3) + 8(n-1)(n-2) + 14(n-1) + 4) =

n/4(n^3 + 2n^2 + n) = n^2(n+1)^2/4

За упражнение: S(n) = \Sigma_{k=1}^n (2l-1)^2

И още една задача: Да се докаже, че \Sigma_{i=k}^n 1/\omega'(x_i) != 0, k \in {1, .., n}

Лявата страна е разделена разлика f[x_0, …, x_n] за функция f(x).

x_i x_0 x_1 … x_{k-1} x_k … x_n


f(x_i) 0 0 … 0 1 1 1

РР е равна на коефициента пред x^n в полинома p(x) от \Pi\n, интерполиращ f(x) в тези възли. Ще покажем, че p(x) е
от степен, точно равна на n.
По теоремата на Рол, p'(x) има нула във всеки интервал (x_0,x_1), (x_1,x_2), …, (x_{k-2},x_{k-1}), (x_k,x_{k+1}),
(x_{k+1},x_{k+2}), …, (x_{n-1}, x_n) - общо n-1 интервала.
p' \in \Pi{n-1}, има -1 нули => p' е от степен n-1 => p е от степен n.

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