Ch1.3.2 Evaluating Polynomials

• A polynomial has the form

\[ f(x) = a_0 + a_1x + \cdots + a_{n-1}x^{n-1} + a_n x^n \]

• Computation involves additions and summations
• This is ideally suited for a computer

• Widely used in scientific computation and numerical analysis
• A common application is to approximate functions
• Recall Taylor polynomials from Calculus II:

\[ \begin{align*} f(x) & \cong \sum_{k=0}^{n} \frac{f^{(k)}(a)}{k!} (x-a)^k \\ & = f(a) + f'(a)(x-a) + \frac{f''(a)}{2}(x-a)^2 + \cdots + \frac{f^{(n)}(a)}{n!}(x-a)^n \end{align*} \]

• Polynomials are represented in R by vector of coefficients.
• Entries listed in order of exponent on x (smallest to largest)
  
• For \( f(x) = 3x^2 -2x +1 \):

(f <- c(1,-2,3))

[1]  1 -2  3

• Degree (order) of polynomial = highest power on x
  
• Thus degree = order = length(f) - 1
• This is a correction to book on page 21
  
• For \( f(x) = 3x^2 -2x +1 \):

f <- c(1,-2,3)
(deg <- length(f) - 1)

[1] 2

• A common application is to approximate functions
• Evaluating a polynomial requires a summation
• Recall summation algorithms are not equal

\[ f(x) \cong f(a) + f'(a)(x-a) + \frac{f''(a)}{2}(x-a)^2 \]

• Calculate left to right & PEDMAS
• Consider \( f(x) = 1 - 2x + 3x^2 \) at \( x = 2 \)
• Thus we compute \( f(4) = 1 - 2*2 + 3*(2^2) \)
• Use running sum \( s \):

\[ \begin{align*} s & = 1 \\ s & = s + (-2)*2 = 1 - 4 = -3\\ s & = s + 3*(2*2) = -3 + 3*4 = -3 + 12 = 9\ \end{align*} \]

• 5 flops = 3 multiplications + 2 additions

• How many flops?

\[ \begin{align*} f(x) & = 1 - 2x + 3x^2 + 4*x^3 + 5*x^4 \\ & = 1 - 2*x \\ & \hspace{1.0in} + 3*x*x \\ & \hspace{2.0in} +4*x*x*x \\ & \hspace{3.0in} +5*x*x*x*x \\ \end{align*} \]

• How many flops?

\[ \begin{align*} f(x) & = 1 - 2x + 3x^2 + 4*x^3 + 5*x^4 \\ & = 1 - 2*x \\ & \hspace{1.0in} + 3*x*x \\ & \hspace{2.0in} +4*x*x*x \\ & \hspace{3.0in} +5*x*x*x*x \\ \end{align*} \]

• 14 flops = 10 multiplications + 4 additions

naivepoly <- function(x, coefs ) {

    y <- rep(0, length(x))

    for(i in 1: length(coefs)) {
        y <- y + coefs[i] * (x ^ (i - 1))
    }

    return (y)
}

rep(0,3)

[1] 0 0 0

• Consider again \( f(x) = 1 - 2x + 3x^2 \) at \( x = 2 \)

x <- 2
f <- c(1,-2,3)
naivepoly(x,f)

[1] 9

naivepoly <- function(x, coefs ) {
   y <- rep(0, length(x))
   for(i in 1: length(coefs)) {
     y <- y + coefs[i] * (x ^ (i - 1)) }
   return (y) }

• Now consider \( f(x) = 1 - 2x + 3x^2 \) at \( x = 0, 1, 2 \)

x <- c(0, 1, 2)
naivepoly(x,f)

[1] 1 2 9

naivepoly <- function(x, coefs ) {
   y <- rep(0, length(x))
   for(i in 1: length(coefs)) {
     y <- y + coefs[i] * (x ^ (i - 1)) }
   return (y) }

• Compute powers of x and save for next power of x.
• How many flops?

\[ \begin{align*} f(x) & = 1 - 2x + 3x^2 + 4*x^3 + 5*x^4 \\ & = 1 - 2*x \\ & \hspace{1.0in} + 3*\overbrace{x*x} \\ & \hspace{2.0in} + 4*\overbrace{(x^2)*x} \\ & \hspace{3.0in} +5*(x^3)*x \\ \end{align*} \]

• Compute powers of x and save for next power of x.
• How many flops?

\[ \begin{align*} f(x) & = 1 - 2x + 3x^2 + 4*x^3 + 5*x^4 \\ & = 1 - 2*x \\ & \hspace{1.0in} + 3*\overbrace{x*x} \\ & \hspace{2.0in} + 4*\overbrace{(x^2)*x} \\ & \hspace{3.0in} +5*(x^3)*x \\ \end{align*} \]

• 11 flops = 7 multiplications + 4 additions

betterpoly <- function(x, coefs ) {

    y <- rep(0, length(x))
    cached.x <- 1

    for(i in 1: length(coefs)) {
        y <- y + coefs[i]*cached.x
        cached.x <- cached.x * x
    }
    return (y)
}

• Naive ~ \( O(n^2) \) vs. Cached ~ \( O(n) \)

naivepoly <- function(x, coefs ) {
    y <- rep(0, length(x))
    for(i in 1: length(coefs)) {
        y <- y + coefs[i] * (x ^ (i - 1)) }
    return (y) }

betterpoly <- function(x, coefs ) {
    y <- rep(0, length(x))
    cached.x <- 1
    for(i in 1: length(coefs)) {
        y <- y + coefs[i]*cached.x
        cached.x <- cached.x * x}
    return (y)}

• Rewrite polynomial as nested linear factors:

\[ \begin{align*} f(x) & = 1 - 2x + 3x^2 \\ & = 1 + x(-2 + 3x) \\ \\ f(x) & = 1 - 2x + 3x^2 +4x^3 \\ & = 1 + x(-2 + x(3 + 4x)) \\ \\ f(x) & = 1 - 2x + 3x^2 +4x^3 +5x^4 \\ & = 1 + x(-2 + x(3 + x(4 + 5x))) \end{align*} \]

• How many flops?

\[ \begin{align*} f(x) & = 1 - 2x + 3x^2 +4x^3 +5x^4 \\ & = 1 + x*(-2 + x*(3 + x*(4 + x*5)) \end{align*} \]

• How many flops?

\[ \begin{align*} f(x) & = 1 - 2x + 3x^2 +4x^3 +5x^4 \\ & = 1 + x*(-2 + x*(3 + x*(4 + x*5)) \end{align*} \]

• 8 flops = 4 multiplications + 4 additions

• Nested representation of \( f(x) \)

\[ f(x) = 1 + x*(-2 + x*(3 + x*(4 + x*5)) \]

• Use running counter, starting with innermost part:

\[ \begin{align*} s & = 5 \\ s & = 4 + x*s \\ s & = 3 + x*s \\ s & = -2 + x*s \\ s & = 1 + x*s \\ \end{align*} \]

• Greatly reduced flop count.

\[ \begin{align*} f(x) & = 1 - 2x + 3x^2 +4x^3 +5x^4 \\ & = 1 + x(-2 + x(3 + x(4 + x5))) \end{align*} \]

horner <- function(x, coefs) {
    y <- rep(0, length (x))

    for(i in length(coefs):1)
        y <- coefs [i] + x * y

    return(y)
}