Wydział FTIMS – Instytut Matematyki Politechniki Łódzkiej

Wst p do metod numerycznych – wykłady – matematyka

1

Posta Newtona wielomianu.

Niech

N

n

∈ ,

1

1

0

,

...

,

,

−

n

x

x

x

b d ustalonymi liczbami rzeczywistymi oraz k

∈P(n)∪{0}. Definiujemy

funkcje

R

R

p

k

→

:

nast puj co:

R

x

∈

∀

−

⋅

⋅

−

−

=

∈

∀

=

−

)

(

...

)

)(

(

)

(

)

(

1

)

(

1

1

0

0

k

k

x

x

x

x

x

x

x

p

n

P

k

x

p

.

Łatwo wykazujemy, e wielomiany

k

p zdefiniowane powy ej, tworz baz w przestrzeni liniowej

wielomianów stopnia co najwy ej n, czyli w przestrzeni R

n

[x]. Rozwa my dowolny wielomian stopnia n

zmiennej rzeczywistej x, zapisany w postaci naturalnej

=

⋅

=

∈

∀

n

k

k

k

x

a

x

w

R

x

0

)

(

. Oczywistym jest, e

].

[x

R

w

n

∈

Zatem istnieje dokładnie jeden ci g {b

k

}

k n

taki, e

=

⋅

=

∈

∀

n

k

k

k

x

p

b

x

w

R

x

0

).

(

)

(

Otrzymane

przedstawienie nazywane jest

postaci Newtona wielomianu w. Wielomian ten mo na zapisa w innej

postaci, wygodniejszej do oblicze numerycznych jego warto ci w punkcie x

∈R.

.

)

(

}

...

)

](

)

(

......[

{

)

(

0

0

1

2

1

1

b

x

x

b

x

x

b

x

x

b

x

w

n

n

n

n

+

−

⋅

+

+

−

+

−

=

−

−

−

Zdefiniujmy rekurencyjnie wielomiany:

(*)

.

0

...,

,

2

,

1

dla

)

(

1

−

−

=

+

−

⋅

=

=

+

n

n

i

b

x

x

w

w

b

w

i

i

i

i

n

n

Wówczas

.

)

(

0

w

x

w

=

Z zale no ci (*) wynika tzw.

Uogólniony algorytm Hornera obliczania warto ci

wielomianu zapisanego w postaci Newtona. Algorytm ten mo emy zapisa w postaci:

].

[

])

[

(

:

0

do

1

od

]

[

:

i

b

i

x

x

w

w

n

i

n

b

w

+

−

∗

=

−

=

=

Mo na pokaza , e algorytm ten jest numerycznie poprawny.

Wyznaczanie współczynników wielomianu w ró nych postaciach.

Znaj c współczynniki

k

b wielomianu w postaci Newtona, mo na wyznaczy współczynniki

k

a dla jego

postaci naturalnej. W tym celu ka dy z wielomianów

i

w postaci (*), zapiszemy w postaci naturalnej.

.

0

...,

,

1

,

dla

−

=

⋅

=

=

−

n

n

i

x

a

w

n

i

k

i

k

i

i

k

St d i z (*) otrzymujemy zale no ci:

n

n

n

b

a

=

+

=

+

=

+

=

⋅

−

+

⋅

⋅

−

+

⋅

=

+

⋅

⋅

−

⋅

=

+

+

−

−

+

+

+

−

+

−

−

+

−

+

n

i

i

i

i

n

i

k

i

i

k

i

k

i

n

i

n

n

i

i

i

k

i

k

i

k

i

k

i

i

k

i

k

i

k

x

a

b

x

x

a

a

x

a

b

x

x

a

x

a

w

1

1

).

(

)

(

1

1

1

1

1

1

1

1

1

1

1

Wstawiaj c te zale no ci do postaci wielomianów w

i

, a nast pnie porównuj c współczynniki przy tych

samych pot gach zmiennej x otrzymamy, e

,

n

n

n

b

a

=

,

1

1

i

i

i

i

i

i

x

a

b

a

⋅

−

=

+

+

.

1

...,

,

2

,

1

dla

1

1

1

−

+

+

=

⋅

−

=

+

+

+

n

i

i

k

x

a

a

a

i

i

k

i

k

i

k

Z tych zale no ci mo emy wywnioskowa , e szukane warto ci współczynników a

k

wielomianu w s

równe

0

k

a

dla k = 0, 1, …, n ( bo w(x)=w

0

(x) ).

Algorytm przej cia od postaci Newtona do postaci naturalnej ma posta :

a[n]=b[n],

dla i=n-1 do 0 wykonuj

Wydział FTIMS – Instytut Matematyki Politechniki Łódzkiej

Wst p do metod numerycznych – wykłady – matematyka

2

xi = x[i]

a[i] = b[i]

dla k=i do n-1 wykonuj

a[k] = a[k]−xi a[k+1].

Koszt tego algorytmu, to

2

)

1

(

+

n

n

mno e i tyle samo odejmowa . Mo na pokaza , e algorytm ten jest

numerycznie stabilny.

Uwagi o innych przedstawieniach wielomianów.

W obliczeniach numerycznych u ywa si równie przedstawienia wielomianów w postaci kombinacji

liniowej tzw.

wielomianów ortogonalnych. Przykładem takich wielomianów s wielomiany Czebyszewa

oznaczane symbolem T

n

. Wielomiany te s okre lone nast puj cymi zale no ciami:

(*)

R

x

∈

∀

.....

,

3

,

2

dla

)

(

)

(

2

)

(

)

(

1

)

(

2

1

1

0

=

−

⋅

=

=

=

−

−

k

x

T

x

T

x

x

T

x

x

T

x

T

k

k

k

Wielomiany te tworz baz w przestrzeni wszystkich wielomianów zmiennej rzeczywistej R[x]. Równie
dla dowolnego n

∈N, układ T

0

, T

1

, …, T

n

tworzy baz w przestrzeni R

n

[x]. Zatem dowolny wielomian

rzeczywisty stopnia n mo na zapisa jako kombinacj liniow wielomianów Czebyszewa. Oczywi cie

współczynniki tej kombinacji s wyznaczone w sposób jednoznaczny:

=

⋅

=

∈

∀

n

k

k

k

x

T

c

x

w

R

x

0

).

(

)

(

Zaproponowany przez Clenshawa algorytm obliczania warto ci wielomianu w, w punkcie x, polega na

wykorzystaniu zale no ci (*). Po rozpisaniu otrzymamy, e

,

~

~

)

(

2

0

1

c

c

x

c

x

w

−

+

⋅

=

gdzie

.

1

,

...

,

1

,

dla

~

~

2

~

2

1

−

=

−

+

=

+

+

n

n

k

c

c

c

x

c

k

k

k

k

oraz

.

0

~

~

1

2

=

=

+

+

n

n

c

c

Algorytm ten ma posta :

wykonaj

do

n

k

dla

x

dwax

c

c

1

2

0

2

1

=

∗

=

=

=

0

1

1

2

],

[

2

1

0

c

c

c

c

k

c

c

c

dwax

c

=

=

+

−

∗

=

.

2

]

0

[

1

c

c

c

x

w

−

+

∗

=

Mo na post puj c podobnie obliczy współczynniki postaci normalnej wielomianu w. (notatki str. 10e-f)

Obliczanie warto ci wielomianu zmiennej zespolonej.

Rozwa my wielomian stopnia n

∈N

0

zmiennej zespolonej

iy

x

z

+

=

, o współczynnikach zespolonych

k

k

ib

a

+

, k=0, 1, …, n. Wielomian ten ma posta

k

n

k

k

iy

x

ib

a

z

F

k

)

(

)

(

)

(

0

+

⋅

+

=

=

i jest w sposób

jednoznaczny okre lony przy pomocy dwóch ci gów współczynników

n

a

a

a

,

...

,

,

1

0

oraz

n

b

b

b

,

...

,

,

1

0

.

Wprowad my oznaczenia: u = Re F(z), v = Im F(z). Zapiszmy wielomian F(z) w postaci:

.

)

(

}

...

)

(

]

)

(

)

...[(

{

)

(

0

0

1

1

1

1

b

i

a

y

i

x

b

i

a

y

i

x

b

i

a

y

i

x

b

i

a

v

i

u

z

F

n

n

n

n

⋅

+

+

⋅

+

⋅

⋅

+

+

⋅

+

⋅

⋅

+

+

⋅

+

⋅

⋅

+

=

⋅

+

=

−

−

Wydział FTIMS – Instytut Matematyki Politechniki Łódzkiej

Wst p do metod numerycznych – wykłady – matematyka

3

Niech

.

0

,

...

,

2

,

1

dla

:

,

:

1

−

−

=

⋅

+

⋅

+

=

⋅

+

=

⋅

+

=

⋅

+

=

+

n

n

k

f

z

b

i

a

v

i

u

f

b

i

a

v

i

u

f

k

k

k

k

k

k

n

n

n

n

n

Wówczas

.

)

(

0

0

0

v

i

u

f

z

F

⋅

+

=

=

Zauwa my, e

,

,

n

n

n

n

b

v

a

u

=

=

oraz dla

0

,

1

...,

,

2

,

1

−

−

=

n

n

k

mamy, e

=

⋅

+

⋅

⋅

+

+

⋅

+

=

⋅

+

+

+

)

(

)

(

1

1

k

k

k

k

k

k

v

i

u

y

i

x

b

i

a

v

i

u

).

(

1

1

1

1

+

+

+

+

⋅

+

⋅

+

⋅

+

⋅

−

⋅

+

k

k

k

k

k

k

v

x

u

y

b

i

v

y

u

x

a

Rozpisuj c cz

rzeczywist oraz cz

urojon otrzymamy, e

,

,

)

(

,

,

1

1

1

1

+

+

+

+

⋅

+

⋅

+

=

⋅

−

⋅

+

=

∈

∀

=

=

k

k

k

k

k

k

k

k

n

n

n

n

u

y

v

x

b

v

v

y

u

x

a

u

n

P

k

b

v

a

u

.

)

(

,

,

0

0

0

0

v

u

iv

u

z

F

v

v

u

u

+

=

+

=

=

=

Schemat blokowy notatki str. 11.

Algorytm oblicze :

Dane: n – całkowite; a[k], b[k] – wektory; x, y – rzeczywiste;

i:=n

u:=a[n]

v:=b[n]

je li i>0 wykonuj

re:=x

⋅u−y⋅v

im:=x

⋅v+y⋅u

u:=re+a[i

−1]

v:=im+b[i

−1]

i:=i

−1

drukuj F(x+iy)=u+iv.