Ch4.1: Polynomial Interpolation

Linear Interpolation

Fit equation of line to two data points

linterp <- function (x1 , y1 , x2 , y2) {
m <- (y2 - y1) / (x2 - x1)
b <- y2 - m * x2
## Convert into a form suitable for horner ()
return (c(b, m))
}

Horner's Method (Ch1.3.2)

Nested polynomial evaluation

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

Example: Linear Interpolation

u <- c(3, 5)
plot(u,type="l")

plot of chunk unnamed-chunk-3

(p<-linterp(1,3,2,5))

[1] 1 2

horner(10,p)

[1] 21

Higher Order Polynomial Interpolation

Fit degree n-1 polynomial \( p(x) \),

\[ p(x) = \beta_n x^n + \beta_{n-1} x^{n-1} + \cdots + \beta_1 x + \beta_0 \]

to n data points

\[ \{(x_1,y_1), (x_2,y_2), \ldots, (x_n, y_n) \} \]

Higher Order Polynomial Interpolation

Six data points, degree 5 polynomial

title

Higher Order Polynomial Interpolation

Our polynomial is

\[ p(x) = \beta_n x^n + \beta_{n-1} x^{n-1} + \cdots + \beta_1 x + \beta_0 \]

Then \( p(x_i) = y_i \) for each \( i \), which can be expressed as a matrix-vector equation:

title

Higher Order Polynomial Interpolation

polyinterp <- function(x,y) {
if(length (x) != length (y))
stop (" Length of x and y vectors must be the same ")
n <- length (x) - 1
vandermonde <- rep(1,length (x))
for(i in 1:n) {
xi <- x^i
vandermonde <- cbind(vandermonde,xi) }
beta <- solve(vandermonde,y)
names(beta) <- NULL
return(beta) }

Higher Order Polynomial Interpolation

x <- c(0, 0.3, 0.8, 1.1, 1.6, 2.3)
y <- c(0.6 ,0.67, 1.01, 1.35, 1.47, 1.25)
(p <- polyinterp(x, y))

[1]  0.6000000  0.5910395 -2.5174715  5.4280961 -3.5892186  0.7303129

title

Higher Order Polynomial Interpolation

x <- c(0, 0.3, 0.8, 1.1, 1.6, 2.3)
y <- c(0.6 ,0.67, 1.01, 1.35, 1.47, 1.25)
(p <- polyinterp(x, y))

[1]  0.6000000  0.5910395 -2.5174715  5.4280961 -3.5892186  0.7303129

poly <- function(t) {p[6]*t^5+p[5]*t^4+p[4]*t^3+p[3]*t^2+p[2]*t+p[1]}
poly(x)

[1] 0.60 0.67 1.01 1.35 1.47 1.25

Higher Order Polynomial Interpolation

Fit degree n-1 polynomial \( p(x) \),

\[ p(x) = \beta_n x^n + \beta_{n-1} x^{n-1} + \cdots + \beta_1 x + \beta_0 \]

to n data points

\[ \{(x_1,y_1), (x_2,y_2), \ldots, (x_n, y_n) \} \]

Error:

\[ E(x) = f(x) - p(x) = \frac{(x-x_1)(x-x_2)\cdots (x-x_n)}{n!}f^{(n)}(x) \]

where \( x_1 \leq x \leq x_n \).