Fedorenko-RP-Vvedenie-v-vychislitelnuyu-fiziku (810773), страница 4
Текст из файла (страница 4)
Например, можно одни и те же переменные, входящие в решаемое уравнение, брать один раз «с верхней» итерации, другой раз «с нижней». Поясним суть дела простым примером. Пусгь имеется функция Р(х, В), а нужно решить уравнение !9 гашение систем ивлиивйиых юаиеиий ми словами, имеется программа, которая по заданному значению аргумента х вычисляет (после миллионов операций) значение г. Именно такую ситуацию изучает современный анализ, в котором термин «функция» (по традиции все-таки ассоциирующийся с такими понятиями, как «формула», «аналитическое выражение» и т.п.) вытесняется термином «отображением х- у, где «- » есть символ каких-то, быть может, очень сложных операций.
В такой ситуации метод Ньютона, требующий использования матрицы У„, должен быть дополнен алгоритмом ее вычисления. Наиболее простым способом (естественно, простота покупаекя большим объемом вычислений) является численное дифференцирование. Пусть У(х) есть У(х„хз, ..., х„), а Л„Лз, Лз, ...
— малые числа, «шаги численного дифференцирования». Приближенно можно положить — „= —, [~(х!...„х, „х, + Л,, хд+„..., х„) — 1(х„..., ха, ..., х„) [. аУ Таким образом, для вычисления всех частных производных нужно и раз вычислить значение У при возмущении поочередно аргументов. Итак, (приближенное) вычисление частных производных функции и переменных по самой простой формуле (называемой формулой одностороннего дифференцирования) требует (и+ 1)-кратиого вычисления функции.
Существуют и другие формулы численного дифференцирования. Среди иих особенно популярна формула «центральной разности» вЂ” — [у(х„..., хд+ Л, ...) — г(х„..., х, — Л, ...)[. ду 1 Она, очевидно, более трудоемка: вычисление всех производных «сгоит» 2п + 1 вычислений г'. Естественно ожидать, что эта формула более точна. Вопросы о точности численного дифференцирования обсуждаются в следующем параграфе. Пока заметим лишь, что напрашивающийся ответ «чем меньше Л, тем точнее численное дифференцирование» неверен. Нормировка задачи.
Практическое применение метода Ньютона в сложных задачах иногда приводит к очень медленной скодимости. В связи с этим возникает необходимость разбираться в причинах такого противоречия между обещаниями теории и реальными фактами. Правильно поняв причину, можно разработать приемы, существенно ускоряющие процесс решения. Один нз них описывается ниже. Начнем с простого примера. Применим схему модифицированно'го метода Ньютона для решения несложной системы уравнений Дх, у) к«хз+ у« — 2=0, р(х, у) ш (х — 2)з+(у — 2)!+ 16=0. Начальное приближение: хд = 2.0, уд = 3.0. !ч.! основы вычислительной мАтемАтики В табл.
1 представлены величины, подробно показывающие процесс решения задачи, Поясним обозначения: й — номер шага (итерации); х, у — текущие значения искомых величии; У, р — значе. Таблица 1 иия функций в точке (х, у); г (72+ рг)пз — невязка; г — шаг спуска, найденный решением задачи одномерной минимизации; а — угол (в градусах) между векторами (7,, У ) и (р,, р„). Этот угол характеризует степень «вевырождеиности» отображения (х, у)- (у, р) в данной точке. Видно, что поиск решения проходит крайне неэффективно, шаг з очень далек от единицы, т.е. линеаризация уравнения работает иа рассюяниях, существенно меньших расстояния от текущей точки до искомого решения. Эволюция величины а указывает на приближение какой-то точки вырождения отображения.
Однако начало процесса проходит очень медленно и при больших значениях а. Основная, видимо, причина — очень малые размеры области, в которой линейное приближение имеет хорошую точность. Точка (2.0, 3.0), однако, ничем ие примечательна, и в данном простом примере можно проверить, что линеаризация ~ и р достаточно точна на расстояниях, ббльших смещения х и у за один шаг процесса. Попробуем разобраться в ситуации. Для этого стоит посмотреть на систему уравненрй метода Ньютона. В точке (2.0, 3.0) она имеет 0 1 2 4 5 7 В 10 12 14 16 2.0000 2.0685 2.1330 2.2334 2.2727 2.3265 2.3437 2.3729 2.3899 2.4031 2.4108 3.0000 2,9380 2.8680 2,7274 2,6589 2.5471 2.5057 2.4284 2.З78! 2.3358 2.3096 111.000 !10.379 109.801 108.906 108.607 108.246 1ОВЛ38 108.008 107.946 107.914 107.898 17,000 16.826 ! 6.656 !6.398 16.306 16.199 16.170 16Л30 16Л!3 16.130 16.099 ! 12.294 1! 1.654 ! 11.057 ! 1О.!34 ! 09.824 109.451 109.340 !09.206 109.141 109Л09 109.092 О.!1 0.108 0.094 0.064 0.047 0.021 0.015 0.012 0.004 0.00!7 0.0010 40 42 48 57 52 46 43 33 25 18 15 г1 гешеиие систем нелинейных гглеиеиий е 1! (В других точках табл.
1 ситуация примерно та же самая.) Решение ягой системы: Ьх *= 6.26, Ьу = — 5.67 (Противоречие между изменением х и у и шагом з в табл, 1 объясняется нормировкой направления дви1кевия.) Обратим внимание на характерную деталь: направление (Ьх, Ьу) «почти ортогонально» вектору (г „, ~„)! У„Ьх + У Ьу 80 6.26 — 108 5.67 ~ 500 — 611 = — 111. (Здесь 111 — действительно малая величина, ведь ее естественно относвть к величине 500 + 611 = 1111, т,е. е «безразмерных» единицах величина 111 мала в том же смысле, в каком 0.1 мала относитально 1.) Итак, направление (Ьх, Ьу) «почти совпадает» с касательной к линии уровня У(х, у) =сооз1, а вдоль касательной приращение / определяется членами второго порядка, которые алгоритм игнорирует. Почему же алгоритм выбирает такое направление, т.е.
его «не интересует» уменьшение величины У = 111, он в болыпей степени заинтересован в уменьшении относительно малой величины р = 17? Возникает парадоксальное предположеннег видимо, в точках (х~, у~) уравнение У = 0 уже почти выполнено, а уравнение р = 0 — нет, Ведь из того, что У = 111, а р = 17, еще ничего не следует. Откуда известно, как нужно сравнявать величины У н р? Подобные вопросы всегда должны возникать перед вычислителем.
Они приводят к требованию нормировки задачи. В самом деле, не меняя существа дела, можно перейтв к системе — У(х, у) =О, — р(х, у) О. 1 1 х, и2 Очевидно, что направление (Ьх, Ьу) инвариантно относительно произвольного выбора «единиц измерения» х, и х . Но величина не- вязки г = [(г'г'х1)~+ ( р/хз) [н~ и, следовательно, шаг з такой инвариантностью не обладают. При этом возникает проблема выбора «праенльных» масштабов х„хи В своей практике автор в подобных ситуациях руководствовался правилом, условно названным «принципом равноправия»: масштабы нужно выбирать такими, чтобы одинаковые изменения х н у приводила к численно близким изменениям У и р. Формулы для малых приращений у и р показывают, что эта цель в известной мере будет достигнута (в окрестности данной точки (х, у)), если взять х = (г'з + г»)11» х = (~рз + <рз)11з Таким образом, мы приходим к модифицированному методу Ньютона с нормировкой.
Алгоритм стандартного шага в точке (х, у) дополняется следующим: после вычисления производных и направления (Ьх, Ьу) вычисляются «масштабы» хп и шаг з выбирается минимизацией масштабированной невязки. Эффект этого прн- ОСНОВЫ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ 1ч. ! ема иллюстрирует табл, 2. Обозначения в ней — те же, что и в табл. 1, только величины гв и г, означают величины масштабнрованной невязки в точке (хь, уа) и в следующей точке (ха+!, ух +!).
Заметим, что теперь у нас нет единой невязки, которая убывала бы в процессе решения, чем в сущности и обеспечивается сходимость метода. В точке (х«+!, у«+!) есть две невязки! при масштабировании в точке (хь, уь) и при масштабировании в точке (х"+', уь+!). Теорема о сходимости модифицированного метода Ньютона утрачивает силу, но зато сама сходнмость стала существенно лучше. Данные г" =0 и р 0 в последней строке табл. 2 означают, что зти величины не больше 5.10 6.
На основании вышесказанного естественно возникает вопрос: действительно ли зто малая величина? Ответ на него несложен. Если вычислитель постулировал„что для Таблица 2 го 5.72 12.75 2,00 0.60 0.33! 0.03! О.оооб 5.52 1 1.59 0.55 0.0826 0.026 0.00054 0 0.066 О.! 25 отш 1.90 2.00 1.0 1.0 х и у величина 10 5 является малой, то естественно считать малыми для г и !р изменения, порождаемые такими малыми Ьх и Ьу.
Это опять-таки приводит нас к тому масштабированию, которое было использовано, и величины г, р порядка 5.10 6 следует тоже считать малыми. Из табл. 2 видно, что в единицах к„к величина / = 111 стала «малой» по сравнению с р = 17. Допускается ее существенное увеличение ради уменьшения !р. Внешне большое значение У = 338 затем сравнительно малыми изменениями Ьх и Ьу доводится до нуля. Это есть следствие разной чувствительности 5 и р к изменениям х, у, т.е. существенно разных величин их производных. После того как два-три раза подряд минимизация г по В в модифицированном методе Ньютона приводит к значениям, близким к единице, переходят на обычный метод Ньютона, не тратя машинного времени на подбор 5. Однако в данном примере, после получения 2.0000 2.414 3.209 2.89! 1.806 1.157 !. ! 4265 1.14220 3.0000 2.626 0.542 -0.389 -0.578 -0.460 -0.48663 -0.48626 ! ! !.Ооо 127.500 338.4 200,0 17.3 0.1! 5 0.004 о 17.000 16.32 ! 4,66 3.07 -1.! 4 0.516 -0.006 о к!1 гкшкннк систем нклннкйных м чзнкннй приближения, хорошего в смысле теоремы 1, сходимость оказывается столь быстрой, что этот прием не дал бы нам никакой экономии.
Другая, но по существу близкая, нормировка была предложена немецким математиком Ддфлхардом. В его варианте модифицированного метода Ньютона после вычисления г(х) и матрицы Р,(х) вычисляется матрица А =г,' и минимизируется невязка г~(к) = (А У(х+ к Ьх), А У(х+ к Ьх)). Смысл этой конструкции станет ясен, если проанализировать поведение правой части при малых Ь (в первом приближении): АГ(х+ Ь) = АГ(х) + А Г„(х) Ь= А У(х) + Ь. Таким образом, в окрестности точки х невязка устроена очень просто: '(Ь) =С+(в, Ь)+(Ь, Ь), Такая ситуация наиболее благоприятна для алгоритмов поиска минимума, а решение системы г'(х) = 0 можно трактовать как поиск минимума гк ш ~~у(х) ~)к, Метод продолжения по параметру. Опишем в общих чертах другой прием, имеющий ту же цель — ослабить требования к выбору начального приближения и обеспечить надежную сходимость метода решения системы уравнений г (х) = О.
В литературе этот метод иногда называют «методом инвариантного погружения». Рассмотрим семейство задач Р(х, Х) = О, где Х вЂ” скалярный параметр. Сконструируем это семейство так, что Р(х, 1) к«У(х), а при А = 0 уравнение Р(х, 0) = 0 легко решается или даже имеет явное решение. Это и есть «погружение» исходной задачи в семейство задач. Формально построить такое погружение часто не представляет труда.
Вот, например, самый простой способ: Р(х, Х) ш (1 — Х)х+ Хг(х). (5) Уравнение Р(х, 0) = 0 имеет очевидное решение х =О. Пусть х( Х) есть решение уравнения (5). Последовательно решается серия задач. Имея решение х(Х), меняем А на Х+ йА и решаем уравнение Р(х, Х + ЬА) = О тем или иным итерационным методом. Используем х(А) как хорошее начальное приближение (ЬХ, естественно, считаем малым изменением). Таким образом можно (прн благоприятном ходе событий) добраться до Х = 1 и получить решение исходной задачи.
Нетрудно оформить эту конструкцию в виде задачи Коши для системы обыкновенных дифференциальных уравнений, т.е. вычислить производную и'хИА. В самом деле, дифференцируя по А, получаем 0= — Р(х, й) =Р„(х, Х) — "„+ Р„(х, А), (ч.( ОСНОВЫ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ откуда †" = — Р„((х, Х) Р (х, Х). Связь с методом Ньютона достаточно прозрачная. Сведение к задаче Коши иногда считают исчерпывающим решением проблемы, поскольку многие полагают эту задачу самой простой в вычислительной математике. Это мнение (ошибочное в столь общей форме, как мы увидим в дальнейшем) основано на том факте, что для решения задачи Коши существуют не только строго обоснованные алгоритмы, но даже стандартные программы н можно, не имея представления о том, как они работают, просто обращаться к ним.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
