Федоренко Р.П. Введение в вычислительную физику (Федоренко Р.П. Введение в вычислительную физику.djvu), страница 4

Так как иа остальных шагах невязка по меньшей мере не возрастает, получаем явное противоречие. Итак, в каждой точке сгущения /(х) =- О. Докззательсгво закончено. Отметим важное обстоятельство: в условиях теоремы 2 по сравнению с условиями теоремы 1 отсутствует предположение о достаточной малости го («количественное» предположение) .

Используются только «качественные» предположения о гладкости и невырожденности (взаимной однозначности) отображения х- /(х). Эти свойства очень важны для существования и единственности решения системы, которые в условия теоремы не включены. Они следуют из сформулированных предположений. Не вдаваясь в подробности, заметим, что если гладкая функция з/(х) й з в области И не обращается в нуль, то она достигает минимума, в котором все ее производные обращаются в нуль. Вычислим ик: л л ю ! ,Если не все /;(х) О, то бе1 (/„) = О, что противоречит одному из предположений, Наконец, важно отметить, что в тех случаях, когда система /(х) = О имеет много решений, модифицированный метод Ньютона приводит к одному из них; к какому именно, это зависит от выбора начального приближения.

Как говорят, каждое решение имеет свою «область притяжения» — совокупность точек х, стартуя из которых метод Ньютона приводит именно к этому решению. Решение систем нелинейных уРАВнениЙ Методы простых итераций. В некоторых ситуациях применение метода Ньютона может быть затруднено как нз-за слишком трудоемкого вычисления матрицы /„, так н из-за необходимости решать систему линейных уравнений. Поэтому наряду с надежным и эффективным методом Ньютона в вычислениях используются и более простые итерационные методы. Рассмотрим простой пример, поясняющий суть дела. Решается система двух уравнений У(х, у) =О, р(х, у) =О. (4) Пусть функции г' и р таковы, что из уравнения Дх, у) = О при заданном у легко определяется х, а из уравнения р(х, у) = О определяется у. Тогда можно построить итерационный процесс следующего вида.

Если известны х», у', то следующее приближение вычисляется так: !) из уравнения Дх, у») = О находится х»+'; 2) из уравнения р(х»~', у) = О находится у»+.', и т.д. Проанализируем сходимость. Анализ таких процессов проводим в предположении, что х», у» достаточно близки к решению х', у', т.е.

полагаем х» = к'+ Ьх», у» у'+ Ьу" Считая Ьх, Ьу малыми, линеаризуем уравнения итерационного про- цесса. Из У(х' + Ьх»+', у' + Ьу») = О, р(х" + Ьх»+', у' + Ьу»") = О, получаем линейные соотношения У„ Ьх~~' + У Ьу» = О, р„ Ьх» ' + р Ьу»+' = О. Обозначая Ьг = (Ьх, Ьу), имеем векторное соотношение Ье»+' =А ЬВ», где А= — ~ Сходнмость обеспечивается нри: а) достаточно хорошем начальном приближении хо; б) при 11А11 н д < 1 (в этом случае 11ЬВ»11 ж м «» 11Ь '1!). Заметим, что между схемой простых итераций и методом Ньютона есть принципиальное отличие: сходимость метода Ньютона обеспечивается (при наличии хорошего приближении) чисто качественными факторами — гладкостью г' и невырожденностью отображения х- г. Для метода простых итераций требуется еще важное колячественное условие: 11А11 < !.

При 11А11 > ! метод может расхо- ОСНОВЫ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ !В У(х) ш Р(х, х) = О. Тогда можно построить итерационный процесс вида Р(х»+', х») =О, конечно, при условии, что нз такого уравнения сравнительно легко находится х»+! прн известном х». .Анализ,сходимости приводит к соотношению илн Ьх» ' = — Р,'Р Ьх», « Р„Ьх»+' + Р! Ьх» = О, и сходимость (в окрестности решения) определяется нормой матрицы Р,!Р»! если она меньше единицы, процесс сходится; если она больше единицы, процесс расходится. Очевидно также, что если процесс сходится, т.е.

существует Еш х» = х', то, переходя к преде» лу в соотношении Р(х»+', х") = О, получаем Р(х', х') = О. Если в уравнении /(х) = О ие удается выделить «разрешаемую» относительно х часть, можно ввести ее искусственно н очень просто, например преобразовав уравнение к виду х — х+ аУ(х) =О и построив итерационный процесс х»'! = х» — айх»). Строятся такие методы, как видим, легко, но сходимость их не гарантируется н является в известном смысле делом случая. Заметим еще, что существуют теоремы, обосновывающие правомерность пренебрежения членами второго порядка: если метод сходится в теории «первого приближения», т.е.

норма соответствующей матрицы !! А!! «е < 1, то прн достаточно хорошем начальном приближении метод действительно сходится. Метод Ньютона в специальных ситуациях. Часто приходится решать уравнение У(х) = О в специальной ситуации, когда функция задана не формулами, а алгоритмом, н достаточно сложным. Други- днться в сколь угодно благополучном случае при сколь угодно хорошем начальном приближении, Метод простых итераций в действительности объединяет необозримое количество итерационншх методов, которые конструируются посвоему в том или ином конкретном случае.

Например, можно одни и те же переменные, входящие в решаемое уравнение, брать один раз «с верхней» итерации, другой раз «с нижней». Поясним суть дела простым примером. Пусгь имеется функция Р(х, В), а нужно решить уравнение !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 Очевидно, что направление (Ьх, Ьу) инвариантно относительно произвольного выбора «единиц измерения» х, и х .