<jupyter_start><jupyter_text>Aitken Extrapolation Task 1: recreate Table 2.10 in the bookIn the table, we have $x_n = \cos(\frac{1}{n})$ which converges to $\cos(0)=1$ since $\cos$ is continuous.  Use Aitken Extrapolation to accelerate this sequence $(x_n)$.<jupyter_code># Recreate Table 2.10 in the book

import numpy as np
from numpy import diff as D   # this is the Delta in the book, aka "forward difference"

N = 7  # total number of terms
p = np.cos( 1/np.r_[1:N+1] ) # Example in book (Table 2.10)
print("The sequence p_n is:")
for pn in p:
  print("{:.5f}".format(pn))

print("The sequence \hat{p}_n is:")  
# Define phat (for p^hat, not as in "that is a phat song!")
phat = p[:-2]  - (D(p)[:-1])**2 / D(D(p))
for pn in phat:
  print("{:.5f}".format(pn))<jupyter_output>The sequence p_n is:
0.54030
0.87758
0.94496
0.96891
0.98007
0.98614
0.98981
The sequence \hat{p}_n is:
0.96178
0.98213
0.98979
0.99342
0.99541<jupyter_text>Task 2: accelerate a root-finding problemYou could do Steffensen's variant, but we didn't discuss that, so I suggest you just to Aitken extrapolationLet's solve $x = g(x)$ where$$g(x) = .7\cos(x)$$insdie the interval $[0,1]$.  We know that $g$ is a contraction since$$|g'(x)| = |-.7\sin(x)| \le .7 < 1$$<jupyter_code># Try a root-finding problem, x = .7*cos(x)
from scipy.optimize import root_scalar
g = lambda x : .7*np.cos(x)

output = root_scalar(lambda x : g(x) - x ,bracket=[0,1])
trueRoot = output.root
print("The root is",trueRoot)
# Accelerate the iteration

# Try fixed-point iteration, starting at 0
x = 0
N   = 20
p   = np.zeros(N)
phat= np.zeros(N-2)
# There are many ways to program this, depending on how/if you want to save
#   all the iterates.
for i in range(N):
  x = g(x)
  p[i] = x
  if i > 1:
    d1_a = p[i-1]-p[i-2]
    d1_b = p[i]-p[i-1]
    phat[i-2] = p[i-2] - (d1_a**2)/( d1_b - d1_a)
    print("p_{:<2d} is {:.5f} and error is {:.3e}; hat(p)_{:<2d} is {:.5f} and error is {:.3e}".format( i, x,abs(x-trueRoot),i-2,phat[i-2],abs(phat[i-2]-trueRoot) ) )
  else:
    print("p_{:<2d} is {:.5f} and error is {:.3e}".format( i, x,abs(x-trueRoot) ) )
# Same thing, but using a different version of the code
#   (designed to be simpler, since it doesn't save the entire history)
x   = 0  # our starting guess
for i in range(10): # i = 0, 1, 2, ..., 9 -- don't forget that Python is 0 based
  if i >= 1:
    xVeryOld = xOld
  xOld = x
  x    = g(x)  # Fixed point iteration update
  if i >= 1:
      DeltaOld = Delta
  Delta = x - xOld
  if i >= 1:
    xhat = xVeryOld - DeltaOld**2/( Delta - DeltaOld)
    print(xVeryOld,xhat)<jupyter_output>0 0.5667292007496922
0.7 0.5828355747666369
0.5353895310991419 0.5838016125355683
0.6020489755511681 0.5839622114962584
0.5769238612151603 0.583984921687019
0.5867011411648845 0.5839883673835934
0.5829400576356008 0.5839888768922955
0.5843934705791918 0.5839889529996376
0.5838328003801305 0.5839889643240639
StarcoderdataJupyterStructuredCleanDedup