Universitaire wiskunde — Bachelor jaar 1 · Bachelor Year 1

8Veeltermen

Veeltermen zijn de favoriete functies van de algebraïcus — behalve dat ze hier niet als functies worden behandeld, maar als formele uitdrukkingen in een onbepaalde $X$ , opgeteld en vermenigvuldigd volgens de regels van een commutatieve ring. De theorie loopt opvallend parallel met Hoofdstuk 6: een euclidische deling, een ggd en Bézout-relaties, irreducibele elementen en een unieke ontbinding. Overal duidt $K$ hierbij $\Q$ , $\R$ of $\C$ aan.

8.1 De ring $K[X]$

Definitie 8.1 (Veelterm, graad)

Een veelterm met coëfficiënten in $K$ is een formele som

P = a_0 + a_1 X + a_2 X^2 + \dots + a_n X^n = \sum_{k} a_k X^k,

met $a_k \in K$ alle nul vanaf een zekere index. Met de natuurlijke optelling en het product

\Bigl(\sum_i a_i X^i\Bigr)\Bigl(\sum_j b_j X^j\Bigr) = \sum_k \Bigl(\sum_{i+j=k} a_i b_j\Bigr) X^k,

is de verzameling $K[X]$ een commutatieve ring. De graad $\deg P$ van $P \neq 0$ is de grootste $n$ met $a_n \neq 0$ ; $a_n$ is de leidende coëfficiënt ( $P$ is monisch wanneer $a_n = 1$ ), en per afspraak is $\deg 0 = -\infty$ . Elke veelterm bepaalt een functie $x \mapsto P(x)$ op $K$ door substitutie.

Propositie 8.2 (Graadregels; integriteitsdomein)

Voor $P, Q \in K[X]$ :

\deg(P + Q) \leq \max(\deg P, \deg Q), \qquad \deg(PQ) = \deg P + \deg Q .

Bijgevolg is $K[X]$ een integriteitsdomein, en zijn eenheden zijn de niet-nulconstanten.

Bewijs. De somregel is duidelijk (coëfficiënten voorbij het maximum verdwijnen). Voor het product, laat $a_m$ en $b_n$ de leidende coëfficiënten zijn: de coëfficiënt van $X^{m+n}$ in $PQ$ is $a_m b_n \neq 0$ ( $K$ is een lichaam, dus een integriteitsdomein), en alle hogere coëfficiënten verdwijnen. Als $P, Q \neq 0$ dan is $\deg PQ = \deg P + \deg Q \geq 0$ , dus $PQ \neq 0$ : integriteitsdomein. Als $PQ = 1$ dan dwingt $\deg P + \deg Q = 0$ dat $\deg P = \deg Q = 0$ : de inverteerbare elementen zijn de inverteerbare constanten, d.w.z. heel $K^*$ . ∎

Stelling 8.3 (Euclidische deling)

Laat $A, B \in K[X]$ met $B \neq 0$ . Er is precies één paar $(Q, R)$ van veeltermen met

A = BQ + R, \qquad \deg R < \deg B .

Bewijs. Bestaan, door sterke inductie op $\deg A$ . Als $\deg A < \deg B$ , neem $(Q, R) = (0, A)$ . Schrijf anders $A = a X^m + \dots$ , $B = b X^n + \dots$ met $m \geq n$ ; de veelterm $A_1 = A - \frac ab X^{m-n} B$ heeft graad $< m$ (de leidende termen heffen elkaar op), dus per inductie $A_1 = BQ_1 + R$ met $\deg R < \deg B$ , en $A = B(Q_1 + \frac ab X^{m-n}) + R$ .

Uniciteit: als $BQ + R = BQ' + R'$ , dan $B(Q - Q') = R' - R$ met $\deg(R' - R) < \deg B$ ; volgens de graadregel dwingt dit $Q - Q' = 0$ , en dan $R = R'$ . ∎

Voorbeeld 8.4

Deel $A = X^4 + X^3 - 2X + 1$ door $B = X^2 + 1$ :

X^4 + X^3 - 2X + 1 = (X^2 + 1)(X^2 + X - 1) + (-3X + 2).

(Reken na: trek $X^2 B$ af, dan $X B$ , dan $-B$ ; de rest $-3X + 2$ heeft graad $1 < 2$ .)

Methode 8.5 (Schema van Horner)

Om $P = a_nX^n + \dots + a_0$ te evalueren in $x$ , of om $P$ door $X - x$ te delen, vermijd je het berekenen van machten: lees de coëfficiënten van links naar rechts, en herhaal vermenigvuldig met $x$ , tel de volgende coëfficiënt op:

b_n = a_n, \qquad b_{k} = a_{k} + x\,b_{k+1} \quad (k = n-1, \dots, 0) .

Dan is $b_0 = P(x)$ , en de eerdere $b_k$ zijn de coëfficiënten van het quotiënt: $P = (X - x)(b_nX^{n-1} + \dots + b_1) + b_0$ (werk uit en vergelijk). Voorbeeld: $P = X^4 - 5X^3 + 6X^2 + 4X - 8$ in $x = 2$ : de $b$ ’s zijn $1, -3, 0, 4, 0$ , dus $P(2) = 0$ en $P = (X-2)(X^3 - 3X^2 + 4)$ — één regel in plaats van een lange deling, en $n$ vermenigvuldigingen in plaats van de $\approx n^2/2$ van de naïeve evaluatie. Het schema herhalen in hetzelfde punt haalt multipliciteiten eruit (vergelijk Voorbeeld 8.12).

Opmerking 8.6 (Rekenkunde van $K[X]$ )

Met de euclidische deling in de hand draagt de volledige rekenkunde van Hoofdstuk 6 over op $K[X]$ , met dezelfde bewijzen, waarbij de graad de rol van absolute waarde speelt: ggd (genormaliseerd tot monisch), uitgebreid algoritme van Euclides, identiteit van Bézout, lemma van Gauss, irreducibele veeltermen en unieke ontbinding. We gebruiken deze overgedragen resultaten vrijelijk, en Oefening 8.6 oefent er één in.

8.2 Wortels

Stelling 8.7 (Factorstelling)

Laat $P \in K[X]$ en $a \in K$ . De rest van $P$ bij deling door $X - a$ is de constante $P(a)$ . In het bijzonder

P(a) = 0 \iff (X - a) \mid P .

Meer algemeen geven verschillende wortels $a_1, \dots, a_r$ van $P$ de ontbinding $P = (X - a_1)\cdots(X - a_r)\, Q$ .

Bewijs. Deel: $P = (X - a) Q + R$ met $\deg R < 1$ , dus $R$ is een constante $c$ ; substitutie van $X = a$ (substitutie respecteert sommen en producten) geeft $P(a) = c$ . De equivalentie volgt. Voor meerdere wortels, induceer op $r$ : het geval $r = 1$ is de zojuist bewezen equivalentie. Neem de uitspraak aan voor $r - 1$ wortels en laat $a_1, \dots, a_r$ verschillende wortels van $P$ zijn. Schrijf $P = (X - a_1)Q_1$ ; voor elke $i \geq 2$ , substitutie van $a_i$ :

0 = P(a_i) = (a_i - a_1)\,Q_1(a_i), \qquad a_i - a_1 \neq 0 ,

en aangezien $K$ geen nuldelers heeft, $Q_1(a_i) = 0$ : de $r - 1$ verschillende punten $a_2, \dots, a_r$ zijn wortels van $Q_1$ . De inductiehypothese ontbindt $Q_1 = (X - a_2)\cdots(X - a_r)\,Q$ , en terugsubstitutie geeft de bewering. ∎

Gevolg 8.8 (Een veelterm van graad $n$ heeft ten hoogste $n$ wortels)

Een niet-nulveelterm $P \in K[X]$ van graad $n$ heeft ten hoogste $n$ verschillende wortels in $K$ . Bijgevolg is een veelterm (van graad $\leq n$ ) die verdwijnt in $n + 1$ verschillende punten de nulveelterm, en zijn twee veeltermen van graad $\leq n$ die in $n+1$ punten overeenkomen gelijk.

Bewijs. Als $a_1, \dots, a_r$ verschillende wortels zijn, geeft Stelling 8.7 $P = (X-a_1)\cdots(X-a_r) Q$ , dus $n = \deg P \geq r$ . De twee gevolgen volgen door tegenspraak en door verschil. ∎

Voorbeeld 8.9 (De truc met de hulpveelterm)

Laat $P$ de veelterm van graad $\leq n$ zijn met

P(k) = \frac{k}{k+1} \qquad (k = 0, 1, \dots, n) ;

hij bestaat en is uniek volgens de Lagrange-interpolatie hieronder. Wat is $P(n+1)$ ? Werk de noemers weg: de veelterm $Q = (X+1)P - X$ heeft graad $\leq n + 1$ en verdwijnt in de $n + 1$ punten $0, 1, \dots, n$ , dus volgens Stelling 8.7

Q = c\,X(X-1)(X-2)\cdots(X-n)

voor een zekere constante $c$ . Evalueer waar $Q$ onafhankelijk bekend is: in $X = -1$ is $Q(-1) = 0 \cdot P(-1) + 1 = 1$ , terwijl het product gelijk is aan $(-1)(-2)\cdots(-1-n) = (-1)^{n+1}(n+1)!$ ; dus $c = \frac{(-1)^{n+1}}{(n+1)!}$ . Evalueer nu in $X = n + 1$ :

(n+2)\,P(n+1) - (n+1) = Q(n+1) = c\,(n+1)! = (-1)^{n+1} ,

dus $P(n+1) = \dfrac{(n+1) + (-1)^{n+1}}{n+2}$ : gelijk aan $1$ voor oneven $n$ , en aan $\frac{n}{n+2}$ voor even $n$ — de interpolerende veelterm zet het patroon $\frac{n+1}{n+2}$ niet voort. De te onthouden truc: codeer de gegevens als wortels van een hulpveelterm, bepaal de onbekende constante in een punt buiten de gegevens, en oogst.

Definitie 8.10 (Afgeleide, multipliciteit)

De formele afgeleide van $P = \sum a_k X^k$ is $P' = \sum_{k \geq 1} k\,a_k X^{k-1}$ ; ze voldoet aan de gebruikelijke regels $(P+Q)' = P' + Q'$ , $(PQ)' = P'Q + PQ'$ (gecontroleerd op monomen en uitgebreid door lineariteit). Een wortel $a$ van $P$ heeft multipliciteit $m \geq 1$ wanneer $(X-a)^m \mid P$ maar $(X-a)^{m+1} \nmid P$ ; de wortel is enkelvoudig als $m = 1$ , meervoudig als $m \geq 2$ .

Propositie 8.11 (Multipliciteit via afgeleiden)

$a$ is een wortel van $P$ van multipliciteit $\geq m$ dan en slechts dan als

P(a) = P'(a) = \dots = P^{(m-1)}(a) = 0 .

In het bijzonder is $a$ een meervoudige wortel van $P$ dan en slechts dan als $P(a) = P'(a) = 0$ .

Bewijs. Schrijf $P = (X - a)^m Q + R$ waarbij $R$ de rest is van de deling door $(X-a)^m$ , $\deg R < m$ . Door $k \leq m - 1$ keer af te leiden en in $a$ te evalueren: de eerste term levert $0$ (elke afgeleide behoudt een factor $(X-a)$ ), dus $P^{(k)}(a) = R^{(k)}(a)$ .

Nu is een veelterm $R$ van graad $< m$ bepaald door $R(a), R'(a), \dots, R^{(m-1)}(a)$ : door $R = \sum_{k < m} c_k (X - a)^k$ te schrijven (mogelijk: werk machten van $X = (X - a) + a$ uit), vindt men $R^{(k)}(a) = k!\, c_k$ . Dus: alle $P^{(k)}(a) = 0$ voor $k < m$ $\iff$ alle $c_k = 0$ $\iff$ $R = 0$ $\iff$ $(X-a)^m \mid P$ . ∎

Voorbeeld 8.12 (Een multipliciteit berekenen)

Wat is de multipliciteit van de wortel $2$ in $P = X^4 - 5X^3 + 6X^2 + 4X - 8$ ? Evalueer de opeenvolgende afgeleiden in $2$ :

P(2) = 16 - 40 + 24 + 8 - 8 = 0, \qquad P'(2) = 32 - 60 + 24 + 4 = 0,

P''(2) = 48 - 60 + 12 = 0, \qquad P'''(2) = 48 - 30 = 18 \neq 0

(met $P' = 4X^3 - 15X^2 + 12X + 4$ , $P'' = 12X^2 - 30X + 12$ , $P''' = 24X - 30$ ). Drie verdwijnende waarden en dan een niet-nulwaarde: multipliciteit precies $3$ . Delen geeft $P = (X - 2)^3(X + 1)$ — wat men nagaat door $(X-2)^3 = X^3 - 6X^2 + 12X - 8$ uit te werken en met $X + 1$ te vermenigvuldigen. Het inzicht: multipliciteiten worden afgelezen uit evaluaties, geen ontbinding nodig — precies zoals men ze detecteert wanneer de ontbinding onbereikbaar is.

Voorbeeld 8.13 (Meervoudige wortels detecteren met een ggd)

Wanneer geen wortel bekend is, geeft Propositie 8.11 nog steeds een globale detector van meervoudige wortels: $a$ is een meervoudige wortel van $P$ dan en slechts dan als het een gemeenschappelijke wortel is van $P$ en $P'$ , dus $P$ heeft een meervoudige wortel (in $\C$ ) dan en slechts dan als $\gcd(P, P') \neq 1$ — berekenbaar via het algoritme van Euclides zonder iets op te lossen. Voorbeeld: $P = X^3 - 3X + 2$ , $P' = 3X^2 - 3 = 3(X - 1)(X + 1)$ . Toets de wortels $\pm1$ van $P'$ in $P$ : $P(1) = 0$ maar $P(-1) = 4$ , dus

\gcd(P, P') = X - 1 :

de wortel $1$ is meervoudig; twee keer delen geeft $P = (X - 1)^2(X + 2)$ . De ggd rapporteert zelfs de volledige verzameling meervoudige wortels, elk met de multipliciteit met één verlaagd — het feit dat elk computeralgebrasysteem uitbuit om “kwadraatvrij te ontbinden” vóór enige worteljacht, en de veeltermtweeling van de argumenten zonder meervoudige wortel in Oefening 8.9.

Stelling 8.14 (Hoofdstelling van de algebra)

Elke niet-constante veelterm van $\C[X]$ heeft een wortel in $\C$ .

Bewijs. Toegegeven op dit niveau. ∎

Opmerking 8.15

Ondanks zijn naam is de stelling een uitspraak van de analyse: elk bekend bewijs gebruikt de volledigheid van $\R$ in een of andere vorm, en geen enkel is zuiver algebraïsch — het eerlijke bewijs wordt gegeven in het volume van Jaar 3, zodra ofwel complexe integratie ofwel compactheidsargumenten beschikbaar zijn. Wat dit hoofdstuk werkelijk bewijst, is de reductie: gegeven één wortel voor elke niet-constante veelterm, volgen de volledige ontbindingen over $\C$ en $\R$ hieronder door zuivere algebra.

Gevolg 8.16 (Ontbinding over $\C$ en over $\R$ )

Elke niet-nulveelterm $P \in \C[X]$ ontbindt als

$P = c\, (X - a_1)^{m_1} \cdots (X - a_r)^{m_r},$

met $c$ de leidende coëfficiënt, $a_i$ de verschillende complexe wortels, $\sum m_i = \deg P$ : geteld met multipliciteit heeft een veelterm van graad $n$ precies $n$ complexe wortels.
Elke niet-nulveelterm $P \in \R[X]$ ontbindt over $\R$ als

$P = c \prod_i (X - a_i)^{m_i} \prod_j (X^2 + p_j X + q_j)^{n_j},$

waarbij de kwadratische factoren verschillend zijn met $p_j^2 - 4q_j < 0$ (geen reële wortels).

Bewijs. (1) Inductie op de graad, waarbij telkens één wortel wordt afgesplitst via Stelling 8.7; de telling van de graden klopt bij elke stap.

(2) Laat $P$ reële coëfficiënten hebben. Als $z$ een complexe wortel van multipliciteit $m$ is, dan ook $\conj z$ : het toevoegen van $P(z) = 0$ geeft $P(\conj z) = \conj{P(z)} = 0$ (de coëfficiënten zijn hun eigen toegevoegden), en hetzelfde geldt voor de afgeleiden (Propositie 8.11). Groepeer de niet-reële wortels in toegevoegde paren: elk paar draagt bij

(X - z)(X - \conj z) = X^2 - 2\Re(z)\, X + \abs z^2 ,

een reële kwadratische met negatieve discriminant. De reële wortels dragen de lineaire factoren bij. ∎

Voorbeeld 8.17

$X^4 + 4$ werd over $\R$ ontbonden in Oefening 3.5 door de vier complexe wortels $\pm 1 \pm \iu$ te paren: $X^4 + 4 = (X^2 - 2X + 2)(X^2 + 2X + 2)$ . Geen van beide kwadratische factoren splitst over $\R$ (discriminanten $-4$ ). Merk op: een irreducibele reële veelterm heeft graad $1$ of $2$ — dit is precies wat de ontbindingsstelling zegt. Dezelfde toevoegd-paren-methode toegepast op $X^4 + 1$ , waarvan de wortels $\eu^{\pm\iu\pi/4}$ en $\eu^{\pm3\iu\pi/4}$ zijn: elk paar draagt bij $X^2 - 2\cos\theta\,X + 1$ , dus

X^4 + 1 = \bigl(X^2 - \sqrt2\,X + 1\bigr) \bigl(X^2 + \sqrt2\,X + 1\bigr) ,

een identiteit die onzichtbaar is voor naïeve ontbindingspogingen over $\Q$ — de prijs van het aandringen op reële (hier zelfs irrationale) coëfficiënten, en een standaardinvoer voor het integreren van $\frac1{x^4 + 1}$ in Hoofdstuk 15.

De Tsjebysjev-veelterm T_5 = 16X5 - 20X3 + 5X op ∈tcc-11: hij oscilleert precies tussen -1 en 1, en raakt de grenzen in zes punten (gemarkeerd). Deze equioscillatie maakt 2-4T_5 tot de monische vijfdegraadsveelterm met de kleinste supnorm op het interval ( en het weekendprobleem). — De Tsjebysjev-veelterm $T_5 = 16X^5 - 20X^3 + 5X$ op $\intcc{-1}1$ : hij oscilleert precies tussen $-1$ en $1$ , en raakt de grenzen in zes punten (gemarkeerd). Deze *equioscillatie* maakt $2^{-4}T_5$ tot de monische vijfdegraadsveelterm met de kleinste supnorm op het interval (Oefening 8.10 en het weekendprobleem).

Opmerking 8.18 (Veelvoorkomende valkuilen bij veeltermen)

Veelterm versus functie. Over $K = \Q, \R, \C$ vallen de twee begrippen samen (gelijke functies hebben gelijke coëfficiënten, volgens Gevolg 8.8 en de oneindigheid van $K$ ), maar conceptueel is een veelterm zijn lijst van coëfficiënten: over het lichaam $\Z/2\Z$ met twee elementen uit Hoofdstuk 7 verdwijnt $X^2 + X$ in beide punten, en toch is het niet de nulveelterm.
Graden onder optelling. $\deg(P + Q)$ kan onder $\max(\deg P, \deg Q)$ zakken wanneer de leidende termen elkaar opheffen; “ $\deg(P + Q) = \max(\dots)$ ” schrijven is alleen veilig voor verschillende graden.
Wortels correct geteld. “ $n$ wortels” in Gevolg 8.16 betekent met multipliciteit, in $\C$ : $X^2 + 1$ heeft geen reële wortels, en $(X-1)^2$ heeft één verschillende wortel maar twee met multipliciteit. Uitspraken die de drie tellingen door elkaar halen zijn de meest voorkomende bron van foute bewijzen.
Irreducibiliteit hangt af van het lichaam. $X^2 - 2$ is irreducibel over $\Q$ , splitst over $\R$ ; $X^2 + 1$ is irreducibel over $\R$ , splitst over $\C$ . Het kale woord “irreducibel” betekent niets tot het lichaam van de coëfficiënten genoemd is.

8.3 Coëfficiënten en wortels

Stelling 8.19 (Formules van Vieta)

Laat $P = X^n + c_{n-1} X^{n-1} + \dots + c_0$ monisch zijn met wortels $a_1, \dots, a_n \in \C$ (met multipliciteit). Dan

\sum_i a_i = -c_{n-1}, \qquad \sum_{i < j} a_i a_j = c_{n-2}, \qquad \dots, \qquad a_1 a_2 \cdots a_n = (-1)^n c_0 ,

waarbij de $k$ -de symmetrische functie van de wortels $(-1)^k c_{n-k}$ is.

Bewijs. Volgens Gevolg 8.16 is $P = (X - a_1)\cdots(X - a_n)$ (monisch, alle wortels opgesomd). Het distributief uitwerken van het product levert één term per manier om, in elke factor, ofwel $X$ ofwel de wortelterm $-a_i$ te kiezen: het kiezen van de wortels in de factoren met index $i_1 < \dots < i_k$ en van $X$ in de $n - k$ overige levert $(-a_{i_1})\cdots(-a_{i_k})\,X^{n-k}$ op. Groeperen naar de macht van $X$ :

P = \sum_{k=0}^{n} (-1)^k \Bigl(\sum_{i_1 < \dots < i_k} a_{i_1}\cdots a_{i_k}\Bigr) X^{n-k} ,

en identificeren met $P = \sum_k c_{n-k}X^{n-k}$ (coëfficiënten zijn uniek, Definitie 8.1) geeft $c_{n-k} = (-1)^k \sigma_k$ , d.w.z. $\sigma_k = (-1)^kc_{n-k}$ , waarbij $\sigma_k$ de $k$ -de symmetrische functie aanduidt die hierboven weergegeven is. De drie weergegeven gevallen zijn $k = 1$ , $k = 2$ en $k = n$ . ∎

Voorbeeld 8.20

Voor de kwadratische $X^2 - sX + p$ : som van de wortels $s$ , product $p$ — al herhaaldelijk gebruikt (Oefening 3.8). Voor een monische derdegraadsveelterm $X^3 + aX^2 + bX + c$ met wortels $\alpha, \beta, \gamma$ :

\alpha + \beta + \gamma = -a, \quad \alpha\beta + \beta\gamma + \gamma\alpha = b, \quad \alpha\beta\gamma = -c ,

wat het berekenen van symmetrische grootheden zoals $\alpha^2 + \beta^2 + \gamma^2 = a^2 - 2b$ mogelijk maakt zonder op te lossen.

Voorbeeld 8.21 (De wortels transformeren zonder ze te vinden)

Laat $\alpha, \beta$ de wortels van $X^2 - 3X + 1$ zijn. Welke monische kwadratische heeft wortels $\alpha^2, \beta^2$ ? Volgens Vieta is $\alpha + \beta = 3$ en $\alpha\beta = 1$ , dus

\alpha^2 + \beta^2 = (\alpha+\beta)^2 - 2\alpha\beta = 7, \qquad \alpha^2\beta^2 = (\alpha\beta)^2 = 1 :

het antwoord is $X^2 - 7X + 1$ — verkregen zonder $\alpha = \frac{3 + \sqrt5}2$ te berekenen. (Controle: $\alpha^2 = \frac{7 + 3\sqrt5}2$ en inderdaad $\alpha^2 + \beta^2 = 7$ .) Dezelfde strategie behandelt inverses ( $X^2 - \frac ba X + \frac ca$ -type transformaties), verschuivingen, en elk symmetrisch gegeven: Vieta zet vragen over onbekende wortels om in algebra op bekende coëfficiënten. Het zal voortdurend van pas komen wanneer de wortels eigenwaarden zijn (Hoofdstuk 22).

Voorbeeld 8.22 (Palindromische vergelijkingen)

Los $X^4 + X^3 - 4X^2 + X + 1 = 0$ op. De coëfficiënten lezen in beide richtingen hetzelfde, dus $0$ is geen wortel en delen door $X^2$ verliest geen oplossingen:

X^2 + X - 4 + \frac1X + \frac1{X^2} = 0 .

Stel $y = X + \frac1X$ : dan $X^2 + \frac1{X^2} = y^2 - 2$ , en de vergelijking valt terug tot

y^2 + y - 6 = 0 \iff (y + 3)(y - 2) = 0 .

Ontvouw elke waarde via $X^2 - yX + 1 = 0$ : voor $y = 2$ geeft $X^2 - 2X + 1 = (X - 1)^2$ de dubbele wortel $1$ ; voor $y = -3$ geeft $X^2 + 3X + 1 = 0$ $X = \frac{-3 \pm \sqrt5}2$ . Vier wortels met multipliciteit voor een vierdegraadsveelterm, zoals Gevolg 8.16 vereist — verkregen door twee kwadratische vergelijkingen op te lossen. De truc dekt elke palindromische veelterm: hun wortels komen in inverse paren $\{x, 1/x\}$ (vervang $X$ door $1/X$ en werk de noemers weg), en $y = X + \frac1X$ is precies de grootheid die constant is op zulke paren, wat de graad halveert.

Stelling 8.23 (Lagrange-interpolatie)

Laat $x_0, \dots, x_n$ verschillende punten van $K$ zijn en $y_0, \dots, y_n \in K$ . Er is precies één $P \in K[X]$ van graad $\leq n$ met $P(x_i) = y_i$ voor alle $i$ , namelijk

P = \sum_{i=0}^{n} y_i\, L_i, \qquad L_i = \prod_{j \neq i} \frac{X - x_j}{x_i - x_j} .

Bewijs. Elke $L_i$ heeft graad $n$ en voldoet aan $L_i(x_i) = 1$ , $L_i(x_j) = 0$ voor $j \neq i$ (elke factor verdwijnt in de overeenkomstige $x_j$ ). Dus de weergegeven $P$ heeft graad $\leq n$ en interpoleert. Uniciteit: twee interpolerende veeltermen van graad $\leq n$ komen overeen in de $n+1$ punten $x_i$ , dus zijn ze gelijk (Gevolg 8.8). ∎

Opmerking 8.24 (Intermezzo: veeltermen zijn ook vectoren)

Een gezichtspuntswisseling die Hoofdstuk 18 officieel zal maken: de veeltermen van graad $\leq n$ vormen een ruimte waarin optelling en schaling zich precies gedragen als coördinaten — een veelterm is zijn lijst van $n + 1$ coëfficiënten. Drie uitspraken van dit hoofdstuk zijn stiekem lineaire algebra. Lagrange-interpolatie (Stelling 8.23) zegt dat de evaluatiegegevens $(P(x_0), \dots, P(x_n))$ $P$ uniek bepalen: evaluatie in $n + 1$ punten is een lineaire bijectie, en de $L_i$ zijn de daaraan aangepaste basis. De ontwikkeling $R = \sum c_k(X - a)^k$ in het bewijs van Propositie 8.11 zegt dat de machten van $(X - a)$ een ander coördinatenstelsel vormen, met $c_k = R^{(k)}(a)/k!$ als coördinaten. En Gevolg 8.8 — meer wortels dan de graad dwingt de nulveelterm af — is de motor van alle uniciteit: het zal “een lineaire afbeelding injectief op een ruimte van dimensie $n + 1$ ” worden in Hoofdstuk 19. Wanneer die hoofdstukken aanbreken, zal de ruimte $K_n[X]$ hun favoriete voorbeeld zijn; het loont de moeite er al vloeiend in aan te komen.

Opmerking 8.25 (Waar dit hoofdstuk gebruikt wordt)

Ontbinding over $\R$ en $\C$ (Gevolg 8.16) is de motor van de splitsing in partiële breuken in Hoofdstuk 9, en dus van een grote klasse integralen in Hoofdstuk 15. De ontwikkeling van een veelterm in machten van $(X - a)$ , aangetroffen in het bewijs van Propositie 8.11, is de algebraïsche schaduw van de Taylor-formules van Hoofdstuk 16. Karakteristieke veeltermen verschenen al bij differentiaalvergelijkingen (Hoofdstuk 5) en keren terug voor matrices in Hoofdstuk 22; Lagrange-interpolatie is de eerste bestaans-en-uniciteitsstelling van de numerieke analyse, en de Tsjebysjev-veeltermen van Oefening 8.10 — waarvan het weekendprobleem hieronder de optimaliteit vaststelt — vertellen die discipline waar te interpoleren. Ten slotte voedt de hele rekenkunde van $K[X]$ , gekopieerd van Hoofdstuk 6, de studie van $K[X]$ -idealen en quotiëntringen in het volume van Jaar 2.

8.4 Oefeningen

Oefening 8.1 ★

Voer de euclidische delingen uit: $X^5 - 1$ door $X^2 + X + 1$ ; dan $2X^4 + X^3 - X + 3$ door $X^2 - 2$ .

Oplossing

Oplossing van Oefening 8.1.

$X^5 - 1 = (X^2 + X + 1)(X^3 - X^2 + 1) + (-X - 2)$ . Stappen: trek $X^3 B$ af, dan $-X^2 B$ , dan $B$ ; de rest $-X - 2$ heeft graad $1 < 2$ . Controle in $X = 1$ : $\;0 = 3 \times 1 + (-3)$ .

$2X^4 + X^3 - X + 3 = (X^2 - 2)(2X^2 + X + 4) + (X + 11)$ . Controle in $X = 0$ : $\;3 = (-2)(4) + 11$ .

Oefening 8.2 ★

Voor welke $n \in \N$ deelt $X^2 + X + 1$ de veelterm $X^{2n} + X^n + 1$ ? Hint: de wortels van $X^2 + X + 1$ zijn $j$ en $j^2$ met $j = \eu^{2\iu\pi/3}$ ; bespreek $n$ mod $3$ .

Oplossing

Oplossing van Oefening 8.2.

$X^2 + X + 1 = (X - j)(X - j^2)$ met $j = \eu^{2\iu\pi/3}$ , $j^3 = 1$ . Het deelt $Q_n = X^{2n} + X^n + 1$ dan en slechts dan als $j$ en $j^2$ wortels van $Q_n$ zijn; aangezien $Q_n$ reële coëfficiënten heeft, is $Q_n(j^2) = \conj{Q_n(j)}$ , dus de voorwaarde is gewoon $Q_n(j) = 0$ . Nu hangt $Q_n(j) = j^{2n} + j^n + 1$ af van $n$ mod $3$ :

$n \equiv 0$ : $Q_n(j) = 1 + 1 + 1 = 3 \neq 0$ ;
$n \equiv 1$ : $Q_n(j) = j^2 + j + 1 = 0$ ;
$n \equiv 2$ : $Q_n(j) = j^4 + j^2 + 1 = j + j^2 + 1 = 0$ .

Dus $X^2 + X + 1 \mid X^{2n} + X^n + 1$ precies wanneer $3 \nmid n$ .

Oefening 8.3 ★

Bepaal de reële $a, b$ zodat $(X-1)^2$ de veelterm $P = X^4 + aX^3 + bX^2 + 1$ deelt, en ontbind dan $P$ over $\R$ voor deze waarden.

Oplossing

Oplossing van Oefening 8.3.

Volgens Propositie 8.11 geldt $(X-1)^2 \mid P$ dan en slechts dan als $P(1) = P'(1) = 0$ :

P(1) = 2 + a + b = 0, \qquad P'(1) = 4 + 3a + 2b = 0 .

Oplossen: $b = -a - 2$ en $4 + 3a - 2a - 4 = a = 0$ , dus $a = 0$ , $b = -2$ : $P = X^4 - 2X^2 + 1 = (X^2 - 1)^2 = (X-1)^2 (X+1)^2$ , wat de reële ontbinding is.

Oefening 8.4 ★

Ontbind over $\C$ en over $\R$ : $X^3 - 1$ ; $\;X^4 + X^2 + 1$ ; $\;X^6 - 1$ .

Oplossing

Oplossing van Oefening 8.4.

$X^3 - 1 = (X - 1)(X - j)(X - j^2)$ over $\C$ ( $j = \eu^{2\iu\pi/3}$ ), en $(X - 1)(X^2 + X + 1)$ over $\R$ .

$X^4 + X^2 + 1 = (X^2 + X + 1)(X^2 - X + 1)$ over $\R$ (werk uit, of merk op dat $X^4 + X^2 + 1 = (X^2+1)^2 - X^2$ ); over $\C$ splitst elke kwadratische: wortels $j, j^2$ en $-j, -j^2$ , d.w.z. $\eu^{\pm 2\iu\pi/3}, \eu^{\pm\iu\pi/3}$ .

$X^6 - 1 = \prod_{k=0}^{5} (X - \eu^{\iu k\pi/3})$ over $\C$ , en over $\R$ :

X^6 - 1 = (X-1)(X+1)(X^2 + X + 1)(X^2 - X + 1),

door de toegevoegde paren $\eu^{\pm 2\iu\pi/3}$ en $\eu^{\pm \iu\pi/3}$ te groeperen.

Oefening 8.5 ★★

Laat $P = X^3 - 6X^2 + 11X - 6$ .

Vind de rationale wortels (een rationale wortel $p/q$ in laagste termen van een monische gehele veelterm is een geheel getal dat de constante term deelt — bewijs dit), en ontbind $P$ .
Bereken zonder op te lossen de som van de kwadraten en de som van de inversen van de wortels via Vieta, en controleer op de ontbinding.

Oplossing

Oplossing van Oefening 8.5.

Laat $p/q$ (laagste termen) een wortel zijn van de monische gehele veelterm $X^3 + \dots + c_0$ : het wegwerken van de noemers in $P(p/q) = 0$ geeft $p^3 = -q\,(\text{geheel getal})$ , dus $q \mid p^3$ ; onderlinge ondeelbaarheid dwingt $q = \pm 1$ : de wortel is een geheel getal $p$ , en $p \mid c_0$ (isoleer $c_0$ ). Hier delen de kandidaten $6$ : bij het toetsen is $P(1) = 0$ , $P(2) = 0$ , $P(3) = 0$ . Dus $P = (X-1)(X-2)(X-3)$ .
Vieta: $s_1 = 6$ , $s_2 = 11$ , $s_3 = 6$ . Som van de kwadraten: $s_1^2 - 2s_2 = 36 - 22 = 14 = 1 + 4 + 9$ , zoals verwacht. Som van de inversen: $\frac{s_2}{s_3} = \frac{11}{6} = 1 + \frac12 + \frac13$ , zoals verwacht.

Oefening 8.6 ★★

Bereken $\gcd(X^4 - 1,\; X^3 - X^2 + X - 1)$ met het algoritme van Euclides, en schrijf het als een combinatie $AU + BV$ van de twee veeltermen.

Oplossing

Oplossing van Oefening 8.6.

Eerste delingsstap van het algoritme van Euclides:

(X + 1)(X^3 - X^2 + X - 1) = X^4 - X^3 + X^2 - X + X^3 - X^2 + X - 1 = X^4 - 1 ,

dus de deling van $X^4 - 1$ door $X^3 - X^2 + X - 1$ is exact (quotiënt $X + 1$ , rest $0$ ), en het algoritme stopt onmiddellijk:

\gcd(X^4 - 1,\; X^3 - X^2 + X - 1) = X^3 - X^2 + X - 1

(al monisch). De Bézout-relatie is de triviale: $\gcd = 0 \cdot (X^4 - 1) + 1 \cdot (X^3 - X^2 + X - 1)$ . Consistentiecontrole door ontbinding: $X^3 - X^2 + X - 1 = (X - 1)(X^2 + 1)$ , wat inderdaad het product is van de gemeenschappelijke irreducibele factoren van $X^4 - 1 = (X-1)(X+1)(X^2+1)$ .

Oefening 8.7 ★★

Laat $P \in \R[X]$ met $P(x) \geq 0$ voor alle $x \in \R$ . Bewijs dat $P$ een som van twee kwadraten van reële veeltermen is: $P = A^2 + B^2$ . Hint: in de reële ontbinding hebben reële wortels even multipliciteit; schrijf de kwadratische factoren als $(X - z)(X - \conj z)$ en gebruik $\abs{\,\cdot\,}^2 = (\Re)^2 + (\Im)^2$ op het product van de $(X - z)$ ’s.

Oplossing

Oplossing van Oefening 8.7.

Aangezien $P \geq 0$ op $\R$ , hebben zijn reële wortels even multipliciteit (in een wortel van oneven multipliciteit verandert $P$ van teken). Met Gevolg 8.16 en paring schrijven we

P = c \prod_i (X - a_i)^{2k_i} \prod_j \bigl((X - z_j)(X - \conj z_j)\bigr)^{n_j},

met $c > 0$ (gedrag in $+\infty$ ). Laat

S = \sqrt c\, \prod_i (X - a_i)^{k_i} \prod_j (X - z_j)^{n_j} \in \C[X],

zodat $P = S\,\conj S$ waarbij $\conj S$ de toegevoegde coëfficiënten heeft. Splits $S = A + \iu B$ met $A, B \in \R[X]$ : dan

P = (A + \iu B)(A - \iu B) = A^2 + B^2 .

Oefening 8.8 ★★

Vind de veelterm $P$ van graad $\leq 2$ met $P(0) = 1$ , $P(1) = 3$ , $P(2) = 2$ , eerst met de formule van Lagrange, dan door het lineaire stelsel op de coëfficiënten op te lossen. Controleer dat beide antwoorden overeenkomen.

Oplossing

Oplossing van Oefening 8.8.

Lagrange (Stelling 8.23) met knopen $0, 1, 2$ :

P = 1\cdot\frac{(X-1)(X-2)}{(0-1)(0-2)} + 3\cdot\frac{X(X-2)}{1\cdot(1-2)} + 2\cdot\frac{X(X-1)}{2\cdot 1} = \frac{(X-1)(X-2)}{2} - 3X(X-2) + X(X-1).

Uitwerken: $\frac{X^2 - 3X + 2}{2} - 3X^2 + 6X + X^2 - X = -\frac{3}{2}X^2 + \frac{7}{2}X + 1$ .

Stelsel: $P = aX^2 + bX + c$ met $c = 1$ ; $a + b + 1 = 3$ ; $4a + 2b + 1 = 2$ . Twee keer de tweede van de derde aftrekken: $2a - 1 = -4$ , dus $a = -\frac32$ , $b = \frac72$ . Dezelfde veelterm: $P = -\frac32 X^2 + \frac72 X + 1$ . (Controle $P(2) = -6 + 7 + 1 = 2$ .)

Oefening 8.9 ★★

Bewijs dat $P = X^{2n+1} - 1$ precies één reële wortel heeft, en dat voor elke $n \geq 1$ de veelterm $1 + X + \frac{X^2}{2!} + \dots + \frac{X^n}{n!}$ geen meervoudige wortel heeft (vergelijk $P$ en $P'$ ).

Oplossing

Oplossing van Oefening 8.9.

$P = X^{2n+1} - 1$ : $P' = (2n+1)X^{2n} \geq 0$ , dus de veeltermfunctie is stijgend (strikt behalve in $0$ ), met limieten $\mp\infty$ : ze verdwijnt precies één keer op $\R$ (in $x = 1$ ).

Laat $E_n = \sum_{k=0}^{n} \frac{X^k}{k!}$ . Dan $E_n' = E_{n-1} = E_n - \frac{X^n}{n!}$ . Een meervoudige wortel $a$ zou voldoen aan $E_n(a) = E_n'(a) = 0$ (Propositie 8.11), dus $\frac{a^n}{n!} = E_n(a) - E_n'(a) = 0$ , dus $a = 0$ ; maar $E_n(0) = 1 \neq 0$ . Geen meervoudige wortel.

Oefening 8.10 ★★★

(Tsjebysjev-veeltermen) Definieer $T_0 = 1$ , $T_1 = X$ en $T_{n+1} = 2X\,T_n - T_{n-1}$ .

Bewijs door inductie dat $T_n(\cos\theta) = \cos n\theta$ voor alle $\theta$ .
Leid de $n$ wortels van $T_n$ en zijn leidende coëfficiënt af.
Bewijs dat $\sup_{x \in \intcc{-1}{1}} \abs{T_n(x)} = 1$ , bereikt in $n + 1$ punten van $\intcc{-1}{1}$ .

Oplossing

Oplossing van Oefening 8.10.

Inductie (twee basisgevallen gelden). Met $\cos(n+1)\theta + \cos(n-1)\theta = 2\cos\theta\cos n\theta$ :

$T_{n+1}(\cos\theta) = 2\cos\theta \cos n\theta - \cos(n-1)\theta = \cos(n+1)\theta .$
$T_n(\cos\theta) = 0$ dan en slechts dan als $n\theta \equiv \frac\pi2 \pmod \pi$ : de getallen

$x_k = \cos\Bigl(\frac{(2k+1)\pi}{2n}\Bigr), \qquad k = 0, 1, \dots, n-1,$

zijn $n$ verschillende punten van $\intoo{-1}{1}$ (de hoeken liggen in $\intoo{0}{\pi}$ waar $\cos$ injectief is), alle wortels van $T_n$ ; aangezien $\deg T_n = n$ (uit de recurrentie, met leidende coëfficiënt $2^{n-1}$ voor $n \geq 1$ , door inductie), zijn dit alle wortels, elk enkelvoudig.
Voor $x = \cos\theta \in \intcc{-1}{1}$ : $\abs{T_n(x)} = \abs{\cos n\theta} \leq 1$ , met gelijkheid dan en slechts dan als $n\theta \equiv 0 \pmod\pi$ , d.w.z. in de $n+1$ punten $y_k = \cos\frac{k\pi}{n}$ , $k = 0, \dots, n$ , waar $T_n(y_k) = (-1)^k$ . (Deze equioscillatie maakt $2^{1-n}T_n$ tot de monische veelterm van graad $n$ met de kleinste supnorm op $\intcc{-1}{1}$ — bewezen in het weekendprobleem van dit hoofdstuk.)

Oefening 8.11 ★★★

Laat $P \in \C[X]$ niet-constant zijn met verschillende wortels $a_1, \dots, a_r$ (multipliciteiten $m_1, \dots, m_r$ ). Bewijs de identiteit van rationale functies

\frac{P'(X)}{P(X)} = \sum_{i=1}^{r} \frac{m_i}{X - a_i},

en leid de stelling van Gauss–Lucas af: elke wortel van $P'$ ligt in het convexe omhulsel van de wortels van $P$ (evalueer de identiteit in een wortel $w$ van $P'$ die geen wortel van $P$ is, neem toegevoegden, en lees het resultaat af als $w$ een gewogen gemiddelde van de $a_i$ ).

Oplossing

Oplossing van Oefening 8.11.

Schrijf $P = c\prod_i (X - a_i)^{m_i}$ . De productregel (uitgebreid tot meerdere factoren) geeft

P' = c\sum_{i} m_i (X - a_i)^{m_i - 1} \prod_{k \neq i} (X - a_k)^{m_k},

en delen door $P$ : $\frac{P'}{P} = \sum_i \frac{m_i}{X - a_i}$ (als rationale functies, d.w.z. weg van de wortels).

Laat $w$ een wortel van $P'$ zijn. Als $w$ een van de $a_i$ is, ligt het triviaal in het convexe omhulsel. Anders, bij evaluatie in $w$ :

0 = \sum_i \frac{m_i}{w - a_i} = \sum_i m_i\, \frac{\conj w - \conj a_i}{\abs{w - a_i}^2} .

Toevoegen: $\sum_i \lambda_i (w - a_i) = 0$ waarbij $\lambda_i = \frac{m_i}{\abs{w - a_i}^2} > 0$ . Dus

w = \frac{\sum_i \lambda_i a_i}{\sum_i \lambda_i} :

een convexe combinatie (positieve gewichten die na normalisatie tot $1$ sommeren) van de wortels $a_i$ . Dus elke wortel van $P'$ ligt in het convexe omhulsel van de wortels van $P$ .

Oefening 8.12 ★★

(Filter met eenheidswortels) Laat $n \in \N^*$ en $j = \eu^{2\iu\pi/3}$ . Bewijs door $(1 + X)^n$ in $1$ , $j$ en $j^2$ te evalueren dat

\sum_{k \geq 0} \binom{n}{3k} = \frac{2^n + 2\cos\frac{n\pi}{3}}{3} ,

en controleer de formule voor $n = 3$ en $n = 6$ . Hint: $1 + j^m + j^{2m}$ is gelijk aan $3$ als $3 \mid m$ en $0$ anders; en $1 + j = \eu^{\iu\pi/3}$ .

Oplossing

Oplossing van Oefening 8.12.

Sommeer de evaluaties van $(1 + X)^n$ in de drie derdemachtseenheidswortels:

2^n + (1 + j)^n + (1 + j^2)^n = \sum_{k=0}^n \binom nk\,\bigl(1 + j^k + j^{2k}\bigr) = 3\sum_{k\,:\,3\mid k}\binom nk ,

aangezien $1 + j^k + j^{2k}$ een meetkundige som is die gelijk is aan $3$ wanneer $3 \mid k$ en aan $\frac{j^{3k} - 1}{j^k - 1} = 0$ anders. Nu is $1 + j = \frac12 + \iu\frac{\sqrt3}2 = \eu^{\iu\pi/3}$ en $1 + j^2 = \conj{1 + j} = \eu^{-\iu\pi/3}$ , dus $(1+j)^n + (1+j^2)^n = 2\cos\frac{n\pi}3$ en

\sum_{k\geq0}\binom n{3k} = \frac{2^n + 2\cos\frac{n\pi}3}{3} .

Controles: $n = 3$ : $\frac{8 + 2\cos\pi}3 = 2 = \binom30 + \binom33$ ; $n = 6$ : $\frac{64 + 2}3 = 22 = 1 + 20 + 1$ .

8.5 Probleem: Tsjebysjev-veeltermen en de vlakste veelterm

Probleem 8.1

Van alle monische veeltermen van graad $n$ , welke blijft het dichtst bij nul op $\intcc{-1}1$ ? Het antwoord — de stelling van Tsjebysjev, de geboorteakte van de approximatietheorie — is $2^{1-n}T_n$ , waarbij $T_n$ de Tsjebysjev-veelterm van Oefening 8.10 is, en geen enkele monische concurrent kan zijn afwijking $2^{1-n}$ verslaan. Dit probleem ontwikkelt de algebra van de familie $(T_n)$ (samenstellingswet, expliciete coëfficiënten, de tweedesoortfamilie $U_n$ , een differentiaalvergelijking), bewijst de extremaliteitsstelling met haar gelijkheidsgeval, en verzamelt toepassingen: optimale interpolatieknopen, de exacte waarde van $\cos 36^\circ$ , en een congruentie $T_p \equiv X^p \pmod p$ . Overal is $T_0 = 1$ , $T_1 = X$ , $T_{n+1} = 2X\,T_n - T_{n-1}$ , en gebruiken we vrijelijk $T_n(\cos\theta) = \cos n\theta$ uit Oefening 8.10.

Deel I — De familie $(T_n)$ .

Bereken $T_2, T_3, T_4, T_5$ uit de recurrentie. (Vergelijk $T_3$ met de identiteit $\cos3\theta = 4\cos^3\theta - 3\cos\theta$ uit Voorbeeld 3.9.)
Bewijs door inductie: $\deg T_n = n$ met leidende coëfficiënt $2^{n-1}$ voor $n \geq 1$ , en $T_n$ heeft de pariteit van $n$ (alleen even of alleen oneven machten verschijnen).
Bewijs het uniciteitsprincipe: $T_n$ is de enige veelterm die voldoet aan $P(\cos\theta) = \cos n\theta$ voor alle $\theta$ . (Twee veeltermen die op $\intcc{-1}1$ overeenkomen, komen overal overeen: Gevolg 8.8.)
Leid de samenstellings- en productwetten af:

$T_m \circ T_n = T_{mn}, \qquad 2\,T_m T_n = T_{m+n} + T_{\abs{m-n}} .$
Herinner uit Oefening 8.10 de wortels $x_k = \cos\frac{(2k+1)\pi}{2n}$ en de equioscillatiepunten $y_k = \cos\frac{k\pi}n$ met $T_n(y_k) = (-1)^k$ . Schrijf de volledige ontbinding van $T_n$ over $\R$ op, en verantwoord dat de $y_k$ afwisselen met de $x_k$ : $y_n < x_{n-1} < y_{n-1} < \dots < x_0 < y_0$ .
Bewijs dat $T_n(\cosh t) = \cosh(nt)$ voor alle $t \in \R$ (dezelfde inductie, met behulp van Propositie 4.18), en leid voor $x \geq 1$ de gesloten vorm af

$T_n(x) = \frac{\bigl(x + \sqrt{x^2 - 1}\bigr)^n + \bigl(x - \sqrt{x^2 - 1}\bigr)^n}{2} ,$

zodat $T_n(x) > 1$ voor $x > 1$ : buiten $\intcc{-1}1$ ontsnapt de veelterm onmiddellijk.

Deel II — Coëfficiënten, de familie $U_n$ , een differentiaalvergelijking.

Bewijs uit de formule van de Moivre (Gevolg 3.8) de expliciete uitdrukking

$T_n(x) = \sum_{0 \leq 2j \leq n} \binom{n}{2j}\, x^{\,n-2j}\,(x^2 - 1)^j ,$

en verifieer haar voor $n = 3$ .
Bereken $T_n(1)$ , $T_n(-1)$ en $T_n(0)$ voor alle $n$ .
Definieer $U_n$ (tweede soort) door $U_0 = 1$ , $U_1 = 2X$ , $U_{n+1} = 2X\,U_n - U_{n-1}$ . Bewijs dat $U_n(\cos\theta) = \frac{\sin(n+1)\theta}{\sin\theta}$ voor $\theta \notin \pi\Z$ , en dat $T_n' = n\,U_{n-1}$ voor $n \geq 1$ .
Bewijs dat $\abs{\sin n\theta} \leq n\,\abs{\sin\theta}$ voor alle $\theta$ (inductie), en leid de Markov-achtige grens af

$\abs{T_n'(x)} \leq n^2 \quad\text{op } \intcc{-1}1, \qquad\text{met } T_n'(\pm1) = (\pm1)^{n-1}\,n^2 .$
Toon aan dat $y = T_n$ voldoet aan de differentiaalvergelijking

$(1 - x^2)\,y'' - x\,y' + n^2\,y = 0 ,$

door de identiteit $\sin\theta\, T_n'(\cos\theta) = n\sin n\theta$ af te leiden naar $\theta$ ; verifieer rechtstreeks voor $T_2$ .

Deel III — De extremaliteitsstelling van Tsjebysjev. Laat $\widetilde T_n = 2^{1-n}\,T_n$ (monisch volgens vraag 2) en schrijf $\norm{P}_\infty = \sup_{x \in \intcc{-1}1}\abs{P(x)}$ .

Verantwoord $\norm{\widetilde T_n}_\infty = 2^{1-n}$ , bereikt met afwisselende tekens in de $n + 1$ punten $y_n < \dots < y_0$ .
Veronderstel dat een monische $P$ van graad $n$ zou voldoen aan $\norm P_\infty < 2^{1-n}$ , en stel $D = \widetilde T_n - P$ . Toon aan dat $\deg D \leq n - 1$ , en dat $D(y_k)$ het strikte teken van $(-1)^k$ heeft voor elke $k = 0, \dots, n$ .
Leid af dat $D$ ten minste $n$ verschillende reële wortels heeft (één in elke tussenruimte, volgens de tussenwaarde-eigenschap, hier gebruikt op middelbareschoolniveau en bewezen in Hoofdstuk 13), en concludeer de stelling van Tsjebysjev: elke monische $P$ van graad $n$ voldoet aan

$\norm{P}_\infty \geq 2^{1-n} .$
(Gelijkheidsgeval, eerste stap) Veronderstel nu $\norm P_\infty = 2^{1-n}$ exact, $P$ monisch van graad $n$ , en laat $D = \widetilde T_n - P$ . Toon aan dat $(-1)^kD(y_k) \geq 0$ voor alle $k$ , en dat als $D(y_k) = 0$ voor een inwendig punt $y_k$ ( $0 < k < n$ ), dan $D'(y_k) = 0$ eveneens. (In een inwendig $y_k$ bereiken zowel $\widetilde T_n$ als $P$ een extremum van absolute waarde $\norm{\cdot} _\infty$ ; een afleidbare functie heeft nulafgeleide in een inwendig extremum — gebruikt op middelbareschoolniveau, bewezen in Hoofdstuk 14.)
(Gelijkheidsgeval, conclusie) Tel de wortels van $D$ met multipliciteit om aan te tonen dat $D = 0$ : de minimalisator is uniek, $P = \widetilde T_n$ .
Breng over naar een willekeurig segment $\intcc ab$ : toon aan dat de minimale supnorm van een monische veelterm van graad $n$ op $\intcc ab$ gelijk is aan $2\bigl(\frac{b-a}4\bigr)^n$ , bereikt door een herschaalde Tsjebysjev-veelterm. (Substitueer $x = \frac{a+b}2 + \frac{b-a}2\,t$ en volg de leidende coëfficiënt.)

Deel IV — Toepassingen.

Werk het geval $n = 3$ met de hand uit: lokaliseer de extrema van $\widetilde T_3 = X^3 - \frac34X$ op $\intcc{-1}1$ , verifieer de viervoudige equioscillatie met waarde $\frac14$ , en concludeer dat geen enkele monische derdegraadsveelterm het beter doet.
(Optimale interpolatieknopen) Voor $n + 1$ knopen $x_0, \dots, x_n \in \intcc{-1}1$ wordt de interpolatiefout beheerst door $\omega(X) = \prod_i (X - x_i)$ (zoals Hoofdstuk 16 zal kwantificeren). Bewijs dat de keuze die $\norm\omega_\infty$ minimaliseert de verzameling $n + 1$ wortels van $T_{n+1}$ is, met $\norm\omega_\infty = 2^{-n}$ : Tsjebysjev-knopen zijn de juiste plaatsen om te interpoleren.
Bewijs met behulp van $T_5$ dat $c = \cos 36^\circ$ voldoet aan $16c^5 - 20c^3 + 5c + 1 = 0$ , ontbind deze veelterm als $(x + 1)(4x^2 - 2x - 1)^2$ , en concludeer

$\cos 36^\circ = \frac{1 + \sqrt5}4 .$

Controleer de consistentie met $\cos 72^\circ = \frac{\sqrt5 - 1}4$ uit Oefening 3.8.
Schat $T_{10}(1.1)$ met de gesloten vorm van vraag 6 (twee significante cijfers volstaan), en interpreteer: een veelterm begrensd door $1$ op $\intcc{-1}1$ kan al meer dan $40$ overschrijden in $x = 1.1$ . (Dat $T_n$ het snelst groeit onder zulke veeltermen is nog een extremale eigenschap van de familie, buiten dit probleem.)
Bewijs de congruentie: voor elk oneven priemgetal $p$ zijn alle coëfficiënten van $T_p - X^p$ deelbaar door $p$ . (Gebruik vraag 7 en $p \mid \binom p{2j}$ voor $0 < 2j < p$ , uit het bewijs van Stelling 6.23.) Verifieer op $T_3$ en $T_5$ .

Deel V — Synthese.

Bereken expliciet de monische kwadratische met minimale supnorm op $\intcc01$ en haar afwijking. (Vraag 17 met $n = 2$ .)
Waar gebruikte het probleem precies: (i) de starheid van veeltermen (Gevolg 8.8); (ii) de trigonometrie van Hoofdstuk 3 en Hoofdstuk 4; (iii) de rekenkunde van binomiaalcoëfficiënten uit Hoofdstuk 6? Eén zin elk.
Synthese, in een korte alinea: de stelling zegt dat de vlakste monische veelterm degene is die equioscilleert, en het bewijs zet optimaliteit om in worteltelling. Becommentarieer dit mechanisme, de rol van de substitutie $x = \cos\theta$ als brug tussen algebra en trigonometrie, en noem de twee plaatsen waar het probleem analysefeiten (tussenwaardestelling, inwendig extremum) nodig had die latere hoofdstukken bewijzen.

Oplossing

Oplossing van Probleem 8.1.

1. $T_2 = 2X^2 - 1$ ; $T_3 = 2X(2X^2 - 1) - X = 4X^3 - 3X$ ; $T_4 = 2X\,T_3 - T_2 = 8X^4 - 8X^2 + 1$ ; $T_5 = 2X\,T_4 - T_3 = 16X^5 - 20X^3 + 5X$ . De identiteit $T_3(\cos\theta) = \cos3\theta$ is precies $\cos3\theta = 4\cos^3\theta - 3\cos\theta$ uit Voorbeeld 3.9.

2. Waar voor $n = 1, 2$ . Als $T_{n-1}$ , $T_n$ graden $n-1$ , $n$ en leidende coëfficiënten $2^{n-2}$ , $2^{n-1}$ hebben, dan heeft $2X\,T_n$ graad $n+1$ en leidende coëfficiënt $2^n$ , terwijl $T_{n-1}$ lagere graad heeft: $T_{n+1}$ heeft graad $n + 1$ , leidende coëfficiënt $2^n$ . Pariteit: als $T_{n-1}$ de pariteit van $n - 1$ heeft en $T_n$ die van $n$ , dan hebben $2X\,T_n$ en $T_{n-1}$ beide de pariteit van $n + 1$ , dus ook $T_{n+1}$ .

3. Als $P(\cos\theta) = \cos n\theta$ voor alle $\theta$ , dan komen $P$ en $T_n$ in elk punt van $\intcc{-1}1$ overeen — een oneindige verzameling — dus $P - T_n$ heeft oneindig veel wortels en is de nulveelterm (Gevolg 8.8).

4. Voor $x = \cos\theta$ : $T_m(T_n(\cos\theta)) = T_m(\cos n\theta) = \cos(mn\theta) = T_{mn}(\cos\theta)$ , en $2T_mT_n(\cos\theta) = 2\cos m\theta\cos n\theta = \cos(m+n)\theta + \cos\abs{m - n}\theta$ . Beide identiteiten gelden op $\intcc{-1}1$ , dus als veeltermidentiteiten volgens het argument van vraag 3.

5. De $x_k$ zijn $n$ verschillende enkelvoudige wortels en de leidende coëfficiënt is $2^{n-1}$ :

T_n = 2^{n-1}\prod_{k=0}^{n-1} \Bigl(X - \cos\frac{(2k+1)\pi}{2n}\Bigr) .

Afwisseling: de hoeken $0 < \frac{\pi}{2n} < \frac\pi n < \frac{3\pi}{2n} < \frac{2\pi}n < \dots < \pi$ wisselen af tussen de $y$ -hoeken $\frac{k\pi}n$ en de $x$ -hoeken $\frac{(2k+1)\pi}{2n}$ ; aangezien $\cos$ strikt dalend is op $\intcc0\pi$ , wisselen de waarden af in de omgekeerde volgorde: $y_n < x_{n-1} < y_{n-1} < \dots < x_0 < y_0$ . Tussen twee opeenvolgende extrema zit precies één wortel, zoals een plaatje van $\cos n\theta$ suggereert.

6. Inductie met $2\cosh a\cosh b = \cosh(a + b) + \cosh(a - b)$ (Propositie 4.18): $T_{n+1}(\cosh t) = 2\cosh t\cosh nt - \cosh(n-1)t = \cosh(n+1)t$ . Voor $x \geq 1$ , schrijf $x = \cosh t$ met $t \geq 0$ ; dan $\eu^t = x + \sqrt{x^2 - 1}$ en $\eu^{-t} = x - \sqrt{x^2 - 1}$ , dus

T_n(x) = \cosh(nt) = \frac{(x + \sqrt{x^2-1})^n + (x - \sqrt{x^2-1})^n}2 .

Voor $x > 1$ overschrijdt de eerste term strikt $\frac12(1)^n$ en groeit meetkundig: $T_n(x) > 1$ .

7. De Moivre: $\cos n\theta = \Re\bigl((\cos\theta + \iu\sin\theta)^n\bigr) = \sum_{2j \leq n}\binom n{2j} \cos^{n-2j}\theta\,(\iu\sin\theta)^{2j}$ , en $(\iu\sin\theta)^{2j} = (-\sin^2\theta)^j = (\cos^2\theta - 1)^j$ . Substitutie van $x = \cos\theta$ en beroep op vraag 3:

T_n(x) = \sum_{0\leq 2j\leq n}\binom n{2j}x^{n-2j}(x^2 - 1)^j .

Voor $n = 3$ : $\binom30 x^3 + \binom32 x(x^2 - 1) = x^3 + 3x^3 - 3x = 4x^3 - 3x$ , zoals in vraag 1.

8. $T_n(1) = \cos(n\cdot0) = 1$ ; $T_n(-1) = \cos(n\pi) = (-1)^n$ ; $T_n(0) = \cos\frac{n\pi}2$ , wat $0$ is voor oneven $n$ en $(-1)^{n/2}$ voor even $n$ .

9. Inductie voor $U_n(\cos\theta) = \frac{\sin(n+1)\theta}{\sin\theta}$ : waar voor $U_0 = 1$ en $U_1 = 2X$ ( $\sin2\theta = 2\sin\theta\cos\theta$ ); de stap is de som-naar-product-identiteit $\sin(n+2)\theta = 2\cos\theta\, \sin(n+1)\theta - \sin n\theta$ . Leid nu $T_n(\cos\theta) = \cos n\theta$ af naar $\theta$ : $-\sin\theta\,T_n'(\cos\theta) = -n\sin n\theta$ , dus voor $\theta \notin \pi\Z$ :

T_n'(\cos\theta) = n\,\frac{\sin n\theta}{\sin\theta} = n\,U_{n-1}(\cos\theta) ,

en de veeltermen $T_n'$ en $nU_{n-1}$ , die op $\intoo{-1}1$ overeenkomen, zijn gelijk.

10. $\abs{\sin(n+1)\theta} = \abs{\sin n\theta\cos\theta + \cos n\theta\sin\theta} \leq \abs{\sin n\theta} + \abs{\sin\theta}$ , en inductie geeft $\abs{\sin n\theta} \leq n\abs{\sin\theta}$ . Dus $\abs{U_{n-1}} \leq n$ op $\intoo{-1}1$ en $\abs{T_n'} = n\abs{U_{n-1}} \leq n^2$ daar; in $\pm1$ strekt de grens zich uit door limieten te nemen (of rechtstreeks: $U_{n-1}(1) = n$ uit de recurrentie, $U_n(1) = n + 1$ door inductie, en de pariteit geeft $U_{n-1}(-1) = (-1)^{n-1}n$ ). Dus $T_n'(1) = n^2$ en $T_n'(-1) = (-1)^{n-1}n^2$ : de grens $n^2$ wordt bereikt in de eindpunten.

11. Leid $\sin\theta\,T_n'(\cos\theta) = n\sin n\theta$ (vraag 9) af naar $\theta$ :

\cos\theta\,T_n'(\cos\theta) - \sin^2\theta\,T_n''(\cos\theta) = n^2\cos n\theta = n^2\,T_n(\cos\theta) .

Met $x = \cos\theta$ en $\sin^2\theta = 1 - x^2$ : $x\,T_n' - (1 - x^2)T_n'' = n^2T_n$ op $\intcc{-1}1$ , dus overal: $(1 - x^2)y'' - xy' + n^2y = 0$ voor $y = T_n$ . Controle voor $T_2 = 2x^2 - 1$ : $(1 - x^2)(4) - x(4x) + 4(2x^2 - 1) = 4 - 4x^2 - 4x^2 + 8x^2 - 4 = 0$ .

12. $\widetilde T_n$ is monisch (vraag 2) en $\abs{\widetilde T_n} = 2^{1-n}\abs{T_n} \leq 2^{1-n}$ op $\intcc{-1}1$ , met $\widetilde T_n(y_k) = (-1)^k2^{1-n}$ in de $n + 1$ punten $y_k$ (Oefening 8.10): de norm is precies $2^{1-n}$ , bereikt met afwisselende tekens.

13. $\widetilde T_n$ en $P$ zijn beide monisch van graad $n$ , dus de leidende termen heffen elkaar op: $\deg D \leq n - 1$ . In $y_k$ : $D(y_k) = (-1)^k2^{1-n} - P(y_k)$ , en $\abs{P(y_k)} \leq \norm P_\infty < 2^{1-n}$ dwingt het teken van $D(y_k)$ om dat van $(-1)^k2^{1-n}$ te zijn, strikt.

14. $D$ verandert van teken tussen $y_{k+1}$ en $y_k$ voor elke $k = 0, \dots, n-1$ : volgens de tussenwaarde-eigenschap heeft $D$ een wortel in elk van deze $n$ paarsgewijs disjuncte open intervallen — $n$ verschillende wortels voor een niet-nulveelterm van graad $\leq n - 1$ , onmogelijk. En $D = 0$ is ook onmogelijk (de normen verschillen). Tegenspraak: geen enkele monische $P$ van graad $n$ heeft $\norm P_\infty < 2^{1-n}$ , wat de stelling van Tsjebysjev is.

15. Nu is $\abs{P(y_k)} \leq 2^{1-n}$ alleen, dus $(-1)^k D(y_k) = 2^{1-n} - (-1)^kP(y_k) \geq 2^{1-n} - \abs{P(y_k)} \geq 0$ . Veronderstel $D(y_k) = 0$ in een inwendig $y_k$ ( $0 < k < n$ ): dan $P(y_k) = (-1)^k2^{1-n}$ , dus $\abs P$ bereikt zijn supremum $2^{1-n}$ in het inwendige punt $y_k$ , waaruit $P'(y_k) = 0$ (inwendig extremum); en $T_n'(y_k) = nU_{n-1}(y_k) = 0$ aangezien $\sin(n\cdot\frac{k\pi}n) = 0$ — dus $\widetilde T_n'(y_k) = 0$ eveneens, en $D'(y_k) = 0$ : $y_k$ is een wortel van $D$ van multipliciteit ten minste $2$ .

16. Tel de wortels van $D$ met multipliciteit. Laat $z$ het aantal inwendige punten $y_k$ zijn met $D(y_k) = 0$ (elk een dubbele wortel, volgens vraag 15) en $e \in \{0, 1, 2\}$ het aantal eindpunten ( $y_0$ of $y_n$ ) met $D = 0$ (elk ten minste een enkelvoudige wortel). Een tussenruimte $(y_{k+1}, y_k)$ waarvan beide eindpunten $D \neq 0$ hebben draagt strikt afwisselende tekens, dus een inwendige wortel. Elk verdwijnend inwendig punt bederft ten hoogste zijn twee aangrenzende tussenruimtes, elk verdwijnend eindpunt ten hoogste één tussenruimte: ten minste $n - 2z - e$ tussenruimtes dragen nog elk één wortel bij, alle verschillend van de $y$ -wortels. Totaal: ten minste $(n - 2z - e) + 2z + e = n$ wortels met multipliciteit, voor een veelterm van graad $\leq n - 1$ : dus $D = 0$ en $P = \widetilde T_n$ . De minimalisator is uniek.

17. De affiene afbeelding $t \mapsto x = \frac{a+b}2 + \frac{b-a}2\,t$ is een bijectie $\intcc{-1}1 \to \intcc ab$ . Als $P$ monisch van graad $n$ is, dan is $Q(t) = P(x(t))$ een veelterm in $t$ met leidende coëfficiënt $\bigl(\frac{b-a}2\bigr)^n$ , en $\sup_{\intcc ab}\abs P = \sup_{\intcc{-1}1}\abs Q$ . De monische veelterm $Q/\bigl(\frac{b-a}2\bigr)^n$ heeft supnorm $\geq 2^{1-n}$ (vragen 13–14), dus

\sup_{\intcc ab}\abs P \geq \Bigl(\frac{b-a}2\Bigr)^n 2^{1-n} = 2\Bigl(\frac{b-a}4\Bigr)^n ,

met gelijkheid precies voor $P(x) = \bigl(\frac{b-a}2\bigr)^n \widetilde T_n\bigl(t(x)\bigr)$ (vraag 16).

18. $\widetilde T_3 = \frac{T_3}4 = X^3 - \frac34X$ ; $\widetilde T_3{}' = 3X^2 - \frac34$ verdwijnt in $\pm\frac12$ . Waarden: $\widetilde T_3(-1) = -\frac14$ , $\widetilde T_3(-\tfrac12) = \frac14$ , $\widetilde T_3(\tfrac12) = -\frac14$ , $\widetilde T_3(1) = \frac14$ : vier afwisselende extrema van absolute waarde $\frac14$ — dus $\norm{\widetilde T_3}_\infty = \frac14$ , en volgens de stelling van Tsjebysjev heeft geen enkele monische derdegraadsveelterm een kleinere supnorm op $\intcc{-1}1$ .

19. $\omega$ is monisch van graad $n + 1$ , dus $\norm\omega_\infty \geq 2^{-n}$ volgens de stelling van Tsjebysjev (graad $n+1$ ), met gelijkheid dan en slechts dan als $\omega = \widetilde T_{n+1} = 2^{-n}T_{n+1}$ (vraag 16), d.w.z. dan en slechts dan als de knopen de $n + 1$ wortels van $T_{n+1}$ zijn. Met Tsjebysjev-knopen is de foutfactor $\norm\omega_\infty$ gelijk aan $2^{-n}$ — de kleinst mogelijke.

20. $5 \times 36^\circ = 180^\circ$ , dus $T_5(c) = \cos180^\circ = -1$ : $16c^5 - 20c^3 + 5c + 1 = 0$ . Toetsen van $x = -1$ : $-16 + 20 - 5 + 1 = 0$ , en uitwerken bevestigt

16x^5 - 20x^3 + 5x + 1 = (x + 1)\bigl(4x^2 - 2x - 1\bigr)^2 .

Aangezien $c = \cos36^\circ \neq -1$ , is $c$ een wortel van $4x^2 - 2x - 1$ , waarvan de wortels $\frac{1 \pm \sqrt5}4$ zijn; aangezien $c > 0$ ,

\cos36^\circ = \frac{1 + \sqrt5}4 .

Consistentie: $\cos72^\circ = T_2(c) = 2c^2 - 1 = 2\cdot\frac{3 + \sqrt5}8 - 1 = \frac{\sqrt5 - 1}4$ , de waarde gevonden in Oefening 3.8.

21. $\sqrt{1.1^2 - 1} = \sqrt{0.21} \approx 0.458$ , dus $x + \sqrt{x^2-1} \approx 1.558$ en $(1.558)^{10} \approx 84.5$ , terwijl $(1.1 - 0.458)^{10} \approx 0.01$ : $T_{10}(1.1) \approx \frac{84.5 + 0.01}2 \approx 42$ . Een veelterm gevangen in $\intcc{-1}1$ op het interval is al voorbij $40$ gegroeid één tiende buiten zijn rand: begrensdheid op een segment zegt niets een duimbreed erbuiten.

22. In de formule van vraag 7 voor $T_p$ is de term $j = 0$ gelijk aan $X^p$ ; elke andere term draagt $\binom p{2j}$ met $0 < 2j < p$ (merk op $2j \neq p$ aangezien $p$ oneven is), die deelbaar is door $p$ volgens de eerste stap van het bewijs van Stelling 6.23. Dus elke coëfficiënt van $T_p - X^p$ is een veelvoud van $p$ . Controles: $T_3 - X^3 = 3X^3 - 3X = 3(X^3 - X)$ ; $T_5 - X^5 = 15X^5 - 20X^3 + 5X = 5(3X^5 - 4X^3 + X)$ .

23. Volgens vraag 17 met $\intcc ab = \intcc01$ en $n = 2$ : minimale afwijking $2\bigl(\frac14\bigr)^2 = \frac18$ , bereikt door $\bigl(\frac12\bigr)^2\widetilde T_2(2x - 1) = \frac14\bigl((2x-1)^2 - \frac12\bigr) = x^2 - x + \frac18$ . De monische kwadratische die het dichtst bij nul ligt op $\intcc01$ is $x^2 - x + \frac18$ , met supnorm $\frac18$ .

24. (i) Starheid — een veelterm met meer wortels dan zijn graad is nul — voedde het uniciteitsprincipe (vraag 3), de overdracht van trigonometrische identiteiten naar veeltermidentiteiten (vragen 4, 7, 9, 11), en beide worteltellingsargumenten van het extremaliteitsbewijs (vragen 14, 16). (ii) De trigonometrie van Hoofdstuk 3 (de Moivre, som-naar-product) en de hyperbolische functies van Hoofdstuk 4 leverden elke identiteit achter de familie; de substitutie $x = \cos\theta$ is de brug. (iii) De deelbaarheid $p \mid \binom p{2j}$ uit Hoofdstuk 6 zette de coëfficiëntenformule om in de congruentie van vraag 22.

25. De stelling van Tsjebysjev zet een optimalisatie over een oneindig-dimensionale familie (alle monische veeltermen) om in eindige combinatoriek: een concurrent beter dan $\widetilde T_n$ zou ervan verschillen door een veelterm van lage graad die $n$ keer van teken moet veranderen — één wortel meer dan zijn graad toelaat. Het equioscillatiepatroon is dus geen curiositeit maar het certificaat zelf van optimaliteit, en het gelijkheidsgeval verscherpt de worteltelling met multipliciteiten. De substitutie $x = \cos\theta$ verdient het laatste woord: ze transporteert de starre, discrete wereld van veeltermen naar de periodieke wereld van de trigonometrie, waar wortels en extrema van $T_n$ eenvoudig het regelmatige raster van $\cos n\theta$ zijn. De twee ontleende analysefeiten — de tussenwaarde-eigenschap (vraag 14; bewezen in Hoofdstuk 13) en de verdwijnende afgeleide in een inwendig extremum (vraag 15; bewezen in Hoofdstuk 14) — zijn precies de gereedschappen die die latere hoofdstukken zullen teruggeven, waarmee de lus gesloten wordt.

8.1 De ring K[X]K[X]K[X]

8.2 Wortels

8.3 Coëfficiënten en wortels

8.4 Oefeningen

8.5 Probleem: Tsjebysjev-veeltermen en de vlakste veelterm

8.1 De ring $K[X]$