Числени методи, първо контролно - условия (и решения)
страницата се нуждае от дописване/преглеждане
Задача 1
Докажете, че ако $\{ x_i \}_{i=0}^{n}$ са различни точки в интервала $[a, b]$, и $f(x) \in C^{n+1}[a, b]$, тогава за всяко $x$ съществува точка $\xi \in [a, b]$, такава че:
(1)
\begin{align} f(x) - L_n(f; x) = \frac{f^{(n+1)}(\xi)}{(n+1)!}\omega(x) \end{align}
Задача 2
Докажете, че ако $\{ l_k(x) \}_{k=0}^{n}$ са базисните полиноми на Лагранж за интерполиране в различните точки $\{ x_k \}_{k=0}^{n}$, то:
(2)
\begin{align} \sum_{k=0}^{n} (x - x_k)^m l_k(x) = 0 \quad m \in \{ 0, 1, \cdots, n \} \end{align}
Доказана е на упражнение
Ами, тази задача всъщност не е вярна…
Ето един пример:
f(x) = x
$n = 1, x_0 = 0, x_1 = 1$
L(f;x) = x
Тогава:
$l_0(x) = \cfrac{x-1}{0-1} = 1-x$
$l_1(x) = \cfrac{x}{1-0} = x$
$\sum_{k=0}^{n} (x - x_k)^m l_k(x) = (1-x)^mx + x^m(1-x) =$
$= x(1-x)(x^{m-1} + (1-x)^{m-1})$
Което, както и да го гледаме, не е тъждествено равно на нула.
Тоест, условието е грешно. Сори, пич. Доцентите също грешат.
Сори, пич. Ти също грешиш.
$\sum_{k=0}^{n} (x - x_k)^m l_k(x) = (x)^m(1-x) + (x-1)^m(x) =$
$= x(1-x)(x^{m-1} - (1-x)^{m-1})$
За m=1 твърдението е изпълнено ;)
Задача 3
Докажете, че ако $\{ l_k(x) \}_{k=0}^{n}$ са базисните полиноми на Лагранж за интерполиране в различните точки $\{ x_k \}_{k=0}^{n}$, то:
(3)
\begin{align} \sum_{k=0}^{n} (x - x_k)^{n+1} l_k(x) = (-1)^n \omega(x) \end{align}
(4)
\begin{array} {} l_k(x) = c \omega_k(x) \\ \sum_{k=0}^{n} (x-x_k)^{n+1} c_k \omega_k(x) = \\ = \omega(x) \sum_{k=0}^{n} (x-x_k)^{n} c_k = \\ = \omega(x) \sum_{k=0}^{n} (x-x_k)^{n} \frac{1}{\prod_{i=0,i \neq k}^{n} (x_k - x_i)} = \\ \end{array}
Задача 4
Докажете, че ако $\{ l_k(x) \}_{k=0}^{n}$ са базисните полиноми на Лагранж за интерполиране в различните точки $\{ x_k \}_{k=0}^{n}$, то:
(5)
\begin{align} \sum_{k=0}^{n} (x - x_k)^{n+2} l_k(x) = (-1)^n \omega(x) \sum_{k=0}^{n} (x - x_k) \end{align}
Задача 5
Докажете, че ако $\{ x_k \}_{k=0}^{n}$ са различни точки, и $p(x) \in \pi_n$, то:
(6)
\begin{align} \frac{p(x)}{\omega(x)} = \sum_{k=0}^{n} \frac{p(x_k)}{(x-x_k)\omega'(x_k)} \end{align}
Тази е лесна.
Тъй като p(x) е полином, то интерполиращият го Полином на Лагранж съвпада с p(x).
След това остава само да прехвърлим разни неща от другата страна на равенството.
$p(x) = L(p,x) = \sum_{k=0}^{n} p(x_k)\cfrac{\omega(x)}{(x-x_k)\omega'(x_k)}$
Не забравяй, че p(x) е функция, но $p(x_k)$ е просто стойност.
А сега, който е внимавал - ще се сети, че това вдясно е именно дефиницията за полином на Лагранж. Това беше, готови сме.
Задача 6
Като използвате интерполационната формула на Лагранж, докажете тъждеството:
(7)
\begin{align} \sum_{k=0}^{n} (-1)^{n-k}\binom{m}{n} \binom{n}{k}\frac{1}{m-k} = \frac{1}{m-n} \quad m > n \ge 0 \end{align}
Вариант 1:
$L_n(f;x) = \sum_{k=0}^n f(x_k) \frac{\omega(x)}{(x-x_k)\omega'(_k)}$
Полагаме x = m и вземаме $[x_0, x_1, \cdots, x_n ] = 0, 1, \cdots, n$
$L_n(f;m) = \sum_{k=0}^n\frac{m(m-1)\cdots(m-n)}{1*2*\cdots*k * ((-1)^{n-k}1*2*\cdots*n(m-k)}f(x_k)$
$L_n(f;m) = \sum_{k=0}^n\binom{n}{k}\binom{m}{n}f(x_k)\frac{m-n}{m-k}$
Сега, сещаме се, че всъщност до момента не са дадени никакви ограничения за f().
Ще вземем да си я нагласим така, че да ни е удобно.
При f(x) = 1 функцията съвпада с полинома си на Лагранж, следователно:
$L_n(f;m) = \sum_{k=0}^n\binom{n}{k}\binom{m}{n}\frac{m-n}{m-k} = 1$
Което трябваше и да докажем.
Вариант 2:
Внимание! Този вариант не ползва точно полином а наа Лагранж. Само казвам.
Вземаме си функцията f(x) и точките $x_0, x_1, \cdots, x_n = [0,1, \cdots, n]$. Още не е ясно какви точно са стойностите на f(x).
Вземаме някои равенства(при стандартните означения на променливите) между разделени и крайни разлики:
$\Delta^n f_0 = \sum_{k=0}^n (-1)^{n-k}\binom{n}{k}f_i$
$\Delta^n f_0 = n! h^n f[x_0,x_1,\cdots,x_n]$
Освен това, избрали сме си h = 1, т.е. $h^n = 1$
И така, стигаме до:
(8)
\begin{align} \sum_{k=0}^n (-1)^{n-k}\binom{n}{k}f_k = n! * f[x_0,x_1,\cdots,x_n] \quad (\bigstar) \end{align}
А трябва да докажем, че:
$\sum_{k=0}^{n} (-1)^{n-k}\binom{n}{k}\frac{1}{m-k} = \frac{1}{m-n} * \cfrac{1}{\binom{m}{n}}$
$\sum_{k=0}^{n} (-1)^{n-k}\binom{n}{k}\frac{1}{m-k} = \frac{1}{m-n} * \cfrac{n!(m-n)!}{m!}$
$\sum_{k=0}^{n} (-1)^{n-k}\binom{n}{k}\frac{1}{m-k} = n! * \cfrac{(m-n-1)!}{m!}$
И сега, какво прави гадният човек когато нещо не му е удобно?
Ами, пресяга се и си го наглася.
Лявата част на уравнението изглежда странно позната(виж $(\bigstar)$).
Приравняваме $f_k = f(x_k) =\frac{1}{m-k}$ и лявата част става точно каквото ни тярбва.
Сега хайде да се хванем на бас дали разделената разлика $f[x_0,x_1,\cdots,x_n]$ не е точно, точно равна на $\frac{(m-n-1)!}{m!}$
Да, сметнах я, точно равна е :) Но хайде, не бъди мързел, сметни си я на листче и ти.
Доказва се по индукция за $f[x_0, x_1, \cdots, x_i]$.
Задачата, впрочем, е решена.
Задача 7
Като използвате интерполационната формула на Лагранж, докажете тъждеството:
(9)
\begin{align} \sum_{k=0}^{n} (-1)^{n-k}\binom{m}{n} \binom{n}{k}\frac{k}{m-k} = \frac{m}{m-n} \quad m > n \ge 1 \end{align}
Решението на тази задача е еквивалентно с решението на Задача 6.
Вариант 1:
Единствената разлика е, че тук $f(x) = x$
При f(x) = x функцията съвпада с полинома си на Лагранж(от степен > 0), следователно:
$L_n(f;m) = \sum_{k=0}^nk\binom{n}{k}\binom{m}{n}\frac{m-n}{m-k} = m$
Вариант 2:
Единствената разлика е, че тук $f(x) = \frac{x}{m-x}$
Задача 8
Изведете интерполационната формула на Нютон (с разделени разлики)
Задача 9
Нека $\{ x_k \}_{k=0}^{n}$ са различни точки. Като използвате свойствата на разделените разлики, докажете тъждеството:
(10)
\begin{align} \sum_{k=0}^{n} \frac{x_k^m}{\omega'(x_k)} = 0 \quad m \in \{0, 1, \cdots, n-1\} \end{align}
Решението използва една важна и не особено тривиална лема:
$f[x_0, x_1, \cdots, x_n] = \sum_{k=0}^n f(x_k)\cfrac{1}{\omega'(x_k)}$
Следващите няколко задачи просто ще си нагласяваме колко е стойността на f.
В случая, вземаме $f(x) = x^m$. Това е полином от степен m, m < n (по условие). Тогава от свойствата на разделената разлика следва:
$f[x_0, x_1, \cdots, x_n] = 0$
КТДД. Бързо, а?
Задача 10
Нека $\{ x_k \}_{k=0}^{n}$ са различни точки. Като използвате свойствата на разделените разлики, докажете тъждеството:
(11)
\begin{align} \sum_{k=0}^{n} \frac{x_k^n}{\omega'(x_k)} = 1 \end{align}
Решението е подобно на задача 9.
Вземаме $f(x) = x^n$ и използваме, че $f[x_0, x_1, \cdots, x_n]$ е равно на старшия коефицент на Полинома на Лагранж, който интерполира f. Но, f е полином, значи съвпада с $L(f,n)$. А коефицентът пред $x^n$ е точно 1.
КТДД.
Задача 11
Нека $\{ x_k \}_{k=0}^{n}$ са различни точки. Като използвате свойствата на разделените разлики, докажете тъждеството:
(12)
\begin{align} \sum_{k=0}^{n} \frac{\omega''(x_k)}{\omega'(x_k)} = 0 \end{align}
Решението е подобно на задача 9.
$f(x) = \omega''(x)$
Това може да изглежда страшно първоначално. Но, $\omega(x)$ е полином, при това от степен точно n+1. Значи втората му производна е от степен n-1. Значи разделената разлика $f[x_0, x_1, \cdots, x_n]$ е задължително равна на 0(също както в задача 9).
КТДД.
Задача 12
Нека $\{ x_k \}_{k=0}^{n}$ са различни точки. Като използвате свойствата на разделените разлики, докажете тъждеството:
(13)
\begin{align} \sum_{k=0}^{n} x_k \frac{\omega''(x_k)}{\omega'(x_k)} = n(n+1) \end{align}
Решението е подобно на задача 9.
$f(x) = x * \omega''(x)$
Това е точно полином от степен n. Тоест, съвпада с интерполационния си полином от степен n.
Интересува ни стойността на $f[x_0, x_1, \cdots, x_n]$, но тя е равна на старшия коефицент на f(x).
Старшият коефицент на $\omega(x)$ е 1 (а степента му е n+1).
Старшият коефицент на $\omega'(x)$ е n+1 (а степента му е n).
Старшият коефицент на $\omega''(x)$ е n(n+1) (а степента му е n - 1).
Ами, това трябваше да докажем. Оттук и от задача 9 директно следва отговорът.
Задача 13
Нека $\{ x_k \}_{k=0}^{n}$ са различни точки. Като използвате свойствата на разделените разлики, докажете тъждеството:
(14)
\begin{align} \sum_{k=0}^{n} \frac{x_k^{n+1}}{\omega'(x_k)} = \sum_{k=0}^n x_k \end{align}
Да, има още от тези вид :(
Това вече става малко по-различно. Подобно е на задача 1.
$f(x) = x^{n+1}$
Пишем следния израз:
$x^{n+1} - L_n(f,x) = \omega(x)$
Този израз е верен. Защо е верен? Защото както лявата, така и дясната част са полиноми от степен n+1 с n+1 нули в точките $[x_0, x_1, \cdots, x_n]$.
Тоест, и двете части са полинома на Лагранж от степен n+1.
Но, поради специфичния вид на f(x) (а именно - няма член от степен n) - можем да кажем нещо за коефицента пред степен n на $L_n(f,x)$. Този коефицент е точно равен на коефицента пред степен n в $\omega(x)$. Който пък е точно равен на $\sum_{k=0}^n x_k$.
Това трябваше и да докажем. Както вече е добре известно, $\sum_{k=0}^{n} \frac{f(x_k)}{\omega'(x_k)} = f[x_0, x_1, \cdots, x_n$ и т.н.
Готово.
Задача 14
Нека фунцията $f(x)$ има производни от всякакъв ред в интервала $[a, b]$, и съществуват положителни константи $C, M$, такива че за всяко естествено число $m$ е изпълнено:
(15)
\begin{align} |f^{(m)}(x)| \le C.M^m \quad \forall x \in [a, b] \end{align}
Да се докаже, че при всеки избор на интерполационни възли $a \le x_0 < x_1 < \cdots < x_n \le b$ е изпълнено:
(16)
\begin{align} \lim_{n \to \infty} \max_{x \in [a, b]}|f(x) - L_n(f; x)| = 0 \end{align}
ОК, как ставаше това? Това е от Анализ 1, хайде :)
Щом доказваме, че някаква граница(от модул) е 0, то трябва да вземем произволно малко $\epsilon$ и да докажем, че е по-малка от него.
Другият начин е да представим границата като безкрайна редица(за стойности на n - $1,2, 3, \cdots$) - при това безкрайна редица, по-малка по модул от някоя доказано сходяща.
Ползваме втория начин.
Модулите ги изпускам - нарочно, за да е по-четимо. Иначе, около всеки един израз трябва да има модул.
Имаме си наготово, че $|f(x) - L_n(f; x)| = \cfrac{f^{(n+1)}(\xi)}{(n+1)!}\omega(x)$.
Тъй като даденото условие беше изпълнено за всяко x и всяко m, то е изпълнено и за $x = \xi, m = n+1$. Следователно:
$|f(x) - L_n(f; x)| = \cfrac{f^{(n+1)}(\xi)}{(n+1)!}\omega(x) \le \cfrac{C.M^{n+1}}{(n+1)!} \omega(x)$
$\cfrac{C.M^{n+1}}{(n+1)!} \omega(x) = \cfrac{C.M^{n+1}}{(n+1)!} (x-x_0)(x-x_1)(x-x_2) \cdots (x-x_n)$
Но, $(x-x_i) \le (b-a)$ следователно $(x-x_0)(x-x_1)(x-x_2) \cdots (x-x_n) \le (b-a)^{n+1}$.
Който не забеляза, току-що дадохме дооооооста груба оценка за $\omega(x)$.
Във всеки случай, получава се следната ситуация:
$|f(x) - L_n(f; x)| = \cfrac{f^{(n+1)}(\xi)}{(n+1)!}\omega(x) \le \cfrac{C.M^{n+1}}{(n+1)!} \omega(x) \le \cfrac{C.(M(b-a))^{n+1}}{(n+1)!}$
Но, последното нещо е степенна фунцкия, делена на факториел. Ако въобще малко от малко сме внимавали в час по Анализ - ще е ясно, че това е много здраво сходяща редица, при това към 0.
$\lim_{n \to \infty} \max_{x \in [a, b]}|f(x) - L_n(f; x)| \le \lim_{n \to \infty}\cfrac{C.(M(b-a))^{n+1}}{(n+1)!} = 0$
Задачата е решена. Браво на нас.