Тема 15

Приближения в Хилбертови пространства. Метод на най-малките квадрати, най-добри средноквадратични приближения с алгебрични полиноми.

Дефиниции

Хилбертово пространство

Едно линейно пространство $H$ се нарича хилбертово, ако в него е въведено скаларно произведение. Това значи, че на всеки два елемента $f,g$ се съпоставя числото $(f,g)$, което наричаме скаларно произведение.

Скаларно произведение

Нека $f, g \in H$, за скаларното произведение са изпълнени:

  1. $(f, f) \ge 0, "=" \iff f = 0$
  2. $(f, g) = (g, f)$
  3. $(\alpha f + \beta g, h) = \alpha(f, h) + \beta(g, h), \ \forall \alpha, \beta \in \mathbb R, \ \forall f, g \in H$

$f \perp g \iff (f, g) = 0$

Норма (в Хилбертови пространства)

$\|f\|:=\sqrt{(f, f)} \ge 0$

Лема (Коши-Буняковски)

$|(f, g)| \le \sqrt{(f, f)}\sqrt{(g, g)}, \ "=" \iff f = \alpha g, \alpha \in \mathbb R$

Доказателство:
$0 \le ( f - \alpha.g, f - \alpha.g ) = (f,f) - 2\alpha( f, g ) + \alpha^2(g, g) = (*)$.
Ако f и g не са линейно зависими: $f - \alpha.g \ne 0 \rightarrow$ неравенството (*) е строго за всяко $\alpha \in \mathbb R$.
Тоест: $D = 4(f, g)^2 - 4(f, f)(g, g) < 0 \rightarrow (f, g) < \sqrt{(f, f)(g, g)}$.
Ако f и g са линейно зависими:

  1. $f = \alpha.g$, то $|(f, g)| = |(g, \alpha.g)|= |\alpha(g, g)|$
  2. $\sqrt{(f, f)}\sqrt{(g, g)} = \sqrt{(\alpha.g, \alpha.g)}\sqrt{(g, g)} = \sqrt{\alpha^2(g, g)}\sqrt{(g, g)} = |\alpha(g, g)|$

от 1. и 2. следва, че е изпълнено равенството.

Следствие (неравенство на триъгълника)

$\| f + g \| \le \| f \| + \|g \|, \ \forall f, g \in H$

Доказателство:
$\| f + g \|^2 = (f + g, f + g) = (f, f) + 2(f, g) + (g, g) \le \sqrt{(f, f)^2} + 2\sqrt{(f, f)(g, g)} + \sqrt{(g, g)^2} = ( \sqrt{(f, f)} + \sqrt{(g, g)} )^2 = ( \| f \| + \|g \| )^2$

$\| f + g \|^2 \le ( \| f \| + \|g \| )^2$
$\| f + g \| \le \| f \| + \|g \|$
Значи H е строго нормирано линейно пространство.

Дефиниция (най-добро приближение)

Нека $\varphi_0, \varphi_1, \dots, \varphi_n \in H$ - линейно независими, тогава
$\Omega_n = \{ \varphi = a_0\varphi_0 + a_1\varphi_1 + \dots + a_n\varphi_n | a_i \in \mathbb R \}$
$\mathrm{E}_n(f) = \underset{\varphi \in \Omega_n}\inf \|f - \varphi \|$ - най-добро приближение на f от $\Omega_n$.
$\exists \varphi^* \in \Omega_n : \| f - \varphi^* \| = \mathrm{E}_n(f)$ - елементът $\varphi^*$ на най-добро приближение е единствен за f в $\Omega_n$.

Теорема (НДУ за ЕНДП)

$\varphi \in \Omega_n$ e елемент на най-добро приближение за f в $\Omega_n$ относно разстоянието породено от нормата (която е зададена от скаларното произведение в H) т.с.т.к $(f - \varphi, p) = 0, \forall p \in \Omega_n \ (\star)$, т.е. $(f - \varphi) \perp \Omega_n$

Доказателство:
1. Достатъчност $|\Leftarrow|$
Нека е изпълнено $(\star)$. Разглеждаме $p \in \Omega_n$ - произволен.

(1)
\begin{eqnarray} \| f - p\|^2 &=& (f - p, f - p) \\ &=& (f - \varphi + \underbrace{\varphi - p}_{ r \in \Omega_n }, f - \varphi + \varphi - p ) \\ &=& ( f - \varphi + r, f - \varphi + r ) \\ &=& ( f - \varphi, f - \varphi ) + 2 \underbrace{( f - \varphi, r )}_0 + (r, r) \\ &=& \|f - \varphi\|^2 + \|r\|^2 \ge \|f - \varphi \|^2 \end{eqnarray}

$\|f - \varphi\|^2 \le \| f - p\|^2, \ \forall p \in \Omega_n$
"=" $\iff \|r\| = 0 \iff p = \varphi$
$\varphi$ е елемент на най-добрo приближение на f от $\Omega_n$

2. Необходимост $|\Rightarrow|$
Нека $\varphi$ е елемент на най-добро приближение на f от $\Omega_n$
$\mathrm{E}_n^2(f) = \| f - \varphi\|^2 = ( f - \varphi, f - \varphi)$
Нека $p \in \Omega_n$ - произволен елемент

(2)
\begin{eqnarray} \|f-\varphi-\lambda p\|^2 &=& (f-\varphi-\lambda p,f- \varphi-\lambda p) \\ &=& ( f - \varphi, f - \varphi ) - 2\lambda(f - \varphi, p) + \lambda^2(p, p) = h(\lambda) \end{eqnarray}

$h(\lambda)$ е квадратен тричлен по $\lambda \in \mathbb R$
$h(\lambda)$ достига своят минумум при $\lambda = 0$, защото $\| f - \varphi \| \le \| f - q \|$, за всяко $q \in \Omega_n$, в частност $q = \varphi - \lambda p$.
Следователно първата производна в точката $\lambda = 0$, е 0 : $h'(0) = -2( f - \varphi, p ) + 2.0(p, p) = 0$, следователно $(f - \varphi, p) = 0$ за произволно $p \in \Omega_n$.
Следователно $(f - \varphi) \perp p \ \forall p \in \Omega_n$ - готово.

В частност:
$(f - \varphi) \perp \varphi_0, \dots, \varphi_n$
Ако $\varphi = \underset{i =0}{\overset{n}{\sum}}a_i \varphi_i$, то $(f - \varphi, \varphi_k) = 0, \ k = 0, \dots, n$
Получаваме системата:

(3)
\begin{array} {|ccccccc} a_0 ( \varphi_0, \varphi_0 ) &+& \cdots &+& a_n ( \varphi_0, \varphi_n ) &=& ( f, \varphi_0 ) \\ a_0 ( \varphi_1, \varphi_0 ) &+& \cdots &+& a_n ( \varphi_1, \varphi_n ) &=& ( f, \varphi_1 ) \\ \vdots & & \ddots & & \vdots & & \vdots \\ a_0 ( \varphi_n, \varphi_0 ) &+& \dots &+& a_n ( \varphi_n, \varphi_n ) &=& ( f, \varphi_n ) \\ \end{array}

На което детерминантата му е небезизвестната такава на Грам-Шмидт:

(4)
\begin{align} D(\varphi_0, \dots, \varphi_n) = \begin{vmatrix} ( \varphi_0, \varphi_0 ) & ( \varphi_0, \varphi_1 ) & \cdots & ( \varphi_0, \varphi_n ) \\ ( \varphi_1, \varphi_0 ) & ( \varphi_1, \varphi_1 ) & \cdots & ( \varphi_1, \varphi_n ) \\ \vdots & \vdots & \ddots & \vdots \\ ( \varphi_n, \varphi_0 ) & ( \varphi_n, \varphi_1 ) & \cdots & ( \varphi_n, \varphi_n ) \end{vmatrix} \end{align}

Ако $\{ \varphi_0, \dots, \varphi_n \}$ - ортогонална система, т.е. $(\varphi_i, \varphi_j) = 0, \ i \ne j$
$a_k( \varphi_k, \varphi_k ) = (f, \varphi_k), \ k = 0, \dots, n$
$\varphi(x) = \underset{k = 0}{ \overset{n}{\sum}}\frac{(f, \varphi_k)}{(\varphi_k, \varphi_k)}\varphi_k, \ k = 0, \dots, n$ за ортогонална система.

Формула (най-добро приближение)

Нека $\varphi \in \Omega_n$ е елемент на НДП за f от $\Omega_n$
$\mathrm{E}^2_n(f)= ( f - \varphi, f - \varphi ) = ( f - \varphi, f ) - \underset{ = 0}{( f - \varphi, \varphi )} = (f, f) - (f, \varphi)$
Ако $\varphi = \underset{i =0}{\overset{n}{\sum}}a_i\varphi_i$, имаме $(\varphi, f) = \underset{i =0}{\overset{n}{\sum}}a_i(\varphi_i, f)$

(5)
\begin{array} {|ccccccccccc} a_0 ( \varphi_0, \varphi_0 ) &+& a_1 ( \varphi_0, \varphi_1 ) &+& \cdots &+& a_n ( \varphi_0, \varphi_n ) &-& ( f, \varphi_0 ) &=& 0 \\ a_0 ( \varphi_1, \varphi_0 ) &+& a_1 ( \varphi_1, \varphi_1 ) &+& \cdots &+& a_n ( \varphi_1, \varphi_n ) &-& ( f, \varphi_1 ) &=& 0 \\ \vdots & & \vdots & & \ddots & & \vdots & & \vdots & & \vdots \\ a_0 ( \varphi_n, \varphi_0 ) &+& a_1 ( \varphi_n, \varphi_1 ) &+& \cdots &+& a_n ( \varphi_n, \varphi_n ) &-& ( f, \varphi_n ) &=& 0 \\ a_0 ( f, \varphi_0 ) &+& a_1 ( f, \varphi_1 ) &+& \cdots &+& a_n ( f, \varphi_n ) &-& [ (f, f) - \mathrm{E}^2_n(f) ] &=& 0 \\ \end{array}

В тази система първите $n+1$ реда определят полинома на НДП. Добавяме още един ред определящ грешката(последния) и сега ще изведем формула за грешката.

Хомогенна система с решение $( a_0, a_1, \dots, a_n, -1 )$ - ненулево решение, следователно детерминантата й е 0 - разбиваме я на две детерминанти, втората развиваме по последен стълб (за повече информация):

(6)
\begin{eqnarray} \begin{vmatrix} ( \varphi_0, \varphi_0 ) & ( \varphi_0, \varphi_1 ) & \dots & ( \varphi_0, \varphi_n ) & (f, \varphi_0) - 0\\ ( \varphi_1, \varphi_0 ) & ( \varphi_1, \varphi_1 ) & \dots & ( \varphi_1, \varphi_n ) & (f, \varphi_1)- 0 \\ \dots \\ ( \varphi_n, \varphi_0 )& ( \varphi_n, \varphi_1 ) & \dots & ( \varphi_n, \varphi_n ) & (f, \varphi_n)- 0 \\ ( f, \varphi_0 ) & ( f, \varphi_1 ) & \dots & ( f, \varphi_n ) & (f, f) - \mathrm{E}^2_n(f) \\ \end{vmatrix} &=& \begin{vmatrix} ( \varphi_0, \varphi_0 ) & ( \varphi_0, \varphi_1 ) & \dots & ( \varphi_0, \varphi_n ) & (f, \varphi_0) \\ ( \varphi_1, \varphi_0 ) & ( \varphi_1, \varphi_1 ) & \dots & ( \varphi_1, \varphi_n ) & (f, \varphi_1)\\ \dots \\ ( \varphi_n, \varphi_0 )& ( \varphi_n, \varphi_1 ) & \dots & ( \varphi_n, \varphi_n ) & (f, \varphi_n)\\ ( f, \varphi_0 ) & ( f, \varphi_1 ) & \dots & ( f, \varphi_n ) & (f, f) \\ \end{vmatrix} \\ &-& \begin{vmatrix} ( \varphi_0, \varphi_0 ) & ( \varphi_0, \varphi_1 ) & \dots & ( \varphi_0, \varphi_n ) & 0\\ ( \varphi_1, \varphi_0 ) & ( \varphi_1, \varphi_1 ) & \dots & ( \varphi_1, \varphi_n ) & 0 \\ \dots \\ ( \varphi_n, \varphi_0 )& ( \varphi_n, \varphi_1 ) & \dots & ( \varphi_n, \varphi_n ) & 0 \\ ( f, \varphi_0 ) & ( f, \varphi_1 ) & \dots & ( f, \varphi_n ) & \mathrm{E}^2_n(f) \\ \end{vmatrix} \\ &=& D(\varphi_0, \varphi_1, \dots, \varphi_n, f) - \mathrm{E}^2_n(f).D(\varphi_0, \varphi_1, \dots, \varphi_n) \\ \end{eqnarray}

Т.е получихме:

(7)
\begin{eqnarray} & & D(\varphi_0, \varphi_1, \dots, \varphi_n, f) - \mathrm{E}^2_n(f).D(\varphi_0, \varphi_1, \dots, \varphi_n) = 0 \\ & & \mathrm{E}^2_n(f) = \frac{D(\varphi_0, \varphi_1, \dots, \varphi_n, f)}{D(\varphi_0, \varphi_1, \dots, \varphi_n)} \end{eqnarray}

Приложения

Най-добри средноквадратични приближения с алгебричен полином

Нека:
$[a, b]$ - интервал
$\mu(x)$ - функция на тегло в $[a, b]$
$(f, g) := \underset{a}{\overset{b}{\int}}\mu(t)f(t)g(t) dt$
$H = \{ f(t) | \underset{a}{\overset{b}{\int}}\mu(t)f^2(t) dt < \infty \}$
$\Omega_n = \pi_n$
Тогава търсим $P(x) \in \pi_n \| f - P\|^2 \rightarrow min$ или $\underset{a}{\overset{b}{\int}}\mu(t)\{ f(t) - P(t) \}^2 dt \rightarrow min$ по $P \in \pi_n$

Съществува единствен полином $P(x) \in \pi_n$, който минимизира $\| f - P\|$. $P(x)$ се нарича полином на най-добро средноквадратично приближение (ПНДСКП) за $f(x)$ в $[a, b]$ при тегло $\mu(x)$

Условието за намиране на този полином е $P(x)$ е:
$(f - P, \varphi ) = 0 , \forall \varphi \in \pi_n$
Ако за базис на $\pi_n$ изберем $\{ P_n(x)\}_{m = 0}^n$ - ортогоналните полиноми в $[a, b]$ при тегло $\mu(x)$, търсим $P(x)$ във вида $P(x) = \underset{i = 0}{\overset{n}{\sum}}a_i P_i(x)$
Тогава $( f - a_0.P_0(x) - a_1 P_1(x) - \dots - a_n P_n(x), P_k) = 0, \ k = 0, 1, \dots, n$
$\rightarrow ( f - a_k.P_k, P_k ) = 0 \rightarrow (f, P_k) - a_k( P_k, P_k ) = 0, \ k = 0, 1, \dots, n$
$a_k = \frac{(f, P_k)}{(P_k, P_k)}, \ k = 0, 1, \dots, n$
$P(x) = \underset{k = 0}{\overset{n}{\sum}}\frac{(f, P_k)}{(P_k, P_k)}P_k(x)$ - ПНДСКП за $f(x)$ в $[a, b]$ при тегло $\mu(x)$

Метод на най-малките квадрати

Да си представим, че имаме данни - двойка $x_i, y_i$ за $i = \overline{1,n}$, и ще опитаме да приближим с функция данните. Обикновенно си записваме в табличка пробите:

(8)
\begin{align} \begin{array}{|c|c|c|c|} \hline x_0 & x_1 & \cdots & x_n \\ \hline y_1 & y_2 & \cdots & y_n \\ \hline \end{array} \qquad (\star) \end{align}

Сега да видим различни алгоритми по които да определяме дадена функция колко точно се приближава до данните.
Ще означим с $d_i = f(x_i) - y_i$ - т.е разликата от целта.

минимизираме максимума

Оптимизираме

(9)
\begin{align} \min \max_{0\le k\le n} d_k \end{align}

Това изглежда доста логично, но за жалост сметките загрубяват на практика, пък и самата функция която оптимизираме няма хубави свойства (диференциране/интегриране етц).

минимизираме сбора от абсолютните стойности на разликите

(10)
\begin{align} \min \{ |d_0| + \dots + |d_n| \} \end{align}

Същите съображения като горния подход - както добре знаете, модула докато не го разкрием е трън в гащите.

минимизираме сумата от квадратите на разликите

(11)
\begin{align} \min \sum_{i=0}^{n} d_i^2 \end{align}

Ако разгледаме най-простия случай, в който приближаваме данните с линейната функция $Ax + B$, тогава горното е същото като:

(12)
\begin{align} \min_{A,B} \sum_{i=0}^{n} (Ax_i + B - y_i)^2 \end{align}

Сега да си означим функцията която ще оптимизираме с $\Phi(A, B)$, т.е:

(13)
\begin{align} \Phi(A, B) = \sum_{i=0}^{n} (Ax_i + B - y_i)^2 \to \min \end{align}

Сега използваме малко знания по анализ - за да достигне функция на няколко локален екстремум, трябва по всяка променлива частната й производна да е 0. Тука имаме две променливи $A, B$ - значи си правим система от две уравнения:

(14)
\begin{array} {|ccc} \frac{\partial \Phi}{\partial A} &=& 0 \\ \frac{\partial \Phi}{\partial B} &=& 0 \\ \end{array} \begin{array}{} \iff \end{array} \begin{array}{|ccc} \sum_{i=0}^{n} (Ax_i + B - y_i)x_i &=& 0 \\ \sum_{i=0}^{n} (Ax_i + B - y_i)1 &=& 0 \\ \end{array} \begin{array}{} \iff \end{array} \begin{array}{|ccccc} A\sum_{i=0}^{n} x_i^2 &+& B\sum_{i=0}^{n}x_i &=& \sum_{i=0}^{n} x_iy_i \\ A\sum_{i=0}^{n} x_i &+& B(n+1) &=& \sum_{i=0}^{n} y_i \\ \end{array}

Та решаваме тази система и получаваме стойности за $A, B$ - и сме щастливи - намерили сме полином, приближаващ данните в таблицата $(\star)$.

Може да усложним леко задачата ако вкараме тегло за всяка точка - т.е колко е важна тя за нас. Така получаваме малко ъпдейтната таблица:

(15)
\begin{align} \begin{array}{|c|c|c|c|} \hline w_0 & w_1 & \cdots & w_n \\ \hline x_0 & x_1 & \cdots & x_n \\ \hline y_1 & y_2 & \cdots & y_n \\ \hline \end{array} \qquad (\star) \end{align}

Като във функцията, която ще оптимизираме просто умножаваме по $w_i$ $i$тия квадрат преди да сумираме:

(16)
\begin{align} \Phi(A, B) = \sum_{i=0}^{n} w_i (Ax_i + B - y_i)^2 \to \min \end{align}

Пак може да приложим същата тактика с частните производни като по-горе.

Сега ако искаме да приближим с полином от по-висока степен: $P(x) = a_0 + a_1x + \dots + a_m x^m$, където за предпочитане е $m$ да е доста по-малко от $n$ - оптимизираме

(17)
\begin{align} \Phi(a_0, \dots, a_m) = \sum_{i=0}^{n} w_i (P(x_i) - y_i)^2 \to \min_{a_0 \dots a_m} \end{align}

Ако си дефинираме скаларано произведение, в което е внедрено тегло:

(18)
\begin{eqnarray} & &\bar x = (x_0, \dots, x_n),\ \bar y = (y_0, \dots, y_n),\ \bar x, \bar y \in \mathbb{R}^{n+1} \\ & &(\bar x, \bar y) := \sum_{i = 0}^{n} w_i x_i y_i \\ \end{eqnarray}

Тогава може да изкажем горната оптимизация, по следния начин: Търсим полином $P(x) \in \pi_m$, за който векторът $(P(x_0), \dots, P(x_n))$ да е възможно най-близо до вектора $\bar y$ по отношение на разстоянието, породено от нормата, породена от скаларното произведение което току що дефинирахме1.

И разбира се може още повече да обобщим постановката на задачата като вместо полином използваме параметризирана функция $F(a_0, a_1, \dots, a_m, x)$, и оптимизираме

(19)
\begin{align} \sum_{i=0}^{n} (F(a_0, \dots, a_m, x_i) - y_i)^2 \to \min_{a_0 \dots a_m} \end{align}

Приближено решаване на преопределени системи

Нека е дадена система (в нашия случай линейна) в която има повече уравнения от колкото неизвестни, и по-важното - няма как всички уравнения да са удовлетворени едновременно (ако може да са удовлетворени - това просто прави задачата тривиална). Ще опитаме да намерим решение, което заместено в системата дава минимални отклонения.

(20)
\begin{eqnarray} & &\begin{array}{|ccccccc} a_{11}x_1 &+& \dots &+& a_{1n} x_n &=& b_1 \\ \vdots & & \ddots & & \vdots & & \vdots \\ a_{m1}x_1 &+& \dots &+& a_{mn} x_n &=& b_m \\ \end{array} \\ & & m > n \end{eqnarray}

Търсим решение $\tilde x = \{ \tilde x_i \}_{i=1}^{n}$, такова че:

(21)
\begin{align} \Phi(\tilde x_1, \dots \tilde x_n) = \sum_{i=1}^{m} (\sum_{j=1}^{n} a_{ij} \tilde x_j - b_i)^2 \to \min \end{align}

Разбира се използваме подхода с частните производни:

(22)
\begin{align} \left| \frac{\partial \Phi}{\partial \tilde x_i} = 0\right| \qquad i = \overline{1, n} \end{align}

И сега ако си отбележим с $A$ оригиналната матрица, с $\bar x$ началните променливи, и с $\bar b$ стълба от $b_i$ то вместо да решаваме $A \bar x = \bar b$ решаваме $A^\mathrm{T}A\tilde x = A^\mathrm{T} \bar b$. Защо? - ами това е просто по-културно записана системата с частните производни от по-горе - който не вярва да го разпише първо на лист, а после и да го въведе тук ;-)

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