Вход

Метод покоординатного спуска (C++)

Реферат* по программированию
Дата добавления: 24 июня 2006
Язык реферата: Русский
Word, rtf, 1.4 Мб (архив zip, 67 кб)
Реферат можно скачать бесплатно
Скачать
Данная работа не подходит - план Б:
Создаете заказ
Выбираете исполнителя
Готовый результат
Исполнители предлагают свои условия
Автор работает
Заказать
Не подходит данная работа?
Вы можете заказать написание любой учебной работы на любую тему.
Заказать новую работу
* Данная работа не является научным трудом, не является выпускной квалификационной работой и представляет собой результат обработки, структурирования и форматирования собранной информации, предназначенной для использования в качестве источника материала при самостоятельной подготовки учебных работ.
Очень похожие работы



ОглаВЛЕНИЕ


Задание 2

Краткое описание метода

покоординатного спуска с удвоением шага 3

Текст программы 4

Результаты решения и его проверки 9

Результаты отыскания минимума квадратичной функции 9

Результаты решения системы линейных уравнений 9

Проверка вычислений при различных начальных векторах 10

Список литературы 12



Задание



1). Изложить метод покоординатного спуска (МПС) для отыскания минимума квадратичной функции

где

, , , - симметричная положительно определенная матрица.


2). Реализовать МПС на компьютере с дроблением шага. В качестве критерия прекращения спуска предусмотреть из следующих:

а) ; б) .

Продемонстрировать работу программы для:


;


Выходные данные программы:

, , , где - номер последнего шага.

Входные данные: .

Решить систему и сравнить с .

Проверить вычисления при различных начальных векторах и проследить за зависимостью от .


Квадратичная функция в данном задании будет иметь вид:



Краткое описание метода покоординатного спуска с удвоением шага


Каждый цикл метода характеризуется тем, что величина шага в течение всех n итераций цикла остается постоянной. Цикл состоит в вычислении точек . Предполагается, что в результате завершения предыдущего цикла получена величина шага .

-я итерация цикла :

Если

(А) ,

то полагают и переходят к следующей итерации.

Если

(В) ,

то вычисляют .

Если

(С) ,

то полагают и переходят к следующей итерации.

Если

(D) ,

то полагают и переходят к следующей итерации.

В случае, если неравенства (В) и (D) имеют место для всех , то уменьшают величину , как правило, полагая , и переходят к следующему циклу, т.е. повторяют все процедуры предыдущего цикла, но уже с двое меньшим шагом.



Текст программы



#include

#include

#include

#include


void Readstr(char *s, int max) // reads a string

{

int c;

while((c = getchar()) != '\n')

{

if(max>1)

*s++ = c, max--;

if(max>0)

*s = 0;

}

}


void ReadMatrix(int flag, double *a, double *c, int sz) //reads the matrix

{

FILE *f; //the matrix file

int i, j;


if(flag == 1) //if that file exists

{

f = fopen("matrix.txt", "rt"); //opens file on reding and check its existence

if(f == NULL) //if file don't exist

{

printf("No file is found. \n");

return;

}

int ch;

for(i=0; i

{

for(j=0; j

{

if(((ch = fgetc(f)) != EOF) && j

fscanf(f, "%lf", &a[i*sz + j]);

else if(j == sz)

fscanf(f, "%lf", &c[i]);

}

}

fclose(f); //closes the file

}

else if(flag == 2) //if you enter a matrix yourself

{

for(i=0; i

{

for(j=0; j

{

printf("Enter an A[%i][%i] element ", i, j);

scanf("%lf", &a[i*sz + j]);

}

}

for(j=0; j

{

printf("\nEnter an b[%i] element ", j);

scanf("%lf", &c[j]);

}

}

}


bool CheckII(double *x, double *prev, int sz, double acc, double &q, double r, double &e, double f)

{ // checking roots by ||x[k] - x[k-1]||

double n = 0;

double w;

int i,j;


for(j=0; j

{

if(fabs((x[j] - prev[j])) >= acc)

n++;

}


if(n==0) // ||x[k] - x[k-1]||

{

q = fabs((x[0] - prev[0]));

for(i=1; i

{

w = fabs((x[i] - prev[i]));

if(w>=q)

q = w;

}

e = r - f; // f(x[k]) - f(x[k-1])

}

if(n)

return false;

else

return true;

}


double MPS(double *a, double *c, double *x, int sz, double acc, int &p, double &q, double &e)

{ //minimizes function "f"

double *prev,g,f,z,r;

double l = 0.7; // the first value of step

int i,j,k,t,y;


prev = new double[sz];


for(i=0; i

{

for(j=0; j

{

a[i*sz + j] = a[i*sz + j]/2; // (1/2)*A

}

}


z = 0;

y=0;


for(i=0; i +

{

g = 0;

for(j=0; j

{

g += a[i*sz + j]*x[j];

}

g = g*x[i];

z += g + c[i]*x[i];

}


do //makes and count iterations

{

yo: for(k=0; k

{

prev[k] = x[k]; // saves previous iteration results

}


t = 0;

for(k=0; k

{

x[k] -= l; // f(x[k-1] - l*e)

f = 0;

for(i=0; i

{

g = 0;

for(j=0; j

{

g += a[i*sz + j]*x[j];

}

g = g*x[i];

f += g + c[i]*x[i];

}

if(!(f= f(x[k-1])

{

x[k] += 2*l; // f(x[k-1] + l*e)

f = 0;

for(i=0; i

{

g = 0;

for(j=0; j

{

g += a[i*sz + j]*x[j];

}

g = g*x[i];

f += g + c[i]*x[i];

}

if(!(f= f(x[k-1])

{

x[k] = prev[k];

t++;

}

else // f(x[k-1] + l*e) < f(x[k-1])

{ r = z; z = f;} // saves previous value of function "f"

}

else // f(x[k-1] - l*e) < f(x[k-1])

{r = z; z = f;} // saves previous value of function "f"

}

if(t==sz)

{

l = l/2; // the step subdivision

goto yo;

}

p++; // a number of steps

} while(!CheckII(x,prev,sz,acc,q,r,e,f)); // ||x[k] - x[k-1]|| < acc


return f;

delete prev;

}

void main(void)

{

double *a, *x, *c, acc; //presents arrays and an accuracy

double f,q,e;

int p, sz; //presents the size of your matrix and the number of iterations

int h, i;

printf("Enter the size of your matrix: "); // asks for the size of your matrix

scanf("%i", &sz);

printf("Enter an accuracy: "); // asks for an accuracy

scanf("%lf", &acc);


a = new double[sz*sz];

c = new double[sz];

x = new double[sz];

do //asks your wish about the entering your matrix

{

printf("Press 1 if you want to read your matrix from the file (matrix.txt)\n");

printf("Press 2 if you want to enter your matrix yourself\n");

scanf("%i",&h);

Readstr(NULL, 0);

}while((h != 1) && (h != 2));

for(i=0; i

{

printf("Enter the first approximation: x[%i] = ", i);

scanf("%lf", &x[i]);

}

ReadMatrix(h, a, c, sz); //reads the matrix

p=0;

q=0;

e=0;

f = MPS(a,c,x,sz,acc,p,q,e);

for(i=0; i

{

printf("\nx[%i] = %.10lf", i, x[i]);

}

printf("\nf = %.10lf", f); //shows value of function "f"

printf("\n\n\nThe number of steps: %i\n", p); //shows the number of steps we need

printf("\n||x[k] - x[k-1]|| = %.10lf\n", q); //shows ||x[k] - x[k-1]||

printf("\nf(x[k]) - f(x[k-1]) = %.10lf\n", e); //shows f(x[k]) - f(x[k-1])

delete a;

delete c;

delete x;

}



Результаты решения и его проверки


Результаты отыскания минимума квадратичной функции

Копия с экрана:


Enter the size of your matrix: 4

Enter an accuracy: 0.001

Press 1 if you want to read your matrix from the file (matrix.txt)

Press 2 if you want to enter your matrix yourself

1

Enter the first approximation: x[0] = 0

Enter the first approximation: x[1] = 0

Enter the first approximation: x[2] = 0

Enter the first approximation: x[3] = 0

x[0] = -1.0000976562

x[1] = 0.0000000000

x[2] = 0.0000000000

x[3] = -1.0000976562

f = -2.3644999775

The number of steps: 9

||x[k] - x[k-1]|| = 0.0006835938

f(x[k]) - f(x[k-1]) = 0.0000003388

Press any key to continue


Результаты решения системы линейных уравнений

Копия с экрана:


Enter the size of your matrix: 4

Enter an accuracy: 0.001

Press 1 if you want to read your matrix from the file (matrix.txt)

Press 2 if you want to enter your matrix yourself

1

Enter the first approximation: x[0] = 0

Enter the first approximation: x[1] = 0

Enter the first approximation: x[2] = 0

Enter the first approximation: x[3] = 0

x[0] = -0.9999910679

x[1] = -0.0000040529

x[2] = 0.0000004381

x[3] = -1.0000010247

c[0] = -2.43998 acc[0] = 0.00002 c[1] = -0.77300 acc[1] = -0.00000 c[2] = -0.632

00 acc[2] = 0.00000 c[3] = -2.28900 acc[3] = 0.00000

The number of iterations: 7

Tell this program: So Wassup?!

Yea, alright!

Press any key to continue


Проверка вычислений при различных начальных векторах

Результаты вычислений сведены в таблицу:



Х1

Х2

Х3

Х4

Примечание




1.

0

0

0

0

9

-1.0000976562

0.0000000000

0.0000000000

-1.0000976562

0.0006835938

-2.3644999775

0.0000003388

-0.9999910679

-0.0000040529

0.0000004381

-1.0000010247

0,0001065883




2.

1

-2

3

-4

11

-1.0001953125

0.0001953125

0.0000488281

-1.0000488281

0.0003417969

-2.3644999423

0.0000001620

-1.0000054308

0.0000022497

-0.0000008345

-0.9999991940

0,0001930628




3.

10

-20

30

-40

73

-1.0003906250

-0.0000976562

-0.0001953125

-0.9996093750

0.0006835937

-2.3644987644

-0.0000007643

-1.0000113456

0.0000037423

-0.0000042787

-0.9999974999

0,0003881249




4.





100

-200

300

-400

584

-1.0002929688

0.0003906250

0.0000976563

-1.0000000000

0.0006835937

-2.3644993380

-0.0000001663

-1.0000172256

0.0000042530

-0.0000102787

-0.9999949862

0,0002757432




5.

1000

-2000

3000

-4000

5724

-1.0000000000

0.0001464844

-0.0000488280

-1.0001464836

0.0003417969

-2.3644999449

0.0000000035

-1.0000023934

-0.0000001994

-0.0000035206

-0.9999986296

0,000147854




6.

10000

-20000

30000

-40000

57151

-0.9998046904

0.0000976470

0.0001952913

-0.9999022946

0.0006835937

-2.3644998757

0.0000002367

-1.0000013968

-0.0000014260

-0.0000055218

-0.9999980838

0,0002008131




7.

100000

-200000

300000

-400000

571443

-0.9999020883

0.0002911854

-0.0001000810

-1.0001963537

0.0006835938

-2.3644996420

0.0000000043

-0.9999979412

-0.0000038900

-0.0000077247

-0.9999977163

0,0002950754




8.

1000000

-2000000

3000000

-4000000

5714293

-1.0001617430

0.0001855390

-0.0000929356

-0.9997993502

0.0003417969

-2.3644996952

-0.0000001419

-0.9999898859

-0.0000082574

-0.0000092154

-0.9999980332

0,000198683




9.

10000000

-20000000

30000000

-40000000

57142871

-0.9997338118

-0.0001125674

0.0000401392

-0.9998566369

0.0006835937

-2.3644991417

-0.0000004546

-0.9999741289

-0.0000152241

-0.0000079577

-0.9999999970

0,0002403171




Список литературы


1). В.Г. Карманов. Математическое программирование – М., Наука, 1980.

2). Н.С.Бахвалов. Численные методы – М.: Физматлит, 1973.

3). Б.П.Демидович и И.А.Марон. Основы вычислительной математики –М.: Физматлит, 1960.



© Рефератбанк, 2002 - 2024