UNIT 2: EVALUATION OF POLYNOMIALS

UNIT 2: EVALUATION OF POLYNOMIALS

2.1 Polynomial Forms and Their Evaluation Algorithms

Polynomials

A polynomial is a mathematical expression that consists of variables, constants, and exponents, combined using addition, subtraction, and multiplication.

Example: 3x2+5x−23x^2 + 5x - 2

Polynomials are essential tools in algorithms due to their ability to represent problems, their role in efficiency analysis, and their applications across various fields.

Polynomial Forms

1. Power Form

• The most common representation of a polynomial as a sum of terms: anxn+an−1xn−1+...+a1x+a0a_nx^n + a_{n-1}x^{n-1} + ... + a_1x + a_0

2. Nested Form (Horner's Form)

• A rearranged form of the power form for efficient evaluation: p(x)=a0+x(a1+x(a2+...+x(an)...))p(x) = a_0 + x(a_1 + x(a_2 + ... + x(a_n)...))

Example: For p(x)=4x3−5x2+2x+7p(x) = 4x^3 - 5x^2 + 2x + 7, Horner's form is: 7+x(−5+x(2+4x))7 + x(-5 + x(2 + 4x))

3. Lagrange Form

• Used for polynomial interpolation, constructing a polynomial that passes through a given set of points.

General Form: L(x)=∑i=0nyili(x)L(x) = \sum_{i=0}^{n} y_i l_i(x) where: li(x)=∏j=0,j≠in(x−xj)(xi−xj)l_i(x) = \prod_{j=0, j \neq i}^{n} \frac{(x - x_j)}{(x_i - x_j)}

4. Newton Form

• Used in interpolation with divided differences.

General Form: N(x)=a0+a1(x−x0)+a2(x−x0)(x−x1)+...N(x) = a_0 + a_1(x - x_0) + a_2(x - x_0)(x - x_1) + ... where aia_i are divided differences.

Key Algorithms for Polynomial Evaluation

1. Direct Evaluation (Power Form)

• Substituting the value of xx into the polynomial and computing term-by-term.

• Computationally expensive due to repeated multiplications.

Example: For P(x)=2x3−5x2+3x+1P(x) = 2x^3 - 5x^2 + 3x + 1, at x=2x = 2: P(2)=16−20+6+1=3P(2) = 16 - 20 + 6 + 1 = 3

2. Horner's Method

• Evaluates polynomials efficiently by reducing the number of multiplications.

Example: For P(x)=3x3−2x2+5x−1P(x) = 3x^3 - 2x^2 + 5x - 1, at x=2x = 2: P(2)=(((3×2)−2)×2+5)×2−1=25P(2) = (((3 \times 2) - 2) \times 2 + 5) \times 2 - 1 = 25

3. Estrin’s Scheme

• A parallel algorithm restructuring computation to allow simultaneous execution of some operations.

Example: For P(x)=2x5+3x4−x3+4x2−5x+1P(x) = 2x^5 + 3x^4 - x^3 + 4x^2 - 5x + 1, at x=2x = 2: P(2)=111P(2) = 111

4. Evaluation with Preprocessing

• Optimizes coefficient handling for multiple evaluations.

Key Considerations for Polynomial Evaluation

1. Efficiency: Measured by the number of arithmetic operations.

2. Accuracy: Managing rounding errors in floating-point arithmetic.

3. Choice of Form: Horner’s form is generally preferred for efficiency.

4. Applications: Polynomial evaluation is used in numerical computing, computer graphics, and data analysis.

END OF UNIT 2