Метод Ньютона, его реализации и модификации

ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ НЕЛИНЕЙНЫХ УРАВНЕНИЙ

МЕТОДИЧЕСКИЕ УКАЗАНИЯ К лабороторной работе ПО ДИСЦИПЛИНЕ «Численные методы»

Составитель И.А.Селиванова, ст.преподаватель.

ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ НЕЛИНЕЙНЫХ УРАВНЕНИЙ:Методические указания к лабораторной работе по дисциплине «Численные методы»

Указания предназначены для студентов всех форм обучения направления 230100 – «Информатика и вычислительная техника».

У ФГАОУ ВПО «УрФУ имени первого
Президента России Б.Н.Ельцина», 2011

СОДЕРЖАНИЕ

1. Постановка задачи.. 4

2. Метод Ньютона, его реализации и модификации.. 4

2.1.Метод Ньютона. 4

2.2.Модифицированный метод Ньютона. 8

2.3.Рекурсивный метод Ньютона. 9

3. Метод простых итераций.. 10

4. ЗАДАНИЕ НА ЛАБОРАТОРНУЮ РАБОТУ.. 12

5. Варианты заданий. 13

Список литературы.. 14

1. ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ НЕЛИНЕЙНЫХ УРАВНЕНИЙ

Постановка задачи

Дана система нелинейных уравнений с неизвестными:

(1.1)

где , - нелинейные функции, определенные и непрерывные в некоторой области . Систему (1.1) можно представить в векторном виде:

(1.2)

где , .

Требуется найти такой вектор , который при подстановке в систему (1.1) превращает каждое уравнение в верное числовое равенство.

Для всех рассматриваемых далее методов требуется находить начальное приближение . В случае это можно сделать графически, определив координаты точки пересечения кривых, описываемых уравнениями или .

Метод Ньютона, его реализации и модификации

2.1.Метод Ньютона

Для решения системы (1.1) воспользуемся методом последовательных приближений. Предположим, что найдено -ое приближение одного из изолированных корней векторного уравнения (1.2). Тогда точный корень уравнения можно представить в виде:

(2.1.1)

где - поправка (погрешность) корня на -ом шаге.

Подставив выражение (2.1.1) в (1.2), получим:

(2.1.2)

Предположим, что функция - непрерывно дифференцируема в некоторой выпуклой области, содержащей и . Тогда левую часть уравнения (2.1.2) разложим в ряд Тейлора по степеням малого вектора , ограничиваясь линейными членами:

(2.1.3)

Под производной следует понимать матрицу Якоби системы функций , относительно переменных , то есть:

(2.1.4)

Формула (2.1.3) может быть записана в следующем виде:

(2.1.5)

Отсюда, предполагая, что матрица - неособенная, получим:

(2.1.6)

Теперь, подставив выражение (2.1.6) в формулу (2.1.1), окончательно получим:

(2.1.7)

Таким образом, получили вычислительную формулу (метод Ньютона), где в качестве нулевого приближения можно взять приближенное (грубое) значение искомого корня.

Для останова процесса вычислений в быстросходящихся методах таких, как метод Ньютона, методы секущих и т.п., часто вполне успешно применяют простой критерий:

(2.1.8)

Это можно объяснить двумя причинами. Во-первых, оценки погрешности здесь довольно «дороги». Имеется в виду как их получение (особенно для различных модификаций базовых методов), так и их реальное применение. Во-вторых, в силу своей быстрой сходимости, к моменту достижения требуемой малости нормы поправки эти методы набирают такую скорость, что зачастую «проскакивают» установленный порог точности. Т.е. выход по критерию (2.1.8) дает значение значительно (иногда на несколько порядков) меньшее, чем . Отслеживать факт сходимости в процессе итерации для того, чтобы реагировать на возможную расходимость в случаях, когда заранее не обеспечены условия сходимости применяемого метода, можно с помощью текущих проверок на уменьшение от шага к шагу поправок и невязок, т.е. выполнение неравенств:

(2.1.11)

Методика решения задачи

1. Задать начальное приближение и малое положительное число (точность). Положить .

2. Найти значение выражения .

3. Вычислить следующее приближение: .

4. Если и , процесс закончить и положить . Иначе, положить и перейти к п.2.

Пример 1. Решить систему методом Ньютона с точностью .

1. Для выбора начального приближения найдем координаты точек пересечения кривых, соответствующих первому и второму уравнениям (рис. 1).

Рис. 1 Выбор начального приближения

Выберем начальное приближение . В поставленной задаче . Положим .

2⁰. Так как

то

3⁰. Вычислим

4⁰. Так как , то положим и перейдем к п.2.

2¹. Так как

3¹. Вычислим

4¹. Так как , то положим и остановим вычисления. Результаты расчетов приведены в табл. 1.

Таблица 1

k
x₁^(k)	3,500000	3,488164032	3,487443000
x₂^(k)	2,200000	2,262718691	2,261628964
	-	0,062718692	0,001089727
	0,299999	0,003941099	0,000001215

Точность достигнута за две итерации.

К недостаткам метода Ньютона следует отнести:

· необходимость задавать достаточно хорошее начальное приближение;

· отсутствие глобальной сходимости для многих задач;

· необходимость вычисления матрицы Якоби на каждой итерации;

Достоинством метода является квадратичная сходимость из хорошего начального приближения при условии невырожденности матрицы Якоби [1].

2.2.Модифицированный метод Ньютона

Если матрицу Якоби вычислить и обратить лишь один раз в методе Ньютона, то придем к модифицированному методу Ньютона

(2.2.1)

· К преимуществам этого метода можно отнести то, что он требует значительно меньших вычислительных затрат на один итерационный шаг, т.к. матрица Якоби вычисляется только один раз.

· Однако недостатком является то, что итераций при этом может потребоваться значительно больше для достижения заданной точности по сравнению с основным методом Ньютона.

Критерий остановки: ,

Методика решения задачи

1. Задать начальное приближение и малое положительное число (точность). Положить .

2. Найти значение выражения .

3. Вычислить следующее приближение: .

4. Если и/или , процесс закончить и положить . Иначе, положить и перейти к п.2.

2.3.Рекурсивный метод Ньютона.

Компромиссный вариант – это вычисление и обращение матриц Якоби не на каждом итерационном шаге, а через несколько шагов (такие методы называют рекурсивными).

Например, простое чередование основного (2.1.7) и модифицированного методов Ньютона (2.2.1) приводит к итерационной формуле:

, (2.3.1)

За здесь принимается результат последовательного применения одного шага основного, а затем одного шага модифицированного метода, т.е. двухступенчатого процесса

(2.3.2)

Доказано, что такой процесс при определенных условиях порождает кубически сходящуюся последовательность .

Критерий остановки: ,

Методика решения задачи

1. Задать начальное приближение и малое положительное число (точность). Положить .

2. Найти значение выражения .

3. Найти значение выражения .

4. Если или , процесс закончить и положить . Иначе, положить и перейти к п.2.

Метод простых итераций

Пусть система (1.1) имеет вид (или преобразована к виду):

(3.1)

или иначе, в компактной записи,

(3.2)

где:

(3.3)

Для этой задачи о неподвижной точке нелинейного отображения запишем формально рекуррентное равенство

, (3.4)

которое определяет метод простых итераций (МПИ) (или метод последовательных приближений) для задачи (3.1).

Если начать процесс построения последовательности с некоторого вектора и продолжить по формуле (3.4), то при определенных условиях эта последовательность со скоростью геометрической прогрессии будет приближаться к вектору - неподвижной точке отображения . А именно, справедлива следующая теорема.

Теорема 2. Пусть функция и замкнутое множество таковы, что:

1.

2. .

Тогда имеет в M единственную неподвижную точку ; последовательность , определяемая МПИ (3.4), при любом сходится к и справедливы оценки .

Однако практическая ценность такой теоремы не так велика из-за неконструктивности ее условий. В случаях, когда имеется хорошее начальное приближение к решению , больший интерес для приложений может представить следующий аналог теоремы 2.

Теорема 3. (о достаточном условии сходимости метода простых итераций) Пусть функции и , , непрерывны в области , причем выполнено неравенство:

(3.5)

где -некоторая постоянная.

Если последовательные приближения не выходят из области , то процесс последовательных приближений сходится: и вектор является в области единственным решением системы (3.1).

Замечание

Условие (3.5) выполняются, если для любого справедливы неравенства

(3.6)

Критерий остановки: ,

Итерационный процесс, реализуемый согласно (3.4) соответствует параллельному итерированию, т.к. для вычисления -го приближения всех неизвестных учитываются вычисленные ранее их -е приближения.

Система (1.1) может быть преобразована к виду (3.1) различными способами, например, это можно сделать, умножив (1.1) на некоторую неособенную матрицу и прибавив к обеим частям уравнения вектор неизвестных . Полученная система эквивалентна данной, и имеет вид задачи о неподвижной точке. Проблема теперь состоит лишь в подборе матричного параметра A такого, при котором вектор-функция обладала бы нужными свойствами.

Методика решения задачи

1. Задать начальное приближение и малое положительное число (точность). Положить k=0.

2. Вычислить по формуле или

(3.5)

3. Если или , процесс закончить и положить . Иначе, положить и перейти к п.2.

ЗАДАНИЕ НА ЛАБОРАТОРНУЮ РАБОТУ

1. Составить и отладить программы вычисления решения системы уравнений своего варианта методами Ньютона и методом простой итерации.

Не нашли, что искали? Воспользуйтесь поиском по сайту:

©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.