8 тажриба машғулот Энг кичик квадратлар усули билан объектни

Polinom funktsiyalarining eng kichik kvadratchalar usuli bilan yaqinlashishi. Algoritm C tilida dastur shaklida amalga oshiriladi, siz dastur qismida yuklab olishingiz mumkin. Birinchidan, taxminan nima ekanligini va bu muammoni qanday hal qilganini tasvirlab beramiz. X0, x1, x 2 nuqtalarida ba'zi segmentlarga ruxsatbering ... xN biz f(x) funktsiyasining qiymatlarini bilamiz, ya'ni y0, y1, y2, ... yN. F(x) = a0 + ax + a 2 x 2 + turidagi a i parametrlarini aniqlash kerak ... + akx^k, qaerda k bunday, qadriyatlar kvadratchalar yig'indisi y funktsiya qadriyatlar f(y) berilgan nuqtalarda x minimal edi, t . u. S = S [yi - F (xi, a0, a1...ak)]^2 -> min Geometrik jihatdan, bu y = F(x) egri, ma'lum bir nuqtalarning har biriga iloji boricha yaqinroq bo'lgan polinni topish kerakligini anglatadi. Bunday tenglama tizimini hal qilsangiz, bunday muammoni hal qilish mumkin: a0n + a1Σ xi + a2Σ xi^2 + ... + akΣ xi^k = Σ yi a0Σ xi + a1Σ xi^2 + a2Σ xi^3 + ... + akΣ xi^k+1 = Σ xiyi ... a0Σ xi^k + a1Σ xi^k+1 + a2Σ xi^k+2 + ... + akΣ xi^2k = Σ xi^kyi S belgisi ostida hamma joyda 0 dan N gacha bo'lgan summani bildiradi. Tizimni hal qilish uchun biz Gauss usulidan foydalanamiz, unda tenglama tizimi uchburchak shaklga olib keladi. Men bu usulni allaqachon tasvirlab berdim. Ushbu bo'limda tasvirlangan dastur yuqorida aytib o'tilganlarga asoslanadi, shuning uchun men Gauss usulining mohiyatiga batafsil to'xtalib o'tmayman, faqat dasturning matnini keltiraman va u bilan ishlash usulini, shuningdek uning tuzilishini qisqacha tasvirlab beraman, ya'ni ushbu dasturda juda ko'p miqdordagi rutinlar xizmat qiladi. #include #include #include float *a, *b, *x, *y, **sums; int N, K; //N - number of data points //K - polinom power //K<=N char filename[256]; FILE* InFile=NULL; void count_num_lines(){ //count number of lines in input file - number of equations int nelf=0; //non empty line flag do{ nelf = 0; while(fgetc(InFile)!='\n' && !feof(InFile)) nelf=1; if(nelf) N++; }while(!feof(InFile)); } void freematrix(){ //free memory for matrixes int i; for(i=0; idelete [] sums[i]; } delete [] a; delete [] b; delete [] x; delete [] y; delete [] sums; } void allocmatrix(){ //allocate memory for matrixes int i,j,k; a = new float[K+1]; b = new float[K+1]; x = new float[N]; y = new float[N]; sums = new float*[K+1]; if(x==NULL || y==NULL || a==NULL || sums==NULL){ printf("\nNot enough memory to allocate. N=%d, K=%d\n", N, K); exit(-1); } for(i=0; isums[i] = new float[K+1]; if(sums[i]==NULL){ printf("\nNot enough memory to allocate for %d equations.\n", K+1); } } for(i=0; ia[i]=0; b[i]=0; for(j=0; jsums[i][j] = 0; } } for(k=0; kx[k]=0; y[k]=0; } } void readmatrix(){ int i=0,j=0, k=0; //read x, y matrixes from input file for(k=0; kfscanf(InFile, "%f", &x[k]); fscanf(InFile, "%f", &y[k]); } //init square sums matrix for(i=0; ifor(j=0; jsums[i][j] = 0; for(k=0; ksums[i][j] += pow(x[k], i+j); } } } //init free coefficients column for(i=0; ifor(k=0; kb[i] += pow(x[k], i) * y[k]; } } } void printresult(){ //print polynom parameters int i=0; printf("\n"); for(i=0; iprintf("a[%d] = %f\n", i, a[i]); } } void diagonal(){ int i, j, k; float temp=0; for(i=0; iif(sums[i][i]==0){ for(j=0; jif(j==i) continue; if(sums[j][i] !=0 && sums[i][j]!=0){ for(k=0; ktemp = sums[j][k]; sums[j][k] = sums[i][k]; sums[i][k] = temp; } temp = b[j]; b[j] = b[i]; b[i] = temp; break; } } } } } void cls(){ for(int i=0; i<25; i++) printf("\n"); } void main(){ int i=0,j=0, k=0; cls(); do{ printf("\nInput filename: "); scanf("%s", filename); InFile = fopen(filename, "rt"); }while(InFile==NULL); count_num_lines(); printf("\nNumber of points: N=%d", N); do{ printf("\nInput power of approximation polinom Kscanf("%d", &K); }while(K>=N); allocmatrix(); rewind(InFile); //read data from file readmatrix(); //check if there are 0 on main diagonal and exchange rows in that case diagonal(); fclose(InFile); //printmatrix(); //process rows for(k=0; kfor(i=k+1; iif(sums[k][k]==0){ printf("\nSolution is not exist.\n"); return; } float M = sums[i][k] / sums[k][k]; for(j=k; jsums[i][j] -= M * sums[k][j]; } b[i] -= M*b[k]; } } //printmatrix(); for(i=(K+1)-1; i>=0; i--){ float s = 0; for(j = i; js = s + sums[i][j]*a[j]; } a[i] = (b[i] - s) / sums[i][i]; } printresult(); freematrix(); } Чтобы воспользоваться этой программой, нужно запустить скомпилированный исполняемый файл. В первую очередь программа спросит, откуда ей брать данные для интерполяции. Создайте в любом текстовом редакторе (но только не в Word-е а, например в notepad-е) файл, где напишите значения xi, yi, построчно через пробел, приблизительно так: x0 y0 x1 y1 x2 y2 ... xN yN Например: 1 5.95 2 20.95 3 51.9 4 105 5 186 6 301 7 456.1 8 657.1 Этот файл необходимо создать в той директории, где лежит программа, иначе она его не найдет. Программа спросит степень полинома, каким вы хотите аппроксимировать данные. При этом степень полинома должна быть менее числа заданных точек (в данном случае восьми). Введите, например, 3. В результате работы программы, она выдаст нечто вроде: a[0] = 0.996902 a[1] = 1.938750 a[2] = 2.016942 a[3] = 0.999054 Это и есть решение системы уравнений, т.е. набор неизвестных коэффициентов ai. Т.е. по нашим данным был построен аппроксимирующий многочлен F(x) = 1 + 2x + 2x^2 + x^3. (я округлил решение до целых чисел) Коротко опишем, для чего служит такое большое количество подпрограмм и переменных в данной программе: a - неизвестные коэффициенты полинома b - столбец свободных членов (в правой части уравнений) x - координаты, заданные в файле y - координаты, заданные в файле sums - суммы степеней x,y при неизвестных коэффициентах полинома N - число заданных точек в файле K - степень аппроксимирующего полинома void count_num_lines() - подсчитывает количество точек, где задана функция void allocmatrix() - выделяет память для массивов a, b, x, y, sums void readmatrix() - прочитывает из файла координаты точек и вычисляет sumsij void diagonal() - делает так, чтобы на главной диагонали не было нулей, чтобы не пришлось однажды делить на ноль в процессе приведения системы к треугольному виду void printresult() - распечатывает получившийся столбец решений void freematrix() - освобождает память, которая была выделена ранее void cls() - стирает экран в начале работы программы void main() - основная функция из которой последовательно вызываются все вышеперечисленные функции, и проходит процесс приведения системы уравнений к треугольному виду и обратная прогонка.