Polynomials And Synthetic Division

1. Core Concept Overview & Intuition

A polynomial in one variable is an expression built from a variable, say $x$, and constants by repeated addition and multiplication, in which the variable appears only with non-negative whole-number powers. The largest such power that actually occurs with a non-zero coefficient is called the degree, and the constants multiplying each power are called coefficients. Polynomials are the most tractable class of functions in numerical work: they can be evaluated using only addition and multiplication, they can be added, subtracted, multiplied and divided by elementary algorithms, and their values can be computed with a controlled number of arithmetic operations. This last property is decisive, because every arithmetic operation performed on a machine introduces a small round-off error, so a procedure that evaluates a polynomial with fewer operations produces a smaller accumulated error.

Division of one polynomial by another is the central operation of this unit. The division algorithm asserts that when a polynomial $P(x)$ is divided by a non-zero polynomial $d(x)$, there exist a unique quotient $q(x)$ and a unique remainder $R(x)$ satisfying

$$
P(x)=d(x)\,q(x)+R(x),
$$

where the remainder is either the zero polynomial or has degree strictly smaller than the degree of the divisor. When the divisor is linear, that is $d(x)=x-r$ for some constant $r$, the remainder must be a constant, and the division algorithm takes the special form

$$
P(x)=(x-r)\,q(x)+R.
$$

The constant $R$ is precisely the value $P(r)$ of the polynomial at $x=r$. This single observation converts the problem of evaluating a polynomial at a point into a problem of division, and it converts the problem of locating roots into a problem of testing remainders.

Long division of polynomials is the direct analogue of long division of integers, but it is laborious: each step requires a multiplication and a subtraction, and the bookkeeping of descending powers is error-prone. Synthetic division is an economical procedure, or algorithm, for producing the quotient $q(x)$ and the remainder $R$ of the division algorithm when the divisor is linear. It works only with the coefficients, never with the powers of $x$, and it arranges the arithmetic in a compact array so that each coefficient is written once and each partial product is added immediately into the next column. Because it is used most often to obtain $R$, and because $R=P(r)$ by the remainder theorem, synthetic division doubles as a fast method for evaluating a polynomial. If $r$ is a root of the equation $P(x)=0$, then the remainder is zero, and the quotient produced by the same array is the polynomial that remains after the linear factor $x-r$ has been removed.

The procedure is best understood as a sequence of six mechanical steps applied to the coefficients of the polynomial written in descending powers of $x$. First, write the coefficients of the polynomial inside an upside-down division symbol, leaving space after the coefficients. Second, put the test zero $x=r$ at the left of the symbol. Third, take the first number inside, which represents the leading coefficient, and carry it down unchanged below the division symbol. Fourth, multiply this carried-down value by the test zero and carry the result up into the next column. Fifth, add down that column. Sixth, repeat the multiplication and addition until every column has been processed. The numbers obtained below the symbol, apart from the last, are the coefficients of the quotient in descending powers, and the last number is the remainder.

The same idea underlies the nested form of a polynomial, which is the algebraic identity behind the synthetic-division array. A polynomial such as

$$
P(x)=x^{3}-6x^{2}+3x-0.14
$$

can be rewritten by successively factoring out $x$ from the highest powers, giving the nested form

$$
P(x)=\bigl[(x-6)x+3\bigr]x-0.14.
$$

Evaluating the nested form requires only three multiplications and three additions, whereas evaluating the expanded form naively requires repeated powers and more operations. Since each operation carries a round-off error, the nested form reduces the relative error of the computed value by decreasing the number of computations. Synthetic division is, in effect, the nested-form evaluation organised as a table, and the two techniques should be studied together.

The unit therefore has three interlocking themes: the algebraic division algorithm and the remainder theorem; the synthetic-division algorithm as a compact computational realisation of that theorem; and the control of numerical error through economical evaluation, including the nested form. The earlier material on errors and approximation supplies the vocabulary of absolute, relative and percentage error, and the material on propagation of errors explains why reducing the operation count matters. The present notes develop these themes in order, with full attention to the definitions, the key words of the definitions, the causes of error and their mitigation, the computation of errors, and the pedagogical and feedback practices that accompany the lesson.

2. Mathematical Formalization & Core Definitions

2.1 Polynomials and the division algorithm

> Definition (Polynomial). A polynomial in the variable $x$ over the real numbers is an expression of the form

$$
> P(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots+a_{1}x+a_{0},
$$

> where $n$ is a non-negative integer, the coefficients $a_{0},a_{1},\dots,a_{n}$ are real constants, and $a_{n}\neq 0$. The integer $n$ is the degree of the polynomial, written $\deg P=n$, and $a_{n}$ is the leading coefficient. The constant $a_{0}$ is the constant term. A polynomial of degree zero is a non-zero constant, and the zero polynomial has no degree.

> Definition (Division algorithm for polynomials). Let $P(x)$ and $d(x)$ be polynomials with $d(x)\neq 0$. Then there exist unique polynomials $q(x)$ and $R(x)$ such that

$$
> P(x)=d(x)\,q(x)+R(x),
$$

> where either $R(x)$ is the zero polynomial or $\deg R<\deg d$. The polynomial $q(x)$ is the quotient and $R(x)$ is the remainder.

When the divisor is linear, $d(x)=x-r$, the remainder has degree less than one, so it is a constant $R$, and the division algorithm reads

$$
P(x)=(x-r)\,q(x)+R.
$$

> Definition (Root or zero). A number $r$ is a root, or zero, of the polynomial $P$ if $P(r)=0$. Equivalently, $r$ is a solution of the polynomial equation $P(x)=0$.

2.2 The remainder theorem and the factor theorem

> Theorem (Remainder theorem). If a polynomial $P(x)$ is divided by $x-r$, then the remainder is $P(r)$.

> Theorem (Factor theorem). The linear polynomial $x-r$ is a factor of $P(x)$ if and only if $P(r)=0$.

The factor theorem is the immediate corollary of the remainder theorem: substituting $x=r$ into $P(x)=(x-r)q(x)+R$ gives $P(r)=R$, so the remainder vanishes exactly when $r$ is a root.

2.3 Synthetic division: statement and algorithm

> Definition (Synthetic division). Synthetic division is an economical procedure, or algorithm, for producing the quotient $q(x)$ and the remainder $R$ of the division algorithm when the divisor is of the form $x-r$. It operates on the coefficients of $P$ alone and is often used to obtain $R$, which by the remainder theorem equals the function value $P(r)$. Thus $P(r)=R$. If $r$ is a root of $P(x)=0$, then $R=0$.

The algorithm proceeds as follows for a polynomial of degree $n$ with coefficients $a_{n},a_{n-1},\dots,a_{0}$ written in descending powers, with a zero inserted for any missing power.

1. Write the coefficients of the polynomial inside an upside-down division symbol, leaving space after the coefficients.
2. Put the test zero $x=r$ at the left of the symbol.
3. Take the first number inside, representing the leading coefficient, and carry it down unchanged below the division symbol.
4. Multiply this carried-down value by the test zero and carry the result up into the next column.
5. Add down the column.
6. Repeat steps 4 and 5 until every column has been processed.

The numbers below the symbol, except the last, are the coefficients of the quotient in descending powers, beginning with degree $n-1$. The last number is the remainder $R=P(r)$.

The array for a cubic $P(x)=a_{3}x^{3}+a_{2}x^{2}+a_{1}x+a_{0}$ divided by $x-r$ has the layout

$$
\begin{array}{c|cccc}
r & a_{3} & a_{2} & a_{1} & a_{0}\
& & r a_{3} & r b_{2} & r b_{1}\
\hline
& a_{3} & b_{2} & b_{1} & R
\end{array}
$$

where the entries are generated by the recurrence

$$
\begin{aligned}
b_{2} &= a_{2}+r a_{3},\
b_{1} &= a_{1}+r b_{2},\
R &= a_{0}+r b_{1}.
\end{aligned}
$$

The quotient is $q(x)=a_{3}x^{2}+b_{2}x+b_{1}$, and the remainder is $R$. Each entry below the line is obtained by multiplying the previous entry below the line by $r$ and adding the coefficient above it. This recurrence is exactly the nested-form evaluation of $P$ at $r$.

2.4 Nested form of a polynomial

> Definition (Nested form). The nested form of a polynomial is the rewriting obtained by successively factoring out the variable from the highest powers, so that the polynomial is expressed as a chain of multiplications by $x$ and additions of coefficients. For example,

$$
> P(x)=x^{3}-6x^{2}+3x-0.14
$$

> has the nested form

$$
> P(x)=\bigl[(x-6)x+3\bigr]x-0.14.
$$

The nested form is called nested because each pair of brackets encloses the next stage of the computation. It reduces the relative error of the computed value by decreasing the number of computations, since the expanded form invites repeated formation of powers whereas the nested form uses only multiplication by $x$ and addition.

2.5 Errors in numerical computation

The numerical evaluation of a polynomial is subject to the same error analysis as any other computation. The following definitions are the ones used throughout the unit.

> Definition (Absolute error). Let $x$ be an exact number and let $x_{r}$ be an approximate value of $x$. The absolute error is

$$
> e_{\mathrm{abs}}=\lvert x-x_{r}\rvert.
$$

> If $\Delta x$ is an upper bound for this difference, so that $\lvert x-x_{r}\rvert=\Delta x$, then $\Delta x$ is called the upper bound on the absolute error.

> Definition (Relative error). The relative error of the approximation is

$$
> e_{r}=\frac{\lvert x-x_{r}\rvert}{\lvert x\rvert}.
$$

> Definition (Percentage error). The percentage error is the relative error expressed as a percentage, that is $100\,e_{r}$.

> Definition (Round-off error). Round-off errors arise because it is impossible to represent all real numbers exactly on a machine with finite memory. Rounding involves dropping decimal places or significant figures, and it can be done by chopping or truncating, or by symmetric rounding.

> Definition (Truncation error). Truncation error is the error committed when an exact process is replaced by a finite process, for instance when an infinite series is replaced by a finite number of its terms or when a decimal expansion is chopped rather than rounded.

> Definition (Propagated error). The error in the result of an arithmetic operation arising from initial errors in the numbers used in that operation is called the propagated error. The total cumulative error at any step of a procedure is called the accumulated error.

2.6 Key words in the definitions

In point form, the key words in the definitions above are the following.

• Exact number: the true value $x$ that the computation is intended to represent.
• Approximate number: the value $x_{r}$ actually used or produced by the machine.
• Absolute difference: the magnitude $\lvert x-x_{r}\rvert$, taken without sign.
• Upper bound: a number $\Delta x$ that the absolute error cannot exceed.
• Relative: the error measured as a fraction of the exact value, $\lvert x-x_{r}\rvert/\lvert x\rvert$.
• Percentage: the relative error multiplied by one hundred.
• Round-off: error caused by the finite representation of numbers on a machine.
• Chopping or truncating: discarding digits beyond a fixed position without adjusting the last retained digit.
• Symmetric rounding: discarding digits and adjusting the last retained digit to the nearer value.
• Significant figures: the digits of a number that carry meaning for its precision.
• Propagated: error transmitted from the inputs of an operation to its output.
• Accumulated: the running total of propagated errors over a sequence of operations.
• Polynomial: a finite sum of constant multiples of non-negative integer powers of a variable.
• Degree: the largest exponent with a non-zero coefficient.
• Coefficient: the constant multiplying a given power of the variable.
• Leading coefficient: the coefficient of the highest power.
• Divisor: the polynomial by which another is divided.
• Quotient: the polynomial result of the division, excluding the remainder.
• Remainder: the polynomial left over, of degree less than the divisor.
• Test zero: the value $r$ in the divisor $x-r$, placed at the left of the synthetic-division array.
• Carry down: to copy the leading coefficient unchanged below the division symbol.
• Nested form: a rewriting of a polynomial as a chain of multiplications by $x$ and additions.

2.7 Causes of errors and how to minimise them

In short notes, the principal causes of error in numerical computation are the following.

• Finite machine memory. Real numbers generally have non-terminating decimal expansions, so a machine with finite memory cannot store them exactly. This is the root cause of round-off error.
• Rounding and chopping. Dropping digits, whether by truncation or by symmetric rounding, replaces the exact value by a nearby representable value.
• Truncation of infinite processes. Replacing an infinite process by a finite one introduces an error that is not removed by using more machine precision.
• Propagation through arithmetic. Errors in the inputs of an addition, subtraction, multiplication or division are transmitted to the output, and they accumulate over a sequence of operations.
• Loss of significance in subtraction. Subtracting two nearly equal numbers can leave a result with very few correct significant figures relative to its size.
• Excessive operation count. Each operation contributes its own round-off, so a formula that performs many redundant operations accumulates more error than a formula that performs few.
• Ill-conditioned formulation. Some algebraic arrangements of the same mathematical expression are numerically far more sensitive to input error than others.

The corresponding measures for minimising error are the following.

• Use symmetric rounding rather than chopping where a choice is available, since symmetric rounding keeps the error bounded by half a unit in the last retained place.
• Reduce the number of operations by rewriting expressions in economical forms; the nested form of a polynomial is the standard example, since it reduces the relative error by decreasing the number of computations.
• Avoid unnecessary subtraction of nearly equal quantities, and rearrange formulas so that such subtractions do not occur.
• Carry guard digits through intermediate steps and round only at the end.
• Use the remainder theorem and synthetic division to evaluate polynomials with a minimal, well-organised sequence of multiplications and additions.
• Estimate the error in advance using the absolute-error bound for a number correct to a given number of decimal places, so that the reliability of the final answer is known.

2.8 Computation of errors

The basic computation rests on the following observation. If a number is correct to $n$ decimal places, then the exact value lies within half a unit in the last place of the stated value, so the maximum absolute error is

$$
e_{\mathrm{abs}}=0.5\times 10^{-n}.
$$

More generally, if a number is correct to $n$ decimal places, the absolute error is bounded by $0.5\times 10^{-n}$. For example, a value quoted as $8.35678$ correct to five decimal places has $e_{\mathrm{abs}}\le 0.5\times 10^{-5}$.

The method is applied by bracketing the exact value between the two numbers that would round to the stated approximation, then subtracting the approximation from each endpoint.

Sample computation (one decimal place). Given $x=2.4$ correct to one decimal place, the exact value lies in the interval

$$
2.35<x<2.45.
$$

Subtracting the approximation $2.4$ from each endpoint gives

$$
\begin{aligned}
2.35-2.4 &\le x-x_{r}\le 2.45-2.4,\
-0.05 &\le x-x_{r}\le 0.05.
\end{aligned}
$$

Hence

$$
\lvert x-x_{r}\rvert\le 0.05,
$$

so the absolute error is $e_{\mathrm{abs}}=0.05$, that is $5.0\times 10^{-2}$.

Sample computation (three decimal places, negative value). Let $x_{r}=-10.788$ be correct to three decimal places. The exact value lies in the interval

$$
-10.7885\le x\le -10.7875.
$$

Adding $10.788$ throughout gives

$$
\begin{aligned}
-10.7885+10.788 &\le x-x_{r}\le -10.7875+10.788,\
-0.0005 &\le x-x_{r}\le 0.0005.
\end{aligned}
$$

Hence

$$
e_{\mathrm{abs}}=\lvert x-x_{r}\rvert=0.0005=0.5\times 10^{-3}.
$$

Relative and percentage error. Once the absolute error is known, the relative error is obtained by dividing by the magnitude of the exact value, and the percentage error by multiplying the relative error by one hundred. For an approximation $p^{*}$ to an exact value $p$, the quantities to report are

$$
e_{\mathrm{abs}}=\lvert p-p^{}\rvert,
\qquad
e_{r}=\frac{\lvert p-p^{}\rvert}{\lvert p\rvert}.
$$

2.9 Computation of propagated errors

Let $x$ and $y$ be two exact numbers, and let $x^{}$ and $y^{}$ be approximations with initial errors $\varepsilon$ and $\eta$ respectively, so that

$$
x=x^{}+\varepsilon,
\qquad
y=y^{}+\eta.
$$

Let $\omega$ denote an arithmetic operation. The error committed in performing that operation on the approximations is obtained by comparing the exact result $x\,\omega\,y$ with the computed result $x^{}\,\omega\,y^{}$. Writing the difference and inserting and removing the intermediate quantity $x^{*}\,\omega\,y$ gives

$$
\begin{aligned}
x\,\omega\,y-x^{}\,\omega\,y^{}
&=\bigl(x\,\omega\,y-x^{}\,\omega\,y\bigr)+\bigl(x^{}\,\omega\,y-x^{}\,\omega\,y^{}\bigr).
\end{aligned}
$$

The first bracket is the error generated by the operation itself, acting on the exact first operand and the approximate second operand; the second bracket is the error transmitted from the second operand. Their sum is the propagated error of the operation, and the running total of such contributions over a sequence of operations is the accumulated error.

For the four elementary operations the propagated error takes the following forms, obtained by substituting $x=x^{}+\varepsilon$ and $y=y^{}+\eta$ and retaining the leading terms.

• Addition. The exact sum is $x+y=x^{}+y^{}+\varepsilon+\eta$, so the error in the sum is $\varepsilon+\eta$. Absolute errors add.
• Subtraction. The exact difference is $x-y=x^{}-y^{}+\varepsilon-\eta$, so the error in the difference is $\varepsilon-\eta$. The absolute error is bounded by $\lvert\varepsilon\rvert+\lvert\eta\rvert$, and cancellation between nearly equal operands can make the relative error very large.
• Multiplication. The exact product is $xy=x^{}y^{}+\varepsilon y^{}+\eta x^{}+\varepsilon\eta$, so the propagated error is $\varepsilon y^{}+\eta x^{}+\varepsilon\eta$, and to first order the relative errors add.
• Division. For $y\neq 0$ the exact quotient satisfies $x/y\approx x^{}/y^{}$ with propagated error dominated by $\varepsilon/y^{}-x^{}\eta/(y^{*})^{2}$, and to first order the relative errors add.

These results explain why the operation count of an algorithm matters: every multiplication and addition in the synthetic-division array or in the nested-form evaluation contributes a term of the kind displayed above, so a shorter algorithm accumulates less error.

2.10 Encouraging participation of all learners

The lesson is designed for active participation rather than passive reception. The following practices are used.

• Individual task before discussion. Each learner first watches the assigned video and, working alone, lists in point form the key words in the definition of errors and algorithms, and makes short notes on the causes of errors and how to avoid them. This ensures that every learner engages with the material before hearing the answers of others.
• Discussion forum posting. Learners post their attempts on the discussion forum, so that every learner, including the quieter ones, has a written contribution on record.
• Reading colleagues' posts. Learners study what their colleagues have posted and note anything new, which exposes them to alternative formulations and to errors they had not anticipated.
• Improving one's own answer. Learners revise their own answers in the light of what they have read, which turns the forum into a formative exercise rather than a display.
• Moderator direction of group discussion. The moderator directs the group discussion so that contributions are drawn from across the group and no single voice dominates.
• Structured pair and group work on the synthetic-division array. Because the array is written column by column, it can be divided among group members, with each member checking the previous member's entry, so that the whole group participates in a single computation.

2.11 Providing feedback

Feedback is provided at three levels.

• Immediate feedback on the forum. The moderator reads the posted lists of key words and the short notes on causes of errors, and responds with corrections, confirmations and pointers to the relevant part of the definition.
• Feedback through worked solutions. The assessment questions on absolute and relative error are followed by full solutions, so that learners can compare their method as well as their answer with the approved method.
• Feedback on the synthetic-division array. Because the array is self-checking, the remainder can be verified by direct substitution of $r$ into $P$, and any discrepancy is located at the column where the arithmetic first went wrong. This gives the learner precise, localised feedback rather than a bare mark.

Feedback should be specific, should identify the step at which an error entered, and should distinguish an arithmetic slip from a conceptual misunderstanding, for example confusing the remainder with the quotient or omitting a zero coefficient for a missing power.

2.12 Summarising the lesson

The lesson closes with a summary that draws together the following points.

• A polynomial is a finite sum of constant multiples of non-negative integer powers of a variable; its degree is the largest exponent with a non-zero coefficient.
• The division algorithm writes $P(x)=d(x)q(x)+R(x)$ with $\deg R<\deg d$; for a linear divisor $x-r$ the remainder is the constant $R=P(r)$.
• Synthetic division is an economical algorithm for producing $q(x)$ and $R$ when the divisor is $x-r$; it works on coefficients only, carries the leading coefficient down unchanged, multiplies each carried value by the test zero, and adds down each column.
• The last entry of the array is the remainder, equal to $P(r)$; if $r$ is a root, the remainder is zero and $x-r$ is a factor.
• The nested form of a polynomial is the algebraic counterpart of the array and reduces the relative error by decreasing the number of computations.
• Errors are classified as absolute, relative, percentage, round-off, truncation, propagated and accumulated; the maximum absolute error of a number correct to $n$ decimal places is $0.5\times 10^{-n}$.
• Errors are minimised by symmetric rounding, by reducing the operation count, by avoiding subtraction of nearly equal quantities, and by carrying guard digits.