Interpolacja wielomianowa. Wzór Lagrange. Wzór Czebyszwa.

/*
Autor: Dawid Mocek
Działa na MS VS Express 2013 lub jakimkolwiek kompilatorze  C++11
Generuje pliki do otwarcia od razu w Excel`u i skonstruowania wykresów
wersja: 2013/01/27  mam nadzieje że w 100% poprawna

Zadanie:

Interpolacja wielomianowa, wzór Lagrange`a
Funkcja interpolowana: f(x)=|cos(x)|
Parametry:
x E <-3,3>, x E <-6,6>
n = 7,8,15,16
mn.n E <100;200>

W programie nalzey zmienic: string katalog_wynikowy

*/
#include <iostream>
#include <iomanip>
#include <cmath>
#include <ostream>
#include <fstream>
#include <cmath>
#include <string>
#include <vector>

// 0 lub 1. Pokazuje troche więcej informacji na stand. wyjsciu
#define DEBUG 1

#define PI 3.14

using namespace std;


/*
Filtr konwersji CSV z pakietu Microsoft Office pracuje przy założeniu, że plik CSV używa przecinka jako separatora,
tymczasem Microsoft Excel i Access wyświetlają i zapisują plik CSV w formacie zgodnym z ustawieniami regionalnymi systemu,
czyli w przypadku języka polskiego używa średnika zamiast przecinka do rozdzielania pól. Aby umożliwić automatyczną konwersję,
tworzone są dedykowane makra.
*/
#define DELIMITER  ";"

#pragma region Funkcje dla debug

void ShowArr_1D(const string nazwa, const double *arr, const int size)
{
    cout << nazwa << ": ";
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}


#pragma endregion

string intToStr(int n)
{
    string tmp, ret;
    if (n < 0) {
        ret = "-";
        n = -n;
    }
    do {
        tmp += n % 10 + 48;
        n -= n % 10;
    } while (n /= 10);
    for (int i = tmp.size() - 1; i >= 0; i--)
        ret += tmp[i];
    return ret;
}


// imbue(locale("")); powoduje zapis liczb zmiennoprzecinkowych z przecinkiem(0,33333) nie kropką(0.333) dla systemow z Locale pl_PL
inline void SetFileAttr(fstream &f, const int precision)
{
    f.imbue(locale(""));
    f.precision(precision);
}

// Nasza funkcja interpolowana f(x)
inline double fcosx(const double x)
{
    return abs(cos(x));
}

// interpolacja
double lagrangeInterpolation(const double *X, const int x_len, const double *Y, const int y_len, const double x)
{

    double y = 0;

    for (int i = 0; i < x_len; i++)
    {
        double t = 1;
        for (int j = 0; j < y_len; j++)
        {
            if (j != i)
            {
                t *= (x - X[j]) / (X[i] - X[j]);
            }
        }
        y += Y[i] * t;
    }
    return y;
}

// Wzor Czebyszwa jest bardzo mocno rozbity ponieważ na technicznym kalulatorze wychodzily znacznie wyzsze(bliższe) wyniki
double * czebyszew(const double a, const double b, const int n)
{
    double *tablica_czebyszewa = new double[n];
    double arg = 0, res = 0;
    double part1 = 0.5 * (a + b);
    double part2 = 0.5 * (b - a);
    int i = 0;

    for (int i = 0; i < n; i++)
    {
        double tmp_n = (double)(n - 1);
        double tmp_i = (double)i;
        double tmp_k = (double)((2 * tmp_i) + 1);
        double tmp_l = (double)((2 * tmp_n) + 2);
        double tmp_o = tmp_k / tmp_l;
        arg = tmp_o * PI;
        double z = cos(arg);
        res = part1 - (part2 * z);
        tablica_czebyszewa[i] = res;
    }

    return tablica_czebyszewa;
}

double * rownoodlegle(const double a, const double b, const int n)
{

    double *tablica_przedzialow = new double[n];
    double h = (b - a) / (double)(n - 1);
    for (int i = 0; i < n; i++)
        tablica_przedzialow[i] = a + ((double)i * h);;

    return tablica_przedzialow;
}

void InterpolacjaRownoodlegle(const string dir, const double a, const double b, const int n, const double density, const int precision)
{
#if(DEBUG)
    cout << "<rownoodlegle>" << endl << endl;
#endif

    int real_n = n + 1;

    string csv_plik = dir + "\\InterpolacjaRownoodegle_n" + intToStr(n) + "_a" + intToStr(a) + "_b" + intToStr(b) + ".csv";
    string csv_wezly_plik = dir + "\\InterpolacjaRownoodegle_n" + intToStr(n) + "_a" + intToStr(a) + "_b" + intToStr(b) + "_wezly.csv";

    fstream csv(csv_plik, ios::trunc | ios::in | ios::out);
    fstream csv_wezly(csv_wezly_plik, ios::trunc | ios::in | ios::out);

    SetFileAttr(csv, precision);
    SetFileAttr(csv_wezly, precision);

    double *rowno_data = rownoodlegle(a, b, real_n);
    double *y_fcosx = new double[real_n];
    double *y_wezly = new double[real_n];
    for (int z = 0; z < real_n; z++)
    {
        y_fcosx[z] = fcosx(rowno_data[z]);
        y_wezly[z] = lagrangeInterpolation(rowno_data, real_n, y_fcosx, real_n, rowno_data[z]);
    }


#if(DEBUG)
    ShowArr_1D("    x", rowno_data, real_n);
    ShowArr_1D(" f(x)", y_fcosx, real_n);
    ShowArr_1D("wezly", y_wezly, real_n);

#endif

    // Zliacza ilosc iteracji
    int i_tmp = 0;

    // Nagłowek CSV
    csv << "\"x\"" << DELIMITER << "\"f(x)\"" << DELIMITER << "\"L(x) - rownoodegle\"" << DELIMITER << "\"L(x)-f(x)\"" << endl;

    double z = a;
    while (z < b)
    {
        // Dane CSV
        double x = fcosx(z);
        double lag = lagrangeInterpolation(rowno_data, real_n, y_fcosx, real_n, z);
        csv << z << DELIMITER << fixed << x << DELIMITER << lag  << DELIMITER << lag-x << endl;
        z += density;
        ++i_tmp;
    }

    // Zrzuca wezly
    csv_wezly << "\"x\"" << DELIMITER << "\"f(x)\"" << DELIMITER << "\"L(x) - rownoodegle\"" << endl;
    for (int z = 0; z < real_n; z++)
        csv_wezly << rowno_data[z] << DELIMITER << y_fcosx[z] << DELIMITER << y_wezly[z] << endl;

    delete[] rowno_data;
    delete[] y_fcosx;
    delete[] y_wezly;


    rowno_data = NULL;
    y_fcosx = NULL;
    y_wezly = NULL;

    csv.close();
    csv_wezly.close();

#if(DEBUG)
    cout << "   Ilosc iteracji: " << i_tmp << endl;
    cout << endl << "</rownoodlegle>" << endl;
#endif

}

void InterpolacjaCzebyszew(const string dir, const double a, const double b, const int n, const double density, const int precision)
{
#if(DEBUG)
    cout << "<czebyszew>" << endl << endl;
#endif

    int real_n = n + 1;

    string csv_plik = dir + "\\InterpolacjaCzebyszew_n" + intToStr(n) + "_a" + intToStr(a) + "_b" + intToStr(b) + ".csv";
    string csv_wezly_plik = dir + "\\InterpolacjaCzebyszew_n" + intToStr(n) + "_a" + intToStr(a) + "_b" + intToStr(b) + "_wezly.csv";

    fstream csv(csv_plik, ios::trunc | ios::in | ios::out);
    fstream csv_wezly(csv_wezly_plik, ios::trunc | ios::in | ios::out);

    SetFileAttr(csv, precision);
    SetFileAttr(csv_wezly, precision);

    double *czebyszew_data = czebyszew(a, b, real_n);
    double *y_fcosx = new double[real_n];
    double *y_wezly = new double[real_n];

    for (int z = 0; z < real_n; z++)
    {
        y_fcosx[z] = fcosx(czebyszew_data[z]);
        y_wezly[z] = lagrangeInterpolation(czebyszew_data, real_n, y_fcosx, real_n, czebyszew_data[z]);
    }

#if(DEBUG)
    ShowArr_1D("    x", czebyszew_data, real_n);
    ShowArr_1D(" f(x)", y_fcosx, real_n);
    ShowArr_1D("wezly", y_wezly, real_n);
#endif

    // Zliacza ilosc iteracji
    int i_tmp = 0;

    // Nagłowek CSV
    csv << "\"x\"" << DELIMITER << "\"f(x)\"" << DELIMITER << "\"L(x) - czebyszew\"" << DELIMITER << "\"L(x)-f(x)\"" << endl;

    double z = a;
    while (z < b)
    {
        // Dane CSV
        double x = fcosx(z);
        double lag = lagrangeInterpolation(czebyszew_data, real_n, y_fcosx, real_n, z);
        csv << z << DELIMITER << fixed << x << DELIMITER << lag << DELIMITER << lag - x << endl;

        z += density;
        ++i_tmp;
    }

    // Zrzuca wezly
    csv_wezly << "\"x\"" << DELIMITER << "\"f(x)\"" << DELIMITER << "\"L(x) - czebyszew\"" << endl;
    for (int z = 0; z < real_n; z++)
        csv_wezly << czebyszew_data[z] << DELIMITER << y_fcosx[z] << DELIMITER << y_wezly[z] << endl;


    delete[] czebyszew_data;
    delete[] y_fcosx;
    delete[] y_wezly;

    czebyszew_data = NULL;
    y_fcosx = NULL;
    y_wezly = NULL;

    csv.close();
    csv_wezly.close();

#if(DEBUG)
    cout << "   Ilosc iteracji: " << i_tmp << endl;
    cout << endl << "</czebyszew>" << endl;
#endif
}

int main(void)
{
    int stop;

    // lista zakresow <a; b>
    vector<vector<int>> zakresy{ { -3, 3 }, { -6, 6 } };
    //vector<vector<int>> zakresy{ { -6, 6 } };

    // Gestosc - zmiana tego spowoduje utracenie zgodnosc wezlow na wykresie z funkcjami interpolujaca i interpolowana
    double density = 0.05;

    // Precyzja liczb zmiennoprzecinkowych
    int precision = 10;

    // Węzeł/y
    int nTab[] = { 7, 8, 15, 16 };

    // Katalog wynikowy
    string dir = "D:\\inter";

    for (vector<vector<int>>::iterator it = zakresy.begin(); it != zakresy.end(); ++it)
    {
        vector<int> tmp = *it;

        int a = tmp[0];
        int b = tmp[1];

        for each (int n in nTab)
        {



#if(DEBUG)
            cout << "Generacja dla: <a, b> = <" << a << ", " << b << ">" << ", n = " << n << ", gestosc = " << density << endl << endl;
#endif
            InterpolacjaRownoodlegle(dir, a, b, n, density, precision);
            InterpolacjaCzebyszew(dir, a, b, n, density, precision);

        }
    }
    cout << "Koniec";
    cin >> stop;
    return 0;
}