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