/*

root.cpp
Author: Ebon Bokody
Description: Numerical Analysis Assignment 2 -

	Finds the polynomial p10 of degree less than or equal to 10 that interpolates
cos x on the interval [0, PI/2] at 11 equally spaced points. Study the error betwee
between the function and the polynomial at 41 equally spaced points over the  
same interval. Repeat the latter but use your 11 points to be Chebyshevs.
	Compare and comment on results.

*/	 

#include <iostream.h>
#include <conio.h>
#include <math.h>

void Error_At_41_Equally_Spaced_Pts(int method) ;
void Method_1() ;
void Method_2() ;

const double PI = 4.0 * atan(1.0) ;
const int n = 11 ;
double x[n] = {0, PI/20.0, PI/10.0, 3.0*PI/20.0, PI/5.0, PI/4.0, 3.0*PI/10.0, 7.0*PI/20.0, 2.0*PI/5.0, 9.0*PI/20.0, PI/2.0} ;
double chebyshev[n] ;
double coeff[n] ;

void main()
{            
  cout << "\n\tJ2788 NUMERICAL ANALYSIS"
		 << "\n\t________________________\n\n"
		 << "  Author:             Ebon Bokody\n"
		 << "  Student ID:         13225966\n"
		 << "  Assignment #:       2\n\n\n  Press any key to begin." ;
  getch();  clrscr();

  cout << "\n\tMETHOD 1 - 11 EQUALLY SPACED POINTS\n\n" ;
  Method_1() ;
  cout << "\n\n\nPress any key to go to method 2 - Chebyshev's points.. " ;
  getch();    clrscr();

  cout << "\n\tMETHOD 2 - USING CHEBYSHEVS POINTS\n\n" ;
  Method_2() ;

  cout << "\n\nUsing Chebyshev's points(method 2) resulted in less error "
		 << "when \ncompared with using 11 equally spaced points(method 1)."
		 << "\n\nGOODBYE, Press any key to exit." ;
}

void Method_1()
{
  for (int j =0; j<n ; j+=1)
	 coeff[j] = cos(x[j]) ;
  for (j =1; j<n ; j++)
	 for (int i=n-1; i>=j; i--)
		coeff[i] = (coeff[i] - coeff[i-1])/(x[i] - x[i-j]) ;
	 
  cout << "The Newton Interpolating Polynomial coefficients are: \n" ;
  for (int i=0; i<n; i++)
	 cout << endl <<  "   a" << i << "\t=  " << coeff[i];

  Error_At_41_Equally_Spaced_Pts(1) ;
}

void Method_2()
{
  for (int j=0; j<=n; j++)
	 chebyshev[j] = 0.5 * (PI/2.0 - (PI/2.0 * cos(PI*((2.0*j)+1.0)/22.0))) ;
	 
  for (j =0; j<n ; j++)
	 coeff[j] = cos(chebyshev[j]) ;
  for (j =1; j<n ; j++)
	 for (int i=n-1; i>=j; i--)
		coeff[i] = (coeff[i] - coeff[i-1])/(chebyshev[i] - chebyshev[i-j]) ;

  cout << "The Newton Interpolating Polynomial coefficients are: \n" ;
  for (int i=0; i<n; i++)
	 cout << endl <<  "   a" << i << "\t=  " << coeff[i];

  Error_At_41_Equally_Spaced_Pts(2) ;
}

void Error_At_41_Equally_Spaced_Pts(int method)
{
  double z[41],y[41] ;           

  for (int j=0; j<41; j++)
	 z[j] = cos((j * PI)/80) ;          // load points

  for (j=0; j<41; j++)
	 y[j] = ((j * PI)/80) ;          // load points

  double total_error = 0 ;

  if (method == 1)  
  for (j=0; j<41; j++)
  {
	 double x1 = y[j], error = coeff[n-1] ;
	 for (int i=n-1 ; i > 0 ; i--)
		error =  error*(x1 - x[i-1]) + coeff[i-1] ;
	 error -= z[j] ;      
	 total_error += fabs(error) ;  
  }                   
  else
  for (j=0; j<41; j++)
  {
	 double x1 = y[j], error = coeff[n-1] ;
	 for (int i=n-1 ; i > 0 ; i--)
		error =  error*(x1 - chebyshev[i-1]) + coeff[i-1] ;
	 error -= z[j] ;       
	 total_error += fabs(error) ;    
  } 
  cout << "\n\nAvg Error:  " << total_error/41.0 ;
}