Chu9

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

---

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

---

Днес ще се занимаваме с приложенията на приближения в Хилбертово пространство - методи на най-малките квадрати
и полиноми на най-добро средноквадратично приближение.

Задача. По дадена таблица от възли, стойности и тегла:

$x_i$	-1	0	1	2
$y_i$	1	3	-1	0
$w_i$	1	1	2	1

Да се намери линейна функция (полином от първа степен) $P(x) = ax + b$, който приближава данните от таблицата по
метода на най-малките квадрати.

Решение. Идеята на метода е да се минимизира сумата от квадратите на разликата в съответните точки.
Образува се сумата $\Phi(a,b) = \sum_{i=0}^3 w_i(ax_i + b - y_i)^2 -> \min_{a,b}$

Условията за минимум налагат следната система:

| $\frac { криво d Ф} {d a} = 0$
| $\frac { криво d Ф} {d b} = 0$

| $\sum_{i=0}^3 w_i(ax_i + b - y_i).x_i = 0$
| $\sum_{i=0}^3 w_i(ax_i + b - y_i).1 = 0$

| $a(\sum_{i=0}^3 w_ix_i^2) + b(\sum_{i=0}^3 w_ix_i) = \sum_{i=0}^3 w_iy_i$
| $a(\sum_{i=0}^3 w_ix_i^2) + b(\sum_{i=0}^3 w_ix_i^0) = \sum_{i=0}^3 w_ix_i^- y_i$

За удобство на записа ще ползваме числата
$S_k := \sum_{i=0}^3 w_ix_i^k$
$T_k := \sum_{i=0}^3 w_ix_i^ky_i$

| $a.S_2 + b.S_1 = T_1$
| $a.S_1 + b.s_0 = T_0$

$s_0 = 5, S_1 = 3, [[$ S_2 = 7$
$T_0 = -1$, $T_1 = -3$

| $7a + 3b = -3$
| $3a + 5b = 2$

Решаваме и получаваме коефициентите на търсения полином: $b = \frac {23} {26}$, $a = -\frac {21} {26}$
Търсеният полином е $P(x) = -\frac {21} {26} x + \frac {23} {26}$

Можем да търсим полином от m-та степен по този начин, като условието е m « n .Идеята е да се намери полином
от ниска степен, който да минимизира сумата от квадратите на разликите. Ако липсва редицата с теглата, то
всички възли са с тегло 1 - никой не е по-равен от равните.
В този пример се вижда, че системата има симетрична матрица.

Още една задача.

$x_i$	-2	-1	0	1	2
$y_i$	1	2	-1	0	1
$w_i$	1	1	2	1	1

Да се намери полином от втора степен, който приближава таблицата по МНК. $P(x) = ax^2 + bx + c$.

Решение. $\Phi(a,b,c) = \sum_{i=0}^4 w_i(ax_i^2 + bx_i + c - y_i)^2 -> \min_{a,b,c}$

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

Построяваме системата

| $\frac {криво d Ф} {криво d a} = 0$
| $\frac {криво d Ф} {криво d b} = 0$
| $\frac {криво d Ф} {криво d c} = 0$

| $S_4 a + S_3 b + S_2 c = T_2$
| $S_3 a + S_2 b + S_1 c = T_1$
| $S_2 a + S_1 b + S_0 c = T_0$

$S_4 = 1(-2)^4 + 1(-1)^4 + 2.0^4 + 1.1^4 + 1.2^4 = 34$
$S_3 = 1(-2)^3 + 1(-1)^3 + 2.0^3 + 1.1^3 + 1.2^3 = 0$
$S_2 = 1(-2)^2 + 1(-1)^2 + 2.0^2 + 1.1^2 + 1.2^2 = 10$
$S_1 = 1(-2) + 1(-1) + 2.0 + 1.1 + 1.2 = 0$
$S_0 = 6$

$T_2 = 1.1.(-2)^2 + 1.2.(-1)^2 + 2.(-1).0^2 + 1.0.1^2 + 1.1.2^2 = 10$
$T_1 = 1.1.(-2) + 1.2.(-1) + 2.(-1).0 + 1.0.1 + 1.1.2 = -2$
$T_0 = 1.1 + 1.2 + 2.(-1) + 1.0 + 1.1 = 2$

| $34a + 0b + 10c = 10$
| $0a + 10b + 0c = -2$
| $10a + 0b + 6c = 2$

Решаваме: $b = -\frac 1 5$. a и b са за упражнение на читателя (duh).

Метод на най-малките квадрати за приближено решаване на преопределени системи линейни уравнения.

Нека имаме системата
| a_{11}x_1 + a_{12}x_2 + … + a_{1n}x_n = b_1
| a_{21}x_1 + a_{22}x_2 + … + a_{2n}x_n = b_2
| \dots
| a_{m1}x_1 + a_{m2}x_2 + … + a_{mn}x_n = b_m

Можем да я запишем като A{x надчертано} = {b надчертано}, където A = (a_{ij})mxn, {надчертано x} =
вектор-стълб(x_1, x_2, …, x_n), {надчертано b} = вектор-стълб(b_1, …, b_m)

Тези системи обикновено нямат решение или са ЛЗ, но търсим нещо, което "приблизително" да отговаря на условията.

\Phi(\~{X_1}, \~{x_2}, \~{x_3} = \sum_{i=1}^m (a_{i1}\~{x_1} + … + a_{in}\~{x_n} - b_i)^2

Условията изглеждат така:
| \frac {криво d Ф} {криво d \~{x_k} = 0
| k = 1, …, n
, т. е. \sum_{i=1}^m a_ik(a_{i1}\~{x_1} + … + a_{in}\~{x_n} = \sum_{i=1}^m a_{ik}b_i

Една конкретна задача. Да се реши приблизително по метода на най-малките квадрати системата

| x + y = 1
| x + y = -1
| x - y = 2
| x - y = 1

Решение. Системата очевидно няма точно решение, но бихме могли да я решим приближено. Това означава да
[не разбрах]:

A = (1 1 | , A^T = (1 1 1 1 | .(1
1 1 | 1 1 -1 -1) | -1
1 -1 | | 1
1 -1) | | 2)

A^T . A = (1 1 1 1 . | (1 1 = (4 0 , | A^t.{b надчертано} = | (3
1 1 -1 -1) | 1 1 0 4) | |-3)
| 1 -1 | |
| 1 -1) | |

| 4\~{x} + 0\~{y} = 3
| 0\~{x} + 4\~{y} = -3

\~{x} = \frac 3 4, \~{y} = -\frac 3 4

Същата задача за друга система:

| x + y = 1
| x - y = -1
| 2x - y = 0
| x + 2y = 1

A = (1 1 1 | ; A^T . A = (1 1 2 1 | . (1 1 1 = | (7 -2 1
1 -1 -1 | 1 -1 -1 2 | 1 -1 -1 | -2 3 2
2 -1 0 | 1 -1 0 1 ) | 2 -1 0 | 1 2 3 )
1 2 1 ) | | 1 2 1 ) |

Тук матрицата е пълна, не единична както в предишния случай.

A^T.{b надчертано} = (1 1 2 1 . | (1 = | (5
1 -1 -1 0 | 3 | -3
1 -1 0 1 ) | 1 | -3)
| -1) |

За да решим първоначалната система приближено по МНК, трябва да решим следната система:

| 7\~{x} - 2\~{y} + \~{z} = 5
| -2\~{x} + 3\~{y} + 2\~{z} = -3
| 1\~{x} + 2\~{y} + 3\~{z} = -3

Решаваме системата: \~{x} = \frac 35 6, \~{y} = \frac 37 3, \~{z} = -\frac 67 6
(\~{x}, \~{y}, \~{z}) = (\frac 35 6, \frac 37 3, -\frac 67 6)

Последно приложение на метода: полиноми на най-добро средноквадратично приближение (ПНДСКП)

Задача(?общ вид). По даден интервал [a,b], функция на тегло $\mu(x)$, f(x) - дефинирана и интегруема, да се
намери полином $P(x) \in \Pi_x$, такъв, че
$\underset {това отгоре е ||f - P||^2} {\int_a^b \mu(x) [f(x) - P(x)]^2 dx} -> min_{p \in \Pi_x}$

$P \in \Pi_x е ПНДСКП \Leftrightarrow$
| $\int_a^b \mu(x) [f(x) - P(x)] x^k dx = 0$
| $k = 0, ..., n$

Това е система от n+1 уравнения за коефициентите a0, …, an на P(x)
Съществува единствен ПНДСКП за f от $\Pi_n$. От единствеността следва следното твърдение:

Задача. Нека $\mu(x)$ е четна функция на тегло в интервала [-a, a]. Да се докаже, че ако f(x) е четна (нечетна)
функция в [-a, a], тогава ПНДСКП за f(x) също е четен(нечетен).

Решение. Нека f(x) е четна (тоест $f(x) \equiv f(-x)$).
Нека P(x) е ПНДСКП за f(x) в [-a, a] при тегло $\mu(x)$.
Тогава $\epsilon _n^2(f) = ||f - P||^2 = \int_{-a}^a \mu(x)[f(x) - P(x)]^2 dx \overset {x = -t} {=}$
$= \int_a^{-a} \mu(-t) [f(-t) - P(-t)]^2 (-dt) = \int_{-a}^a \mu(t) [f(t) - P(-t)]^2 dt = e_n^2(f)$

Следва, че P(-t) също е ПНДСКП за f(x) в [-a,a]. Но ПНДСКП е единствен, следователно $P(t) \equiv P(-t)$

Задача. Да се намери ПНДСКП от трета степен в [-1, 1] при тегло $\mu(x) = -1$ за $f(x) = x^4$

Решение. f(x) е четна, интервалът е симетричен ([-1, 1]), $\mu(x) = 1$ - четна, следователно ПНДСКП къщо е четен.
$P(x) = ax^2 + b$
$\int_{-1}^1 (x^4 - ax^2 - b)x^k dx = 0$ за = 0, 1, 2, 3.

От избора ни на четна функция, интегралът автоматично ще е 0 за k = 1, 3 .

$k = 0. \int_{-1}^1 (x^4 - ax^2 - b)1 dx = 2\int_0^1 (x^4 - ax^2 - b)dx ->$
$\frac 1 5 - \frac 1 3 a - b = 0$

$k = 1. \int_{-1}^1 (x^4 - ax^2 - b)x^k dx = 0.$

$k = 2. \int_{-1}^1 (x^4 - ax^2 - b)x^k dx = 2\int_0^1 (x^4 - ax^2 - b)x^2 dx$
$\frac 1 7 - \frac 1 5 a - \frac 1 3 b = 0$

$k = 3. \int_{-1}^1 (x^4 - ax^2 - b)x^k dx = 0.$

Получихме следната система:
$| \frac 1 3 a + b = \frac 1 5$
$| \frac 1 5 a + \frac 1 3 b = \frac 1 7$

решаваме и получаваме коефициентите в полинома: $a = \frac 6 7, b = -\frac 3 35$
$P(x) = \frac 6 7 x^2 - \frac 3 35$

Уравненията за k = 1, 3 нямаше да са тривиално изпълнени, ако пред степени 1 и 3 имахме коефициенти, различни
от 0. Тогава щяхме да решим хомогенна система.