多项式计算

下面通过多项式求值的例子

$$p(x) = \sum_{i=0}^d a_ix^i$$

来说明扰动理论、条件数、向后稳定性和舍入误差分析的思想。

多项式求值：Horner 规则

$\begin{aligned} &p = a_d\\ &\text{for } i = d-1 \text{ down to } 0\\ &\quad p = x*p + a_i\\ &\text{end for} \end{aligned}$

多项式求值示例

给定如下多项式

$$\begin{aligned} p(x) =& (x-2)^9 \\ =& x^9 - 18x^8 +144x^7 - 672x^6 + 2016x^5 - 4032x^4 + 5376x^3 - 4608x^2 + 2304x -512 \end{aligned}$$

编写 Python 程序, 分别用 $(x-2)^9$ 和 Horner 规则计算上述多项式在区间 $[1.92, 2.08]$ 的函数图像。

import numpy as np
import matplotlib.pyplot as plt

def horner(x):
    a = np.array([1, -18, 144, -672, 2016,-4032, 5376, -4608, 2304, -512],dtype=np.float)
    n = len(x)
    p = np.ones(n)*a[0]
    for i in range(1, 10):
        p = x*p + a[i]
    return p

def poly(x):
    return (x-2)**9


x = np.linspace(1.92, 2.08, num=8000)

y0 = horner(x)
y1 = poly(x)

fig0 = plt.figure()
fig1 = plt.figure()

axes0 = fig0.gca()
axes1 = fig1.gca()

axes0.plot(x, y0)
axes1.plot(x, y1)

plt.show()

利用二分法编程求解多项式的零点

$$\begin{aligned} &\text{proc Bisect }(p, x_{low}, x_{high}, tol)\\ \end{aligned}$$

• 讲解二分法的思想
• 编程实现二分法
• 用于求上述多项式的零点
• 比较两者的误差