Реферат: Метод Дэвидона-Флетчера-Пауэлла
<span ParkAvenue",«serif»">Министерствонауки, высшей школы и технической
<span ParkAvenue",«serif»">политикиРоссийской Федерации.
<span ParkAvenue",«serif»"><span ParkAvenue",«serif»">
<span ParkAvenue",«serif»">НовосибирскийГосударственный
<span ParkAvenue",«serif»">ТехническийУниверситет.
<img src="/cache/referats/1177/image002.jpg" v:shapes="_x0000_i1025">
<span ParkAvenue",«serif»">Рефератпо исследованию операций на тему
<span ParkAvenue",«serif»"><span ParkAvenue",«serif»; mso-ansi-language:EN-US">«
<span ParkAvenue",«serif»">Метод Дэвидона — Флетчера — Пауэлла<span ParkAvenue",«serif»; mso-ansi-language:EN-US">»<span ParkAvenue",«serif»">.<span ParkAvenue",«serif»">
<span ParkAvenue",«serif»">Вариант№2.
<span ParkAvenue",«serif»"><span ParkAvenue",«serif»">Факультет:
АВТ.<span ParkAvenue",«serif»">Кафедра:
АСУ.<span ParkAvenue",«serif»">Группа:
АС-513.<span ParkAvenue",«serif»">Студент:
БойкоКонстантин Анатольевич.<span ParkAvenue",«serif»">Преподаватель:
РенинСергей Васильевич.<span ParkAvenue",«serif»">Дата:
19октября 1997 года.<span ParkAvenue",«serif»">Новосибирск
<span ParkAvenue",«serif»; mso-fareast-font-family:«Times New Roman»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:RU;mso-fareast-language:RU;mso-bidi-language:AR-SA"><span ParkAvenue",«serif»">Введение.
<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">Первоначальнометод был предложен Дэвидоном
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(Davidon [1959])<span Arial",«sans-serif»;mso-bidi-font-family: «Times New Roman»">, а затем развит Флетчером и Пауэллом <span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">(Fletcher, Powell [1963] ). <span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">МетодДэвидона — Флетчера — Пауэлла называют также и методом переменной метрики. Он попадает в общий классквазиньютоновских процедур, в которых направления поиска задаются в виде -<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">Dj<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"><img src="/cache/referats/1177/image004.gif" v:shapes="_x0000_i1026"><span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">f(y).<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">Направление градиента является, таким образом, отклоненным в результатеумножения на -<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">Dj<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»"><span Arial",«sans-serif»;mso-bidi-font-family: «Times New Roman»">, где <span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">Dj<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">- положительно определенная симметрическая матрица порядка <span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">n хn,<span Arial",«sans-serif»;mso-bidi-font-family: «Times New Roman»"> аппроксимирующая обратную матрицу Гессе. На следующем шагематрица <span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">Dj<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">+1<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">представляется в виде суммы <span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">Dj<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">и двух симметрических матриц ранга один каждая. В связи с этим схема иногданазывается схемой коррекции ранга два.<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»">
<span ParkAvenue",«serif»">АлгоритмДэвидона — Флетчера — Пауэлла.
<span ParkAvenue",«serif»"><span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"> Рассмотрим алгоритм Дэвидона — Флетчера — Пауэлла минимизации дифференцируемой функции нескольких переменных. Вчастности, если функция квадратичная, то, как будет показано позднее, методвырабатывает сопряженные направления и останавливается после выполнения однойитерации, т.е. после поиска вдоль каждого из сопряженных направлений.
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»;mso-bidi-font-family: «Times New Roman»">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»">Начальный этап<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">.<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"> <span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US"><span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">
<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">Пусть<img src="/cache/referats/1177/image006.gif" v:shapes="_x0000_i1027">
><span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">0- константа для остановки. Выбрать точку х1 и начальную симметрическуюположительно определенную матрицу <span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»;mso-ansi-language: EN-US">D1<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»">. Положить <span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">y1 = x1,<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"> <span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">k = j = 1 <span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»">и перейти к основному этапу.<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»">
<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US"><span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»">Основной этап
<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">.<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"><span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»">Шаг 1.
<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">Если<span Arial",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US"> çê<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»"><img src="/cache/referats/1177/image004.gif" v:shapes="_x0000_i1028"><span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">f(yj)çê<<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US"> e<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">, <span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»">то остановиться; в противном случаеположить <span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">dj =<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»"><span Arial",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">-<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»"><span Arial",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">Dj<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»"><img src="/cache/referats/1177/image004.gif" v:shapes="_x0000_i1029"><span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">f(yj)<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">ивзять в качестве l<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">j<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"> оптимальное решение задачи минимизации<span Arial",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">f(yj + l<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">dj) <span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»">при l<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"> ³<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"> 0. Положить <span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">yj+1 = yj + l<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">j<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»;mso-ansi-language: EN-US">dj. <span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»">Если <span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">j <<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US"> n, <span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»">то перейти к шагу 2. Если <span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">j = n, <span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»">то положить <span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">y1 = xk+1 = yn+1, <span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">заменить<span Arial",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">k <span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">на <span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">k+1<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»">, положить <span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">j=1 <span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»">и повторить шаг 1.<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"> Шаг 2. Построить
<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">Dj<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">+1<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">следующим образом :<span Arial",«sans-serif»;mso-bidi-font-family: «Times New Roman»"><img src="/cache/referats/1177/image008.gif" v:shapes="_x0000_i1030">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US"> <span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»"> <span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US"> (1)<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»"><span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"> где
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»">
<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">pj = l<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">j<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»;mso-ansi-language: EN-US">dj, <span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»"> <span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">(2)<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">
<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»"> <span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US"> qj= <span Arial",«sans-serif»;mso-bidi-font-family: «Times New Roman»"><img src="/cache/referats/1177/image004.gif" v:shapes="_x0000_i1031"><span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">f(yj+1)- <span Arial",«sans-serif»;mso-bidi-font-family: «Times New Roman»"><img src="/cache/referats/1177/image004.gif" v:shapes="_x0000_i1032"><span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">f(yj).<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"> <span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US"> (3)<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»"><span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»">Заменить
<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">j <span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»">на <span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">j + 1 <span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»">и перейти к шагу 1.<span Arial",«sans-serif»;mso-bidi-font-family: «Times New Roman»">
Пример.
<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"> Рассмотримследующую задачу :
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"> минимизировать
<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»;mso-ansi-language: EN-US">(x1 — 2)4 + (x1 — 2x2)2.<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">
<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">Результатывычислений методом Дэвидона — Флетчера — Пауэлла приведены в таблице 1.
<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US"><span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">
<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">Таблица 1.
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"> <span Arial",«sans-serif»;mso-bidi-font-family: «Times New Roman»">Результаты вычислений по методу Дэвидона — Флетчера — Пауэлла.<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»"><span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">k
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"><span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">xk
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">f(xk)
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"><span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">j
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"><span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">yj
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">f(yj)
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"><img src="/cache/referats/1177/image004.gif" v:shapes="_x0000_i1033">f(yj)<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»">
çê<img src="/cache/referats/1177/image004.gif" v:shapes="_x0000_i1034">f(yj) çê<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">D
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"><span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">dj
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»">l<span Arial",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">j
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"><span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">yj+1
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"><span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">1
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"><span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(0.00, 3.00)
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(52.00)
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"><span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">1
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">2
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"><span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(0.00, 3.00)
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(52.00)
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(2.70, 1.51)
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(0.34)
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"><span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(-44.00, 24.00)
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(0.73, 1.28)
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">50.12
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">1.47
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"><img src="/cache/referats/1177/image010.gif" v:shapes="_x0000_i1035">
<img src="/cache/referats/1177/image012.gif" v:shapes="_x0000_i1036"><span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(44.00, -24.00)
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(-0.67, -1.31)
<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»"><span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">0.062
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">0.22
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"><span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(2.70, 1.51)
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(2.55, 1.22)
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"><span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">2
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"><span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(2.55, 1.22)
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(0.1036)
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"><span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">1
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">2
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"><span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(2.55, 1.22)
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(0.1036)
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(2.45, 1.27)
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(0.0490)
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"><span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(0.89, -0.44)
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(0.18, 0.36)
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"><span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">0.99
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">0.40
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»">
<img src="/cache/referats/1177/image010.gif" v:shapes="_x0000_i1037">
<img src="/cache/referats/1177/image014.gif" v:shapes="_x0000_i1038"><span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(-0.89, 0.44)
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(-0.28, -0.25)
<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»"><span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">0.11
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">0.64
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"><span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(2.45, 1.27)
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(2.27, 1.11)
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"><span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">3
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"><span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(2.27, 1.11)
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(0.008)
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"><span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">1
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">2
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"><span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(2.27, 1.11)
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(0.008)
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(2.25, 1.13)
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(0.004)
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"><span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(0.18, -0.20)
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(0.04, 0.04)
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"><span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">0.27
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">0.06
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"><img src="/cache/referats/1177/image010.gif" v:shapes="_x0000_i1039">
<img src="/cache/referats/1177/image016.gif" v:shapes="_x0000_i1040"><span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(-0.18, 0.20)
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(-0.05, -0.03)
<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»"><span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">0.10
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">2.64
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"><span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(2.25, 1.13)
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(2.12, 1.05)
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"><span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">4
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"><span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(2.12, 1.05)
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(0.0005)
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"><span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">1
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">2
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"><span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(2.12, 1.05)
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(0.0005)
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(2.115, 1.058)
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(0.0002)
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"><span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(0.05, -0.08)
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(0.004, 0.004)
<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»"><span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">0.09
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">0.006
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"><img src="/cache/referats/1177/image010.gif" v:shapes="_x0000_i1041"><span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(-0.05, 0.08)
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">0.10
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"><span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">(2.115, 1.058)
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»">
<span Arial",«sans-serif»;mso-bidi-font-family: «Times New Roman»">
<span Arial",«sans-serif»;mso-bidi-font-family: «Times New Roman»">
<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">Накаждой итерации вектор
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">dj <span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">для<span Arial",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">j = 1,<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»"> 2 определяется ввиде–<span Arial",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">Dj<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»"><img src="/cache/referats/1177/image004.gif" v:shapes="_x0000_i1042"><span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">f(yj)<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">,где <span Arial",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">D<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">1<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">– единичная матрица, а <span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">D<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">2<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»"> вычисляется по формулам <span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">(1) — (3). <span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»">При
<span Arial",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">k = 1<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»"> имеем <span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">p1 = (2.7, -1.49)T, q1= (44.73, -22,72)T. <span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»">На второй итерации
<span Arial",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">p1 = (-0.1, 0.05)T,q1 = (-0.7, 0.8)T <span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»">и, наконец, на третьей итерации
<span Arial",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">p1 = (-0.02, 0.02)T,q1 = (-0.14, 0.24)T. <span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">Точка <span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">yj+1 <span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»">вычисляется оптимизацией вдоль направления<span Arial",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">dj <span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">приначальной точке <span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">yj<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">для <span Arial",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">j = 1, 2.<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">Процедура остановлена в точке
<span Arial",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">y2 = (2.115, 1.058)T<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">начетвертой итерации, так как норма<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US"> çê<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">f(y2) çê<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">=0.006 достаточно мала. Траектория движения, полученная методом, показана нарисунке 1.<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">Рисунок 1.
<span Arial",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US"> <span Arial",«sans-serif»;mso-bidi-font-family: «Times New Roman»">Метод Дэвидона — Флетчера — Пауэлла<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">.<span Arial",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US"><span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US"><img src="/cache/referats/1177/image018.jpg" v:shapes="_x0000_i1043">
<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">Лемма1 показывает, что каждая матрица
<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»;mso-ansi-language: EN-US">Dj<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"> положительно определена и <span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">dj<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"> является направлением спуска.<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US"><span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">Длядоказательства леммы нам понадобится :
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»">Теорема 1
<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">.<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">Пусть <span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">S<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">- непустое множество в Е<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">n<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">,точка <span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">x Î<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US"> cl S.<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"> Конусом возможных направлений в точке <span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">x<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"> называется множество <span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">D = {d: d ¹<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US"> 0, x + l<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">d Î<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US"> S <span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»">при всех l<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"> Î<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"> (0, d<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»">) для некоторого d<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»"><span Arial",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">> 0}.<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»"><span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»">Определение.
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"> <span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">Пусть <span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">x <span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»">и <span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">y <span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»">- векторы из Е<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">n<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»;mso-ansi-language: EN-US"> <span Arial",«sans-serif»;mso-bidi-font-family: «Times New Roman»">и |<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">xTy|<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US"> — <span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">абсолютноезначение скалярного произведения <span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»;mso-ansi-language: EN-US">xTy<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»">. Тогда выполняется следующеенеравенство, называемое неравенствомШварца: |<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">xTy|<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">£<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">||<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">x||<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US"> ||<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">y||<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">.<span Arial",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">
<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">Лемма1.
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»">
<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US"><span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">Пусть
<span Arial",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">y1<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">Î<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">Е<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">n<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">, <span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»">а <span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">D1<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"> – начальная положительно определеннаясимметрическая матрица. Для <span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">j = 1, ..., n<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">положим <span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">yj+1= yj + l<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">j<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">dj<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»">, где <span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">dj<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"> = –<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">Dj<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"><img src="/cache/referats/1177/image004.gif" v:shapes="_x0000_i1044"><span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">f(yj),<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">аl<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">j<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»;mso-ansi-language: EN-US"> <span Arial",«sans-serif»;mso-bidi-font-family: «Times New Roman»">является оптимальным решением задачи минимизации <span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">f(yj + l<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">dj)<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"> при l<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"> ³<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"> 0. Пусть, кроме того, для<span Arial",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">j = 1, ..., n – 1 <span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">матрица<span Arial",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">Dj+1 <span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">определяетсяпо формулам (1)<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US"> — (3).<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">Если <img src="/cache/referats/1177/image004.gif" v:shapes="_x0000_i1045"><span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">f(yj)<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">¹<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">0 для
<span Arial",«sans-serif»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US">j = 1, ..., n, <span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">томатрицы <span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">D1<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">,..., <span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">Dn <span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">симметрическиеи положительно определенные, так что <span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»;mso-ansi-language: EN-US">d1, ..., dn – <span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">направленияспуска.
<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"> Доказательство.
<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US"><span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»"> Проведем доказательство по индукции. При
<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">j = 1 <span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»">матрица <span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">D1<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"> симметрическая и положительноопределенная по условию леммы. Кроме того,<img src="/cache/referats/1177/image004.gif" v:shapes="_x0000_i1046"><span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">f(y1)Td1= –<span Arial",«sans-serif»;mso-bidi-font-family: «Times New Roman»"><img src="/cache/referats/1177/image004.gif" v:shapes="_x0000_i1047"><span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">f(y1)TD1<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»"><img src="/cache/referats/1177/image004.gif" v:shapes="_x0000_i1048"><span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">f(y1)<<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US"> 0<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">,так как <span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US">D1<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">положительно определена. Тогда по теореме 1 вектор <span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">d1<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"> определяет направление спуска.Предположим, что утверждение леммы справедливо для некоторого <span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">j £<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US"> n – 1, <span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»">и покажем, что оно справедливо для <span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">j+1.<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»"> Пусть <span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">x – <span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»">ненулевой вектор из <span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»; mso-ansi-language:EN-US">En, <span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»">тогда из (1) имеем
<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»"><img src="/cache/referats/1177/image020.gif" v:shapes="_x0000_i1049">