назад Оглавление вперед


[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232] [233] [234] [235] [236] [237] [238] [239] [240] [241] [242] [243] [244] [245] [246] [247] [248] [249] [ 250 ] [251] [252] [253] [254] [255] [256] [257] [258] [259] [260] [261] [262] [263] [264] [265] [266] [267] [268] [269] [270] [271] [272] [273] [274] [275] [276] [277] [278] [279] [280] [281] [282] [283] [284] [285] [286] [287] [288] [289] [290] [291] [292] [293]


250

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. В общем случае надо сделать несколько попыток решения задачи методом Ньютона-Рафсона при различных начальных значениях, чтобы отыскать все корни уравнения. В данном примере нам "повезло" - мы знаем, что наше уравнение имеет три корня. Однако в случае сложных уравнений или уравнений, зависящих от нескольких переменных, как правило неизвестно ни количество корней, ни их местоположение.

[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232] [233] [234] [235] [236] [237] [238] [239] [240] [241] [242] [243] [244] [245] [246] [247] [248] [249] [ 250 ] [251] [252] [253] [254] [255] [256] [257] [258] [259] [260] [261] [262] [263] [264] [265] [266] [267] [268] [269] [270] [271] [272] [273] [274] [275] [276] [277] [278] [279] [280] [281] [282] [283] [284] [285] [286] [287] [288] [289] [290] [291] [292] [293]