1

Metody numeryczne, 3 INF,

Szczecin WI, Anna Barcz

Zagadnienia z INTERPOLACJI

Ogólne sformułowanie zadania interpolacji.
Interpolacja za pomocą wielomianów. Twierdzenie o istnieniu wielomianu

interpolacyjnego.
Zastosowanie macierzy Vandermonda (wady i zalety)
Wielomian Lagrangea i Newtona.
Szacowanie błędu.
Zjawisko Rungego.
Zbieżność zadań interpolacyjnych.
Interpolacja przy pomocy funkcji trygonometrycznych i sklejanych –

informacje ogólne.

2

Metody numeryczne, 3 INF,

Szczecin WI, Anna Barcz

Przybliżanie funkcji – ZADANIE INTERPOLACJI

Zadanie interpolacji:

wyznacz funkcję g(x), która w punktach x

i

, tzw. węzłach, przyjmuje

ustalone wartości y

i

, czyli spełnia warunek interpolacji

g

x

i

= y

i

, 0

in.

Pojęcia do zapamiętania:
✔ węzły

✔ funkcja interpolująca

3

Metody numeryczne, 3 INF,

Szczecin WI, Anna Barcz

Przybliżanie funkcji – ZADANIE INTERPOLACJI

Funkcje interpolujące:

✔ wielomiany algebraiczne,
✔ wielomiany trygonometryczne,
✔ wielomiany ortogonalne,
✔ funkcje sklejane.

4

Metody numeryczne, 3 INF,

Szczecin WI, Anna Barcz

Przybliżanie funkcji – ZADANIE INTERPOLACJI

Postacie wielomianu algebraicznego

✔ postać naturalna (rozwinięcie potęgowe)

w

 x=

∑

k

=0

n

a

k

x

k

obliczanie całek, pochodnych i działań na wielomianach

5

Metody numeryczne, 3 INF,

Szczecin WI, Anna Barcz

Przybliżanie funkcji – ZADANIE INTERPOLACJI

Postacie wielomianu algebraicznego

✔ postać Newtona

w

 x=

∑

k

=0

n

b

k

p

k

 x

p

0

 x=

df

1

p

k

x=

df

x−x

0

 x−x

1

x−x

k

−1



gdzie:

dla k

=1,2 ,,n

6

Metody numeryczne, 3 INF,

Szczecin WI, Anna Barcz

INTERPOLACJA WIELOMIANOWA

Dana jest funkcja f(x) i wielomian

Zadanie interpolacji – znaleźć wielomian p możliwie najniższego

stopnia taki, że dla danych n+1 punktów (x

i

, y

i

) jest

w

 x =

∑

k

= 0

n

b

k

p

k

 x 

p

0

 x =

df

1

Mówimy wtedy, że

wielomian p interpoluje wartości y

k

w węzłach x

k

.

7

Metody numeryczne, 3 INF,

Szczecin WI, Anna Barcz

INTERPOLACJA WIELOMIANOWA

Twierdzenie

Istnieje dokładnie jeden wielomian interpolacyjny

stopnia co najwyżej n (n

≥

0), który

w punktach x

0

, x

1

, ... , x

n

przyjmuje wartości y

0

, y

1

, ..., y

n

.

8

Metody numeryczne, 3 INF,

Szczecin WI, Anna Barcz

INTERPOLACJA WIELOMIANOWA

W postaci macierzowej

[

1

x

0

x

0

2

x

0

3

 x

0

n

1

x

1

x

1

2

x

1

3

 x

1

n

     

1

x

n

x

n

2

x

n

3

 x

n

n

]

⋅

[

a

0

a

1



a

n

]

=

[

y

0

y

1



y

n

]

V – macierz Vandermonde'a,

V

⋅A=Y

9

Metody numeryczne, 3 INF,

Szczecin WI, Anna Barcz

INTERPOLACJA WIELOMIANOWA

Jeżeli założymy, że dla to

x

i

≠x

j

i

≠ j

det

V =

∏

0

 jin

x

i

−x

j

≠0

Układ równań ma dokładnie jedno rozwiązanie.

10

Metody numeryczne, 3 INF,

Szczecin WI, Anna Barcz

INTERPOLACJA WIELOMIANOWA

Wzór interpolacyjny Lagrange'a

[

1

x

0

x

0

2

x

0

3



x

0

n

1

x

1

x

1

2

x

1

3



x

1

n













1

x

n

x

n

2

x

n

3



x

n

n

]

⋅

[

a

0

a

1



a

n

]

=

[

y

0

y

1



y

n

]

Wielomian Lagrange'a jest jedynym wielomianem stopnia co najwyżej n.
W sposób jawny zależy liniowo od zadanych wartości funkcji y

j

.

11

Metody numeryczne, 3 INF,

Szczecin WI, Anna Barcz

INTERPOLACJA WIELOMIANOWA

 x

i

=x

i

1

−x

i

Funkcja f(x) jest określona za pomocą węzłów x

0

, x

1

, ... , x

n

i wartości

funkcji w tych węzłach f(x

0

), f(x

1

), ... , f(x

n

). Dodatkowo

dla i różnice nie są na ogół stałe.

x

i

≠x

j

i

≠ j

Wzór interpolacyjny Newtona z ilorazami różnicowymi

12

Metody numeryczne, 3 INF,

Szczecin WI, Anna Barcz

INTERPOLACJA WIELOMIANOWA

f

[ x

0

, x

1

]=

f

 x

1

− f  x

0



x

1

−x

0

f

[ x

1

, x

2

]=

f

 x

2

− f  x

1



x

2

−x

1



f

[ x

n

−1

, x

n

]=

f

 x

n

− f  x

n

−1



x

n

−x

n

−1

Ilorazy różnicowe pierwszego rzędu

Wzór interpolacyjny Newtona z ilorazami różnicowymi

13

Metody numeryczne, 3 INF,

Szczecin WI, Anna Barcz

INTERPOLACJA WIELOMIANOWA

f

[ x

i

, x

i

1

,

, x

i

n

]=

f

[ x

i

1

, x

i

2

,

, x

i

n

]− f [ x

i

, x

i

1

,

, x

i

n−1

]

x

i

n

−x

i

Ilorazy różnicowe rzędu n

n

=1,2 ,

i

=0,1,2 ,

Wzór interpolacyjny Newtona z ilorazami różnicowymi

14

Metody numeryczne, 3 INF,

Szczecin WI, Anna Barcz

INTERPOLACJA WIELOMIANOWA

Wzór interpolacyjny Newtona

Tablica ilorazów różnicowych dla 4 węzłów

x

0

f

 x

0

 f [ x

0

, x

1

] f [ x

0

, x

1

, x

2

] f [ x

0

, x

1

, x

2

, x

3

]

x

1

f

 x

1

 f [ x

1

, x

2

] f [ x

1

, x

2

, x

3

]

x

2

f

x

2

 f [ x

2

, x

3

]

x

3

f

 x

3



Wzór interpolacyjny Newtona z ilorazami różnicowymi

15

Metody numeryczne, 3 INF,

Szczecin WI, Anna Barcz

INTERPOLACJA WIELOMIANOWA

Wzór interpolacyjny Newtona z ilorazami różnicowymi

W

n

x= f  x

0

 f [ x

0

, x

1

]

0

 x f [ x

0

, x

1

, x

2

]

1

 x

 f [ x

0

, x

1

,

, x

n

]

n

−1

 x



0

x=x−x

0





1

x= x−x

0

 x−x

1







n

−1

x= x−x

0

 x−x

1

 x−x

n

−1



16

Metody numeryczne, 3 INF,

Szczecin WI, Anna Barcz

INTERPOLACJA WIELOMIANOWA

Błąd interpolacji wielomianowej

Jeśli , a wielomian interpoluje

wartości funkcji f w n+1 różnych punktach x

0

, x

1

, ... , x

n

przedziału

[a,b], to dla każdego istnieje takie , że

Twierdzenie

f

∈C

n

1

[a ,b]

p

∈

n

x

∈[a ,b]



x

∈a ,b

f

x− px=

1

n1!

f

n1



x



∏

i

=0

n

 x−x

i



17

Metody numeryczne, 3 INF,

Szczecin WI, Anna Barcz

INTERPOLACJA WIELOMIANOWA

Błąd interpolacji wielomianowej

M

n+1

- kres górny modułu (n+1) pochodnej funkcji f na przedziale [a,b]

M

n

1

= sup

x

∈[a , b]

∣ f

n

1

 x∣

∣ f  x− p x∣

1

n1!

M

n

1

∏

i

=0

n

 x−x

i



18

Metody numeryczne, 3 INF,

Szczecin WI, Anna Barcz

INTERPOLACJA ZA POMOCĄ FUNKCJI SKLEJANYCH

Ustalone jest n+1 węzłów t

0

, t

1

, ... , t

n

takich, że t

0

<t

1

<...<t

n

.

Dla danej liczby całkowitej nieujemnej k funkcją sklejaną stopnia k
nazywamy taką funkcję S, która:

w każdym z przedziałów [t

i

, t

i+1

]

jest wielomianem klasy ,

ma ciągłą (k-1)-szą pochodną w przedziale [t

0

,t

n

].

∏

k

w

 x =

∑

k

=0

n

a

k

x

k

19

Metody numeryczne, 3 INF,

Szczecin WI, Anna Barcz

INTERPOLACJA ZA POMOCĄ FUNKCJI SKLEJANYCH

Funkcję sklejaną stopnia 2k-1 z węzłami t

0

<t

1

<...<t

n

nazywamy

naturalną funkcją sklejaną, jeśli w przedziałach i
dana jest wielomianami stopnia k-1.

Definicja

−∞ ,t

0

 t

n

,

∞

20

Metody numeryczne, 3 INF,

Szczecin WI, Anna Barcz

INTERPOLACJA ZA POMOCĄ FUNKCJI SKLEJANYCH

Jeżeli węzły t

i

są różne dla i=0,1,...,n oraz , to dla

dowolnych wartości y

i

istnieje dokładnie jedna naturalna funkcja

sklejana interpolująca punkty (x

i

, y

i

), tzn.

taka, że dla i=0,1,..., n.

Twierdzenie

1

mn1

S

∈N

2m

−1

t

0,

t

1,

,t

n



S

 x

i

= y

i

1

mn1