Numerical Methods

• Newton's divided-difference interpolating polynomials:
• Python code for Newton's divided differences polynomial coefficients:

  def divided_differences(x, y):

  n=len(y)

  coeff=np.zeros([n,n])

  coeff[:,0]=y

  for i in range(1,n):

  for j in range(n-i):

  coeff[j,i]=(coeff[j+1,i-1]-coeff[j,i-1])/(x[i+j]-x[j])

  return coeff
• Python code for Newton Interpolation:

  def newton_interpolation(coeff, x, x_value):

  n=len(x)

  f=0

  for i in range(n):

  term=1

  for j in range(i):

  term*=(x_value-x[j])

  f+=coeff[i]*term

  return f
• Python code for Lagrange Interpolating Polynomial:

  def lagrange_interpolation(x,y,x_value):

  n=len(x)

  P=0

  for i in range(n):

  term=1

  for j in range(n):

  if(j!=i):

  term*=(x_value-x[j])/(x[i]-x[j])

  P+=y[i]*term

  return P
• Python code for Richardson Extrapolation:

  def Richardson(x,h,n):

  D=np.zeros([n+1,n+1])

  for i in range(n+1):

  D[i,0]=numerical_diff(x,h/i**2)

  for j in range(1,n+1):

  for i in range(j,n+1):

  D[i,j]=D[i,j-1]+(D[i,j-1]-D[i-1,j-1])/(4**j-1)

  return D[n,n]
• Forward Difference :

  $(f(x+h)-f(x))/h$
• Backward Difference:

  $(f(x)-f(x-h))/h$
• Central Difference:

  $(f(x+h)-f(x-h))/2h$
• Second order derivative formula:

  $(f(x+h)-2f(x)+$$f(x-h))/h^2$
• Python code for Linear Regression:

  A=np.array([n,sum(x)],

  [sum(x),sum(x**2)]])

  b=np.array([sum(y),sum(y*x)])

  coeff=np.linalg.inv(A).dot(b)

  
  

  y=coeff[0]+coeff[1]*x
• Richardson formula for Numerical Differentiation:

  $D[n,m]=$$D[n,m-1]+$$1/(4^m-1)(D[n,m-1]-D[n-1,m-1])$
• first column of Richardson Extrapolation table:latex>D[n,0]=central_diff(x,h/(2^i)) </latex> - in a loop
• Trapezoid Rule:

  $I=$$(b-a)(f(b)+$$f(a))/2$
• The Multiple-Application Trapezoid Rule:

  $h/2[f(x_0)+$$f(x_n)+$$sum(f(x_i))]$
• Recursive Trapezoid Rule:

  $R[n,0]=$$R[n-1,0]/2+$$h[sum(f(a+(2k-1)h))]$
• Romberg Method Formula:

  $R[n,m]=$$(1/(4^m-1))[4^mR[n,m-1]-R[n-1,m-1]]$
• Python code for Trapezoid Rule:

  def trapezoid(a,b,n):

  h=(b-a)/n

  integral=(f(a)+f(b))/2

  x=a+h

  while x<b:

  integral+=f(x)

  x+=h

  integral*=h

  return integral
• Python code for Lower-Upper Sums Method:

  def low_upper_sums(a,b,n):

  h=(b-a)/n

  x=a

  low=0; upper=0

  while x<b:

  m=min(f(x),f(x+h))

  M=max(f(x),f(x+h))

  low+=m

  upper+=M

  x+=h

  return (low+upper)/2*h
• Python code for Recursive Trapezoid Rule:

  def recursive_trapezoid(a,b,n):

  R=np.zeros([n,n])

  h=b-a

  R[0,0]=((f(a)+f(b))/2)*h

  for m in range(1,n+1):

  h/=2

  s=0

  for i in range(1,(2**(m-1))+1):

  s+=f(a+(2*i-1)*h)

  R[m,0]=R[m-1,0]/2+s*h

  return R
• Python code for Romberg Method:

  def romberg(R,N):

  for n in range (1,N+1):

  for m in range(1,n+1):

  R[n,m]=(1/(4**m-1))*(4**m*R[n,m-1]-R[n-1,m-1])

  return R