20. Wielomiany i ich własności - Wstęp do matematyki 06-DPMALI0

Treści kształcenia. Wielomiany: dzielenie pisemne wielomianów, schemat Hornera i jego zastosowanie do wyliczania wartości w punkcie i dzielenia przez dwumian, schemat Hornera jako algorytm - zapis w pseudokodzie. Pierwiastek wielomianu i jego krotność, wzory Viete’a i ich wykorzystanie w obliczeniach komputerowych (zamiast wzorów na oba pierwiastki - “zero maszynowe”).

Efekty kształcenia. Student potrafi wykonywać podstawowe operacje na wielomianach, w szczególności niezbędne w informatyce (np. schemat Hornera). Potrafi wykorzystać wzory Vieta.

Podczas zajęć 20 przypomnimy sobie i nieco rozszerzymy informacje o wielomianach i ich znaczeniu w informatyce. Pełnią one tam bardzo ważną rolę z prostego powodu: wartość wielomianu można obliczyć wykonując tylko mnożenie i dodawanie, możemy to zatem zrobić za pomocą komputera. Później na analizie matematycznej dowiemy się, że bardzo wiele funkcji można ,,przybliżać’’ wielomianami i ponadto kontrolować przy tym błąd, jaki popełniamy podczas takiego przybliżania.

Wielomiany¶

Definicja wielomianu jednej zmiennej rzeczywistej¶

Funkcję $p\colon\mathbb{R}\to\mathbb{R}$ nazywamy wielomianem jednej zmiennej rzeczywistej (w skrócie wielomianem), gdy istnieją $n\geq 0$ oraz $a_0,a_1,\ldots,a_n\in\mathbb{R}$ takie, że

p(x)=a_nx^n+a_{n-1}x^{n-1}+\ldots+a_1x+a_0 \textrm{ dla wszystkich }x\in\mathbb{R}.

Liczby $a_0,a_1,\ldots, a_{n-1}, a_n$ nazywamy współczynnikami wielomianu $p$ .
Dwa wielomiany uznajemy za równe wtedy i tylko wtedy, gdy są one równe jako funkcje (co sprowadza się do tego, że mają takie same współczynniki).

Uwaga:

Wielomiany to funkcje o pewnej szczególnej postaci, możemy zatem wykonywać na nich wszystkie operacje, jakie umiemy wykonywać na funkcjach. W szczególności wielomiany możemy do siebie dodawać i przez siebie mnożyć. Łatwo jest się przekonać, że suma i iloczyn dwóch wielomianów (a nawet ich złożenie) jest również wielomianem.

Definicja stopnia wielomianu¶

Niech $p$ będzie wielomianem

p(x)=a_nx^n+a_{n-1}x^{n-1}+\ldots+a_1x+a_0.

Jeśli $p(x)=0$ dla wszystkich $x\in\mathbb{R}$ , to $p$ nazywamy wielomianem zerowym i mówimy, że jego stopień jest równy $-\infty$ .
Jeśli $p$ nie jest wielomianem zerowym, to największą liczbę $i$ taką, że $a_i\not=0$ , nazywamy stopniem tego wielomianu.
Stopień wielomianu $p$ będziemy oznaczać symbolem $\operatorname{deg}(p).$

Uwaga:

Napis $-\infty$ czytamy jako minus nieskończoność. Umawiamy się, że dla dowolnej liczby rzeczywistej $c$ mamy, że $-\infty$ jest mniejsze od $c$ i piszemy $-\infty<c$ .

Przykład: działania na wielomianach¶

Niech $p$ i $q$ będą dane wzorami:

p(x)=x^2+x+2,\quad q(x)=x^3.

Wtedy $\operatorname{deg}(p)=2$ i $\operatorname{deg}(q)=3$ .

Ponadto wielomian $p+q$ dany jest wzorem

(p+q)(x)= x^3+x^2+x+2

a wielomian $p\cdot q$ dany jest wzorem

(p\cdot q)(x)=x^5+x^4+2x^3.

Przykład: uwaga na stopień!¶

Niech $p$ oraz $q$ będą wielomianami. Wtedy

\operatorname{deg}(p+q)\leq\max\{ \operatorname{deg}(p), \operatorname{deg}(q)\}.

Może się ponadto zdarzyć, że nierówność ta jest ostra. Istotnie, jeśli $p(x)=x^2+1$ i $q(x)=-x^2$ , to $\operatorname{deg}(p+q)=0$ .

Wielomiany stopnia mniejszego bądź równego niż jeden¶

Definicja

Funkcję $f\colon\mathbb{R}\to\mathbb{R}$ nazywamy funkcją liniową (dwumianem), gdy istnieją $a,b\in\mathbb{R}$ takie, że

f(x)=ax+b \textrm{ dla wszystkich }x\in\mathbb{R}.

Liczbę $a$ nazywamy współczynnikiem kierunkowym funkcji liniowej $f$ .

Uwaga:

Wykresem funkcji liniowej jest prosta. Poniżej znajduje się kod pozwalający narysować jej wykres w zależności od parametrów $a$ oraz $b$ . Warto zauważyć, że wykres funkcji liniowej $f(x)=ax+b$ zawsze przechodzi przez punkt $(0,b)$ , oraz że dla każdego $x$ mamy

f(x+1)-f(x)=a(x+1)+b-(ax+b)=a.

Zatem zwiększając argument funkcji liniowej o 1 zmieniamy jej wartość o $a$ . Obserwacje te pozwalają szybko rysować wykresy funkcji liniowej.

import matplotlib.pyplot as plt
import numpy as np
a = 2
b = 1
fig = plt.figure()
ax = fig.add_subplot(1, 1, 1)
x = np.linspace(-5,5,100)
ax.spines['left'].set_position('zero')
ax.spines['bottom'].set_position('zero')
ax.spines['right'].set_color('none')
ax.spines['top'].set_color('none')
ax.xaxis.set_ticks_position('bottom')
ax.yaxis.set_ticks_position('left')
plt.plot(x, a*x+b,'--r', label='y=ax+b')
plt.show()

Miejsca zerowe funkcji liniowej¶

Fakt

Niech $f\colon\mathbb{R}\to\mathbb{R}$ będzie funkcją liniową daną wzorem $f(x)=ax+b$ .
Jeśli $a=0$ oraz $b=0$ , to każda liczba rzeczywista jest miejscem zerowym funkcji $f$ .

Jeśli $a=0$ oraz $b\not=0$ , to $f$ nie ma miejsc zerowych.

Jeśli $a\not=0$ , to liczba $-\frac b a$ jest jedynym miejscem zerowym funkcji $f$ .

Przykłady do samodzielnego rozwiązania¶

Wyznacz wzór funkcji liniowej $f$ , której wykres przechodzi przez punkty $(0,4)$ i $(2,2)$ .

Wyznacz miejsca zerowe funkcji $f(x)=2x+3$ .

Liczba 2 jest jedynym miejscem zerowym funkcji liniowej $f$ , której wykres przechodzi przez punkt $(0,2)$ . Wyznacz jej wzór.

Wielomiany stopnia dwa¶

Definicja

Funkcję $f\colon\mathbb{R}\to\mathbb{R}$ nazywamy funkcją kwadratową (lub trójmianem kwadratowym), gdy istnieje $0\not=a\in\mathbb{R}$ oraz $b,c\in\mathbb{R}$ takie, że

f(x)=ax^2+bx+c \textrm{ dla wszystkich }x\in\mathbb{R}.

import matplotlib.pyplot as plt
import numpy as np
a = 1
b = 0
c = 0
fig = plt.figure()
ax = fig.add_subplot(1, 1, 1)
x = np.linspace(-5,5,100)
ax.spines['left'].set_position('zero')
ax.spines['bottom'].set_position('zero')
ax.spines['right'].set_color('none')
ax.spines['top'].set_color('none')
ax.xaxis.set_ticks_position('bottom')
ax.yaxis.set_ticks_position('left')
plt.plot(x, a*x**2+b*x+c,'--r')
plt.show()

Miejsca zerowe funkcji kwadratowej¶

Fakt:

Niech $f\colon\mathbb{R}\to\mathbb{R}$ będzie funkcją daną wzorem $f(x)=ax^2+bx+c$ , gdzie $a\not=0$ . Niech

\Delta=b^2-4ac.

Jeśli $\Delta<0$ , to funkcja $f$ nie ma miejsca zerowego.
Jeśli $\Delta=0$ , to funkcja $f$ posiada dokładnie jedno miejsce zerowe, które wyraża się wzorem $x_0=-\frac{b}{2a}$ .
Jeśli $\Delta>0$ , to funkcja $f$ posiada dokładnie dwa miejsca zerowe $x_1$ i $x_2$ , które wyrażają się wzorami:

x_1=\frac{-b-\sqrt{\Delta}}{2a}, \quad x_2=\frac{-b+\sqrt{\Delta}}{2a}.

Uwagi:

Liczbę $\Delta$ nazywamy wyróżnikiem trójmianu kwadratowego $ax^2+bx+c$ .
Jeśli $\Delta=0$ , to

f(x)=ax^2+bx+c=a\left(x-x_0\right)^2.

Jeśli $\Delta>0$ , to

f(x)=ax^2+bx+c=a(x-x_1)(x-x_2).

Jest to tak zwana postać iloczynowa funkcji kwadratowej.

Mamy

f(x)=ax^2+bx+c=a(x^2+\frac b ax+\frac c a)= a\left(x+\frac{b}{2a}\right)^2-\frac{\Delta}{4a}.

Jest to tak zwana postać wierzchołkowa funkcji kwadratowej.

Przykład¶

Niech $f(x)=x^2-6x+8$ . Miejscami zerowymi tej funkcji są 2 oraz 4. Zatem $f(x)=(x-2)(x-4)$ . Funkcja $f$ w postaci wierzchołkowej wyraża się wzorem $f(x)=(x-3)^2-1$ .

Przykłady do samodzielnego rozwiązania¶

Wyznacz miejsca zerowe poniższych funkcji i przedstaw je w postaci wierzchołkowej.

$f(x)=x^2-5x+6$ ;
$f(x)=x^2-25$ ;
$f(x)=x^2-3x+8$ ;
$f(x)=x^2-4x+4$ .

Wzory Viete’a:¶

Twierdzenie

Jeżeli funkcja kwadratowa $f(x)=ax^2+bx+c$ posiada dwa miejsca zerowe $x_1$ oraz $x_2$ , to

x_1+x_2=-\frac{b}{a}\text{ oraz }x_1\cdot x_2=\frac{c}{a}.

Zadanie

Nie wyznaczając rozwiązań $x_1,x_2$ równania $x^2-5x+6=0$ oblicz

$x_1^2+x_2^2$ ;
$\frac{1}{x_1}+\frac{1}{x_2}$ .

Znaczenie wzorów Viete’a

Poniżej znajduje się kod, w którym są zaimplementowane wzory na miejsca zerowe funkcji kwadratowej.

import math  
  
# function for finding roots  
def roots(a, b, c):  
  
    dis= b * b - 4 * a * c  # delta
      
    if dis> 0:  
        print(" real and different roots ")  
        print((-b + math.sqrt(dis)) / (2 * a))  
        print((-b - math.sqrt(dis)) / (2 * a))  
  
    elif dis == 0:  
        print(" real and same roots")  
        print(-b / (2 * a))  
  
  
    else:  
        print(" no real roots")  

a = 1
b = 2**28
c = 1
        
roots(a, b, c)

 real and different roots 
0.0
-268435456.0

W przypadku funkcji kwadratowej $f(x)=x^2+2^{28}x+1$ otrzymujemy za jego pomocą dwa miejsca zerowe: 0 oraz -268435456.0. Zauważmy, jak bardzo pomylił się komputer: $f(0)=1$ . Problem bierze się stąd, że

\Delta= 2^{56}-4

i pierwiastek z tej liczby to dla komputera (który oblicza jego przybliżenie), to 2²⁸.

math.sqrt(2**56-4)

268435456.0

2**28

268435456

Aby poprawić dokładność naszego algorytmu, zastosujemy wzory Viete’a. Jedno z miejsc zerowych (to, które jest dalej od zera) obliczamy za pomocą tradycyjnego wzoru, drugie obliczamy stosując wzór Viete’a.

import math  
  
# function for finding roots using Viete'a formulas 
def viete_roots(a, b, c):  
  
    dis= b * b - 4 * a * c  # delta
      
    if dis > 0 and b <= 0 :  
        print(" real and different roots ")  
        x_1 = (-b + math.sqrt(dis)) / (2 * a)
        x_2 = c / (a*x_1)
        print(x_1)
        print(x_2)
        
    elif dis > 0 and b > 0 :  
        print(" real and different roots ")  
        x_1 = (-b - math.sqrt(dis)) / (2 * a)
        x_2 = c / (a*x_1)
        print(x_1)
        print(x_2)
  
    elif dis == 0:  
        print(" real and same roots")  
        print(-b / (2 * a))  
  
  
    else:  
        print(" no real roots")  

a = 1
b = 2**28
c = 1
        
viete_roots(a, b, c)

 real and different roots 
-268435456.0
-3.725290298461914e-09

Tym razem jest lepiej.

x_2 =-3.725290298461914e-09
a*x_2**2+b*x_2+c

0.0

Wielomiany stopnia większego niż dwa.¶

Dla wielomianów stopnia 1 i 2 znamy wzory pozwalające obliczać nam ich miejsca zerowe. Takie wzory istnieją również dla wielomianów stopnia 3 i 4, ale ich stosowanie jest trudne. O wzorach tych można poczytać tutaj: https://pl.wikipedia.org/wiki/Równanie_sześcienne https://pl.wikipedia.org/wiki/Równanie_czwartego_stopnia

Dla wielomianów o stopniu większym bądź równym niż 5 takich wzorów nie ma i być nie może (jest to Twierdzenie Abela - Ruffiniego).

Dzielenie wielomianów¶

Twierdzenie

Niech $p$ oraz $w$ będą wielomianami, przy czym wielomian $w$ nie jest wielomianem zerowym. Istnieją jednoznacznie wyznaczone wielomiany $q$ oraz $r$ takie, że spełnione są warunki

p(x)=w(x)q(x)+r(x) \text{ oraz } \operatorname{deg}(r)<\operatorname{deg}(w).

Wielomian $q$ nazywamy ilorazem, a wielomian $r$ resztą z dzielenia wielomianu $p$ przez $w$ .

Jeżeli $r$ jest wielomianem zerowym, to mówimy, że wielomian $p$ jest podzielny przez wielomian $w$ .

Przykład

Wykonamy dzielenie wielomianu

w(x)=x^7+x^6+x^4+x^2+x+1

przez wielomian

p(x)=x^3+x+1.

Korzystając z algorytmu dzielenia pisemnego omawianego w szkole otrzymujemy:

Stąd

x^7+x^6+x^4+x^2+x+1=(x^3+x+1)(x^4+x^3-x^2-x)+3x^2+2x+1.

Przykład

Podzielimy wielomian $P(x)=x^4-1$ przez wielomian $W(x)=x^2$ . Zastosujemy tym razem inną metodę niż w powyższym przykładzie. Wiemy, że ilorazem jest wielomian stopnia dwa, a reszta jest stopnia co najwyżej jeden. Musimy zatem znaleźć liczby $a,b,c,d,e,$ takie, że

x^4-1=x^2(ax^2+bx+c)+dx+e.

Stąd po wymnożeniu dostajemy

x^4-1=ax^4+bx^3+cx^2+dx+e.

Porównując odpowiednie współczynniki dostajemy kolejno, że $a=1$ , $b=c=d=0$ oraz $e=-1$ . Stąd

x^4-1=x^2\cdot x^2-1.

Przykład do samodzielnego rozwiązania¶

Podziel wielomian $p(x)=x^4+2x+1$ przez wielomian $w(x)=x^2+1$ .

Schemat Hornera¶

W przypadku dzielenia wielomianów przez dwumian niezwykle użyteczne jest następujące twierdzenie.

Twierdzenie

Niech $p$ będzie wielomianem danym wzorem

p(x)=a_nx^n+a_{n-1}x^{n-1}+\ldots+a_1x+a_0.

Ilorazem z dzielenia tego wielomianu przez dwumian

x-a

jest wielomian $q$ dany wzorem

q(x)=b_{n-1}x^{n-1}+\ldots+b_1x+b_0,

gdzie

b_{n-1}=a_n\quad\text{oraz}\quad b_k=a_{k+1}+a\cdot b_{k+1} \quad\text{dla}\quad k=0,1,\ldots,n-2,

a reszta z tego dzielenia jest równa

r=a_0+a\cdot b_0.

Przykład¶

Podzielimy wielomian

P(x)=x^4+1

przez dwumian

x-2.

Mamy

a_4=1, a_3=0, a_2=0,a_1=0, a_0=1, a=2.

Z powyższego twierdzenia kolejno otrzymujemy, że

b_3=1, b_2=0+2\cdot 1=2, b_1=0+2\cdot 2=4, b_0=0+2\cdot 4=8, r=1+2\cdot 8=17.

Zatem

x^4+1=(x-2)(x^3+2x^2+4x+8)+17

Zauważmy ponadto, że $P(2)=17.$

Uwaga

Reszta z dzielenia wielomianu $p$ przez dwumian $x-a$ jest zawsze wielomianem stopnia co najwyżej zero (tzn. jest funkcją stałą) zawsze równym $p(a)$ . Istotnie, z twierdzenia o dzieleniu wielomianów wynika, że istnieje wielomian $q$ oraz wielomian $r$ stopnia co najwyżej zero takie, że

p(x)=(x-a)q(x)+r(x).

Podstawiając do tego równania za $x$ liczbę $a$ dostajemy, że $p(a)=r(a)$ .

Znaczenie schematu Hornera¶

Aby obliczyć wartość wielomianu

p(x)=a_nx^n+a_{n-1}x^{n-1}+\ldots+a_1x+a_0.

dla liczby rzeczywistej $a$ metodą naiwną, potrzeba wykonać $\frac{n(n+1)}{2}$ mnożeń i $n$ dodawań. Schemat Hornera pozwala nam znacznie to przyspieszyć! Istotnie, z uwagi powyżej wynika, że aby obliczyć wartość $p(a)$ , wystarczy policzyć resztę z dzielenia $p$ przez dwumian $x-a$ . A to wymaga $n$ mnożeń i $n$ dodawań.

# function to calculte the value of a polynomial (given as a list of coefficients) at a

def value(a, poly):
        n = len(poly)
        b = poly[n-1]
        for i in range(n-1):
            b = poly[n-i-2]+a*b 
        
        return b
        
poly = [1,0,0,0,1] # 1+x^4
a=2
print(value(a,poly))