WWW.DIS.KONFLIB.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

 
<< HOME
Научная библиотека
CONTACTS

А. П. Иванов

Методические указания

Тема 4: Метод Ньютона решения нелинейных уравнений и систем уравнений

факультет ПМ–ПУ СПбГУ 2007 г.

Оглавление

1. Решение скалярных уравнений........................... 2

1.1. Описание метода Ньютона.......................... 2 1.2. О локализации корней............................ 3 1.3. Задания..................................... 5 2. Метод Ньютона решения систем нелинейных уравнений............. 5 2.1. Изложение метода............................... 2.2. Пример решения системы методом Ньютона............... 2.3. Задания..................................... 1. Решение скалярных уравнений Для скалярного уравнения f (·) C 2 (a, b) f (x) = 0, (1) далее рассматривается задача уточнения корня x, локализованного на отрезке [a, b].

1.1. Описание метода Ньютона При наличии хорошего приближения xk к корню x функции f (·) можно использовать метод Ньютона, называемый также методом линеаризации или методом касательных. Расчётные формулы метода могут быть получены путём замены исходного уравнения (1) линейным уравнением в окрестности корня f (xk ) + f (xk )(x xk ) = 0, (2) Решение этого уравнения принимается за очередное приближение xk+1 :

f (xk ) xk+1 = xk. (3) f (xk ) Метод Ньютона имеет простую геометрическую интерпретацию: график функции заменяется касательной к нему в точке (xk, f (xk )) и за очередное приближение xk+1 принимается абсцисса точки пересечения её с осью OX. Используя эту интерпретацию легко получить расчётные формулы (3) метода Ньютона и вследствие этой интерпретации он именуется также методом касательных.

Рис. 1.

Здесь x0, x1, x3 поледовательные приближения к корню x, полученные в результате применения метода Ньютона.

Ясно, что сходимость последовательности {xk } к корню зависит от свойств функции f (·) и не всегда имеет место. Так, легко представить, что уже приближение x1 не попадает на исходный интервал и процесс итераций останавливается.

Приведём полезную теорему, гарантирующую сходимость метода.

Теорема 1. Если f (a) · f (b) 0, причём f (x) и f (x) отличны от нуля (и, следовательно, сохраняют определённые знаки при x [a, b]), то, исходя из начального приближения x [a, b], удовлетворяющего условию f (x0 ) · f (x0 ) 0, можно вычислить методом Ньютона по формуле (3) единственный корень x уравнения (1) с любой степенью точности.

Замечание. Практическим критерием окончания вычислений является выполнение условия |xn+1 xn |, где – требуемая точность вычисления корня.

Метод Ньютона – удобный способ вычисления корня целой степени. Поскольку задача извлечения корня n c равносильна задаче решения уравнения (1) с функцией f (x) = xn c, то расчётная формула метода Ньютона приобретает вид n1 c xk+1 = xk +.

nxn n k Пусть n = 2, c = 2, и тогда f (x) = x2 2. Можно принять [a, b] = [1, 2]. Проверим выполнение условий теоремы 1: f (1) = 1, f (2) = 2, f (x) = 2x 0, f (x) = 2 0 при x [1, 2]. Положим x0 = 2. Поскольку f (2) · f (2) = 2 · 2 4 0, то обеспечена сходимость = последовательности {xk }, получаемой по формуле (3) к 2:

x0 = 2; x1 = (2 + 1) = 1, 5; x2 = 1, 41667; x3 = 1, 414216, x4 = 1, 414214.

Все цифры последнего приближения являются верными.

Если же условия теоремы 1 не выполняются или проверка их затруднительна, то очередное "приближение" xk+1 может оказаться вне интервала, на котором расположен корень x. В этом случае xk+1 строится либо методом половинного деления либо методом хорд. В первом случае полагают во втором – Здесь ak, bk – левый и правый конец интервала, которому принадлежит корень x на предыдущем шаге.

На начальном этапе полагаем a0 = a, b0 = b. Пусть для определённости f (a) 0, f (b) 0. Если x1 [a, b], то вычислив c = f (x1 ), полагаем a1 = c, b1 = b0 при c 0, и a1 = a0, b1 = c при c 0 и повторяем вычисления.

Если же приближение x1 [a, b], то применяем формулы (4) либо (5) и поступаем как и выше: вычисляя c = f (x1 ), полагаем a1 = c, b1 = b0 при c 0, и a1 = a0, b1 = c при c и применяем метод Ньютона.

1.2. О локализации корней Если в уравнении f (x) = 0 функция f (·) непрерывна, то основой для локализации корня обычно служит следствие из теоремы Коши: если f (a)f (b) 0, то на интервале [a, b] имеется по крайней мере один корень указанного уравнения (точнее нечётное число корней). Для локализации корня на интервале [a, b] можно применять такие подходы:

• Графический метод. Исходное уравнение (1) приводится к виду g(x) = h(x), строятся графики функций y = g(x) и y = h(x) и определяется интервал оси OX, которому принадлежит абсцисса точки пересечения графиков. Он и используется для уточнения • Последовательный перебор. Интервал [a, b] разбивается на N равных отрезков и вычисляются значения функции f (·) в точках xk = a + kh, k = 0, 1,..., N, где h = (b a)/N. Если при этом найдётся интервал [xk, xk+1 ], для которого f (xk )f (xk+1 ) 0, то тем самым корень функции будет локализован с точностью h/2. Может оказаться, что функция f (·) не меняет знака на последовательности {xk }. Если корень на [a, b] существует, то последнее означает, что шаг h слишком велик и его следует заменить на меньший, полагая, например, N = 2N.



• Перебор с переменным шагом. Если функция f (x) является Липшицевой, т.е.

то можно строить последовательность {xk } вида:

Основанием к этому может служить то, что при f (x) = cx+d, можно принять L = |c| и в этом случае значение x1, полученное указанным способом, удовлетворяет уравнению Если L неизвестна, то можно её заменить через • Использование мажорант. Если известны оценки функции f (·) на [a, b], т.е.

и корни x и x+ этих функций, то x [min{x, x+ }, max{x, x+ }].

Пример. Пусть f (x) = sin x + x3 2, x [0, ]. Поскольку на указанном интервале 0 sin x 1, то в данном случае можно принять: f (x) = x3 2, f + (x) = 1+x3 2 = x3 1.

Следовательно, x 1; 3 2 [1; 1, 28].

Итеративная последовательность метода Ньютона по формуле (3) имеет вид:

1.3. Задания.

Локализовать и получить методом Ньютона минимальный по модулю ненулевой корень уравнения с точностью 0.0001:

2. Метод Ньютона решения систем нелинейных уравнений 2.1. Изложение метода Рассмотрим систему нелинейных уравнений и предположим, что существует вектор x D Rn, являющийся решением системы (6).

Будем считать, что F (x) = (f1 (x), f2 (x),..., fn (x))T, причём fi (·) C 1 (D) i.

Разложим F (x) в окрестности точки x: F (x) = F (x0 ) + F (x0 )(x x0 ) + o( x x0 ). Здесь называется матрицей Якоби, а её определитель – якобианом системы (6). Исходное уравнение заменим следующим: F (x0 ) + F (x0 )(x x0 ) = 0. Считая матрицу Якоби F (x0 ) неособой, разрешим это уравнение относительно x: x = x0 [F (x)]1 F (x0 ). И вообще положим При сделанных относительно F (·) предположениях имеет место сходимость последовательности {xk } к решению системы со скоростью геометрической прогрессии при условии, что начальное приближение x0 выбрано из достаточно малой окрестности решения x.

При дополнительном предположении F (·) C метода, т.е.

Сформулируем теорему.

Теорема. Пусть в некоторой окрестности решения x системы (6) функции fi (·) C 2 и якобиан системы отличен от нуля в этой окрестности. Тогда существует -окрестность точки x такая, что при любом выборе начального приближения x0 из этой окрестности последовательность {xk } не выходит из неё и имеет место квадратичная сходимость этой последовательности.

Замечание 1. В качестве критерия окончания процесса итераций обычно берут условие:

Замечание 2. Сложность метода Ньютона – в обращении матрицы Якоби. Вводя обозначение xk = xk+1 xk получаем для вычисления xk СЛАУ откуда и находим искомую поправку xk, а затем и следующее приближение xk+1 = xk + x к решению x. Очевидно, что это значительно сокращает количество арифметических операций для построения очередного приближения.

Замечание 3. Начиная с некоторого шага k0 решают стационарную СЛАУ Данное видоизменение носит название модифицированный метод Ньютона.

Замечание 4. (О выборе начального приближения). Пусть вектор-функция (, x) такова, что (1, x) = F (x), а система (0, x) = 0 может быть решена. Тогда разбивая [0, 1] на N частей решают методом Ньютона набор из N систем принимая для каждой следующей системы в качестве начального приближения решение предыдущей системы.

2.2. Пример решения системы методом Ньютона Рассмотрим задачу решения системы уравнений с точностью 0.001:

Отделение корней произведём графически (см. рисунок 2).

Второе уравнение системы геометрически суть эллипс с полуосями (, ). Кривую, соответствующую первому уравнению, строим по точкам в диапазоне x [1.1; +1.1].

Система имеет два решения. уточним одно из них, расположенное в четвёртой четверти, приняв в качестве начального приближения значения x0 = 0.4; y0 = 0.75.

Имеем далее:

Уточнение корней будем вести методом Ньютона с учётом замечания 2:

где gn и hn – решение СЛАУ (8):

Отсюда последовательно получаем:

Поскольку три первые знака после запятой установились, процесс вычислений заканчиваем (см. замечание 1.) 2.3. Задания.

Используя метод Ньютона, решить систему нелинейных уравнений с точностью 0.0001:

ЛИТЕРАТУРА

1. Н. Бахвалов, Н. Жидков, Г. Кобельков. Численные методы.

Физматлит, М.– СПб – 2000.

2. В. М Вержбицкий. Численные методы. Линейная алгебра и нелинейные уравнения.

М., Высшая школа 2000.

3. Г. Н. Воробьёва, А. Н. Данилова. Практикум по вычислительной математике. М., Высшая школа 1990.



 

Похожие работы:

«Artrit_A5 copy-new.qxd 30/08/2007 16:14 Page 1 ВРАЧ – ПАЦИЕНТУ ИНФОРМАЦИЯ О РЕВМАТИЧЕСКИХ ЗАБОЛЕВАНИЯХ РЕВМАТОИДНЫЙ АРТРИТ (методическое пособие по материалам научно-практической конференции (школы) Ревматоидный артрит. Современные методы лечения 15 марта 2007 г.) Межрегиональная общественная организация инвалидов Ревматологическая Ассоциация Надежда www.revmo-nadegda.ru e-mail: revmo-nadegda@mail.ru Artrit_A5 copy-new.qxd 30/08/2007 16:14 Page Artrit_A5 copy-new.qxd 30/08/2007 16:14 Page...»

«Управление образования и науки Тамбовской области Тамбовское областное государственное образовательное автономное учреждение дополнительного профессионального образования Институт повышения квалификации работников образования Тамбовское областное государственное бюджетное учреждение Межрегиональный центр возрождения духовно-нравственного наследия Преображение Формирование системы духовно-нравственного развития и воспитания детей и молодежи в образовательных учреждения всех видов и типов...»

«СТАТИСТИЧЕСКИЕ ИНСТРУМЕНТЫ КОНТРОЛЯ КАЧЕСТВА Методические указания к лабораторным работам для студентов по направлению 080200.62 Менеджмент Омск 2012 Министерство образования и науки РФ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Сибирская государственная автомобильно-дорожная академия (СибАДИ) Кафедра Управление качеством и сертификация СТАТИСТИЧЕСКИЕ ИНСТРУМЕНТЫ КОНТРОЛЯ КАЧЕСТВА Методические указания к лабораторным работам для...»

«Министерство образования и науки РФ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Сибирская государственная автомобильно-дорожная академия (СибАДИ) Кафедра Менеджмент ПРОГРАММА КУРСА И МЕТОДИЧЕСКИЕ УКАЗАНИЯ для выполнения контрольной работы по дисциплине Производственный менеджмент и Организация производства и менеджмент для студентов заочной формы обучения Составители: Е.С. Гришина, В.Н. Иванов Омск СибАДИ 2013 УДК 005.932 ББК 65.050.9(2...»

«Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Амурский государственный университет Кафедра религиоведения УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС ДИСЦИПЛИНЫ Религия и средства массовой информации Основной образовательной программы по специальности 031801.65 Религиоведение Благовещенск 2012 УМКД разработан ассистентом Воронковой Евгенией Андреевной Рассмотрен и рекомендован на заседании кафедры...»

«УДК 004:001.8(075) ББК 32.973+20я73 И74 Электронный учебно-методический комплекс по дисциплине Информационнокоммуникационные технологии в естественнонаучных исследованиях подготовлен в рамках реализации Программы развития федерального государственного образовательного учреждения высшего профессионального образования Сибирский федеральный университет (СФУ) на 2007–2010 гг. Рецензенты: Красноярский краевой фонд науки; Экспертная комиссия СФУ по подготовке учебно-методических комплексов дисциплин...»

«ОСНОВЫ ПРОЕКТИРОВАНИЯ ДОРОГ Методические указания к выполнению курсового проекта для студентов специальности 270205, 190702 Омск • 2007 Федеральное агентство по образованию Сибирская государственная автомобильно-дорожная академия (СибАДИ) Кафедра проектирования дорог ОСНОВЫ ПРОЕКТИРОВАНИЯ ДОРОГ Методические указания к выполнению курсового проекта для студентов специальности 270205, 190702 Составители: Г.И. Гречнева, О.А. Рычкова Омск Издательство СибАДИ 2 УДК 625. ББК 39.311- О Рецензент канд....»

«УДК 364.4(075.8) ББК 65.272я73 МИНОБРНАУКИ РОССИИ У 91 ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ ПОВОЛЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СЕРВИСА (ФГБОУ ВПО ПВГУС) Кафедра Социальные технологии Рецензент к.ф.н., доц. Рузова Л. А. УЧЕБНО-МЕТОДИЧЕСКОЕ ПОСОБИЕ по дисциплине Организация медико-социальной помощи населению для студентов специальности 040101.65 Социальная работа Учебно-методическое пособие по дисциплине Организация меУ 91...»

«Пояснительная записка Рабочая программа по географии составлена в соответствии с федеральным компонентом государственного стандарта общего образования, одобренный совместным решением коллегии Минобразования России и Президиума РАО от 23.12.2003 г. № 21/12 и утвержденный приказом Минобрнауки РФ от 05.03.2004 г. № 1089, инструктивно-методического письма О преподавании предмета География в общеобразовательных учреждениях Белгородской области в 2013-2014 учебном году. Примерная структура рабочей...»

«Дифференциальные уравнения ОНЛ (2 этаж), ЧЗО-1(2 этаж) Абдрахманов, В. Г. Элементы вариационного исчисления и оптимального управления : учебное пособие / В. Г. Абдрахманов, А. В. Рабчук, Н. Г. Важина ; УГАТУ.— Уфа : УГАТУ, 2005.— 101 с. ; 21 см.— ISBN 5-86911-509-4. ОГЛАВЛЕНИЕ http://www.library.ugatu.ac.ru/pdf/diplom/Abdrahmanov_Elementy_variatcionnogo_2005.pdf Алексеев, В. М. Сборник задач по оптимизации. Теория, примеры, задачи : задачник для вузов / В. М. Алексеев, Э. М. Галеев, В. М....»




 
© 2013 www.dis.konflib.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.