Algoritmus (Bézier–Horner).

BEGIN IF t^{∗} ≤ \frac{1}{2} THEN BEGIN

b := b_{n};

FOR i := 1 TO n DO b := b · \frac{i}{n−i+1} · \frac{t^{∗}}{1−t^{∗}} + b_{n−i};
b := (1 − t^{∗})^{n}.b;

END ELSE BEGIN

b := b_{0};

FOR i := 0 TO n − 1 DO b := b · \frac{i+1}{n−i} · \frac{1−t^{∗}}{t^{∗}} + b_{i+1} ;
b := (t^{∗})^{n}.b;

END; b(t^{∗}) := b;

END.

Věta (Korektnost Bézierova–Hornerova algoritmu).

Bézierův–Hornerův algoritmus je korektní, tj. jeho výsledek splývá s výsledkem Casteljauova algoritmu.

Důkaz.

Nejprve provedeme důkaz pro t^{∗} ≤ \frac{1}{2}. Označme výsledky v jednotlivých krocích cyklu FOR

b^{0} = b_{n}; b^{i} = b^{i−1} · \frac{i}{n − i + 1} · \frac{t^{∗}}{1 − t^{∗}} + b_{n−i}, i = 1, …, n.

Dokážeme indukcí, že pro i = 1, …, n pak platí

b^{i} = b_{n−i} + ∑_{j=n−i+1}^{n} b_{j} · (\frac{t^{∗}}{1 − t^{∗}})^{i+j−n} · \frac{(n + 1 − j) ⋯ i}{(n + 1 − i) ⋯ j} ·  (ℸ)

Pro i = 1 dostáváme b^{1} = b^{0} · \frac{1}{n} · \frac{t^{∗}}{1−t^{∗}} + b_{n−1} = b_{n−1} + b_{n} · \frac{t^{∗}}{1−t^{∗}} · \frac{1}{n}· Pro i > 1 potom

b^{i} = b^{i−1} · \frac{1}{n − i + 1} · \frac{t^{∗}}{1 − t^{∗}} + b_{n−i} =

= [b_{n−i+1} + ∑_{j=n−i+2}^{n} b_{j} · (\frac{t^{∗}}{1 − t^{∗}})^{i−1+j−n} · \frac{(n + 1 − j) ⋯ (i − 1)}{(n + 2 − i) ⋯ j} ] · \frac{i}{n − i + 1} · \frac{t^{∗}}{1 − t^{∗}} + b_{n−i} =

= b_{n−i} + [b_{n−i+1} · \frac{t^{∗}}{1 − t^{∗}} · \frac{i}{n − i + 1} + ∑_{j=n−i+2}^{n} b_{j} · (\frac{t^{∗}}{1 − t^{∗}})^{i+j−n} · \frac{(n + 1 − j) ⋯ i}{(n − i + 1) ⋯ j} ] =

= b_{n−i} + ∑_{j=n−i+1}^{n} b_{j} · (\frac{t^{∗}}{1 − t^{∗}})^{i+j−n} · \frac{(n + 1 − j) ⋯ i}{(n − i + 1) ⋯ j} ·

Tedy skutečně výsledek v i-tém kroku cyklu FOR je dán vztahem (ℸ). Nyní s použitím (ℸ) dostaneme

b(t^{∗}) = (1 − t^{∗})^{n}.b^{n} = (1 − t^{∗})^{n}. [b_{0} + ∑_{j=1}^{n}b_{j} · (\frac{t^{∗}}{1 − t^{∗}})^{j} · \frac{(n − j + 1) ⋯ n}{1 ⋯ j} · \frac{(n − j)!}{(n − j)!}] =

= b_{0}.1.(t^{∗})^{0}(1 − t^{∗})^{n−0} + ∑_{j=1}^{n}b_{j} · \frac{n!}{j!(n − j!)} · (t^{∗})^{j}(1 − t^{∗})^{n−j} =

= ∑_{j=0}^{n}b_{j}.\binom{n}{j}(t^{∗})^{j}(1 − t^{∗})^{n−j} = ∑_{j=0}^{n}b_{j}B_{j}^{n}(t^{∗}).

A nyní provedeme důkaz pro t^{∗} > \frac{1}{2}. Opět označíme výsledky po krocích cyklu FOR

b^{0} = b_{0}; b^{i} = b^{i−1} · \frac{i}{n − i + 1} · \frac{1 − t^{∗}}{t^{∗}} + b_{i}, i = 1, …, n.

Dokážeme indukcí, že pro i = 1, …, n pak platí

b^{i} = b_{i} + ∑_{j=0}^{i−1}b_{j} · (\frac{1 − t^{∗}}{t^{∗}} )^{i−j} · \frac{i ⋯ (j + 1)}{(n − i + 1) ⋯ (n − j)} ·  (ℷ)

Pro i = 1 dostáváme b^{1} = b^{0} · \frac{1}{n} · \frac{1−t^{∗}}{t^{∗}} + b_{1} = b_{1} + b_{0} · \frac{1−t^{∗}}{t^{∗}} · \frac{1}{n}· Pro i > 1 potom

b^{i} = b^{i−1} · \frac{1}{n − i + 1} · \frac{1 − t^{∗}}{t^{∗}} + b_{i} =

= [b_{i−1} + ∑_{j=0}^{i−2}b_{j} · (\frac{1 − t^{∗}}{t^{∗}} )^{i−1−j} · \frac{(i − 1) ⋯ (j + 1)}{(n − i + 2) ⋯ (n − j)} ] · \frac{i}{n − i + 1} · \frac{1 − t^{∗}}{t^{∗}} + b_{i} =

= b_{i} + [b_{i−1} · \frac{1 − t^{∗}}{t^{∗}} · \frac{i}{n − i + 1} + ∑_{j=0}^{i−2}b_{j} · (\frac{1 − t^{∗}}{t^{∗}} )^{i−j} · \frac{i ⋯ (j + 1)}{(n − i + 1) ⋯ (n − j)} ] =

= b_{i} + ∑_{j=0}^{i−1}b_{j} · (\frac{1 − t^{∗}}{t^{∗}} )^{i−j} · \frac{i ⋯ (j + 1)}{(n − i + 1) ⋯ (n − j)} ·

Tedy skutečně výsledek po i-tém kroku cyklu FOR je dán vztahem (ℷ). Nyní s použitím (ℷ) dostaneme

b(t^{∗}) = (t^{∗})^{n}.b^{n} = (t^{∗})^{n}. [b_{n} + ∑_{j=0}^{n−1} b_{j} · (\frac{1 − t^{∗}}{t^{∗}} )^{n−j} · \frac{n … (j + 1)}{1 ⋯ (n − j)} · \frac{j!}{j!}] =

= b_{n}.1.(t^{∗})^{n−0}(1 − t^{∗})^{0} + ∑_{j=0}^{n−1} b_{j} · \frac{n!}{(n − j!)j!} · (t^{∗})^{j}(1 − t^{∗})^{n−j} =

= ∑_{j=0}^{n}b_{j}.\binom{n}{j}(t^{∗})^{j}(1 − t^{∗})^{n−j} = ∑_{j=0}^{n}b_{j}B_{j}^{n}(t^{∗}).

V obou případech jsme tak dospěli ke stejnému výsledku jako u Casteljauova algoritmu.

□

Typeset by AMS L^{A}TEX