<jupyter_start><jupyter_text>IntroductionLast time we have used Lagrange basis to interpolate polynomial. However, it is not efficient to update the interpolating polynomial when a new data point is added. We look at an iterative approach.Given points $\{(z_i, f_i) \}_{i=0}^{n-1}$, $z_i$ are distinct and $p_{n-1} \in \mathbb{C}[z]_{n-1}\, , p_{n-1}(z_i) = f_i$.  We add a point $(z_n, f_n)$ and find a polynomial $p_n \in \mathbb{C}[x]_{n-1}$ which satisfies $\{(z_i, f_i) \}_{i=0}^{n}$.  We assume $p_n(z)$ be the form\begin{equation}p_n(z) = p_{n-1}(z) + C\prod_{i=0}^{n-1}(z - z_i)\end{equation}so that the second term vanishes at $z = z_0,...,z_{n-1}$ and $p_n(z_i) = p_{n-1}(z_i), i = 0,...,n-1$. We also want $p_n(z_n) = f_n$ so we have\begin{equation}f_n = p_{n-1}(z_n) + C\prod_{i=0}^{n-1}(z_n - z_i) \Rightarrow C = \frac{f_n - p_{n-1}(z_n)}{\prod_{i=0}^{n-1}(z_n - z_i)}\end{equation}Thus we may perform interpolation iteratively. **Example:** Last time we have\begin{equation}(z_0, f_0) = (-1,-3), \quad(z_1, f_1) = (0,-1), \quad(z_2, f_2) = (2,4), \quad(z_3, f_3) = (5,1)\end{equation}and \begin{equation}p_3(x) = \frac{-13}{90}z^3 + \frac{14}{45}z^2 + \frac{221}{90}z - 1\end{equation}<jupyter_code>z0 = -1; f0 = -3; z1 = 0; f1 = -1; z2 = 2; f2 = 4; z3 = 5; f3 = 1; z4 = 1; f4 = 1
p3 = -13*x**3/90 + 14*x**2/45 + 221*x/90 - 1<jupyter_output><empty_output><jupyter_text>We add a point $(z_4,f_4) = (1,1)$ and obtain $p_4(x)$<jupyter_code>z4 = 1; f4 = 1
C = (f4 - p3.subs(x,z4))/((z4-z0)*(z4-z1)*(z4-z2)*(z4-z3))
C
p4 = p3 + C*(x-z0)*(x-z1)*(x-z2)*(x-z3)
sp.expand(p4)<jupyter_output><empty_output><jupyter_text>**Remark:** the constant $C$ is usually written as $f[z_0,z_1,z_2,z_3,z_4]$. Moreover by iteration we have$$p_n(z) = \sum_{i=0}^n f[z_0,...,z_n] \prod_{j=0}^i (z - z_j)$$  Newton Tableau We look at efficient ways to compute $f[z_0,...,z_n]$, iteratively from $f[z_0,...,z_{n-1}]$ and $f[z_1,...,z_n]$. We may first construct $p_{n-1}$ and $q_{n-1}$ before constructing $p_n$ itself, where\begin{gather}p_{n-1}(z_i) = f_i \quad i = 0,...,n-1\\q_{n-1}(z_i) = f_i \quad i = 1,...,n\end{gather}**Claim:** The following polynomial interpolate $\{(z_i,f_i)\}_{i=0}^n$\begin{equation}p_n(z_i) = \frac{(z - z_n)p_{n-1}(z) - (z - z_0)q_{n-1}(z)}{z_0 - z_n}\end{equation}Since interpolating polynomial is unique, by comparing coefficient of $z_n$, we have$$f[z_0,...,z_{n}] = \frac{f[z_0,...,z_{n-1}]-f[z_1,...,z_{n}]}{z_0 - z_n}$$<jupyter_code>def product(xs,key,i):
    
    #Key: Forward or Backward
    
    n = len(xs)-1
    l = 1
    
    for j in range(i):
        if key == 'forward':
            l *= (x - xs[j])
        else:
            l *= (x - xs[n-j])

    return l
def newton(xs,ys,key):
    
    # Key: Forward or Backward
    
    n = len(xs)-1
    # print(xs)
    print(ys)
    old_column = ys
    
    if key == 'forward':
        coeff = [fs[0]]
    elif key == 'backward':
        coeff = [fs[len(fs)-1]]
    else:
        return 'error'
    
    for i in range(1,n+1): # Column Index
        new_column = [(old_column[j+1] - old_column[j])/(xs[j+i] - xs[j]) for j in range(n-i+1)]
        print(new_column)
        if key == 'forward':
            coeff.append(new_column[0])
        else:
            coeff.append(new_column[len(new_column)-1])
        old_column = new_column
    
    # print(coeff)
    
    poly = 0
    for i in range(n+1):
        poly += coeff[i] * product(xs,key,i)
        
    return poly
zs = [1, 4/3, 5/3, 2]; fs = [np.sin(x) for x in zs]
p = newton(zs,fs,'backward')
sp.simplify(p)<jupyter_output>[0.8414709848078965, 0.9719379013633127, 0.9954079577517649, 0.9092974268256817]
[0.3914007496662487, 0.07041016916535667, -0.25833159277824974]
[-0.481485870751338, -0.4931126429154095]
[-0.011626772164071542]
{'fraction_non_alphanumeric': 0.21542130365659778, 'fraction_numerical': 0.08982511923688394, 'mean_word_length': 3.289772727272727, 'pattern_counts': {'":': 0, '<': 12, '<?xml version=': 0, '>': 12, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '10698', 'license': 'MIT', 'n_tokens_mistral': 1861, 'n_tokens_neox': 1688, 'n_words': 355, 'path': 'M2AA3/M2AA3-Polynomials/Lesson 02 - Newton Method/Newton Tableau.ipynb', 'repo_name': 'ImperialCollegeLondon/Random-Stuff', 'size': '3774'}