TECHNOLOGIE INFORMACYJNE, Sem.1

Interpolacja i Aproksymacja

1

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 (x

i

,y

i

). 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) = a

1

u

1

(x) + a

2

u

2

(x) +…+ a

n

u

n

(x)

Przy czym funkcje u

i

(x) są funkcjami bazowymi o różnych postaciach:

a) jednomianowej

1, x, x

2

, x

3

, …, x

n

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 (x

1

,y

1

), (x

2

,y

2

), …, (x

n

,y

n

). Wielomian uogólniony zwany

w tym przypadku wielomianem interpolacyjnym, przechodzi przez wszystkie z danych

punktów.

W

i

(x

i

) = y

i

przy i = 1 ÷ n

Liczba poszukiwanych współczynników a

i

jest zatem równa liczbie punktów (n).

Poszukiwanie współczynników a

i

prowadzi do rozwiązania układu n równań liniowych

w postaci:













=

+

+

+

=

+

+

+

=

+

+

+

n

n

n

n

n

2

2

n

1

1

2

2

n

n

2

2

2

2

1

1

1

1

n

n

1

2

2

1

1

1

y

)

(x

u

a

...

)

(x

u

a

)

(x

u

a

.........

..........

..........

..........

..........

..........

..........

y

)

(x

u

a

...

)

(x

u

a

)

(x

u

a

y

)

(x

u

a

...

)

(x

u

a

)

(x

u

a

TECHNOLOGIE INFORMACYJNE, Sem.1

Interpolacja i Aproksymacja

2

W przypadku zastosowania interpolacji wielomianowej w postaci

u

i

(x) = 1, x, x

2

, x

3

, …, x

n-1

otrzymujemy













=

+

+

+

+

=

+

+

+

+

=

+

+

+

+

−

−

−

n

1

n

n

n

2

n

3

n

2

1

2

1

n

2

n

2

2

3

2

2

1

1

1

n

1

n

2

1

3

1

2

1

y

x

a

...

x

a

x

a

a

..........

..........

..........

..........

..........

..........

y

x

a

...

x

a

x

a

a

y

x

a

...

x

a

x

a

a

co zapisać można w postaci macierzowej

A × X = B

n

2

1

n

2

1

1

n

n

2

n

n

1

n

2

2

2

2

1

n

1

2

1

1

y

...

y

y

a

...

a

a

x

...

x

x

1

...

...

...

...

...

x

...

x

x

1

x

...

x

x

1

=

×

−

−

−

Rozwiązanie sprowadza się do wykonania operacji matematycznej

A

T

× A × X = A

T

× B

gdzie:

A

T

- jest macierzą transponowaną (tj. odwrotna – powstająca przez przestawienie

wieszy z kolumnami) do macierzy A przy czym A

T

× A = 1, a zatem:

X = A

T

× 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 (x

1

,y

1

), (x

2

,y

2

), …, (x

n

,y

n

). 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:

ε

(x

i

) = y

i

– W

l

(x

i

) przy i = 1 ÷ n

TECHNOLOGIE INFORMACYJNE, Sem.1

Interpolacja i Aproksymacja

3

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

ε

(x

i

) = y

i

– W

l

(x

i

)

ponieważ:

W

l

(x) = a

1

u

1

(x) + a

2

u

2

(x) +…+ a

k

u

k

(x) gdzie k<<n

a zatem:

ε

(x

i

) = y

i

–

∑

=

k

1

l

a

l

u

l

(x

i

)

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

( )

(

)

∑

∑

=

=

⇒













−

=

n

1

i

2

k

1

l

i

l

l

i

min

)

(x

u

a

x

f

ϕ

Poszukiwanie współczynników a

l

prowadzi do rozwiązania układu k równań liniowych

w postaci:





















−

⋅

+

+

+

−

=

−

⋅

+

+

+

−

=

−

⋅

+

+

+

−

=

∑

∑

∑

=

=

=

n

1

i

i

k

i

k

k

i

2

2

i

1

1

i

k

n

1

i

i

2

i

k

k

i

2

2

i

1

1

i

2

n

1

i

i

1

i

k

k

i

2

2

i

1

1

i

1

))

(x

u

(

)))

(x

u

a

...

)

(x

u

a

)

(x

u

(a

)

(f(x

2

δa

δ

....

..........

..........

..........

..........

..........

..........

..........

..........

..........

..........

))

(x

u

(

)))

(x

u

a

...

)

(x

u

a

)

(x

u

(a

)

(f(x

2

δa

δ

))

(x

u

(

)))

(x

u

a

...

)

(x

u

a

)

(x

u

(a

)

(f(x

2

δa

δ

ϕ

ϕ

ϕ

W przypadku zastosowania bazy kwadratowej

(

)

∑

=

⇒

+

+

−

=

n

1

i

2

3

i

2

2

i

1

i

min

a

x

a

x

a

y

)

(

ϕ

Układ równań przyjmuje zatem postać

TECHNOLOGIE INFORMACYJNE, Sem.1

Interpolacja i Aproksymacja

4





















−

⋅

+

+

−

=

−

⋅

+

+

−

=

−

⋅

+

+

−

=

∑

∑

∑

=

=

=

n

1

i

3

i

2

2

i

1

i

3

n

1

i

i

3

i

2

2

i

1

i

2

n

1

i

2

i

3

i

2

2

i

1

i

1

1)

(

))

a

x

a

x

(a

(y

2

δa

δ

)

x

(

))

a

x

a

x

(a

(y

2

δa

δ

)

x

(

))

a

x

a

x

(a

(y

2

δa

δ

ϕ

ϕ

ϕ

Ponieważ warunkiem istnienia minimum jest

0

δa

δ

l

=

ϕ

otrzymujemy układ równań w postaci:



















=

−

⋅

−

−

−

=

−

⋅

−

−

−

=

−

⋅

−

−

−

∑

∑

∑

=

=

=

n

1

i

3

i

2

2

i

1

i

n

1

i

i

3

i

2

2

i

1

i

n

1

i

2

i

3

i

2

2

i

1

i

0

1)]

(

)

a

x

a

x

a

[(y

2

0

)]

x

(

)

a

x

a

x

a

[(y

2

0

)]

x

(

)

a

x

a

x

a

[(y

2



















=

+

+

+

=

+

+

+

=

+

+

+

∑

∑

∑

=

=

=

n

1

i

3

i

2

2

i

1

i

n

1

i

i

3

2

i

2

3

i

1

i

i

n

1

i

2

i

3

3

i

2

4

i

1

2

i

i

0

)

a

x

a

x

a

(-y

2

0

)

x

a

x

a

x

a

x

(-y

2

0

)

x

a

x

a

x

a

x

(-y

2



















=

+

+

=

⋅

+

⋅

+

⋅

=

⋅

+

⋅

+

⋅

∑

∑

∑

∑

∑

∑

=

=

=

=

=

=

n

1

i

i

3

i

2

2

i

1

n

1

i

i

i

i

3

i

i

2

i

2

i

1

n

1

i

2

i

i

2

i

3

2

i

i

2

2

i

2

i

1

y

)

a

x

a

x

(a

x

y

)

x

a

x

x

a

x

x

(a

x

y

)

x

a

x

x

a

x

x

(a

n

i

n

i

n

i

1

1

1



















=

+

+

=

+

⋅

+

⋅

=

+

⋅

+

⋅

∑

∑

∑

∑

∑

∑

∑

∑

∑

∑

∑

=

=

=

=

=

=

=

=

=

=

=

n

i

n

i

n

i

n

i

n

i

n

i

n

i

n

i

n

i

n

i

n

i

1

1

1

1

1

1

1

1

1

1

1

i

3

i

2

2

i

1

i

i

i

3

i

i

2

i

2

i

1

2

i

i

2

i

3

2

i

i

2

2

i

2

i

1

y

a

x

a

x

a

x

y

x

a

x

x

a

x

x

a

x

y

x

a

x

x

a

x

x

a

TECHNOLOGIE INFORMACYJNE, Sem.1

Interpolacja i Aproksymacja

5

co zapisać można w postaci macierzowej

A × X = B

∑

∑

∑

∑

∑

∑

∑

∑

∑

∑

∑

=

=

=

=

=

=

=

=

=

=

=

=

×

n

1

i

i

n

1

i

i

i

n

1

i

2

i

i

3

2

1

n

1

i

i

n

1

i

2

i

n

1

i

i

n

1

i

2

i

n

1

i

3

i

n

1

i

2

i

n

1

i

3

i

n

1

i

4

i

y

x

y

x

y

a

a

a

1

x

x

x

x

x

x

x

x

Rozwiązanie sprowadza się do wykonania operacji matematycznej

A

T

× A × X = A

T

× B

gdzie:

A

T

- jest macierzą transponowaną (tj. odwrotna – powstająca przez przestawienie

wieszy z kolumnami) do macierzy A przy czym A

T

× A = 1, a zatem:

X = A

T

× 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.