/*
 * Created on 2005-2-26	by 可冰(k.b)
 *
 * 此算法實現了Lagrange插值.
 * 
 */
 
/**
 * @author k.b
 * 
 * TODO 2005-2-26:
 * 		不過現在還沒有實現截斷誤差的分析
 * 		還可以添加一些功能,如給定一組值后算出所有可能組合的值(有一定
 * 	上限),并可根據截斷誤差的比較可得出最好的一組數據.
 */


#include <stdio.h>
#include <stdlib.h>


//求Lagrange插值:
//輸入: ( x[i], y[i] ) 已知的n+1組值; n 多項式次數; x 將求的自變量
//輸出: y 求得的函數值
void Lagrange( double* xi, double* yi, const int n,
				double x, double* y )
{
	int i, j;
		
	double tmp = 1.0;	//連乘積
	*y = 0.0;
		
	for( i = 0; i < n+1; i++ )
	{
		for( j = 0, tmp = 1.0; j < n+1; j++ )
		{
			//跳過x[i] - x[i]
			if( j == i ) continue;
			tmp *= ( x - xi[j] ) / ( xi[i] - xi[j] );
		}
		
		*y += tmp * yi[i];
	}
}
//end Lagrange


//初始值:
const int n = 2;	//多項式次數
double xi[] = { 0.5, 0.6, 0.7 };
double yi[] = { 0.47943, 0.56464, 0.64422 };

double x = 0.57891;

//結果值:
double y = 0.0;


int main()
{
	Lagrange( xi, yi, n, x, &y );
	
	printf( "%f", y );
	
	system( "Pause" );
	return 0;
}