d) /(*) = (Зх - 2)\2х - 3)\
e) f(x) = 6xs-4x3 + 10.
2. Найдите экстремальные точки следующих функций.
a) /(X) = х3 + xl - Зх,х2.
b) f(X) = 2xf +xj и-*2 + 6(х, + х2 + х}) + 2х1х2х1.
3. Проверьте, что функция
/ (х,, х2, х,) = 2x1x2xJ - 4хххг - 2х2х, + х* + х\ + х2 - 2xt - 4х2 + 4х,
имеет стационарные точки (0, 3, 1), (0, 1, -1), (1, 2, 0), (2, 1, 1) и (2, 3, -1). Используйте достаточные условия для нахождения экстремумов функции.
4. Решите следующую систему уравнений путем превращения ее в задачу минимизации нелинейной целевой функции при отсутствии ограничений на переменные.
х2 - xf = 0 , хг - хх = 2.
(Подсказка, min / \xv х2) имеет место при /(*,, хг) = 0.)
5. Докажите теорему 20.1.3.
20.1.2. Метод Ньютона-Рафсона
В общем случае использование необходимого условия экстремума V/(X) = 0 для поиска стационарных точек функции /(X) может быть сопряжено с трудностями, возникающими при численном решении соответствующей системы уравнений. Метод Ньютона-Рафсона предлагает итерационную процедуру решения системы нелинейных уравнений. Несмотря на то что данный метод рассматривается в этом разделе именно в указанном контексте, на самом деле он относится к числу градиентных методов численного поиска экстремумов функций при отсутствии ограничений (см. раздел 21.1.2).
Рассмотрим систему уравнений
/,(Х) = 0,£=1,2, ...,т. Пусть X* - некоторая фиксированная точка. Используя разложение Тейлора, имеем /((Х) * /,(Х*) + V/,(Xk)(X - X*), i - 1, 2, т.
Следовательно, исходная система уравнений приближенно представима в виде
/,(Х*) + V/,(X)(X - X*) = 0, i = 1, 2.....т.
Эти уравнения можно записать в матричной форме:
Ак + ВДХ-Х*) = 0.
Предположим, что векторы /,(Х) независимы, тогда матрица В, является невырожденной. В результате из предыдущего уравнения получим
х = х-в;Ч,.
Идея метода Ньютона-Рафсона состоит в следующем. На первом шаге выбирается начальная точка Х°. С помощью полученного уравнения по известной точке X* можно вычислить координаты новой точки X**1. Процесс вычислений завершается в точке X", которая считается приближенным решением исходной системы, если Xm » X""1.
Геометрическая интерпретация данного метода для функции одной переменной f(x) приведена на рис. 20.3. Связь между точками хк и х*+1 в этом случае выражается формулой
Рис. 20,3. Итерационный процесс в методе Нъютона-Рафсона
На рис. 20.3 видно, что положение точки хк+1 определяется углом 0 наклона касательной к графику функции f(x) в точке хк, где tg0= fix").
Одним из недостатков изложенного метода является то, что для функций общего вида не всегда гарантируется его сходимость. На рис. 20.3 видно, что при выборе в качестве х° точки а итерационный процесс расходится. Простых рецептов для выбора "хорошего" начального приближения не существует.
Пример 20.1.3
Для демонстрации работы метода Ньютона-Рафсона рассмотрим задачу нахождения стационарных точек функции
f{x) = (Зх - 2)\2х - З)2.
Чтобы найти стационарные точки, надо решить уравнение f(x) = 0, которое в данном случае принимает вид кубического уравнения
72х3 - 234х2 + 241х - 78 = 0.
Шаблон Excel ch20NewtonRaphson.xls методом Ньютона-Рафсона может решить любое уравнение с одной переменной. На рис. 20.4 показано решение в этом шаблоне уравнения данного примера. Чтобы найти это решение, надо в ячейку СЗ ввести следующее выражение, заменив переменную х ссылкой на ячейку A3.
72л3 - 234л:2 + 24 Ьс -78 216х2-468л-+ 241
Отметим, что числитель этого выражения является формулой для вычисления первой производной функции f(x), а знаменатель - формулой второй производной, что и требуется для метода Ньютона-Рафсона при решении уравнения f(x) = 0. Перед началом вычислений также задается предел точности А (= 0,001) и начальное значение х0 (= 10). Если разность между значениями хь и Xм будет меньше предела точности, то процесс вычислений завершается. В данном примере метод сошелся к значению х = 1,5.
| | | |
| Newton-Raphson (One-Variable) Method |
| Input data: Type f(A3)/f (A3) in C3. where A3 represents x in f(x) |
| | #3HA4! |
| | 0.0001 | |
| Initial x0= | | |
| Solution: i.excei | i Si te It if =eiertpd *0 rai | |
| x* = | 1.50000] | |
| Calculations: | | rforrocslcui |
| | x(k+1) | f(x(k))/f (x(k)) |
| 10.000000 | 7 032108 | 2 967892314 |
| 7.032108 | 5 055679 | 1.97642875 |
| 5.055679 | 3.741312 | 1.314367243 |
| 3.741312 | 2.869954 | 0.871358025 |
| 2.869954 | 2.296406 | 0.573547408 |
| 2.296406 | 1.925154] | 0.371251989 |
| 1.925154 | 1 694452 | 0.230702166 |
| 1.694452 | 1.565453 | 0128999578 |
| 1 565453 | 1 511296 | 0.054156405 |
| 1 511296 | 1.500432 | 0 010864068 |
| 1 500432 | 1 500001 | 0 000431385 |
21 , 1.500001 | 1.500000 | 6 70394E-07 |
Рис. 20.4. Решение алгебраического уравнения методом Ньютона-Рафсона
На самом деле наша функция f(x) имеет три стационарные точки х = 2/3, х = 13/12 и х = 3/2. Оставшиеся две стационарные точки можно найти, если задать соответствующие начальные значения, например, л:0 = 0,5 и х0= 1. В общем случае надо сделать несколько попыток решения задачи методом Ньютона-Рафсона при различных начальных значениях, чтобы отыскать все корни уравнения. В данном примере нам "повезло" - мы знаем, что наше уравнение имеет три корня. Однако в случае сложных уравнений или уравнений, зависящих от нескольких переменных, как правило неизвестно ни количество корней, ни их местоположение.