450 2

450

12. Rozwiązania zadań

p(x) jcsi ostatnią wartością s. Ten sposób wymaga 2{n+ !) mnożeń i /i-h dodaw -Z (1.3.1) wynika jednak, że schemat Homera wymaga tylko n mnożeń i n dodawań ^

3. (a) Należy przestudiować dowód twierdzenia 1.3.1 i zauważyć, że

p'(z)= lim

ł-*i

ppt)-p(z) X -z

(b) Z twierdzenia Taylora

■    ®**V z)

p(.r)= £ c_i(r)(x-2)ⁱ1    c,(z) = __ .

i-0    • !

Następnie dowodzimy indukcyjnie, że

9»(x. z| = ^

1=0

Przyjmując tu jr=z, otrzymuje się, że r)=r₄(z).

4. Niech p(x)=.r⁴ + 2x³ — 3x² + 2. Schemat Homera dla z-2 daje wiersz I 4 5 10 22, gdzie 22=p(2) i (zob. twierdzenie 1.3.1 i zadanie 3)

1 • x³+4x²+5x+ I0=[(x*+2x^j—3x² -0-x+2)-22]/(x-2).

Używając znów schematu Homera (dla tego nowego wielomianu o współczynnikach £<).. otrzymujemy nowy wiersz I 6 7 44, gdzie 44=p' (2)/l! (z zadania 3) i podobnie dalej 33= =p"(2)/2\, IOs=p"'(2)/3!, I = p^<A,l2)/4!. Ponieważ

®'(2)    p^iA\2)

P (x) = /* (2)+(x — 2) -t-... + —(x — 2)⁴,

więc ply + 2)=.v* + IOy³ 4-33>’³ — 44y4-22.

5.    Fortran:    Algol:

S=0.    s: = 0;

DO 10 1=1, N    for i:=l step I ttnfil n do

10 S=S + A(I)x B(l)    j:=j+a[/]xó[i]

6.    (a) Algorytm jest oczywiście poprawny dla n = l. Załóżmy jego poprawność da wszystkich ułamków łańcuchowych o długości A', tzn. dla n^N. Dla ułamka łańcuchowego o A + l elementach algorytm daje

d,v_+l = ó_w-,. d_s =*b_>-ra_N+tfd_ll+1.

Ponieważ taki ułamek można uznać za ułamek łańcuchowy o N elementach z

b‘_M=b_s + aN+xłb_K+_t,

więc twierdzenie jcsL prawdziwe.

(b) DIMENSfON A(10), B(I0)

READ(S,90I) N N1 = N + I

READ(5. 902)    1=1, NJ), (A{1), 1 = 2, NI)