Numerical Techniques for Polynomials: Roots, Evaluation & Special Functions

TAKEAWAYS

• Root-finding methods (Newton-Raphson, bisection) iteratively approximate polynomial roots, with Newton’s method requiring derivatives and bisection guaranteeing convergence if bracketing is correct.
• Horner’s rule rewrites polynomials as nested multiplication for faster evaluation (O(n) time) and is foundational for root-finding algorithms.
• Finite differences approximate derivatives of tabulated functions using forward/backward/central difference formulas, with error proportional to $h^2$ or $h^4$.
• Least-squares fitting minimizes error for overdetermined systems (e.g., linear regression $y=a+bx$) by solving normal equations $A^{T}A\hat{x}=A^T\mathbf{b}$.
• Special functions (e.g., Bessel, Legendre) often require numerical evaluation via series expansions or recurrence relations, with truncation errors controlled by term limits.
• Extrapolation vs. interpolation: Extrapolation predicts beyond given data points (risky) while interpolation fits within them; Lagrange and Newton polynomials are common tools.

1. Polynomial Root-Finding Methods

Polynomial equations $P(x)=0$ often lack analytical solutions, so numerical methods approximate roots iteratively. Two key techniques appear in exams:

1.1 Bisection Method

Definition: A bracketing method that repeatedly halves an interval $[a,b]$ where $P(a)P(b)<0$ (sign change guarantees a root by Intermediate Value Theorem).

Algorithm:

1. Choose $a,b$ such that $P(a)P(b)<0$.
2. Compute midpoint $c=(a+b)/2$.
3. If $|P(c)|<\text{tolerance}$, return $c$.
4. Else, replace $a$ or $b$ with $c$ based on $P(c)P(a)$ or $P(c)P(b)$ sign, and repeat.

Worked Example: Find a root of $f(x)=x^2-e^{-x}-3$ to 3 significant figures.

• Step 1: Find bracket: $f(1)=1-e^{-1}-3=-2.632$, $f(2)=4-e^{-2}-3=0.865$. Sign change → root in $[1,2]$.
• Step 2: Iterate:
  • $c_1=1.5$, $f(1.5)=-0.326$ → new bracket $[1.5,2]$.
  • $c_2=1.75$, $f(1.75)=0.263$ → $[1.5,1.75]$.
  • $c_3=1.625$, $f(1.625)=-0.031$ → $[1.625,1.75]$.
  • $c_4=1.6875$, $f(1.6875)=0.116$ → $[1.625,1.6875]$.
  • Stop: $|f(1.65625)|<0.001$ → root ≈ 1.66.

Advantages/Disadvantages:

Mermaid Diagram: Bisection Method Flow

flowchart TD
    A["Start: Choose [a,b] with P(a)P(b) < 0"] --> B["Compute c = (a+b)/2"]
    B --> C["Check |P(c)| < tolerance?"]
    C -->|Yes| D["Return c as root"]
    C -->|No| E["Update bracket:"]
    E --> F["If P(c)P(a) < 0, set a = c"]
    E --> G["Else set b = c"]
    F --> B
    G --> B

1.2 Newton-Raphson Method

Definition: Uses the tangent line at $x_0$ to approximate the root: $$x_{n+1}=x_n-\frac{f(x_n)}{f^{\prime }(x_n)}.$$ Requirements: $f^{\prime }(x)$ must exist, and initial guess $x_0$ must be close to the root.

Worked Example: Find a real negative root of $P(x)=x^4+2x^3+3x^2+4x-5$.

• Step 1: Guess $x_0=-1.5$.
• Step 2: Compute $P(x_0)=(-1.5{)}^4+2(-1.5{)}^3+3(-1.5{)}^2+4(-1.5)-5=5.0625-6.75+6.75-6-5=-6$.
• Step 3: $P^{\prime }(x)=4x^3+6x^2+6x+4$ → $P^{\prime }(-1.5)=-13.5+13.5-9+4=-5$.
• Step 4: $x_1=-1.5-(-6)/(-5)=-1.5-1.2=-2.7$.
• Iterate:
  • $x_2=-2.7-P(-2.7)/P^{\prime }(-2.7)\approx -2.7-(-1.7)/(-11.7)\approx -2.846$.
  • $x_3\approx -2.846-(-0.1)/(-12.1)\approx -2.854$.
  • Converged: $x\approx -2.854$ (true root ≈ $-2.853$).

Advantages/Disadvantages:

Comparison Table:

2. Polynomial Evaluation: Horner’s Rule

Definition: Rewrites $P(x)=a_n{x}^n+\cdots +a_0$ as nested multiplication: $$P(x)=a_0+x(a_1+x(a_2+\cdots +x(a_{n-1}+x{a}_n)\dots )).$$ Advantages:

• Reduces multiplications from $O(n^2)$ to $O(n)$.
• Minimizes rounding errors.

Worked Example: Evaluate $P(x)=2x^3-3x^2+5x-2$ at $x=3$ using Horner’s rule.

• Step 1: Rewrite as $P(x)=-2+x(5+x(-3+x(2)))$.
• Step 2: Compute: $$\begin{array}{rl}{b}_3& =2,\\ b_2& =-3+3\times 2=3,\\ b_1& =5+3\times 3=14,\\ b_0& =-2+3\times 14=40.\end{array}$$
• Result: $P(3)=40$.

Algorithm:

def horner(p, x):
    result = 0
    for coeff in reversed(p):  # p = [a_n, ..., a_0]
        result = result * x + coeff
    return result

Mermaid Diagram: Horner’s Rule Evaluation

flowchart TD
    A["Initialize: result = 0"] --> B["For each coefficient from a_n to a_0:"]
    B --> C["result = result * x + coeff"]
    C --> D["Return result"]

3. Finite Differences for Derivatives

For tabulated functions $f(x_i)$, derivatives are approximated using:

3.1 Forward Difference

$$f^{\prime }(x_i)\approx \frac{f(x_{i+1})-f(x_i)}{h},\text{Error}=O(h).$$

3.2 Central Difference

$$f^{\prime }(x_i)\approx \frac{f(x_{i+1})-f(x_{i-1})}{2h},\text{Error}=O(h^2).$$

3.3 Second Derivative

$$f^{\prime \prime }(x_i)\approx \frac{f(x_{i+1})-2f(x_i)+f(x_{i-1})}{h^2},\text{Error}=O(h^2).$$

Worked Example: Given $f(x)$ at $x=[1.0,1.2,1.4,1.6]$ with $f(x)=[1.53,2.25,3.18,4.32]$, estimate $f^{\prime }(1.2)$ using central difference ($h=0.2$): $$f^{\prime }(1.2)\approx \frac{3.18-1.53}{0.4}=\mathrm{4.125.}$$

Algorithm for $f^{\prime }(x_i)$:

def central_diff(f, x, h):
    return (f(x + h) - f(x - h)) / (2 * h)

4. Least-Squares Curve Fitting

Fits a model $y=\varphi (x,\beta )$ to data $(x_i,y_i)$ by minimizing $\sum (y_i-\varphi (x_i,\beta ){)}^2$.

4.1 Linear Regression ($y=a+bx$)

Solve the normal equations: $$\left[\begin{array}{cc}n& \sum x_i\\ \sum x_i& \sum x_i^2\end{array}\right]\left[\begin{array}{c}a\\ b\end{array}\right]=\left[\begin{array}{c}\sum y_i\\ \sum x_i{y}_i\end{array}\right].$$

Worked Example: Fit $y=a+bx$ to $(x,f(x))=\{(-1,1),(1.2,20),(2,27),\dots \}$ (from past exam).

• Compute sums: $$\sum x_i=12.4,\sum y_i=167,\sum x_i{y}_i=580.4,\sum x_i^2=\mathrm{38.98.}$$
• Solve: $$\{\begin{array}{l}6a+12.4b=167,\\ 12.4a+38.98b=\mathrm{580.4.}\end{array}$$
• Solution: $a=1.2$, $b=14.2$ → $y=1.2+14.2x$.

Mermaid Diagram: Least-Squares Steps

flowchart TD
    A["Given data (x_i, y_i)"] --> B["Choose model (e.g., y = a + bx)"]
    B --> C["Compute sums: n, Σx, Σy, Σx², Σxy"]
    C --> D["Form normal equations Aβ = B"]
    D --> E["Solve for β (coefficients)"]
    E --> F["Return fitted model"]

5. Special Functions and Numerical Evaluation

Special functions (e.g., Bessel $J_n(x)$, Legendre $P_n(x)$) often require numerical methods:

5.1 Series Expansions

• Bessel Function (first kind): $$J_n(x)=\sum _{k=0}^{\infty }\frac{(-1{)}^k}{k!(n+k)!}{\left(\frac{x}{2}\right)}^{n+2k}.$$ Truncate at $k=K$ where terms $<ϵ$.

• Legendre Polynomials: Recurrence relation: $$(n+1)P_{n+1}(x)=(2n+1)x{P}_n(x)-n{P}_{n-1}(x).$$

Worked Example: Approximate $J_0(1)$ using 3 terms: $$J_0(1)\approx 1-\frac{1^2}{2^2}+\frac{1^4}{2^2\cdot 4^2}=1-0.25+0.0156\approx 0.7656(\text{true}\approx 0.7652).$$

6. Interpolation vs. Extrapolation

Lagrange Interpolation Example: Given $(x,y)=\{(5,12),(6,13),(9,14),(11,16)\}$, find $y(10)$: $$P(x)=12\frac{(x-6)(x-9)(x-11)}{(5-6)(5-9)(5-11)}+\cdots +16\frac{(x-5)(x-6)(x-9)}{(11-5)(11-6)(11-9)}.$$ At $x=10$: $$P(10)\approx 12.5(\text{exact}=12.5).$$

Exam Tip

1. Root-Finding:

   • For Newton-Raphson, always show the derivative calculation and iteration steps.
   • For bisection, justify the initial bracket and show convergence to required precision (e.g., 3 significant figures).
   • Common Pitfall: Forgetting to check $P(a)P(b)<0$ for bisection or $f^{\prime }(x_n)\ne 0$ for Newton-Raphson.

2. Horner’s Rule:

   • Rewrite the polynomial in nested form before evaluation.
   • Exam Trick: If asked to evaluate a polynomial at multiple points, use Horner’s rule to avoid recomputing powers.

3. Finite Differences:

   • Use central differences for better accuracy unless at endpoints (use forward/backward).
   • Formula Sheet: Memorize the $O(h)$ and $O(h^2)$ error terms.

4. Least-Squares:

   • Set up the normal equations correctly (transpose matrices).
   • For linear regression, solve the 2×2 system by substitution or Cramer’s rule.
   • Shortcut: Use the formulas: $$b=\frac{n\sum xy-\sum x\sum y}{n\sum x^2-(\sum x{)}^2},a=\bar{y}-b\bar{x}.$$

5. Special Functions:

   • For series expansions, show the first 2–3 terms and the truncation error.
   • For recurrence relations, write out the first few terms explicitly.

6. Interpolation:

   • For Lagrange, use the product form and simplify before substituting $x$.
   • Warning: Extrapolation is unreliable—only interpolate within the data range.

7. Numerical Integration (Bonus):

   • Although primarily in Unit 6, Simpson’s 1/3 and 3/8 rules often appear here. For tabulated data:
     • Simpson’s 1/3: Requires even number of intervals ($n$ even).
     • Simpson’s 3/8: Uses 3 intervals ($n$ divisible by 3).
   • Worked Example: For $x=[0,0.2,\dots ,1.6]$, $n=8$ (even) → use Simpson’s 1/3: $${\int }_0^{1.6}f(x)dx\approx \frac{h}{3}[f(x_0)+4f(x_1)+2f(x_2)+\cdots +4f(x_7)+f(x_8)].$$ Here, $h=0.2$: $$\text{Integral}\approx \frac{0.2}{3}[0+4(0.24+0.92+1.84+2.95)+2(0.55+1.63+2.37)+3.56]\approx \mathrm{1.80.}$$

Final Checklist for Exams:

• For root-finding, show all iterations until convergence.
• For Horner’s rule, rewrite the polynomial in nested form.
• For least-squares, verify the normal equations before solving.
• For interpolation, substitute $x$ carefully into the Lagrange formula.
• For numerical integration, count intervals to choose the correct Simpson’s rule.