politechnika Lubelska

Wydział Elektryczny

Katedra Metod Numerycznych

Temat: Aproksymacja średniokwadratowa

Plik: Wykład został udostępniony w formie elektronicznej w G:\Konspect.sic\aproksy1.doc

Jest to plik edytora WORD 2.0c for Windows.

Student: Prowadzący:

Piotr Osmałek dr hab. J. Sikora

Styczeń 1997, Lublin Spis Treści

1. Wstęp 3

2. Aproksymacja średniokwadratowa. 7

2.1 Aproksymacja średniokwadratowa funkcji dyskretnej 7

2.1.1 Aproksymacja wielomianowa 9

2.1.2 Przykład 1 11

2.1.3 Przykład 2 13

2.2 Aproksymacja średniokwadratowa funkcji ciągłych 17

1. Wstęp

Zadanie aproksymacyjne może być sformułowane bardzo różnie. W klasycznym przypadku dla danej funkcji f spośród funkcji ustalonej klasy poszukujemy tej funkcji F (też ustalonej klasy), która w określonym sensie najlepiej przybliża f. Innym zadaniem jest wyznaczenie, możliwie niskim kosztem, przybliżenia F funkcji f z zadaną dokładnością. Można wreszcie stawiać problem aproksymacji nie jednej, ale całej klasy funkcji funkcjami innej klasy. Rozwiązania tak różnie postawionych zadań są oczywiście różne, nie istnieje więc jedna "optymalna" aproksymacja.

Funkcję f(x), znaną lub określoną tablicą wartości, będziemy aproksymować (zastępować) inną funkcją F(x), zwaną funkcją aproksymującą lub przybliżeniem funkcji f(x). Oczywiście przybliżenie takie powoduje powstanie błędów aproksymacji.

Niech f(x) będzie funkcją, którą chcemy aproksymować, X - pewną przestrzenią liniową unormowaną (tzn. określona jest w niej funkcja nazywana normą)
a Xm - m-wymiarową podprzestrzenią liniową przestrzeni X.

Aproksymacja funkcji f(x) polega na wyznaczeniu takich współczynników

a0, a1, a2, ..., am funkcji

(1)

gdzie 0, 1, ..., m są funkcjami bazowymi m+1 wymiarowej podprzestrzeni liniowej Xm+1, aby funkcja F(x) spełniała pewne warunki, np. minimalizowała normę różnicy ||f(x) - F(x)||.

Norma:

Funkcja która każdemu elementowi f X przyporządkowuje liczbę rzeczywistą ||f|| i spełnia następujące warunki:

a) ||f|| 0 ;||f|| = 0 f = 0

b) ||af|| = |a| ||f||

c) ||f+g||
||f|| + ||g||

Wybór odpowiedniej podprzestrzeni Xm i związanej z nią bazy (funkcji bazowych k(x)) jest zagadnieniem istotnym ze względu na numeryczny koszt rozwiązania i błędy zaokrągleń.

Często obieraną podprzestrzenią Xm jest:

a) Podprzestrzeń funkcji trygonometrycznych z bazą

1, sin x, cos x, sin 2x, cos2x, ..., sin kx, cos kx

szczególnie przydatna, gdy aproksymowana funkcja f(x) jest funkcją okresową.

b) Podprzestrzeń wielomianów stopnia co najwyżej m z bazą jednomianów

1, x, x2, x3, ..., xm

Mimo prostoty działań na wielomianach baza ta ma istotną wadę - wrażliwość na błędy zaokrągleń; kumulujące się błędy w przypadku działań na małych oraz niewiele różniących się liczbach mogą całkowicie zniekształcić obliczenia.

c) Podprzestrzeń wielomianów stopnia co najwyżej m, określonych
na przedziale <-1, 1> z bazą wielomianów Czebyszewa

T0, T1(x), T2(x), ..., Tm(x)

czy też wielomiany Legendre'a

L0, L1(x), L2(x), ..., Lm(x)

Zagadnienie najlepszej aproksymacji przy wybranych funkcjach bazowych k(x) sprowadza się do znalezienia wartości współczynników ak takich, aby otrzymać minimum normy

||f(x) - F(x)||

||f(x) - ||

i aby istniało jedyne możliwe rozwiązanie tego zagadnienia ze względu na ak.

Normą taką może być na przykład:

a) norma Czebyszewa

Zagadnienie aproksymacji sformułujemy wówczas:

Dla funkcji f(x) określonej na przedziale <a, b> poszukujemy funkcji F(x) dającej najmniejsze maksimum różnicy między F(x) a f(x) na całym przedziale <a, b>

Aproksymacja taka nazywa się aproksymacją jednostajną.

Rys. 1 Interpretacja graficzna aproksymacji jednostajnej. Aproksymacja jednostajna polega na takim wyznaczeniu funkcji F(x) aby największa odległość punktów (wartości funkcji danej - f(x)) była
jak najmniejsza. Odległość ta określa nam jednocześnie maksymalny błąd bezwzględny jaki wystąpi jeśli funkcję f(x) zastąpimy funkcją F(x).

b) dla funkcji znanej f(x) określonej na przedziale <a, b> normą L2 z wagą

gdzie: w(x) jest ciągłą, nieujemną funkcją wagową, dodatnią poza zbiorem miary zero.

dla funkcji f(x) określonej na dyskretnym zbiorze punktów xi, tablicą wartości xi, f(xi) normą:

gdzie: w(xi) - funkcja wagowa taka, że w(xi) 0 dla i = 0, 1, 2, ..., n

Zagadnienie aproksymacji sformułujemy wówczas:

Dla funkcji f(x) określonej na przedziale <a, b> poszukujemy minimum całki

(2)

a dla funkcji f(xi) danej na dyskretnym zbiorze argumentów poszukujemy minimum sumy (metoda najmniejszych kwadratów)

(3)

gdzie: w(x) i w(xi) określono j.w.

Aproksymacja taka nazywa się aproksymacją średniokwadratową.

Rys. 2 Interpretacja graficzna aproksymacji średniokwadratowej. Aproksymacja średniokwadratowa polega na takim wyznaczeniu funkcji F(x) aby suma kwadratów odległości punktów (wartości funkcji danej - f(x)) była jak najmniejsza. Aproksymacja ta znacznie lepiej od aproksymacji jednostajnej "eliminuje" duże błędy przypadkowe np. wynikające z pomyłek przy pomiarach.

Istnieją twierdzenia mówiące, że zawsze można znaleźć wielomian Pn(x) (n=n())
o dowolnie małym odchyleniu od funkcji f(x) ciągłej na danym przedziale jeśli tylko weźmiemy dostatecznie duże n.

2. Aproksymacja średniokwadratowa.

Aproksymacja średniokwadratowa funkcji dyskretnej

Zajmiemy się teraz przypadkiem aproksymacji średniokwadratowej, gdy funkcja aproksymowana f(x) dana jest jedynie na dyskretnym zbiorze argumentów X
(w postaci tablicy xi, f(xi)). Idea tej aproksymacji jest zilustrowana na rysunku:

Rys. 3 Interpretacja graficzna aproksymacji i interpolacji. Funkcja interpolacyjna przechodzi dokładnie przez węzły interpolacji, funkcja aproksymacyjna natomiast "wygładza" je.

Niech będzie dana funkcja y = f(x), która na pewnym zbiorze X punktów
x0, x1, x2, ..., xn przyjmuje wartości y0, y1, y2, ..., yn. Wartości te możemy znać tylko w przybliżeniu, z pewnymi błędami (np. jako wyniki pomiarów obarczone błędami obserwacji). Będziemy poszukiwać takiej funkcji F(x) przybliżającej daną funkcję f(x), która umożliwi wygładzenie funkcji f(x), tzn. pozwoli z zakłóconych błędami danych wartości funkcji przybliżanej otrzymać gładką funkcję przybliżającą, z dużym prawdopodobieństwem mało odchylającą się od funkcji przybliżanej zarówno między węzłami, jak i w węzłach x0, x1, x2, ..., xn, jeżeli tylko przyjmiemy, że funkcja przybliżana ma dość gładki przebieg.

Niech j(x), j = 0, 1, 2, .., m, będzie układem funkcji bazowych podprzestrzeni Xn. Poszukujemy wielomianu uogólnionego:

(1)

lub

(1')

będącego najlepszym przybliżeniem średniokwadratowym funkcji f(x), przy czym

współczynniki ai są tak określone, aby wyrażenie

było minimalne.

Oznaczmy

(4)

gdzie: w(x) - funkcja wagowa ustalona z góry taka, że w(xi) 0 dla i = 0, 1, 2, ..., n.

Rj jest odchyleniem w punkcie Xj.

Najczęściej przyjmuje się, że funkcja wagowa w(x) ma stałą wartość,
równą tożsamościowo jedności, można jednak dobrać inną funkcję wagową (np. jeżeli znamy wartości funkcji w pewnych punktach z mniejszym błędem i chcemy aby otrzymane przybliżenie było w tych punktach lepsze
to przyjmujemy w tych punktach większe wartości funkcji wagowej.

Aby znaleźć takie współczynniki ak dla których funkcja H ma minimum obliczamy pochodne cząstkowe względem zmiennych ai.

otrzymamy wówczas układ m+1 równań z m+1 niewiadomymi ai.

(5)

k = 0, 1, 2, ..., m

zwany układem normalnym. Ponieważ funkcje j(x) tworzą bazę przestrzeni Xm, więc układ ten ma wyznacznik różny od zera (układ ma jednoznaczne rozwiązanie) i rozwiązanie tego układu daje minimum funkcji H.

W zapisie macierzowym układ ten przyjmuje postać

DTDA=DTf (6)

gdzie

, ,

Macierz współczynników układu jest macierzą symetryczną i dodatnio określoną
co zapewnia jednoznaczność rozwiązania.

Układ (5) lub (6) można otrzymać z równania (1) po podstawieniu wartości punktów węzłowych xi(i=0, 1, 2, ..., n). Otrzymujemy wówczas nadokreślony układ n+1 równań z m+1 niewiadomymi

DA=f

z którego popomnożeniu(lewostronnie)przezDTotrzymujemy (6)

2.1.1 Aproksymacja wielomianowa

Jeżeli jako funkcje bazowe j(x) przyjmiemy ciąg jednomianów

1, x, x2, x3, ..., xm

to wzór (5) przyjmie postać

lub po przekształceniu

k = 0, 1, 2, ..., m (7)

oznaczając

otrzymujemy układ normalny postaci

lub

gdzie wszystkie sumowania są od j = 0 do j = n

Można wykazać, że jeżeli punkty xo, x1, x2, ..., xn są różne i m 
 n, to wyznacznik układu jest różny od zera, a więc układ ten ma jednoznaczne rozwiązanie.
Jeżeli m = n, to wielomian aproksymacyjny F(x) pokrywa się z wielomianem interpolacyjnym dla punktów xo, x1, x2, ..., xn i wówczas H = 0. W praktyce stopień wielomianu m jest i powinien być znacznie niższy od liczby punktów n, wtedy bowiem korzystamy z dużej ilości informacji (np. wyników pomiarów) uzyskując równocześnie prostsze (niskiego stopnia) funkcje aproksymujące.

Wielomian aproksymujący daną funkcję f(x) w sensie najmniejszych kwadratów powinien mieć stopień na tyle wysoki, aby dostatecznie przybliżać aproksymowaną funkcję, a jednocześnie stopień ten powinien być wystarczająco niski, aby wielomian ten wygładzał losowe błędy wynikające np. z pomiarów. W praktyce stopień wielomianu określamy a piori
na podstawie analizy modelu fizycznego badanego zjawiska bądź też przeprowadzamy aproksymację kolejno wielomianami coraz to wyższych stopni i obliczamy odchylenia funkcji H. Proces ten prowadzimy tak długo, jak długo ze wzrostem stopnia wielomianu funkcja H maleje w znaczny sposób.

Dla m
6 układ jest źle uwarunkowany, wskutek czego otrzymane wyniki obliczeń na maszynach cyfrowych mogą być tak bardzo zaburzone, iż nie nadają się
do praktycznego wykorzystania przy aproksymacji.

Złe uwarunkowanie:

Niech xi będą rozłożone w jednakowych odstępach w przedziale <0, 1>. Liczby gik można dla dużych m przybliżyć następująco

i,k = 0, 1, 2, ..., m

Elementy macierzy odwrotnej A-1 są rzędu 31012 co powoduje błędy zaokrągleń tak duże, że wyniki praktycznie tracą sens.

Tak więc stosowanie aproksymacji z funkcjami bazowymi typu jednomianów xi ma sens jedynie dla małych m (m < 6). Aby można było aproksymować wielomianami wyższych stopni można:

- zastosować specjalną metodę rozwiązywania układów równań, których macierz współczynników ma wyznacznik bliski zeru.

- zwiększyć precyzję (dokładność) wykonywania obliczeń na maszynie cyfrowej.

- zamienić bazę jednomianów xi bazą złożoną z wielomianów ortogonalnych.

Przykład 1

Dane są wyniki pomiarów

x	1	3	4	6	8	9	11	14
y	1	2	4	4	5	7	8	9

Poszukujemy zależności między x i y postaci

ax + by = 1

przy czym należy dobrać "optymalne" wartości współczynników a i b.

Przy tak sformułowanym zadaniu pojawia się problem: czy rozpatrywać odchylenia x czy y ?

Tabela pomocnicza n=7

j	0	1	2	3	4	5	6	7	j
x	1	3	4	6	8	9	11	14	56
y	1	2	4	4	5	7	8	9	40
xy	1	6	16	24	40	63	88	126	364
x2	1	9	16	36	64	81	121	196	524
y2	1	4	16	16	25	49	64	81	256

y = 1/b - (a/b)x y = f(x)

y = -(a/b)x + 1/b

a1 = -a/b a0 = 1/b

wszystkie sumowania od j = 0 do j = n

otrzymujemy:

i poszukiwane równanie

11y - 7x = 6

x = 1/a - (b/a)y x=f(y)

x = - (b/a)y +1/a

a1 = -b/a a0 = 1/a

wszystkie sumowania od j = 0 do j =n

otrzymujemy:

i poszukiwane równanie

2x - 3y = -1

Tak więc rozpatrując odchylenia x lub y otrzymujemy różne równania, chociaż ich wykresy prawie się pokrywają.

Przykład 2

Dane są wyniki pomiarów

x	1	2	3
f(x)	1	2	4

Poszukujemy funkcji aproksymującej kolejno stopnia 1,2,3:

a)
n=2 m=1

b)
n=2 m=2

c)
n=2 m=3

gdzie m - stopień wielomianu, n+1 - liczba węzłów aproksymacji

Ogólna postać wzoru na obliczenie "optymalnych" współczynników ak :

Tabela pomocnicza n=2 m=1,2,3

j	0	1	2	suma
x	1	2	3	6
f(x)	1	2	4	7
x2	1	4	9	14
x3	1	8	27	36
x4	1	16	81	98
x5	1	32	243	276
x6	1	64	729	794
f(x)*x	1	4	12	17
f(x)*x2	1	8	36	45
f(x)*x3	1	16	108	125

a)
n=2 m=1

Wzór ogólny przyjmie postać:

po rozwiązaniu otrzymujemy

= -0,6667

= 1,5

b)
n=2 m=2

Wzór ogólny przyjmie postać:

po rozwiązaniu otrzymujemy

= 1

= -0,5

= 0,5

c)
n=2 m=3

Wzór ogólny przyjmie postać:

Po dokonaniu eliminacji Gaussa otrzymujemy

otrzymaliśmy więc układ 3 równań z 4 niewiadomymi, którego rozwiązanie
nie jest jednoznaczne. Jeśli podstawimy zamiast dowolnej zmiennej (np.
) parametr t (
=t) to otrzymamy rozwiązanie zależne od parametru t.

= 1 - 6 t

= - 1/2 + 11 t

= 1/2 - 6 t

= t

Jeśli liczba n (n = liczba danych węzłów aproksymacji - 1) jest większa
od stopnia wielomianu m to otrzymujemy wielomian aproksymacyjny.

Jeśli n = m to otrzymujemy wielomian interpolacyjny (krzywa przechodzi dokładnie przez węzły aproksymacji).

Jeśli n < m to otrzymujemy całą rodzinę funkcji (charakterystyk) zależną
od parametru. Wszystkie te przypadki dla naszego przykładu przedstawia rys.5.

Wyznaczymy kilka wielomianów

t
-1	7	-11,5	6,5	-1
0	1	-0,5	0,5	0
1	-5	10,5	-5,5	1
2	-11	21,5	-11,5	2

Rys. 5 Wyniki aproksymacji danych z przykładu 2 wielomianami stopnia 1, 2 i 3.

2.2 Aproksymacja średniokwadratowa funkcji ciągłych

Przyjmijmy, że daną funkcję f(x) ciągłą na przedziale <a, b> mamy aproksymować funkcją postaci

(8)

gdzie 0, 1, ..., m są elementami bazy pewnej podprzestrzeni funkcji całkowalnych z kwadratem na przedziale <a, b>.

Aproksymacja średniokwadratowa funkcji ciągłych polega na znalezieniu takiego ciągu współczynników ai (i = 0, 1, 2, ...,m) aby otrzymać minimum normy

(9)

gdzie: w(x) jest ciągłą, nieujemną funkcją wagową, dodatnią poza zbiorem miary zero. Oznaczmy jak poprzednio

H(a0, a1, a2, ..., am)

Jak poprzednio aby rozwiązać zadanie obliczamy pochodne cząstkowe

otrzymamy wówczas układ m+1 równań z m+1 niewiadomymi ai.

---