Форсайт Дж., Малькольм М., Моулер К. - Машинные методы математических вычислений (1040536), страница 35
Текст из файла (страница 35)
Результат; Х=О.81650. С ИЛЛЮСТРИРУЮЩАЯ ПРОГРАММА ДЛЯ ГМ1Н С ЕЕА! РОМСТ!ОМ Р(Х) КЕАЬ Х Р =- Х*(Х~Х вЂ” 2.) — 0. ЕЕТЦКН ЕКО ЕХТЕЯНАЬ Р НЕАЬ А,В,Х,ТОЬ,РМ(Н А=о. В=-!. Т01. = !.ОŠ— З 2 = РМ1К(А,В,Р,ТО!.) %И!ТЕ(6, !)2 ! ГОКМАТ(ЗН 2 =,Г12.5) ВТОР ЕГ(О КЕАЬ РЦНСТ1ОМ ГМЩАХ,ВХ,Г,ТО~) ЙЕЛЬ АХ,ВХ,Г,ТОЬ С С ВЫЧИСЛЯЕТСЯ ПРИБЛИЖЕНИЕ Х К ТОЧКЕ, ГДЕ Г ДОСТИГАЕТ С МИНИМУМА НА ИНТЕРВАЛЕ (АХ,ВХ) С С С ВХОДНАЯ ИНФОРМАЦИЯ.. С С АХ ЛЕВЫЙ КОНЕЦ ИСХОДНОГО ИНТЕРВАЛА С ВХ ПРАВЫЙ КОНЕЦ ИСХОДНОГО ИНТЕРВАЛА С Р ПОДПРОГРАММА-ФУНКЦИЯ, КОТОРАЯ ВЫЧИСС ЛЯЕТ Р(Х) ДЛЯ ЛЮБОГО Х В ИНТЕРВАЛЕ (АХ, ВХ) С ТОЬ ЖЕЛАЕМАЯ ДЛИНА ИНТЕРВАЛА НЕОПРЕДЕЛЕНС НОСТИ КОНЕЧНОГО РЕЗУЛЬТАТА ( .ОЕ.
0.0) С кз.многомсгнля оптимнзлция 50 1Г(АВ8(О) .СЕ. Т01.!) !)=-Х+О 1Р(АВЗ(О) .ЬТ. Т01.1) () = Х+81СМ(ТОЬ1, О) Г() = — Р(()) С С ПРИСВОИТЬ НОВЫЕ ЗНАЧЕНИЯ ПАРАМЕТРАМ А, В, г', '1у И Х С )Р(Г() .СТ. РХ) СО ТО 80 1Р(У .СЕ. Х) А = Х !Г(() .ЬТ. Х) В =Х у=% ГУ=ГУГ %==-Х Г1Ч= РХ Х=() ГХ =Г() СО ТО 20 60 1Р(13 .1.Т. Х) А=() 1Р(У.
СЕ. Х) В с П 1Г(Р() .ЬЕ. Рш) СО ТО 70 )Р(1у .ЕО. Х) 00 ТО 70 !Р(Р1! .1.Е. РУ) СО ТО 80 !Р(Р .ЕО. Х) СО ТО 80 1Р(У .ЕО. ТУ) СО ТО 80 СО ТО 20 70 У=- 1У Ру= Ртч 1У =!) Гнг= Г() Со То 20 80 У=1) ГУ=Г(5 СО ТО 20 С С КОНЕЦ ОСНОВНОГО ЦИКЛА С 90 ГМ1М=Х ЕЕТ!!ЕМ ЕКО В.З.
Многомерная ог)тимизация Локальная минимизация функции и переменных — настолько важная задача, что алгоритмы для ее решения были изобретены еще более !30 лет назад. В 1845 г. Коши предложил метод, называемый теперь методом скорейшего спуска. Обозначим вектор (к„..., х„)т через х; предположим, что функция ((х) достаточно гладкая. Пусть й(х) обозначает градиент функции ! в точке х, т. е. вектор, !'-я компонента которого равна дГ)дхо Тогда — д(х) определяет направление наискорейшего убывания 7 в точке х.
Коши предложил искать минимальное значение Г на полупрямой х — 1й(О(! =ос). Это одномерный поиск того типа, который мы обсуждали в конце 2 8.2. Найдя этот минимум, начинают новый Х ОПТИМИЗАЦИЯ поиск вдоль полупрямой скорейшего спуска, исходящей из нового х. При некоторых слабых предположениях метод сойдется к тому локальному минимуму функции Г, в чьей чаше находится первое приближение. Теоретический анализ предсказал, что метод Коши в некоторых ситуациях должен сходиться крайне медленно, и опыт подтвердил это во многих практических случаях даже для скромных значений п, равных 2, 3 или 4.
Причину можно понять, рассматривая при п=й функцию (, для которой линиями уровня являются эллипсы большого эксцентриситета, вроде показанного на рнс. 8.2. (В качестве такой функции можно взять, например, х,'+100 000 х~,) Продвижение к минимуму, находящемуся в центре, происходит очень медленно; при этом маршрут состоит из осцилляций в направлениях локальных градиентов.
Имеется явная необходимость в ускорении сходимости. Основная трудность здесь в том, что локальный градиент даже приблизительно не указывает направление к центру эллипсов. Чтобы найти направление быстрого изменения произвольной строго выпуклой квадратичной функции ~ от п переменных, разложим ~(х) около точки минимума, которую обозначим через а. Пусть  — постоянная матрица, составленная из вторых частных производных функции )' в точке а,— так называемая матрица Гессе: Ь; гу дх;дху' Тогда, применяя теорему Тейлора и учитывая, что й(а) =0 в точке минимума, можем написать ((х) ~(а) + 2 (х а) В(х — а).
Следовательно, градиент д в точке х равен й (х) =- В(х — а). Если мы находимся в произвольной точке х, то можем вычислить а по формуле а = х — В ' я (х) . Таким образом, минимум функции ~ можно найти, зная В-' н градиент й в точке х. ( — положительно определенная мат- ах мномаминная оптиагизация 207 рица.) Обозначим матрицу В-' через Н.
Тогда матрица Н есть оператор, который переводит локальное направление скорейшего спуска — д в точке х в правильное направление от х к центру эллипсоидов, т. е. к точке минимума 7. Через Н точку минимума а можно выразить как а=х — Нй. Можно рассматривать эту формулу как применение метода Ньютона к решению системы уравнений й(х)==0. Если гладкая функция 7 не является квадратичной, она тем не менее будет приблизительно квадратичной в окрестности минимума, в котором матрица Гессе не вырождается. Поэтому полученные уравнения подсказывают возможный подход к задаче нахождения минимума произвольной функции 7. Применим итерационный процесс вида хае, =- х„— ееаНапа, где дд — — д(ха), а На есть ге-е приближение к матрице Н, обратной для матрицы Гессе В функции 1' в точке минимума а. Положительное число аа выбирается на каждом шаге итераций так, чтобы достигался локальный минимум 7" в направлении — Нейе от точки ха.
В этом итерационном процессе пытаются одновременно найти и точку минимума а, и обратную матрицу Н. Основная идея — строить На таким образом, чтобы после и шагов Ни совпала с Н, будь 7 квадратичной функцией. Таким образом, в случае квадратичной функции 1' и-е приближение х„совпало бы при использовании точной арифметики с а. Можно полагать поэтому, что и для неквадратичных функций и-е приближение х„должно быть гораздо лучшим приближением к минимуму а, чем х,.
Методы этого типа называются алгоритмами с переменкой метрикой, поскольку матрицу В можно интерпретировать как метрику в пространстве векторов д. Другое распространенное наименование — капикьютокоеьг методы. Первый подобный алгоритм построил в 1959 г. Давндон. Со времени опубликования статьи Давндона был предложен ряд усовершенствований квазиньютоновых методов. Мы отсылаем читателя к обзору Бройдена, содержащемуся в сборнике Мюррей (1972).
Пауэлл доказал сходимость алгоритма для любой функции 7" (х), матрица Гессе которой положительно определена при всех х; однако функции, к которым применяется алгоритм, редко удовлетворяют этому условию. Известно, что сходимость метода быстрее линейной.
Алгоритмы этого класса называют еще квадратичко зааерша ющимися '), поскольку для квадратичных функций онн сходятся '1 В оригинале — Чнг1гаиеаПу 1еггппацпю — Прим. нерее. в оптимизация в конечное число шагов. Это не означает, что для функций общего вида порядок сходимости равен 2, хотя так и может случиться. Подпрограммы для нелинейной оптимизации можно классифицировать соответственно тому, решают ли оии безусловные задачи или задачи с ограничениями, является ли целевая функция суммой квадратов или произвольной нелинейной функцией, требуется или нет вычисление производных.
Библиотеки таких программ обычно включают и программы для решения нелинейных систем уравнений. Большой вклад в ведущуюся сейчас работу по созданию надежных, эффективных и универсальных подпрограмм внесли британские ученые, в особенности сотрудники Научно-исследовательского центра атомной энергии в Харуэлле н Национальных физических лабораторий в Теддингтоне. Примерами таких программ могут быть АЛГОЛ бΠ— процедуры, включенные в сборник Гилл и др. (1972).
Ряд других программ вместе с соответствующим теоретическим обоснованием описан в двух родственных обзорах: один из них (Мюррей (1972)) посвящен безусловной оптимизации, другой (Гнлл, Мюррей (1972)) — оптимизации при наличии ограничений. Ко времени написания этой главы (т. е. в !976 г.) наиболее современными были программы, имеющиеся в Харуэлле, Теддингтоне и Оксфорде, где работает Британская группа по численным алгоритмам. За пределами Великобритании, в США, группа из Национальных лабораторий в Аргонне ведет работу по созданию пакета подпрограмм под названием М1ЫРАСК.
Эти программы будут опубликованы после тщательного тестирования. УПРАЖНЕНИЯ 8.1. При расширении аблзсти определения функции ег1(х) на комплексные аначеиия аргумента возникает действительная функция действительного переменного х, иазываелгая интегралом Доусона: х Р (х)= е "') е" Ш. а Поскольку Р (х) стремится к нулю при стремлении х н О или се, а для промежуточных значенийР(х) положительна, то должен иметьсн конечный максимум.
Используя гМ1(ч', найдите максимум функции Р(х). 8ХЬ С помощью ГМ(М найдите максимум функции 1(х) = — (Мп х)'1я (! — х) ез'х на интервале 10,1]. 8.3. Для любого ь>0 обозначим через з(ь) изименьший положительный нуль функции у(г), являющейся решением задачи Коши для обыкновенного УПРЛЖНЕНИЯ 209 дифференциального уравнения у" (1) + 1 (у) -1- — = О, у (0) =0, д (0) = Д, где Iа(1) — модифицированная функция Бесселя нулевого порядка (сч.
Абрамовиц, Стегун (!964), с. 374 — 375) '). График решения д (1) приблизительно совпадает с показанным на рисунке, (а) Найдите )г ,„ — единственное значение )г, для которого я(Ц максимально. (б) Накднте также г(дмая). (в) Постройте таблицу значений у (1) при 1=0 (О 1) а(смак) для той функции у(1), кгггорая максимязирует е!х), т. е, для у(0, удовлетворяюжей условию У (0)=-Дмак (г) Обсудите точность полученных результатов.
ы Или: Никифоров А. Ф., Уваров В. Б. Специальные функции математнческой фнзикн.— Мс Наука, 1973, с. 112.— Прим. перел. 9. НАИМЕНЬШИЕ КВАДРАТЫ И СИНГУЛЯРНОЕ РАЗЛОЖЕНИЕ 9.1. Выравнивание данных методом наименьших квадратов Во многих различных областях науки встречается такая задача. Предположим, что заданы т точек (г у) (=1 ° и Будем рассматривать г как независимое переменное, а у — как зависимое, связанное с ( некоторой неизвестной функциональной зависимостью ум =у(г ') Предположим, далее, что у нужно аппроксимировать линейной комбинацией п заданных базисных функций асс уяжс,р,(!)+с,'р,(Г)+ +с э' (Г).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
