Минимизация квадратных функций. Градиентный метод наискорейшего спуска, страница 3

for i:=1 to d do z:=z+ax[i]*x[k-2,i];

for i:=1 to d do z1:=z1+b[i]*x[k-2,i];

f1:=(1/2)*z+z1;

//цикл нахождения значения функционала в т. xk

for j:=1 to d do begin

ax[j]:=0;

for i:=1 to 4 do  ax[j]:= ax[j]+a[i,j]*x[k-1,i];

end;

z:=0;

z1:=0;

for i:=1 to d do z:=z+ax[i]*x[k-1,i];

for i:=1 to d do z1:=z1+b[i]*x[k-1,i];

f2:=(1/2)*z+z1;

//цикл нахождения A*x-b

for j:=1 to d do begin

axb[j]:=0;

for i:=1 to d do axb[j]:= axb[j]+a[i,j]*x[k-1,i];

if j>1 then axb[j]:=axb[j-1] + kv(axb[j]-b[j])

else axb[j]:=kv(axb[j]-b[j]);

end;

//цикл нахождения ||xk-xk-1||^2

for j:=1 to d do begin

if j>1 then xx[j]:=xx[j-1]+kv(x[k-1,j]-x[k-2,j])

else xx[j]:=kv(x[k-1,j]-x[k-2,j]);

end;

end;

//количество шагов

label1.caption:=inttostr(k);

//заполнение поля ответа

for i:=1 to d do begin

st3.cols[0][i-1]:=fs(x[k,i]);

st4.cols[0][i-1]:=fs(x[k,i] - x[k-1,i]);

end;

end;

end;

Общее число компилируемых линий:214

Полный размер кода без информации отладки: 337212 bytes

Память, необходимая хранить глобальные переменные: 5705 bytes

Память, необходимая хранить локальные переменные: 16384 bytes

Размер конечного файла: 388096 bytes

Оперативная память при загрузке: 2154496 bytes

Оперативная память при автозаполнении: +659456 bytes

Оперативная память при нахождении решения: +4096 bytes

Другие виды памяти: 196608 bytes

Результаты: процесс спуска прекратился на 3943 шаге,  все три критерия обеспечивают примерно одно и то же условие остановки при ξ=10^-15.

||x³⁹⁴³-x³⁹⁴²||= 9,91851272148332E-16(мало=>точность решения)

X(0)	x(3943)	x3943-x3942	A*x(3943)
1	-8,73839798985883E-14	7,85787878018883E-16	-3,4
1	-0,999999999999964	-9,99200722162641E-16	-3,8
1	2,29141536796884E-14	-5,89340908514159E-16	-2,60000000000001
1	-0,999999999999983	-7,7715611723761E-16	-5,8

Таким образом, мы получили на основании пункта 1, что минимум заданного функционала достигается при x=x⁽³⁹⁴³⁾.

Рассмотрим вопрос обусловленности нашей задачи:

Cond(A)=280, т.е. очень велико относительно единицы, а это говорит о том, что при малейших изменениях начальных параметров результаты потерпят значительные отклонения.

ОТВЕТ задание 3

Рассмотрим решение системы Ax=b:

X*	x*- x(3943)	x3943-x3942
-8,46852969693668E-14	-2,6986829292215E-15	7,85787878018883E-16
-0,999999999999965	1,00001387379201E-15	-9,99200722162641E-16
2,23299026838597E-14	5,842509958287E-16	-5,89340908514159E-16
-0,999999999999983	0	-7,7715611723761E-16

||x³⁹⁴³-x³⁹⁴²||= 9,91851272148332E-16

||x^*-x³⁹⁴²||= 2,93671015362001E-15

ð  ||x³⁹⁴³-x³⁹⁴²||<||x*-x³⁹⁴²||

Следовательно, найденная точка, которая обеспечивает минимум нашему функционалу, очень близка к точному решению систему Ax=b, о чём и говорит теорема1. 

Данные выводы могут распространятся для любых крайних шагов (k).

Теперь исследуем зависимость результата от задания начальных приближений:

рассмотрим:

||x^(m) -x*|| =<(||r⁽⁰⁾||/λ_n)[( λ₁-λ_n)/( λ₁+ λ_n)]^m

ð  Lim| ||x^(m) -x*|| -(||r⁽⁰⁾||/λ_n)[( λ₁-λ_n)/( λ₁+ λ_n)]^m  | = 0 <=>

r⁽⁰⁾ → 0,  m→ + _°°

Следовательно, чем меньше(норма) вектор x⁽⁰⁾ тем быстрей произойдёт остановка спуска и, наоборот, чем больше(норма) тем больше потребуется шагов для нахождения минимума функционала.

НАПРИМЕР:

k=3664	K=3851	k=3967	k=3663	k=3413	k=3833	k=4231
0,3	0,5	0,9	2	7	55	1000
0,3	0,5	0,9	2	7	55	1000
0,3	0,5	0,9	2	7	55	1000
0,3	0,5	0,9	2	7	55	1000

То есть существует ещё зависимость положения начального вектора, относительно единичного.

ВЫВОД:

Градиентный метод наискорейшего спуска (ГМНС) для отыскания минимума квадратной функции является нелинейным в отличие от метода итерации и метода Зейделя, т.к. приближение x^(k+1) выражается через x^(k) нелинейно. Ответ даёт не только минимум для функционала, но и решение системы Ax=b.