Metody numeryczne

Instytut Sterowania i Systemów Informatycznych

Wydział Elektrotechniki, Informatyki i Telekomunikacji

Uniwersytet Zielonogórski

Elektrotechnika stacjonarne-dzienne pierwszego stopnia z tyt. inżyniera

Informatyka stacjonarne-dzienne drugiego stopnia z tyt. magistra inżyniera

Interpolacja

Laboratorium, prowadzący: mgr inż. Błażej Cichy

Rok akademicki 2010/2011

1

Kilka uwag teoretycznych

1.1

Interpolacja liniowa

Jest to najprostszy przypadek interpolacji. Poniższy wzór został tak skonstruowany

aby w punktach węzłowych wartość błędu była równa zero:

y = P (x) = y

0

+ (y

1

− y

0

)

x − x

0

x

1

− x

0

(1)

Wzór ten jest wygodniej zapisywać w następującej postaci:

y = P

1

(x) = y

0

x − x

1

x

0

− x

1

+ y

1

x − x

0

x

1

− x

0

(2)

1.2

Wielomian Lagrange

Wielomian Lagrange stanowi uogólnienia interpolacji liniowej dla wielomianów dowol-

nego stopnia. Zapisujemy go w następujący sposób:

P

N

(x) =

N

X

k=0

y

k

L

N,k

(x)

(3)

Gdzie symbol L

N,k

(x) oznacza współczynniki wielomianu dla podanych węzłów:

L

N,k

(x) =

(x − x

0

) . . . (x − x

k−1

)(x − x

k+1

) . . . (x − x

N

)

(x

k

− x

0

) . . . (x

k

− x

k−1

)(x

k

− x

k+1

) . . . (x

k

− x

N

)

(4)

Możemy to zapisać w przy zastosowaniu symbolu produktowego, co skróci zapis:

L

N,k

(x) =

Q

N
j=0,j6=k

(x − x

j

)

Q

N
j=0,j6=k

(x

k

− x

j

)

(5)

1

Interpolacja

2

1.3

Oszacowanie błędu interpolacji

Interesuje nasz błąd ε dla punktów leżących wewnątrz przedziału określamy w nastę-

pujący sposób:

ε(x) = f (x) − P

N

(x)

(6)

Bowiem wartość błędu dla węzłów wynosi zero. Możemy skorzystać z następującej zależ-
ności:

|f (x) − P

N

(x)| ≤

M

n+1

(n + 1)!

|ω

x

(x)|

(7)

Symbolem M

n+1

oznaczamy kres górny (n + 1)-szej pochodnej interpolowanej funkcji:

M

n+1

= sup

x∈ha,bi

|f

(n+1)

(x)|

(8)

Natomiast pod symbolem ω

x

(x) ukrywa się następujące wyrażenie:

ω

n

(x) = (x − x

0

)(x − x

1

) . . . (x − x

n

)

(9)

1.4

Wzór interpolacyjny Newtona

Wielomian interpolacyjny jest dany następującym wzorem:

P

N

(x) = a

0

+ a

1

(x − x

0

) + . . . + a

N

(x − x

0

)(x − x

1

) . . . (x − x

N

1

)

(10)

Przez a

k

oznaczamy ilorazy różnicowe funkcji: a

k

= f [x

0

, x

1

, ..., a

k

], gdzie k = 0, 1, 2, . . . , N .

Wzory na iloraz różnicowy funkcji dwóch wartości. czyli iloraz różnicowy pierwszego

rzędu są następująco zdefiniowane:

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

W podobny sposób określone są ilorazy drugiego rzędu:

f (x

0

; x

1

; x

2

) =

f (x

1

; x

2

) − f (x

0

; x

1

)

x

2

− x

0

. . . . . . . . . . . . . . . . . .

f (x

n−2

; x

n−1

; x

n

) =

f (x

n−1

; x

n

) − f (x

n−2

; x

n−1

)

x

n

− x

n−2

Ogólnie wzór na dowolny rząd ilorazy różnicowego funkcji jest następujący:

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

(11)

Interpolacja

3

Do wyznaczanie ilorazów różnicowych pomocą może być następująca tabela:

x

i

f (x

i

)

rzędu 1

rzędu 2

rzędu 3

rzędu 4

rzędu 5

x

0

f (x

0

)

f (x

0

; x

1

)

x

1

f (x

1

)

f (x

0

; x

1

; x

2

)

f (x

1

; x

2

)

f (x

0

; x

1

; x

2

; x

3

)

x

2

f (x

2

)

f (x

1

; x

2

; x

3

)

f (x

0

; x

1

; x

2

; x

3

; x

4

)

f (x

2

; x

3

)

f (x

1

; x

2

; x

3

; x

4

)

f (x

0

; x

1

; x

2

; x

3

; x

4

; x

5

)

x

3

f (x

3

)

f (x

2

; x

3

; x

4

)

f (x

1

; x

2

; x

3

; x

4

; x

5

)

f (x

3

; x

4

)

f (x

2

; x

3

; x

4

; x

5

)

x

4

f (x

4

)

f (x

3

; x

4

; x

5

)

f (x

4

; x

5

)

x

5

f (x

5

)

Dla funkcji f (x) = x

3

tablica ilorazów różnic jest następująca:

x

i

f (x

i

) f (x

i

; x

i+1

) f (x

i

; x

i+1

; x

i+2

) f (x

i

; x

i+1

; x

i+2

; x

i+3

) f (x

i

; x

i+1

; x

i+2

; x

i+3

; x

i+4

)

0

0

4

2

8

5

19

1

3

27

10

0

49

1

5

125

14

91

6

216

1.5

Interpolacja za pomocą funkcji sklejanych

Podobnie jak w interpolacji liniowej w podobny sposób można podać wzór na inter-

polację za pomocą funkcji sklejanych za pomocą funkcji liniowych, gdzie d

k

= (y

k+1

−

d

k

)/(x

k+1

− x

k

):

S(x) =











































y

0

+ d

0

(x − x

0

)

x ∈ [x

0

, x

1

]

y

1

+ d

1

(x − x

1

)

x ∈ [x

1

, x

2

]

y

2

+ d

2

(x − x

2

)

x ∈ [x

2

, x

3

]

..

.

..

.

y

k

+ d

k

(x − x

k

)

x ∈ [x

k

, x

k+1

]

..

.

..

.

y

N −1

+ d

N −1

(x − x

N −1

) x ∈ [x

N −1

, x

N

]

Krzywą interpolująca sklejaną nazywamy naturalną krzywą interpolującą (ang. natural

cubic spline) wykorzystującą wielomiany stopnia trzeciego, gdy spełnione są następujące
warunki:

• s(x) jest wielomianem stopnia ≤ 3 na każdym przedziale [x

j−1

, x

j

] dla j = 2, 3, ..., n.

• s(x), s

0

(x),s

00

(x), są ciągłe ma przedziale a ≤ x ≤ b

• s

00

(x

1

) = s

00

(x) = 0

Interpolacja

4

Uzyskanie krzywej dla n węzłów rozpoczniemy od uzyskania wartości współczynników M

j

według następującego wzoru:

x

j

− x

j−1

6

M

j−1

+

x

j+1

− x

j−1

3

M

j

+

x

j+1

− x

j

6

M

j+1

=

y

j+1

− y

j

x

j+1

− x

j

−

y

j

− y

j−1

x

j

− x

j−1

Gdzie j = 2, 3, ..., n − 1, zakładamy również, że M

1

= M

n

= 0. Poszczególne wielomiany

otrzymujemy wykorzystując następującą relację:

s(x) =

(x

j

− x)

3

M

j−1

+ (x − x

j−1

)

3

M

j

6(x

j

− x

j−1

)

+

(x

j

− x)y

j−1

+ (x − x

j−1

)y

j

x

j

− x

j−1

−

1

6

(x

j

− x

j−1

)[(x

j

− x)M

j−1

+ (x − x

j−1

)M

j

]

2

Zadania

1. Stosując interpolację liniową wyznaczyć wielomian interpolacyjny dla funkcji f (x) =

√

x. Określić błąd średniokwadratowy dla otrzymanego wielomianu dla przedziału

h1, 4i.

2. Podać wielomian interpolacyjny (Lagrange’a, Newtona), jeśli dane są następujące

węzły: (−2, 3), (1, 1), (2, −3), (4, 8).

3. Stosując metody Lagrange’a i Newtona zbudować wielomian interpolacyjny 4-go

stopnia dla następującej tablicy:

x

0.0

0.1

0.3

0.6

1.0

f (x) −6.00000 −5.89483 −5.65014 −5.17788 −4.28172

4. Z jaką dokładnością można oszacować wartość

√

2 wielomianem Lagrange dla na-

stępujących punktów węzłowych: 1, 25/16, 16/9, 9/4. Wykorzystać wzór ??.

5. Ocenić dokładność z jaką można obliczyć wartość ln 100.5 przy zastosowaniu wzo-

ru interpolującego Lagrange’a. Dane są następuję wartości węzłowe: ln 100, ln 101,
ln 102, ln 103.

6. Dane sa 3 punkty (1, 0), (3, 3), (4, 1). Znaleźć wielomian posiadający w każdym z

nich punkt ekstremalny lub punkt przegięcia. Jaki jest minimalny stopień takiego
wielomianu?

7. Populacja ludności w USA od 1930 do 1980 wynosiła (w mln):

rok

1930

1940

1950

1960

1970

1980

ludno 123.203 131.669 150.697 179.323 203.212 226.505

Wyznaczyć wielomian interpolacyjny Lagrange’a 5-go stopnia używając powyższych
danych. Wykorzystaj wyznaczony wielomian do oceny populacji w latach 1920, 1965
i 2002. Co można powiedzieć o dokładności oceny populacji w 1965 oraz w 2002
roku?

8. Dla następujących węzłów: (0, 0), (1, 0.5), (2, 2.0), (3, 1.5) wyznaczyć naturalną krzy-

wą sklejaną.

Interpolacja

5

9. Poniższa tabela prezentuje wartości temperatury (w stopniach Fahrenheita) w Los

Angeles. Wyznaczyć naturalną krzywą składaną i narysować jej wykres:

Czas Stopnie

Czas Stopnie

1

58

7

57

2

58

8

58

3

58

9

60

4

58

10

64

5

57

11

67

6

57

12

68

Literatura

[1] Bj¨

arck Ake i Dahlquist Germund. Metody numeryczne. PWN, Warszawa, 1987.

[2] Jerzy Brzózka i Lech Dorobczyński.

Programowanie w MATLAB.

Warszawa,

Wydanie I, 1998.

[3] Zenon Fortuna, Bohdan Macukow i Janusz Wąsowski. Metody numeryczne. WNT,

Warszawa, 1995.

[4] Jerzy Klamka i in. Metody numeryczne. Politechnika Śląska, Gliwice, 1998.

[5] David Kincaid i Ward Cheney. Analiza numeryczna. WNT, Warszawa, 2006.

[6] Anna Kamińska i Beata Pańczyk. Matlab. Ćwiczenia z . . . , Przykłady i zadania.

Warszawa, Wydanie I, 2002.

[7] Wanat Kazimierz. Algorytmy numeryczne. Helion, Gliwice, 1994.

[8] Bogumiła Mrozek i Zbigniew Mrozek. MATLAB i Simulink. Poradnik użytkownika.

Wydanie II, 2004.

[9] Jurij Povstenko.

Wprowadzenie do metod numerycznych.

Akademicka Oficyna

Wydawnicza EXIT, Warszawa, Wydanie drugie poprawione i uzupełnione, 2005.

[10] Rudra Pratap. MATLAB 7 dla naukowców i inżynierów. PWN, 2007.

[11] Wiesława Regel. Wykresy i obiekty graficzne w MATLAB. Warszawa, Wydanie I,

2003.

[12] Marcin Stachurski. Metody numeryczne w programie Matlab. Warszawa, Wydanie I,

2003.