Вход

Метод покоординатного спуска (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 - 2017