Главная » Просмотр файлов » Fedorenko-RP-Vvedenie-v-vychislitelnuyu-fiziku

Fedorenko-RP-Vvedenie-v-vychislitelnuyu-fiziku (810773), страница 3

Файл №810773 Fedorenko-RP-Vvedenie-v-vychislitelnuyu-fiziku (Fedorenko-RP-Vvedenie-v-vychislitelnuyu-fiziku) 3 страницаFedorenko-RP-Vvedenie-v-vychislitelnuyu-fiziku (810773) страница 32020-08-18СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

Без труда угадываем общую форму: г Ц С 1(Сг»)з. Именно эту формулу (с показателем 2«) имеют в виду, когда говорят о квадратичной скорости сходимости. Теперь можно более точно указать, насколько хорошим должно быть начальное приближение хз, чтобы процесс заведомо сходился.

Очевидно, для этого достаточно выполнения неравенства СЦ/(х )Ц ж ч< 1. гешеиие систем нелинейных и'хеиеиий ец Можно уточнить и вид области, в которой предполагаются выполненными сформулированные в условиях теоремы оценки пронзводнмх.

Такой областью может быть область, выделенная неравенспюм 1Ях)11 < 1/С. В самом деле, если хе лежит в области С 11д(хе)11 н д< 1, то 11у(х')11 н дг/с и т.ц., т.е. все последующие приближения х» лежат в этой области. Условие 11У„'(х) 11 ж С, существенно.

Оно гарантирует взаимную однозначность (в некоторой области) отображения х- у(х), что, как известно, очень важно для существования и единственности решения системы У(х) = О. Модификация метода Ньютона. Метод Ньютона, являясь весьма эффективным средством уточнения сравнительно хорошего начального приближения, может расходится, если хд — слишком грубое приближение к искомому решению. В схему алгоритма были Рис. 2 внесены изменения, имеющие целью ослабить требования к начальному приближению и сделать сходимость не столь зависящей от его выбора.

Идею такой модификации поясним, начав с геометрической интерпретации метода Ньютона в двумерном случае (и = 2). Итак, пусть решается система У,(хи х ) =О, У (хи хг) О. На рис. 2 изображены плоскости (х„хг) и (Уи Уг). Точка х отображается е точку Уе. В этой точке отображение х- ~(х) линеаризуется, т.е. заменяется отображением А + дх (Х~ Х1) + дх (Хг — Хг) д дд~ е дг~ 1 дхг .~ог+ — (х» — х») + д (хг — хг) 1 И- и находится точка (х'„хг), в линейном отображении переходящая в точку (О, 0).

Однако в нелинейном отображении х- У(х) точка х' отображается не в нуль, а в ~'. 1ч. г основы вычислительной млтемьтикя 14 Изучим непрерывное движение от хз к х' по прямой. Обозначив Ьх х' — хо, рассмотрим отрезок прямой х(з) = хе+ з Ьх„зжО, х(1) = х' (в расчетах обычно берут х(з) = хе+ з Ьх/))Ьх[[). Образ этого отрезка в нелинейном отображении есть кривая У[з[ ~Дх(з)) (см. рис. 2). В точке з = О она касается направления на точку (О, 0).

В самом деле, при достаточно малых з имеем У[э[ =Дх~+ з Ьх) =Уз+ зУ„(хо) Ьх+ 0(зз). В силу У„(хо) Ьх= — Уо функция /[з[ = гз — г ~е + 0(зз) = (1 — з) Уз + О(зз). Другими словами, при малых з точка У[э] движется почти (с точностью до 0(зз)) прямо в начало координат. По мере увеличения з величины 0(з*) возрастают, они могут стать определяющими и существенно отклонить траекторию У[э[ от желаемого движения в начало координат. Теперь очевидно, что нужно двигаться по [хз, х'[ до тех пор, пока точка У[э[ приближается к началу координат, т.е.

шаг з' определяется решением одномерной задачи минимизации. Ищется ш)п [[7(хо+ з Ьх) [[. Точку минимума принято обозначать л виде з' = агя ппп Щх'+ з Ьх) 1[. Итак, сформируем алгоритм модифицированного метода Ньютона (ммн): 1) имеется некоторая точка х; 2) вычисляются /(х) и у„(х); 3) находится Ьх нз системы У + г„бх = О; 4) определяется функция скалярного аргумента сс Г(з) ш Щх+ з Ьх) [[; 5) находится з' = агк ппп Р(з); 6) вычисляется следующее приближение: х:= х+ з' Ьх. гешенне систем нелинейных тг»вненнй 1нп х» = х', » ф 1пп 㻠— — О. » > Доказательство. Отметим очевидный факт: невязки г» монотонно убывают, т.с.

гв> г, » ... г» и ... Следовательно, все х» е й. Оценим величину убывания невязкн г за один шаг, используя со- отношение /(х» + з Ьх) = (1 — з) /(х») + зз О(Ц ЬхЦз), Ьх =,/„'/(х»). Отсюда следует (при з Е 10, 11) г»,, = пнп Ц/'(х" + з Ьх) Ц м ш1п ((1 — з) Ц/(х») Ц + Сз гз»). Онов! Здесь мы оценили ЦО(ЦЬхЦ )Ц и Сз ЦЬхЦ к Сз Ц/ 'Ц Ц /(х )Ц . Таким образом, Г», иш1п Н1 — з)Г + Ся~г~~). о»*»~ Вычислим минимум правой части (игнорируя пока ограничение Оа » и 1). Он достигается в точке з' = 1/(2Сг ), а значение В приведенном алгоритме есть элемент, требующий уточнения, — это решение задачи ппп Р.

Этой задаче посвящен 5 26. Иногда используют совсем простую процедуру дробления шага. Сначала берут значение з = 1 (как в стандартном методе Ньютона). Если окажется, что ЦУ(х+ з Ьх)Ц < Ц/(х)Ц, тозтотшагиостается. В противном случае з заменяют на з/2 и снова сравнивают нормы. И т.д. — до получения со- отношенияЦУ(х+ Ьх/2г)Ц < ЦУ(х)Ц. Докажем теорему о сходнмости модифицированного метода Ньютона. Теорема 2. Определим область й как множество точек, в котовых Ц/(х)Ц «Ц/(хв)Ц. Предположим, что: а) /(х) — гладкая функция и Ц/„х(х) Ц и См х Я й; б) отображение х - /(х) равномерно невырождено и Ц/„'(х) Ц и ж Со Ч х е й; в) й — ограниченная связная область. Пусть х» — точки, последовательно полученные, начиная с хв, согласно модифицированному методу Ньютона, а г — соответствующие невязки (г = Ц/(х )Ц).

Тогда в области й существует единственное решение х' системы уравнений (т.е. /(х') = О) н осиозы вычислительиоа мАтемАтики 1б минимума в этом случае есть г — 1/(4С). Если з" м1, будем использовать зту оценку; если з' > 1, оценим минимум значением в точке »=1, В этом случае г„+, ж Сгз~.

Так как при этом з' = 1/(2Сге) > 1, то Сг~~ < г /2. Итак, в любом случае при переходе от хе к хам невязка убывает не меньше, чем на величину ппп (1/(4С), г /2). Теперь допустим, что метод не сходится, т.е. Вш хь ~ х* и. Вш г„> О. По предположению й — ограниченная замкнутая область, т,е. последовательность (хе)" имеет в 0 хотя бы одну точку сгущения х, причем г Щх)а ~О. Тогда в силу непрерывности г(х) = В/(х) Й > г/2 в некоторой а-окрестности х. В эту окрестность попадает бесконечное число точек х"; обозначим их хе, (1= 1, 2, 3, ...).

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

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

Как говорят, каждое решение имеет свою «область притяжения» — совокупность точек х, стартуя из которых метод Ньютона приводит именно к этому решению. Решение систем нелинейных уРАВнениЙ Методы простых итераций. В некоторых ситуациях применение метода Ньютона может быть затруднено как нз-за слишком трудоемкого вычисления матрицы /„, так н из-за необходимости решать систему линейных уравнений.

Поэтому наряду с надежным и эффективным методом Ньютона в вычислениях используются и более простые итерационные методы. Рассмотрим простой пример, поясняющий суть дела. Решается система двух уравнений У(х, у) =О, р(х, у) =О. (4) Пусть функции г' и р таковы, что из уравнения Дх, у) = О при заданном у легко определяется х, а из уравнения р(х, у) = О определяется у.

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

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

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

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

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

Характеристики

Тип файла
DJVU-файл
Размер
6,23 Mb
Тип материала
Высшее учебное заведение

Список файлов книги

Свежие статьи
Популярно сейчас
А знаете ли Вы, что из года в год задания практически не меняются? Математика, преподаваемая в учебных заведениях, никак не менялась минимум 30 лет. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6384
Авторов
на СтудИзбе
308
Средний доход
с одного платного файла
Обучение Подробнее