Исследование методов решения линейных уравнений
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
?араллельным координатным осям.
Градиентные методы очень просты в реализации и поэтому часто используются на практике. Но при сложной структуре f(Xk) они могут плохо сходится. Поэтому используют вторые производные f(Xk).
Рис.5
Метод второго порядка
Рис.6
Методы второго порядка являются обобщенным методом Ньютона. На рис.6 приведена геометрическая интерпретация отыскания корня уравнения j(X)=0 методом касательных. Разложение j(X) в окрестности Xk дает
j(X) = j(Xk) + j(Xk)(X - Xk) + 0(| X - Xk |)
Отбрасывая малые высшего порядка и пологая, что j(X)=0,получим
X = Xk+1 = Xk - j(Xk) / j(Xk).
Пусть теперь j(X)- функция n-мерного аргумента. Разложим ее в ряд Тейлора, отбросив малые высшего порядка
j(Xk) + j(Xk)(X - Xk)., откуда Xk+1 = Xk - j(Xk) / j(Xk).
Теперь считаем j(X)градиентом f(X), т.е. j = f. Приравнивая f=0, находим стационарные точки f(X). Формула для вычисления координат этих точек преобразуется к виду:
Xk+1 = Xk - f(Xk) / f(Xk).
Недостатки метода Ньютона заключаются в том, что на каждом шаге необходимо вычислять f, и она должна быть положительно определена, иначе процесс может расходится.
Метод весьма эффективен, но его лучше применять, когда к X0 подошли достаточно близко, причем в районе X0 функция сильно выпукла.
Листинг программы по методам 1го и 2го порядков
f(x:real):real;
// result:=sin(x);:=(x-3)*(x-3)*(x-3)*(x-3);;df(x:real):real;
// result:=cos(x);:=4*(x-3)*(x-3)*(x-3);;ddf(x:real):real;
//result:=-sin(x);:=12*(x-3)*(x-3);;TForm1.Button1Click(Sender: TObject);e,h,xk,xk1,d:real;:integer;:=StrToFloat(Edit3.Text);:=StrToFloat(Edit1.Text);:=StrToFloat(Edit4.Text);.Clear;
Memo1.Text:=Поиск с использованием f(x)#13#10#13#10;
0thenh:=h*2;f(xk)=abs(f(xk1)));.Lines.Add(Format(X( %d )= %4.4f f( %1:4.4f ) = %2:4.4f f(%1:4.4f )=%3:4.4f h=%4:4.4f,[i,xk,f(xk),df(xk),h] ));(i);(abs(xk1-xk)<e) or (df(xk)=0);.Lines.Add(Format(#13#10Найдено значение f(%4.4f)=%4.4f с погрешностью e=%4.4f,[xk,f(xk),e]));;TForm1.Button2Click(Sender: TObject);e,h,xk,xk1,d:real;:integer;:=StrToFloat(Edit3.Text);:=StrToFloat(Edit1.Text);:=StrToFloat(Edit4.Text);.Clear;
Memo1.Text:=Поиск с использованием f(x)#13#10#13#10;
0thenh:=h*2;f(xk)=f(xk1));.Lines.Add(Format(X( %d )= %4.4f f( %1:4.4f ) = %2:4.4f f(%1:4.4f )=%3:4.4f h=%4:4.4f,[i,xk,f(xk),df(xk),h] ));(i);(abs(xk1-xk)<e) or (ddf(xk)=0);.Lines.Add(Format(#13#10Найдено значение f(%4.4f)=%4.4f с погрешностью e=%4.4f,[xk,f(xk),e]));;.
Оптимальный поиск
функция программирование задача
Рассмотрим класс функций одного аргумента, которые называются унимодальными. Определим унимодальную функцию y = f(X) следующим образом:
1.f(X) задана на отрезке [a,b]. 2. пусть X1 и X2 ? [a,b], причем X1 f(X2).
Примеры унимодальных функций приведены на рис.7. Заметим, что определение унимодальности исключает возможность участков f(X) с постоянным значением
рис. 7
минимум f(X) может находится во внутренней точке [a,b] или на границе. Первоначально о положении X0 ничего не известно, кроме того, что, X0 ? [a,b]. [a,b] можно назвать отрезком неопределенности.
Выбор Xi и вычисление F(Xi) называется экспериментом. Во всех случаях после выполнения заданных экспериментов отрезок неопределенности становится уже. Последовательное повторение экспериментов позволит достигнуть величины отрезка неопределенности меньшей, чем любое наперед заданное ? > 0. правило выбора Xi называется стратегией. Оптимальной называется стратегия, которая приводит к X0 (с точностью до ?) за минимальное число шагов (экспериментов).
Обозначим длину отрезка неопределенности Ln(X1, X2, . . ., Xn), где n - число экспериментов;
f(Xk) = min f(Xi), 1? i ? n,
где K - номер эксперимента, которому соответствует минимальное значение f(Xi). Тогда получим:
X2 - X1, k=1;
Ln(X1, X2, . . ., Xn, к) = Xk+1 - Xk-1, 1? k ? n;
Xn - Xn-1, k=n.
Т.о., Ln зависит как от выбора способа разбиения [a,b], так и от поведения f(X).
Пассивный поиск
В пассивном поиске все эксперименты проводятся одновременно. Без ограничения общности положим X1 = a = 0; Xn = b = 1;
Рассмотрим n = 4; 0 < X2 < X3 < 1
Тогда Ln = max { X2 - 0, X3 - 0, 1 - X2, 1 - X3}= max { X3, 1 - X2}
1? k ? 4= min max { X3, 1 - X2}
0 < X2 < X3 < 1 k= 2,3
Так как X2 < X3, то оптимальной стратегией будет X2 = - ? /2, X3 = + ? /2, а соответствующее Ln = + ? /2 (рис.8,а ).
Под ? > 0 понимают минимальное число, которое делает 2 эксперимента X2 и X3 различными.
При рассмотрении n = 5 получаем (рис 8,б), что Ln улучшилось на ? /2, что заставляет отказаться от нечетного числа экспериментов.
При произвольном четном n наилучшая стратегия составляется парами ? - экспериментов (Xi разнесены на расстояние ?).
В общем случае Ln ? 2/n + ? /2.
рис.8
метод дихотомии
Существует довольно очевидная теорема: "Если непрерывная функция на концах некоторого и