VersChIlrijen

De volledige documentatie is te vinden in het artikel van Roel Timmermans. Het onderstaande programma is hierop gebaseerd. Mogelijk kun jij dit programma nog uitbreiden. Laat het weten! Stuur je programma naar [email protected].

Een polynoom of veelterm $P(x)$ is een uitdrukking van de vorm $P(x)=p_nx^n+p_{n-1}x^{n-1}+\cdots+p_2x^2+p_1x+p_0$.

$p_0, p_1, p_2, p_3, \ldots ,p_n$ heten coëfficiënten.

Polynomen worden in het onderstaande programma gerepresenteerd door $P=[p_0,p_1,p_2,p_3,\ldots,p_n]$. De degree of graad van $P(x)$ is de grootste macht van $x$ met een coëfficiënt ongelijk aan $0$.

Met $C(a,b)$ geven we in deze tekst aan de binomiaalcoëfficiënt ${n\choose k}$. Roel Timmermans telt een aantal van deze binomiaalcoëfficiënten bij elkaar op. Die moeten natuurlijk wel eerst berekend worden:

• $C(x,0)=1$
• $C(x,1)=x/1$
• $C(x,2)=x(x-1)/2=\frac{1}{2}x^2-\frac{1}{2}x$
• $C(x,3)=x(x-1)(x-2)/6=\frac{1}{6}x^3-\frac{1}{2}x^2+\frac{1}{3}x$
• $C(x,4)=x(x-1)(x-2)(x-3)/24=\frac{1}{24}x^4-\frac{1}{4}x^3+\frac{11}{24}x^2-\frac{1}{4}x$

We gebruiken een aantal procedures:

1. F(P,x) Gegeven een polynoom $P$ en een getal $x$.
2. AddPol(P1, P2) We moeten twee polynomen bij elkaar kunnen optellen.
3. MulPol(P1, P2) We moeten twee polynomen met elkaar kunnen vermenigvuldigen.
4. BasPol(n) Roel Timmermans maakt gebruik van de polynomen $C(x,n)=x(x-1)(x-2)\cdots(x-n+1)/n!$. BasPol(n) berekent deze polynomen. Deze polynomen worden geplaatst in BasicPol. Dus BasPol wordt maar eenmaal aangeroepen.

Het programma staat twee maal onder elkaar. De eerste versie gaat uit van reële coëfficiënten. Daarna volgt een versie waarbij de coëfficiënten breuken zijn. Om dat programma goed te laten werken moeten er ook extra procedures worden geschreven om breuken bij elkaar op te tellen en met elkaar te vermenigvuldigen. Een breuk teller/noemer wordt steeds weergegeven door (teller,noemer).

Versie 1 (ReëlE CoËfFiCiëNten)

# Verschilrijen
# Gegeven T bepaal een polynoom P z.d.d. P(n) = T_n

def F(P,x):
    prod = 1
    sum = 0
    for n in range(len(P)):
        sum += P[n] * prod
        prod *= x
    return sum

def AddPol(P1, P2):
    l1 = len(P1)
    l2 = len(P2)
    l = max(l1,l2)
    P = []
    for i in range(l):
        P.append(0)
    for i in range(l1):
        P[i] = P1[i]
    for i in range(l2):
        P[i] += P2[i]
    return P

def MulPol(P1, P2):
    l1 = len(P1)
    l2 = len(P2)
    l = l1+l2-1
    P = []
    for i in range(l):
        P.append(0)
    for i in range(l1):
        for j in range(l2):
            P[i+j] += P1[i] * P2[j]
    return P

BasicPol = [[1], [0,1]]
def BasPol(n):
    if n < 0:
        return 0
    elif n == 0:
        return BasicPol[0]
    elif n == 1:
        return BasicPol[1]
    elif n > 1:
        BasicPol.append(MulPol([(-n+1)/n,1/n],BasicPol[n-1]))
        return BasicPol[n]

T = [1,1,2,3,5,8,13]
#T = [0,1,4,9]
P1 = [0,1,2,0]
P2 = [2,1,0,1]
print("Testen optellen en vermenigvuldigen polynomen.")
print("P1 =", P1)
print("P2 =", P2)
print("P1 + P2 =", AddPol(P1,P2))
print("P1 x P2 =", MulPol(P1,P2))
print("De basis polynomen.")
for n in range(10):
    print(n, BasPol(n))
print("T =", T)
print("De verschillen.")
DT = T
lt = len(T)
COEF = [T[0]]
for i in range(lt-1):
    DDT = []
    ldt = len(DT)
    for j in range(ldt-1):
        DDT.append(DT[j+1]-DT[j])
    COEF.append(DDT[0])
    DT = DDT
print(COEF)
print("Het beste polynoom:")
print(P)
print("P(0), P(1), P(2), ...")
P = [0]
for i in range(len(COEF)):
    C = [COEF[i]]
    Pi = MulPol(C, BasicPol[i])
    P = AddPol(P,Pi)
for x in range(10):
    print("P(",x,") =", F(P,x))

Versie 2 (COëFfiCIËnteN Als breukEn)

# Verschilrijen
# Gegeven T bepaal een polynoom P z.d.d. P(n) = T_n
# Breuken worden weergegeven door (p,q)

import math

def Vereenvoudig(a):
    (p,q) = a
    g = math.gcd(p,q)
    return (p//g,q//g)

def Plus(a,b):
    (p,q) = a
    (r,s) = b
    t = p*s+q*r
    n = q*s
    c = (t,n)
    return Vereenvoudig(c)

def Maal(a,b):
    (p,q) = a
    (r,s) = b
    t = p*r
    n = q*s
    c = (t,n)
    return Vereenvoudig(c)

def MaakBreukRij(T):
    R = []
    for t in T:
        R.append((t,1))
    return R

def F(P,x):
    prod = (1,1)
    sum = (0,1)
    for n in range(len(P)):
        sum = Plus(sum, Maal(P[n], prod))
        prod = Maal(prod,x)
    return sum

def AddPol(P1, P2):
    l1 = len(P1)
    l2 = len(P2)
    l = max(l1,l2)
    P = []
    for i in range(l):
        P.append((0,1))
    for i in range(l1):
        P[i] = P1[i]
    for i in range(l2):
        P[i] = Plus(P[i],P2[i])
    return P

def MulPol(P1, P2):
    l1 = len(P1)
    l2 = len(P2)
    l = l1+l2-1
    P = []
    for i in range(l):
        P.append((0,1))
    for i in range(l1):
        for j in range(l2):
            P[i+j] = Plus(P[i+j],Maal(P1[i],P2[j]))
    return P

BasicPol = [[(1,1)], [(0,1),(1,1)]]
def BasPol(n):
    if n < 0:
        return 0
    elif n == 0:
        return BasicPol[0]
    elif n == 1:
        return BasicPol[1]
    elif n > 1:
        BasicPol.append(MulPol([(-n+1,n),(1,n)],BasicPol[n-1]))
        return BasicPol[n]

TT = [1,1,2,3,5,8,13]
#T = [0,1,4,9]
PP1 = [0,1,2,0]
PP2 = [2,1,0,1]
T = MaakBreukRij(TT)
P1 = MaakBreukRij(PP1)
P2 = MaakBreukRij(PP2)
print("Testen optellen en vermenigvuldigen polynomen.")
print("P1 =", P1)
print("P2 =", P2)
print("P1 + P2 =", AddPol(P1,P2))
print("P1 x P2 =", MulPol(P1,P2))
print("De basis polynomen.")
for n in range(10):
    print(n, BasPol(n))
print("T =", T)
print("De verschillen.")
DT = T
lt = len(T)
COEF = [T[0]]
for i in range(lt-1):
    DDT = []
    ldt = len(DT)
    for j in range(ldt-1):
        DDT.append(Plus(DT[j+1],Maal((-1,1),DT[j])))
    COEF.append(DDT[0])
    DT = DDT
print(COEF)
P = [(0,1)]
for i in range(len(COEF)):
    C = [COEF[i]]
    Pi = MulPol(C, BasicPol[i])
    P = AddPol(P,Pi)
print("Het beste polynoom:")
print(P)
print("P(0), P(1), P(2), ...")
for xx in range(10):
    x = (xx,1)
    print("P(",x,") =", F(P,x))