TECHNOLOGIE INFORMACYJNE, Sem.1

Interpolacja i Aproksymacja

INTERPOLACJA I APROKSYMACJA FUNKCJI

W praktyce obliczeniowej, zwłaszcza inżynierskiej, częstokroć nie znana jest postać funkcji y = f(x), dane są natomiast punkty ( xi,yi). Występuje zatem potrzeba zastąpienia funkcji danej punktowo (np. z urządzenia pomiarowego) za pomocą dogodnej postaci analitycznej. Powszechnie stosuje się w tym celu funkcje w postaci tzw. wielomianów uogólnionych.

W(x) = a1u1(x) + a2u2(x) +…+ anun(x)

Przy czym funkcje ui(x) są funkcjami bazowymi o różnych postaciach: a) jednomianowej

1, x, x2, x3, …, xn

b) trygonometrycznej

1, sin(x), cos(x), sin(2x), cos(2x)

c)itp.

Zadanie interpolacyjne (aproksymacyjne) polega na określeniu wartości (przybliżonej wartości) y = f(x) w dowolnym innym niż dane punkcie x.

INTERPOLACJA FUNKCJI

Danych jest n punktów (x1,y1), (x2,y2), …, (xn,yn). Wielomian uogólniony zwany w tym przypadku wielomianem interpolacyjnym, przechodzi przez wszystkie z danych punktów.

Wi(xi) = yi przy i = 1 ÷ n

Liczba poszukiwanych współczynników ai jest zatem równa liczbie punktów ( n).

Poszukiwanie współczynników ai prowadzi do rozwiązania układu n równań liniowych w postaci:

 a u (x ) + a u (x ) + ... + a u (x ) = y



1 1

1

2

2

1

n

n

1

1

 a u (x ) + a u (x ) + ... + a u (x ) = y



1 1

2

2

2

2

n

n

2

2

 .....................................................................

 a u (x ) + a u (x ) + ... + a u (x ) = y

1 1

n

2

2

n

n

n

n

n

1

TECHNOLOGIE INFORMACYJNE, Sem.1

Interpolacja i Aproksymacja

W przypadku zastosowania interpolacji wielomianowej w postaci

ui(x) = 1, x, x2, x3, …, xn-1

otrzymujemy

 a + a x +

2

a x

+ ... +

− 1

n

a x

=



y

1

2

1

3

1

n

1

1

 a + a x +

2

a x

+ ... +

− 1

n

a x

= y

 1

2

2

3

2

n

2

2

 ............................................................



2

n−

 a + a x + a x

+ ... +

1

a x

= y

1

2

n

3

n

n

n

n

co zapisać można w postaci macierzowej

A × X = B

2

n 1

1

x

x

... x −

a

y

1

1

1

1

1

2

n 1

1

x

x

... x −

a

y

2

2

2

2

2

×

=

...

...

...

...

...

...

...

2

n 1

1

x

x

... x −

a

y

n

n

n

n

n

Rozwiązanie sprowadza się do wykonania operacji matematycznej AT × A × X = AT × B

gdzie:

AT - jest macierzą transponowaną (tj. odwrotna – powstająca przez przestawienie wieszy z kolumnami) do macierzy A przy czym AT × A = 1, a zatem:

X = AT × B

Interpolacja funkcji stosowana jest w przypadku małej ilości n danych punktów, gdyż duża ilość punktów powoduje konieczność rozwiązywania rozbudowanych układów równań wielomianów wysokich stopni. Efektem czego jest pojawianie się znacznych błędów, zwłaszcza w początkowym i końcowym zakresie (tzw. Problem Runge’go – niestabilność funkcji)

APROKSYMACJA

Danych jest n punktów (x1,y1), (x2,y2), …, (xn,yn). Wielomian uogólniony zwany w tym przypadku wielomianem aproksymacyjnym, przechodzi w pobliżu danych punktów, oddając w ten sposób przybliżony przebieg funkcji. Powoduje to powstawanie różnicy pomiędzy wartościami rzeczywistymi danych punktów, a wartościami z aproksymacji. Różnica ta wynosi:

ε (xi) = yi – Wl(xi) przy i = 1 ÷ n

2

TECHNOLOGIE INFORMACYJNE, Sem.1

Interpolacja i Aproksymacja

Zadanie

aproksymacyjne

polega

na

takim

dobraniu

wielomianu

aproksymacyjnego, aby był on jak najlepiej dopasowany, przez co różnica ta była jak najmniejsza i określeniu przy jego pomocy przybliżonej wartości y = f(x) w dowolnym innym niż dane punkcie x.

Istnieje kilka metod aproksymacji, przy czym najczęściej stosowaną jest metoda najmniejszych kwadratów.

W przypadku najmniejszych kwadratów różnica ta wynosi ε (xi) = yi – Wl(xi)

ponieważ:

Wl(x) = a1u1(x) + a2u2(x) +…+ akuk(x) gdzie k<<n

a zatem:

k

ε (xi) = yi – ∑ alul(xi)

l = 1

Zadanie minimalizacji tej różnicy sprowadza się tu zatem do postaci:

n

2

k

ϕ = ∑ f ( x

a u (x )

min

i ) − ∑ ( l l

i

)



 ⇒

i = 1 

l = 1



Poszukiwanie współczynników al prowadzi do rozwiązania układu k równań liniowych w postaci:



n

δϕ



= 2∑ (f(x ) − (a u (x ) + a u (x ) + ... + a u (x ))) ⋅ ( − u (x ))

i

1 1

i

2

2

i

k

k

i

1

i

 δa1

i = 1

n

 δϕ = 2∑ (f(x ) − (a u (x ) + a u (x ) + ... + a u (x ))) ⋅ ( − u (x ))



i

1 1

i

2

2

i

k

k

i

2

i

δa



2

i = 1

 ........................................................................................................

n

ϕ

 δ

= 2∑ (f(x ) − (a u (x ) + a u (x ) + ... + a u (x ))) ⋅ ( − u (x ))



i

1 1

i

2

2

i

k

k

i

k

i

δak

i = 1

W przypadku zastosowania bazy kwadratowej

n

ϕ = ∑( y −

2

( a x + a x + a )

min

i

1

i

2

i

3 ) 2 ⇒

i = 1

Układ równań przyjmuje zatem postać

3

TECHNOLOGIE INFORMACYJNE, Sem.1

Interpolacja i Aproksymacja



n

δϕ

2

2



= 2∑ (y − (a x + a x + a )) ⋅ ( − x )

i

1

i

2

i

3

i

 δa1

i = 1

n

δϕ



= 2∑ (y −

2

(a x + a x + a )) ⋅ ( − x )



i

1

i

2

i

3

i

δa

2

i =



1

n

δϕ



= 2∑ (y −

2

(a x + a x + a )) ⋅ ( − 1)



i

1

i

2

i

3

δa3

i = 1



Ponieważ warunkiem istnienia minimum jest

δϕ = 0

δal

otrzymujemy układ równań w postaci:

 n

2

2

 2∑ [(y − a x − a x − a ) ⋅ ( − x )] = 0

i

1

i

2

i

3

i

 i= 1

 n

 2∑ [(y −

2

a x − a x − a ) ⋅ ( − x )] = 0

i

1

i

2

i

3

i

 i= 1



n

2

 2∑ [(y − a x − a x − a ) ⋅ ( − 1)] = 0



i

1

i

2

i

3

i = 1

 n

2

4

3

2

 2∑ (-y x + a x + a x + a x ) = 0

i

i

1

i

2

i

3

i

 i= 1



n

 2∑ (-y x +

3

a x +

2

a x + a x ) = 0

i

i

1

i

2

i

3

i

 i= 1



n

2



2∑ (-y + a x + a x + a ) = 0



i

1

i

2

i

3

i = 1

 n

n

2

2

2

2

2

∑ (a x ⋅ x + a x ⋅ x + a ⋅ x ) =

y x

1

i

i

2

i

i

3

i

∑ i i

 i= 1

i=1



n

n

 ∑

2

(a x ⋅ x + a x ⋅ x + a x ⋅ ) =

y x

1

i

i

2

i

i

3

i

∑ i i

 i= 1

i=1



n

n

2



∑ (a x + a x + a ) = y

1

i

2

i

3

∑



i

i = 1

i=1



n

n

n

n

2

2

2

2

2

 a

x

x

a

x x

a

x

y x

1 ∑

⋅

+

i

i

2 ∑

⋅

+

i

i

3 ∑

=

i

∑ i i

 i=1

i=1

i=1

i=1



n

n

n

n

 a

x

x

a

x x

a

x

y x

1 ∑

2 ⋅

+

i

i

2 ∑

⋅ +

i

i

3 ∑

=

i

∑ i i



i=1

i=1

i=1

i=1



n

n

n

2



a

x

a

x

a

y

1 ∑

+

i

2 ∑

+

=

i

3

∑



i

i=1

i=1

i=1

4

TECHNOLOGIE INFORMACYJNE, Sem.1

Interpolacja i Aproksymacja

co zapisać można w postaci macierzowej

A × X = B

∑ n 4

a

x

x

x

y x

i

∑ n 3i ∑ n 2

1

i

∑ n

2

i

i

i = 1

i = 1

i = 1

i = 1

∑ n 3

x

x

x

a

y x

i

∑ n 2i ∑ n

n

×

=

i

2

∑ i i

i = 1

i = 1

i = 1

i = 1

∑ n 2

x

x

1

y

i

∑ n i

a

∑ n i

i = 1

i =

3

1

i = 1

Rozwiązanie sprowadza się do wykonania operacji matematycznej AT × A × X = AT × B

gdzie:

AT - jest macierzą transponowaną (tj. odwrotna – powstająca przez przestawienie wieszy z kolumnami) do macierzy A przy czym AT × A = 1, a zatem:

X = AT × B

Aproksymacja funkcji stosowana jest zazwyczaj w przypadku bardzo dużej ilości n danych punktów, gdyż duża ilość punktów nie powoduje konieczność rozwiązywania rozbudowanych układów równań wielomianów wysokich stopni.

Aproksymacja oddaje jednak tylko przybliżony (najbardziej) przebieg funkcji, co powoduje powstawanie błędów aproksymacji. Nie występuje tu jednak problem niestabilności (tzw. Runge’go) tj. „rozbiegnięcia” na początku i końcu zakresu danych. Pozwala to na prognozowanie wartości funkcji w punktach leżących poza zakresem danych.

5