Условия
Задача 1
Намерете полинома от първа степен на най-добро равномерно приближение в интервала [-1; 1] за функцията f(x) = |x - 0.5|
Ще използваме критерия на Чебишов за алтеранса.
Той дава необходимо и достатъчно условие, за да е един полином най-добро равномерно приближение в краен и затворен интервал.
За полином $P(x_i)$ от степен n Трябва да съществуват n+2 точки в интервала, за които да е изпълнено:
$x_0 < x_1 < \cdots < x_{n+1}$
$f(x_i) - P(x_i) = (-1)^i\varepsilon||f-P||$
Където епсилон е -1 или +1.
Тоест, полиномът на приближение да пресича f (n+1) пъти, като във всеки от така обособените n+2 интервала се достига максималната разлика между f и P.
Тук има лееееек момент на досещане.
Но, от съображения за симетрия(естеествено) можем да се досетим, че 3-те точки(тук n = 1, n+2 = 3) са именно [-1, 0.5, 1].
Търсим P(x) = Ax + B
В такъв случай, записваме си следните уравнения:
$f(-1) - P(-1) = P(0.5) - f(0.5) = f(1) - P(1)$
$1.5 - (-A + B) = 0.5A + B = 0.5 - (0.5A + B)$
От горното условие се намират $A = -\frac{1}{2}, B = \frac{5}{8}$.
Естествено, на контролно ще трябва малко повече локуми да бъдат разтеглени.
Задача 2
Намерете полинома от първа степен на най-добро равномерно приближение в интервала [0; 1] за функцията $f(x) = \frac{1}{x+1}$
Както и преди, трябват ни 3 точки, за да намерим полинома P.
Лесно се доказва, че две от тях са 0 и 1. То буквално е очевидно, но все пак на контролно трябва да се докаже (ако не се сещаш как да се докаже - еми, помисли малко, егати).
Третата точка още не я знаем. Кръщаваме си я с t.
За момента имаме:
$f(0) - (A*0 + B) = f(1) - (A*1 + B) = (-1)*(f(t) - (A*t + B))$
Важно! Гледай да не объркаш минусите. Ако нещо не излиза, провери дали всичко там е както трябва.
От първите две излиза $A = -\frac{1}{2}$.
Ии тук идва грубият момент.
Трябва ни да намерим къде е(и колко е) максимумът на $f - P$. Ами, формираме си функцията $(f - P)$ и вземаме нейната производна. Там където се нулира - има екстремуми(точно един, който - би трябвало да е очевидно - ще е максимум). Егати пичовете дето сме, честно.
$(f-P)' = (\frac{1}{x+1} - (-\frac{x}{2} + B))' = -\frac{1}{(x+1)^2} + \frac{1}{2} = 0$
Това се свежда до квадратно уравнение. Понякога имам странното чувство, че нарочно са ни ги нагласили по този начин.
Има един корен в интервала [0,1] и той е $\sqrt{2} - 1$.
Ако си изпуснал(а) нишката, току-що намерихме колко е стойността на $t$.
Връщаме се малко назад:
$f(0) - (A*0 + B) = f(1) - (A*1 + B) = f(t) - (A*t + B)$
Вземаме първото и третото:
$1 - B = -\frac{1}{t+1} -\frac{t}{2} + B$
$\cfrac{2+t^2+t}{2(t+1)} = 2B - 1$
При $t = \sqrt{2} - 1$ магически решаваме горното(линейно спрямо B) уравнение и намираме:
$B = \cfrac{4+\sqrt{2}}{4\sqrt{2}}$
$A = -\frac{1}{2}$, впрочем.
Това беше.
Задача 3
Намерете полинома от втора степен на най-добро равномерно приближение в интервала [-1; 1] за функцията $f(x) = x^3$
Полиномът е $P(x) = Ax^2 + Bx + C$. Ноо f(x) е нечетна функция. Това означава, че най-доброто нейно приближение също е нечетна функция. Тоест $P(x) = Bx$. Грубо, а?
Ето вече добре известните уравнения:
$1 - B = Bt - t^3$
$(f - P)' = 3x^2 - B$
$3t^2 - B = 0$
$B = 3t^2$
Тук идва тънкият момент - не заместваме t, а B:
$1 - 3t^2 = 3t^3 - t^3$
$1 - 3t^2 = 2t^3$
Това има 3 корена: $t = -1, \plusminus \frac{1}{2}$.
Първият не ни интересува, другите два са валидни. От тях излиза $B = \frac{3}{4}$
$P(x) = \frac{3}{4} x$
Задача 4
Намерете полинома от втора степен на най-добро равномерно приближение в интервала [-1; 1] за функцията $f(x) = |x|$
За да намерим P трябва първо да намерим 4 точки с максимална разлика $(f - P)$. Както може би е очевидно, тук яко ще вкарваме "съображения за симетрия".
Полиномът е от вида $Ax^2 + C$, защото ако $B \ne 0$ P няма да е симетричен спрямо Oy. Следователно от съображения за симетрия както $Ax^2 + Bx + C$, така и $Ax^2 - Bx + C$ ще отговарят на условието, а по дефиниция има точно един такъв полином. Та, отново, B = 0.
Също така, две от точките са [-1, 1], а други две са [-t, t] (още не знаем колко е t).
Само че, за всеки постарал се да си нарисува графиката става ясно, че тези точки не удовлетворяват условието $f(x_i) - P(x_i)$ да си сменя знака за всяко следващо i. Трябва ни още една точка(казано е, че има поне 4, не е казано, че няма 5). Отново от симетрия следва, че тази точка може да е само 0(Отново, на контролно трябва да се доказва).
Записваме уравненията:
$f(1) - (A*1^2 + C) = (-1)*( f(t) - (A*t^2 + C) ) = f(0) - (A*0^2 + C)$
Намираме A:
$1 - A - C = 0 - 0 - C$
А = 1.
Намираме екстремумите на производната на (f-P) в интервала [0:1] (за да не си играем с модули, иначе в [-1:0] е същата работа):
$(x - (A*x^2 + C))' = 1 - 2Ax = 1 - 2x = 0$
Екстремумът е в 0.5 ($t = \frac{1}{2}$).
Вземаме второто и третото уравнения от горе:
$- f(t) + (t^2 + C) = f(0) - (0 + C)$
$-\frac{1}{2} + \frac{1}{4} + C = -C$
$C = \frac{1}{8}$
Готово:
$P(x) = x^2 + \frac{1}{8}$
Задача 5
Да се докаже, че ако $P_n(x)$ е ортогонален полином в $[a, b]$, то всичките му корени са разположени в интервала $(a, b)$.
Последното свойство от тук.
Задача 6
Докажете, че всеки три ортогонални при едно и също тегло полиноми $P_{n-1}(x), P_n(x), P_{n+1}(x)$ увовлетворяват рекурентна връзка от вида:
(1)
\begin{equation} P_{n+1}(x) = (A_n x + B_n)P_n(x) + C_n P_{n-1}(x) \end{equation}
Предпоследното свойство от тук.
Задача 7
Намерете полинома от първа степен на най-добро средноквадратично приближение в $[0,1]$ при тегло $\omega (x) = 1$ за функцията $f(x) = \mathrm{ln}(1+x)$.
Тук трябва да оптимизираме:
(2)
\begin{align} \int_0^1 \omega(x)(f(x) - P(x))^2 dx \to \min \end{align}
където $P(x) = ax + b$.
Ще използваме, че горният минимум се достига в точка, за която са изпълнени:
(3)
\begin{array} {|ccc} \int_0^1 \omega(x)(f(x) - P(x)) dx &=& 0 \\ \int_0^1 \omega(x)(f(x) - P(x))x dx &=& 0 \\ \end{array}
Сега остава да заместим с конкретните данни от задачата:
(4)
\begin{array} {|ccc} \int_0^1 \ln(1 + x) - ax - b dx &=& 0 \\ \int_0^1 (\ln(1 + x) - ax - b)x dx &=& 0 \\ \end{array} &\iff& \begin{array}{|ccc} \int_0^1 \ln(1 + x) dx - \int_0^1 (ax + b) dx &=& 0 \\ \int_0^1 \ln(1 + x)x dx - \int_0^1 (ax^2 + bx) dx &=& 0 \\ \end{array} \\ &\iff& \begin{array}{|ccc} \int_0^1 \ln(1 + x) dx - (\frac{a}{2} + b) &=& 0 \\ \int_0^1 \ln(1 + x)x dx - (\frac{a}{3} + \frac{b}{2}) &=& 0 \\ \end{array}
Да разгледаме поотделно двата интеграла (и да ги решим де :)):
(5)
\begin{eqnarray} \int_0^1 \ln(1 + x)\ dx &=& \int_0^1 \ln(1 + x)\ d (1+x) \\ &=& (1 + x) \ln (1 + x) \Big|_0^1 - \int_0^1 (1+x)\ d \ln(1 + x) \\ &=& 2 \ln 2 - \int_0^1 \frac{1 + x}{1 + x}\ d x \\ &=& 2 \ln 2 - x \Big|_0^1 \\ &=& 2 \ln 2 - 1 \\ \end{eqnarray}
(6)
\begin{eqnarray} \int_0^1 \ln(1 + x)x\ dx &=& \frac{1}{2} \int_0^1 \ln(1 + x)\ d x^2 \\ &=& \frac{1}{2} \Big[ \ln(1 + x)x^2 \Big|_0^1 - \int_0^1 x^2\ d \ln(1 + x) \Big] \\ &=& \frac{1}{2} \Big[ \ln(2) - \int_0^1 \frac{x^2}{1 + x}\ d x \Big] \\ &=& \frac{1}{2} \Big[ \ln(2) - \int_0^1 \frac{x^2 + 2x + 1}{1 + x} - \frac{2x + 2}{1 + x} + \frac{1}{1+x}\ dx \Big] \\ &=& \frac{1}{2} \Big[ \ln(2) - \Big(\int_0^1 (1+x)\ d(1+x) - \int_0^1 2\ dx + \int_0^1 \frac{1}{1 + x}\ dx \Big) \Big] \\ &=& \frac{1}{2} \Big[ \ln(2) - \Big(\frac{(1+x)^2}{2}\Big|_0^1 - 2x\Big|_0^1 + \ln(1 + x)\Big|_0^1 \Big) \Big] \\ &=& \frac{1}{2} \Big[ \ln(2) - \Big(\frac{4}{2} - \frac{1}{2} - 2 + \ln(2)\Big) \Big] \\ &=& \frac{1}{2} \Big[ \frac{1}{2} \Big] \\ &=& \frac{1}{4} \end{eqnarray}
Остава да решим системата:
(7)
\begin{array} {|ccc} 2\ln(2) - 1 - \frac{a}{2} - b &=& 0 \\ \frac{1}{4} - \frac{a}{3} - \frac{b}{2} &=& 0 \\ \end{array}
от където се получава:
(8)
\begin{eqnarray} a &=& 9 - 12 \ln 2 \\ b &=& \frac{16 \ln 2 - 11}{2} \\ \end{eqnarray}
Задача 8
Намерете полином от първа степен, приближаващ данните от таблицата:
Търсеният полином има вида $A*x + B$.
Разликата на функцията и нейното приближение в точката $x_i$ е $d_i$.
$d_i = (y_i - (A*x_i + B) )$
Искаме сумата от квадратите на разликите в точките $x_i$ да е минимизирана. Т.е.:
$F(A,B) = \sum d_i^2$
Търсим min(F(A,B)). Търсим екстремуми(които 100% ще са минимуми - защо? Защото така.):
$\cfrac{\partial F}{\partial A} = 0$
$\cfrac{\partial F}{\partial B} = 0$
Това са двете условия, които трябва да са изпълнени.
Преведени, те гласят:
$\sum (y_i - (A*x_i + B) ) x_i = 0$
$\sum (y_i - (A*x_i + B) ) = 0$
Решаваме в текущия случай:
i |
di |
1 |
2-B |
2 |
4-A-B |
3 |
2-2A-B |
4 |
1-3A-B |
$\sum (y_i - (A*x_i + B) ) x_i = 11 - 14A - 6B = 0$
$\sum (y_i - (A*x_i + B) ) = 9 - 6A - 4B = 0$
Оттук, приемайки сметките ми за верни, следва
A = -0.5
B = 3
Графиката изглежда е съгласна с мен. Макар че по четири точки е малко трудно да се каже.
Задача 9
Намерете полином от първа степен, приближаващ данните от таблицата:
xi |
-1 |
0 |
1 |
2 |
yi |
2 |
1 |
0 |
-1 |
wi |
1 |
1 |
2 |
1 |
Тук е същата работа като в предишната задача, просто вече имаме и тегло на точките.
О да, впрочем, точките са на една права. Нарочно. За да чувстваш още по-силно, че си губиш времето докато решаваш.
$d_i = w_i(y_i - (A*x_i + B) )$
$F(A,B) = \sum d_i^2$
$\cfrac{\partial F}{\partial A} = 0$
$\cfrac{\partial F}{\partial B} = 0$
$\sum w_i(y_i - (A*x_i + B) ) x_i = 0$
$\sum w_i(y_i - (A*x_i + B) ) = 0$
Решаваме:
i |
di |
1 |
2+A-B |
2 |
1-B |
3 |
-A-B |
4 |
-1-2A-B |
$\sum (y_i - (A*x_i + B) ) x_i = 4 + 7A + 3B = 0$
$\sum (y_i - (A*x_i + B) ) = 2 - 3A - 5B = 0$
Оттук, приемайки сметките ми за верни, следва
A = -1
B = 1
Е, поне лесно се проверява…
Задача 10
Да се реши преопределената система:
(9)
\begin{array} {|ccccr} 2x & + & y & = & 1 \\ x & - & y & = & 1 \\ x & - & 2y & = & -2 \\ \end{array}
Ако разглеждаме системата като $A.\bar x = \bar b$, където:
(10)
\begin{align} A = \left(\begin{array}{rr} 2 & 1 \\ 1 & -1 \\ 1 & -2 \end{array}\right) \quad \bar b = \left(\begin{array}{c} 1 \\ 1 \\ -2 \end{array}\right) \end{align}
тогава решението на тази преопределена система се дава от решението на следната (нормална) система:
(11)
\begin{align} A^\mathrm{T} A \tilde x = A^\mathrm{T} \bar b \end{align}
което всъщност е:
(12)
\begin{align} \left(\begin{array}{rrr} 2 & 1 & 1 \\ 1 & -1 & -2 \end{array}\right) \left(\begin{array}{rr} 2 & 1 \\ 1 & -1 \\ 1 & -2 \end{array}\right) \tilde x = \left(\begin{array}{rrr} 2 & 1 & 1 \\ 1 & -1 & -2 \end{array}\right) \left( \begin{array}{c} 1 \\ 1 \\ -2 \end{array} \right) \end{align}
(13)
\begin{align} \left( \begin{array}{rr} 6 & -1 \\ -1 & 6 \end{array} \right) \tilde x = \left( \begin{array}{c} 1 \\ 4 \end{array} \right) \end{align}
Аз получих $x = \frac{2}{7}, y = \frac{5}{7}$.
Задача 11
Нека функцията $f(x) \notin \pi_n$ е непрекъсната в $[-1,1]$ и $p(x)$ е полиномът на най-добро средноквадратично приближение за $f$ от степен $n$ в $[-1,1]$ с тегло $1$. Докажете, че разликата $f(x)-p(x)$ има поне една смяна на знака в $(-1,1)$
Условието ни казва, че $\int_{-1}^{1}1(f(x)-p(x))^2dx$ е минимален. Имаме $p(x) \in \pi_n$, значи $p(x) = a_nx^n + ... + a_1x + a_0$. Разглеждаме интеграла като функция на $a_0, ..., a_n$ - въпросната функция достига минимума си точно за нашето p(x) - т.е. това е локален екстремум и всички частични производни трябва да са нули. Разглеждаме частичната производна относно $a_0$:
$\cfrac{\partial F}{\partial a_0} = \int_{-1}^{1}2.1(f(x)-p(x))1dx = 0$.
Имаме, че $\int_{-1}^{1}1(f(x)-p(x))dx=0$ тогава или $f-p$ има смяна на знака или $f-p \equiv 0$. Но няма как да е $0$, защото $f(x) \notin \pi_n$, а $p(x) \in \pi_n$
Задача 13
Да се намери естествено число $n$, за което $n$-тата съставна квадратурна формула на правоъгълниците пресмята интегралa
$\int_0^2\sin (x)dx$ с грешка ненадминаваща $\epsilon = 10^{-5}$.
Квадратурната формула на правоъгълниците е
(14)
\begin{align} Q^{sq} = (b-a)f(\dfrac{a+b}{2}) \end{align}
където $f = sin (x)$, тоест функцията която интегрираме.
Разбира се ние разделяме интервала над който интегрираме на $n$ парчета и прилагаме формулата за всяко парче. След това сумираме лицата на парчетата, за да намерим интеграла.(Учудващо много прилича на сума на риман).
Ограничението на грешката при квадратурна формула на квадратите е
(15)
\begin{align} R(Q^{sq};f) = \dfrac{f''(\xi)}{24}(b-a)^3, \ \xi \in [a,b] \end{align}
Когато имаме разделяне на интервала на $n$ парчета грешката изглежда така
(16)
\begin{align} | R(Q^{sq};f) | \leq \dfrac{M}{24n^2}(b-a)^3, \ M = max_{x \in [a,b]} |f''(x)|,\ \end{align}
Сега трябва да заместим $[a,b]$ с $[0,2]$ и да видим за кое $n$ е изпълнено неравенството $\dfrac{M}{24n^2}(b-a)^3 \leq 10^{-5}$
Задача 14
Да се намери естествено число $n$, за което $n$-тата съставна квадратурна формула на трапеците пресмята интегралa
$\int_0^2\cos (x)dx$ с грешка ненадминаваща $\epsilon = 10^{-5}$.
(17)
\begin{align} R(Q^{tr};f) = \dfrac{-f''(\xi)}{12}(b-a)^3, \ \xi \in [a,b] \end{align}
Задача 15
Да се намери естествено число $n$, за което $n$-тата съставна квадратурна формула на Симпсон пресмята интегралa
$\int_{-1}^1 e^x dx$ с грешка ненадминаваща $\epsilon = 10^{-7}$.
(18)
\begin{align} R(Q^{Sim};f) = \dfrac{-f^{iv}(\xi)}{2880}(b-a)^5, \ \xi \in [a,b] \end{align}