ОглаВЛЕНИЕ
Задание 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.