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

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

Введение

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

1. Метод Ньютона для нелинейных скалярных уравнений

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

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

Пусть дано нелинейное уравнение

(1.1)

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

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

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

(1.2)

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

Замечание.

Если уравнение - алгебраический многочлен, то уравнение (1.1) называют алгебраическим -ой степени:

(1.3)

где - действительные числа, коэффициенты уравнения.

Число есть корень уравнения (1.1) кратности , если при вместе с функцией обращаются в нуль ее производные до ()-го порядка включительно, т.е. … а Корень кратности называют простым.

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

Решение осуществляется в два этапа:

Первый этап. Находятся отрезки внутри каждого из которых содержится один простой или кратный корень . Этот этап называется процедурой отделения корней. На этом этапе осуществляется грубое нахождение корней.

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

В вычислительной практике обычно используются следующие способы отделения корней:

1. Средствами математического анализа с помощью исследования функций и построения графиков;

2. Формированием простых функций таких, что получается равносильное уравнение в виде (1.2), и дальнейшим построением графиков этих функций.

1.2 Типы сходимости итерационных последовательностей

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

Определение 1.1. Пусть Тогда говорят, что последовательность сходится к , если

Если, кроме того, существует константа и такой номер что для всех

то говорят, что является линейно сходящейся к Если для некоторой последовательности , сходящейся к нулю, имеет место

то говорят, что сходится сверхлинейно к Если сходится к и существуют постоянные и такой номер что для всех

то говорят, что сходится к по меньшей мере с -м порядком. Если или 3, то говорят, что скорость сходимости является квадратичной или кубической соответственно.

На практике линейная сходимость может быть довольно медленной, в то время как квадратичная или сверхлинейная сходимость станет в конце концов довольно быстрой.

1.3 Изложение метода Ньютона

Метод Ньютона (метод касательных, или метод линеаризации) является одним из наиболее популярных численных методов. Он быстро сходится и допускает различные модификации, которые могут быть применены для решения векторных задач. Однако этот метод эффективен при весьма жестких ограничениях на функцию :

1. Существование второй производной функции на множестве

2. Удовлетворение первой производной условию для всех

3. Знакопостоянство для всех .

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

Геометрическая интерпретация метода Ньютона состоит в следующем. Задается начальное приближение . Далее проводится касательная к кривой в точке (см. рисунок ниже). Т.е. кривая заменяется прямой. В качестве следующего приближения берется точка пересечения этой касательной с осью абсцисс. Процесс построения касательных и нахождения точек пересечения с осью абсцисс продолжается до тех пор, пока приращение не станет меньше заданной величины .

Рис. 1

Получим расчетную формулу метода Ньютона. Вместо участка кривой BC (точка С соответствует ) возьмем участок AB - касательную, проведенную в точке Для этого отрезка справедливо соотношение

где - угол наклона касательной в точке к оси абсцисс. Разрешая это соотношение относительно , получаем

Повторяя процесс, найдем общую формулу:

Применим для вывода формулы (1.4) метод линеаризации. Положим, что итерационный процесс имеет вид

(1.5)

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

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

отсюда выражаем поправку -му приближению и далее подставляем в (1.5), т.о. получаем общую формулу (1.4).

Говоря проще, на каждой итерации строится локальная модель функции и решается задача отыскания корня в этой модели. В нашем случае модель в общем виде

представляет собой линейную функцию со значением и наклоном в точке . Нетрудно убедиться в том, что пересекает ось абсцисс в точке определенной в (1.4).

Теорема 1.1 (о достаточных условиях сходимости метода Ньютона).

Пусть выполняются следующие условия:

1. Функция определена и дважды дифференцируема на

2. Отрезку принадлежит только один простой корень , так что

3. Производные на сохраняют знак , и

4. Начальное приближение должно удовлетворять неравенству (знаки функций в точке совпадают).

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

Замечание.

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

Первый случай. Пусть отрезок не мал. Тогда на основе теоремы Лагранжа получим

 (1.6)

где .

Преобразуем с использованием (1.6) итерационную формулу (1.4):

где

В силу монотонности последовательности

Таким образом, вдали от корня получаем линейную сходимость

Второй случай. Пусть теперь отрезок мал, т.е. итерации выполняются вблизи корня. Тогда, полагая, что указанные выше предположения теоремы 1.8 выполнены, разложим функцию в окрестности корня относительно точки , учитывая члены второго порядка. Получим

где ( - малая величина). Из данного соотношения выражаем :

Так как первые два слагаемых в правой части равны в соответствии с (1.4), то запишем

Из последнего соотношения следует оценка погрешности -го приближения через погрешность -го приближения:

где принято . Оценка (1.7) свидетельствует о квадратичной сходимости метода вблизи корня. С вычислительной точки зрения это означает, что на каждом приближении количество верных цифр результата удваивается.

Метод Ньютона может также применяться для определения кратных корней (см. раздел 1.3.1), т.е. когда на отрезке , содержащем корень, не выполняется условие .

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

Лемма 1.1. Пусть и для открытого интервала . Тогда для любых

Доказательство. Как известно из анализа, что эквивалентно

После замены переменных

(1.9)

принимает вид

И, таким образом, используя непрерывность по Липшицу получаем

Теорема 1.2 (достаточные условия для сходимости метода Ньютона).

Пусть:

a) Дана функция , где - открытый интервал, и

Для некоторого выполняется условие при всех из . Если уравнение имеет решение , то существует некоторое , такое, что если , то последовательность , задаваемая формулой (1.4), существует и сходится к . И справедлива оценка

Здесь обозначение означает, что функция непрерывна по Липшицу с константой на множестве , т.е. для любых из .

Доказательство. Пусть и пусть есть радиус наибольшего открытого интервала с центром в содержащегося в . Обозначим . Покажем по индукции, что для выполняется (1.10) и

Доказательство по сути показывает, что на каждой итерации погрешность ограничена константой, умноженной на погрешность, допускаемую линейной моделью при аппроксимации и оцениваемую по лемме 1.1 как . Для

Выражение в скобках есть т.е. погрешность в локальной линейной модели, построенной в Таким образом, из леммы 1.1

и далее по предположениям относительно

Поскольку , мы имеем Аналогично проводится доказательство индуктивного предположения.

Замечания.

1. Требование теоремы 1.9, чтобы производная функции имела ненулевую нижнюю границу в , определяет, что значение должно быть ненулевым для квадратичной сходимости метода Ньютона. Если же , то является кратным корнем, а метод Ньютона сходится лишь линейно.

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

3. Метод Ньютона является локально сходящимся, так как он сходится с определенной скоростью к истинному решению при условии, что стартует в достаточной близости от этого решения.

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

1. Задать начальное приближение так, чтобы выполнялось неравенство , а также малое положительное число . Положить .

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

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

Пример 1.1. Найти корни уравнения

методом Ньютона с точностью .

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

Рис. 2

Результат отделения корней - три промежутка .

Проверим выполнение условий 1, 2, 3 теоремы 1.1. для каждого из отрезков.

Так как , т.e. выполняется , производные сохраняют знак при , то условия сходимости выполняются.

Так как , т.e. выполняется , производные сохраняют знак при , то условия сходимости выполняются.

Так как , т.e. выполняется , производные сохраняют знак при , то условия сходимости выполняются.

Зададим начальные приближения: на отрезке выберем , т.к. ; на отрезке выберем , т.к. ; на отрезке выберем , т.к. .

Результаты расчетов по формуле (1.4)

приведены в таблицах 1.1-1.3.

Таблица 1.1

	0	1	2	3	4
	-4	-3,145833333	-2,829126401	-2,782280851	-2,781284243
	-	0,854166667	0,316706933	0,04684555	0,000996608

Таблица 1.2

	0	1	2	3	4	5
	4	3,28125	2,9818071	2,92152858	2,91909292	2,91908899
	-	0,71875	0,2994428	0,06027851	0,00243567	0,00000392

Таблица 1.3

	0	1	2	3
	0,4	0,845192308	0,86213533	0,8621947
	-	0,445192308	0,016943022	0,0000594

В результате получены приближенные значения корней: .

Пример 1.2. Найти корень трансцендентного уравнения

с точностью , где искомый корень .

Проверим выполнение условий 1, 2, 3 теоремы 1.1. для заданного отрезка.

Так как , т.e. выполняется , производные сохраняют знак при , то условия сходимости выполняются.

Зададим начальное приближение из 4 условия теоремы 1.8. Выберем , так как .

Результат расчета по формуле (1.4)

приведен таблице 1.4.

Таблица 1.4

	0	1	2	3
	-1	-0,733043605	-0,703807786	-0,703467468
	-	0,266956395	0,029235819	0,000340318

В результате получено приближенное значение корня -0,703467. Для достижения заданной точности, проверяемой по модулю разности , потребовалось выполнить 3 приближения.

Нахождение кратных корней.

Обратимся к теоремам (1.1 и 1.2) о сходимости метода Ньютона. Их условия предполагают неравенство нулю первой производной функции на промежутке , где применяется метод. Это означает, что они регламентируют применение метода Ньютона только для нахождения простых нулей функции , поскольку для кратного корня уравнения (1.1) имеет место равенство Пусть корень кратности (; тогда функция представима в виде

и ее производная обращается в нуль при .

Согласно (1.4), формально нужно, чтобы производная не равнялась нулю в точках (, но в точке допустимо обращение производной в нуль. Метод Ньютона может сходиться и в случае, когда является кратным корнем уравнения (1.1), но сходимость при этом будет лишь линейная.

Если заранее известно число - показатель кратности корня , то для ускорения сходимости метода Ньютона в формулу (1.4) рекомендуется ввести корректирующий параметр :

Получаем модифицированный метод Ньютона с параметром.

Пример 1.3 Сравним процесс нахождения трехкратного корня функции по формулам (1.4) и (1.8) .

Ниже представлены таблицы с расчетами метода Ньютона по формуле (1.4) и метода Ньютона с параметром по формуле (1.11) с начальным приближением .

Таблица 1.5. Метод Ньютона с параметром

	0	1	2	3	4
	3	2,1	2,0015625	2,000000406	2

Таблица 1.6. Метод Ньютона

	0	1	2	3	4
	3	2,7	2,485227273	2,333368079	2,227296848

Налицо эффективность коррекции метода Ньютона путем введения в него показателя кратности корня.

1.4 Модификации метода Ньютона

Метод Ньютона, являясь весьма эффективным средством численного анализа, к сожалению, имеет достаточно жесткие ограничения на характер функции. Действительно, он не может применяться при нарушении знакопостоянства производных. Так, если даже условие знакопостоянства нарушено вдали от корня, а близи выполняется, то все равно метод касательных неприменим.

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

В силу этого в ряде случаев могут оказаться более предпочтительными следующие модификации метода Ньютона.

Упрощенный метод Ньютона.

Методика его применения совпадает с изложенной в разделе 1.3, но вместо формулы (1.4) используется следующая формула:

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

Рис. 3

При такой модификации метод Ньютона утрачивает высокую скорость сходимости, т.к. процесс не реагирует на изменение наклона кривой к оси абсцисс при приближении к корню, и вместо квадратичной имеет лишь линейную скорость сходимости.

Пример 1.4 Найти отрицательный корень уравнения

упрощенным методом Ньютона.

Корень был отделен в примере 1.1: .Выберем начальное приближение и зададим . Выполнять расчеты будем по формуле (1.12):

Результаты расчетов приведены в таблице 1.7.

Таблица 1.7

0	-4	-	6	-2,7976	0,0128
1	-3,1458	0,8541	7	-2,7905	0,0071
2	-2,9612	0,1846	8	-2,7865	0,004
3	-2,8769	0,0842	9	-2,7842	0,0022
4	-2,8337	0,0431	10	-2,7829	0,0012
5	-2,8105	0,0232	11	-2,7822	0,0007

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

Методы с конечно-разностными производными.

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

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

и таким образом полученная модель представляет из себя



Тогда общая формула конечно-разностного метода Ньютона принимает вид

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

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

Сравним конечно-разностный метод Ньютона и метод секущих, примененные на простом примере где и

Таблица 1.8. Конечно-разностный метод Ньютона (

	0	1	2	3	4	5
	2	1,24999998	1,02499998	1,00030488	1,00000005	1

Таблица 1.9. Метод секущих ( выбирается по конечно-разностному методу Ньютона)

	0	1	2	3	4	5	6
	2	1,24999998	1,07692307	1,00826446	1,00030488	1,00000125	1

Обратим внимание, насколько похожи результаты конечно-разностного метода Ньютона и метода секущих. При этом метод секущих сходится немного медленнее.

Графическая иллюстрация метода секущих представлена на графике (см. рисунок ниже).

Рис. 4

По сравнению с методом Ньютона метод секущих является более экономичным по количеству функций, подлежащих расчету. Хоть метод секущих и немного уступает методу Ньютона в скорости сходимости, он оказывается полезным в тех случаях, когда вычисление производной затруднено, так как не требует вычисления производной.

Решим пример методом секущих, который был рассмотрен ранее (см. пример 12).

Пример 1.5. Найти корень трансцендентного уравнения методом секущих

с точностью , где искомый корень .

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

Для вычисления будем использовать конечно-разностный метод Ньютона (1.13) , для этого зададим Таким образом получаем

Дальнейшие расчеты будут выполнены по формуле (1.14) и представлены в таблице 1.10.

Таблица 1.10

	0	1	2	3	4
	-1	-0,733043615	-0,706632351	-0,703504119	-0,703467468
	-	0,266956385	0,026411264	0,003128231	0,000036650

Очевидно, метод секущих сходится чуть хуже метода Ньютона (см. пример 1.2), однако скорость сходимости выше линейной.

1.4 Сравнение результатов

Типичное поведение метода Ньютона и различных его модификаций рассмотрим на примере 1.2. Для этого найдем корень трансцендентного уравнения

с точностью , где за начальное приближение возьмем

Результаты применения к этому уравнению различных итерационных процессов, начинающихся с точки начального приближения и заканчивающихся, как только выполнится неравенство

трансцендентный ньютон итерационный сходимость

представлены в таблице 1.11. В ней приведены: приближенные решения, полученные на -ой итерации, значения при которых сработал критерий (1.15), а также невязки, характеризующие некоторую меру близости найденного приближенного решения к точному решению заданного уравнения. При этом шаг аппроксимации в конечно-разностном методе Ньютона и методе секущих брался на каждой итерации

Таблица 1.11

№	Метод	Приближенное решение	Число итераций	Невязка
1	Ньютона	-0,7034674225	4	0,000000000000001
2	Упрощенный Ньютона	-0,7034756501	7	0,000003079860769
3	Конечно-разностный Ньютона	-0,7034674225	4	0,000000000000005
4	Секущих	-0,7034674225	5	0,000000000001268

Данный численный пример подтверждает сделанные ранее заявления о скорости сходимости используемых итерационных методов. Из таблицы 1.7 видно, что результаты, полученные методом Ньютона и конечно-разностным методом Ньютона, имеют очень схожую ошибку погрешности, однако конечно-разностный метод Ньютона сходится чуть медленнее. Для нахождения приближенного решения методом секущих, потребовалось выполнить на одну итерацию больше, чем для метода Ньютона, однако невязка метода секущих больше. Решение, вычисленное упрощенным методом Ньютона, было найдено за семь приближений, но полученная погрешность вычислений достаточно велика по сравнению с методом Ньютона и другими его модификациями, что говорит нам о не высокой скорости сходимости данной модификации.

2. Метод ньютона в нелинейных системах

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

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

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

,

(2.1)

,

где - нелинейные функции, определенные и непрерывные в некоторой области , или в векторном виде

где .

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

Замечание1.

Если стоит задача нахождения комплексных корней , то она может быть сведена к решению двух уравнений с двумя неизвестными. Для этого следует положить и выделить действительную и мнимую часть функции:

Отсюда получаем систему уравнений

которая решается как система (2.1).

2.2 Изложение метода Ньютона

Рассмотрим систему нелинейных уравнений в векторном виде

и предположим, что существует вектор , являющийся решением системы (2.2), где , причем .

Формула для нахождения решения является естественным обобщением формулы (1.4):

(2.3)

Где



Так как процесс вычисления обратной матрицы является трудоемким, преобразуем (2.2) следующим образом:

где - поправка к текущему приближению .

Умножим последнее выражение на матрицу Якоби :

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

Сравнивая (2.4) с формальным разложением в ряд Тейлора

видим, что последовательность в методе Ньютона получается в результате подмены при каждом нелинейного уравнения или, что то же, уравнения

линейным уравнением

т.е. пошаговой линеаризацией. Иначе говоря, на каждой итерации строится линейная модель функции , которую будем обозначать следующим образом

.

Можно рассчитывать, что при достаточной гладкости и достаточно хорошем приближении сходимость порождаемой методом Ньютона последовательности к решению будет квадратичной и в многомерном случае.

Теорема 2.1 (о достаточных условиях сходимости метода Ньютона).

Пусть функция непрерывно дифференцируема в открытом выпуклом множестве . Предположим, что существует и , такие, что , , и существует , причем и . Тогда существует такое, что для всех последовательность порождаемая соотношением (2.3), сходится к и удовлетворяет неравенству

Здесь использованы следующие обозначения: - открытая окрестность радиусом с центром в точке : ; запись означает, что непрерывна по Липшицу, где - константа Липшица, т.е.

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

Покажем индукцией по что на каждом шаге выполняется (2.5), а также, что

и тогда

Покажем, что якобиан не вырожден. Но для начала рассмотрим некоторое утверждение.

Если не вырождена и , то не вырождена и выполняется следующее соотношение

Из непрерывности по Липшицу в и (2.6) следует, что

Таким образом, из соотношения (2.8) вытекает невырожденность и

Следовательно, корректно определено и

Заметим, что выражение в скобках представляет из себя разность между и значением линейной модели , вычисленным в Запишем что эквивалентно

Сделаем замену переменных

и получим



Далее, используя непрерывность по Липшицу получаем

Следовательно, используя (2.9) и (2.10) получаем

Это доказывает (2.5). Поскольку имеем

что указывает на справедливость (2.7) и тем самым завершает доказательство для случая Идентично проводится доказательство индуктивного предположения.

Замечания.

1. Теорема 2.1 свидетельствует о локальной квадратично сходимости метода Ньютона.

2. К недостаткам метода следует отнести:

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

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

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

· Необходимость решения на каждой итерации системы линейных уравнений, которая может быть плохо обусловленной.

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

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

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

2. Решить систему линейных алгебраических уравнений (2.4) относительно поправки

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

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

Пример 2.1 Найти решение системы

Методом Ньютона, расположенное в третьем квадранте, с точностью .

Выберем начальное приближение . Расчеты будем проводить по формуле (2.3)

которые представлены ниже в таблице 2.1.

Таблица 2.1

	0	1	2	3	4
	-1	-0,85714286	-0,83107249	-0,83030083	-0,83030016
	-1	-1,1428571	-1,1445528	-1,1448149	-1,1448151
	-	0,142857	0,0260704	0,0007716	0,00000067

Из таблицы 2.1 видно, что для нахождения решения в третьем квадранте, с заданной точностью , потребовалось четыре приближения.

Пример 2.2 Найти решение системы

Методом Ньютона с точностью .

Выберем начальное приближение . Расчеты будем проводить по формуле (2.3)

которые представлены ниже в таблице 2.2.

Таблица 2.2

	0	1	2	3	4
	1	0,875	0,85298002	0,85259127	0,85259117
	1	0,875	0,86032958	0,86019845	0,86019844
	1	0,75	0,73030547	0,73016912	0,73016912
	-	0,25	0,02202	0,000388753	0,00000025

За четыре итерации было найдено решение системы .

Пример 2.3 Найти решение комплексного уравнения

Методом Ньютона с точностью , если известно, что корень лежит в первом квадранте.

Сведем задачу нахождения корня комплексного уравнения к решению двух уравнений с двумя неизвестными (см. замечание 1, раздел 2.1). Откуда получаем систему уравнений

Выберем начальное приближение . Расчеты будем проводить по формуле (2.3) и записывать в таблицу 2.3.

Таблица 2.3

	0	1	2	3	4	5
		0,495814	0,32092851	0,30276766	0,30545907	0,30543349
		0,3718605	0,17639658	0,16598503	0,16882656	0,16880099
	-	0,128139	0,195464	0,0181609	0,00284153	0,00002557

Из таблицы 2.3 видно, что для нахождения решения с заданной точностью , потребовалось пять итераций.

2.3 Модификации метода

Новым, по сравнению со скалярным случаем, фактором, осложняющим применение метода Ньютона к решению -мерных систем, является необходимость выполнения -мерных линейных задач на каждой итерации (обращение матрицы в (2.3) или решение СЛАУ в (2.4)) вычислительные затраты на которые растут с ростом . Уменьшение таких затрат - одно из направлений модификаций метода Ньютона.

Упрощенный метод Ньютона.

Этот метод требует значительно меньших затрат на один итерационный шаг, но итераций может потребоваться значительно больше для достижения заданной точности по сравнению с основным методом Ньютона. В данной модификации метода Ньютона матрица Якоби вычисляется и обращается лишь в точке начального приближения. Методика решения задачи аналогична изложенной в разделе 2.1, где вместо (2.3) используется формула

(2.11)

очевидно, что скорость сходимости упрощенного метода Ньютона в общем случае хуже по сравнению со сходимостью процесса (2.3).

Пример 2.4 Найти решение системы

упрощенным Методом Ньютона с точностью .

Выберем начальное приближение . Расчеты будем проводить по формуле (2.5)

которые представлены ниже в таблице 2.4.

Таблица 2.4

	0	1	2	3	4	5	6
	1	0,875	0,85742188	0,85357067	0,85277879	0,85262564	0,85259732
	1	0,875	0,86263021	0,86058986	0,86026037	0,86020816	0,86019996
	1	0,75	0,73307292	0,73061494	0,73023832	0,7301799	0,7301708
	-	0,25	0,0175781	0,0038512	0,00079188	0,00015314	0,00002832

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

Методы с конечно-разностными производными

На основе метода Ньютона (2.3) построим близкий к нему по поведению итерационный процесс, не требующий вычисления производных. Для этого будем заменять частные производные в матрице Якоби конечно-разностными соотношениями, то есть будем аппроксимировать матрицу Якоби следующим образом

При удачном задании последовательности малых векторов постоянной или сходящейся к нулю (для удобства будем считать постоянной на всех итерациях) полученный таким путем конечно-разностный метод Ньютона

(2.12)

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

Если связать задание с какой-либо сходящейся к нулю векторной последовательностью, например, с последовательностью поправок Тогда, полагая где а приходим к методу секущих - обобщению скалярного метода секущих (1.14)

(2.13)

где

По аналогии со скалярным случаем первое приближение рассчитывается с помощью конечно-разностного метода Ньютона (2.12) или задается вместе с начальным приближением, а дальнейшие вычисления проводятся по формуле (2.13). Как и в одномерном случае, метод секущих немного уступает методу Ньютона в скорости сходимости и имеет сверхлинейную скорость сходимости.

Проведем сравнение метода секущих и конечно-разностного метода на простом примере. Найдем решение системы

с точностью , где за начальное приближение возьмем

Таблица 2.5. Конечно-разностный метод Ньютона ()

	0	1	2	3	4	5
	2	1,299999979	1,039140254	1,000759153	1,000000288	1
	2	1,199999984	1,011764699	1,000045777	1,000000001	1

Таблица 2.6. Метод секущих ( выбирается по конечно-разностному методу Ньютона)

	0	1	2	3	4	5	6
	2	1,299999979	1,105339099	1,014357343	1,00073509	1,00000526	1
	2	1,199999984	1,047619044	1,002932551	1,000045777	1,000000045	1

Видно, что результаты метода секущих и конечно-разностного метода Ньютона достаточно близкие, однако конечно-разностный метод Ньютона сходится чуть быстрее.

Метод секущих Бройдена.

Чтобы лучше понять идеи, лежащие в основе метода секущих (метода Бройдена), вернемся к разделу 1.4.2, где метод секущих рассматривается для одномерного случая.

В процессе построения методов Ньютона и секущих решения нелинейного скалярного уравнения , функция в окрестности текущего приближения подменяется линейной функцией (моделью)

где - некоторый ненулевой коэффициент и .

Приравнивание к нулю линейной модели, т.е. решения линейного уравнения

порождает итерационную формулу

для вычисления приближений к корню уравнения (1.1).

Если потребовать, чтобы линейная модель , заменяющая функцию вблизи точки , имела одинаковую с ней производную, то, дифференцируя (2.14) получаем значение коэффициента

при подстановке которого в (2.15) приводит к методу Ньютона (1.4). Если же исходить из того, что наряду с равенством должно иметь место совпадение функций и в предшествующей точке , т.е. из равенства



или, в соответствии с (2.14),

то получаем коэффициент

превращающий (2.15) в формулу секущих (1.14).

Равенство (2.16), переписанное в виде

называют соотношением секущих. Оно обобщается на многомерный случай и лежит в основе вывода метода Бройдена. Рассмотрим этот вывод.

В многомерном случае соотношение секущих имеет вид

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

и преобразуем соотношение (2.17)



Аналогично одномерному случаю, а именно, по аналогии с формулой (2.15), будем искать приближения к решению векторного уравнения (2.2) по формуле

Желая, чтобы эта формула обобщала метод секущих (1.14), матрицу в ней нужно подобрать таким образом, чтобы она удовлетворяла соотношению секущих (2.17), но это соотношение не определяет матрицу однозначно. Глядя на равенство (2.17а), видно, что существует множество матриц , которые преобразуют заданный вектор в заданный вектор .

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

к такой же модели в точке

у нас нет никаких сведений от матрице линейного преобразования , кроме соотношения (2.17). Поэтому будем исходить из того, что при этом переходе изменения в модели должны быть минимальными. Эти изменения характеризует разность . Распишем эту разность



Представим вектор в виде линейной комбинации фиксированного вектора и некоторого вектора , ему ортогонального:

Подставляя представление вектора в разность получаем

Заметим, что первое слагаемое в (2.21) не может быть изменено, так как

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

Непосредственно проверкой можно убедиться, что условие (2.22) выполняется, если матричную поправку представить в виде



Таким образом приходим к так называемой формуле пересчета Бройдена

которая позволяет простыми вычислениями перейти от старой матрицы к новой такой, чтобы выполнялось соотношение секущих (2.17а) в новой точке и при этом изменения в линейной модели (2.20) были минимальны.

Совокупность формул (2.19), (2.23) вместе с обозначениями (2.18) называют методом секущих Бройдена. Метод Бройдена имеет линейную скорость сходимости при достаточной близости к и к

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

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

2. Положить и

3. Решить систему линейных алгебраических уравнений относительно - поправки к текущему приближению.

4. Вычислить

5. Если , процесс завершить и положить Если , вычислить

и перейти к п.3.

Пример 2.5 Найти решение системы

методом секущих Бройдена с точностью .

Выберем начальное приближение . Все расчеты будут представлены ниже в таблице 2.7

Таблица 2.7

	0	1	2	3	4	5
	1	0,875	0,85578748	0,8527228	0,85260167	0,85259133
	1	0,875	0,86148008	0,86014743	0,86018994	0,86019827
	1	0,75	0,73149905	0,73008557	0,73015883	0,73016905
	-	0,25	0,0192125	0,00306467	0,00012113	0,00001033

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

Пример 2.6 Найти решение системы

методом секущих Бройдена, расположенное в третьем квадранте, с точностью .

Выберем начальное приближение . Все расчеты будут представлены ниже в таблице 2.8.

Таблица 2.8

	0	1	2	3	4	5
	-1	-0,85714286	-0,83619345	-0,8302782	-0,83031798	-0,83030076
	-1	-1,1428571	-1,1419657	-1,145125	-1,1447873	-1,1448143
	-	0,142857	0,0209494	0,00591525	0,000337664	0,0000269491

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

2.4 Сравнение результатов

Рассмотрим типичное поведение рассмотренных методов решения систем нелинейных уравнений на следующем численном примере.

Требуется найти решение системы

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

будут приведены в сравнительной таблице 2.9.

В ней приведены: приближенные решения, полученные на -ой итерации, значения при которых сработал критерий (2.24), а также невязки, характеризующие некоторую меру близости найденного приближенного решения к точному решению заданной системы нелинейных уравнений. При этом шаг аппроксимации в конечно-разностном методе Ньютона и методе секущих брался на каждой итерации равным

Таблица 2.9

№	Метод	Приближенное решение	Число итераций	Невязка
1	Ньютона	0,3054334902 0,1688009872	6	-0,00000000000000000001 0,0000000000000000002
2	Упрощенный Ньютона	0,3054627077 0,1688302689	34	-0,0000017085529146506 0,0000013352376860446
3	Конечно-разностный Ньютона	0,3054334902 0,1688009872	6	0,00000000000000000559 -0,0000000000000000174
4	Секущих	0,3054334857 0,1688009828	7	0,00000000024866282742 -0,00000000025062889409
5	Секущих Бройдена	0,3054334695 0,1688009656	12	0,00000000149265249955 -0,00000000015396246037

Данный численный эксперимент, подкрепляет сделанные ранее заявления о сходимости представленных методов. Как видно из результатов, метод Ньютона и конечно-разностный метод Ньютона имеют достаточно схожие результаты, для достижения заданной точности обоим методам понадобилось рассчитать шесть приближений, однако конечно-разностный метод Ньютона сходится чуть медленнее. Используя упрощенный метода Ньютона, затраты на один итерационный шаг значительно снижаются, однако утрачивается квадратичная скорость сходимости и требуется значительно больше итераций для достижения заданной точности решения, в частности потребовалось выполнить тридцать четыре приближения. Решения, найденные методами секущих и секущих Бройдена, имеют достаточно близкую погрешность вычислений, однако метод секущих имеет сверхлинейную сходимость, а метод секущих Бройдена линейную. Вследствие чего для нахождения решения методом секущих потребовалось семь приближений, а для метода секущих Бройдена двенадцать приближения.

Заключение

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

Литература

1. Численные метода в примерах и задачах: Учеб. пособие/В.И. Киреев, А.В. Пантелеев. - М.: Высш. шк., 2004. - 480 с.: ил..

2. Основы численных методов: Учебник для вузов/В.М. Вержбицкий. - М.: Высш. шк., 2002. - 840 с.: ил..

3. Деннис Дж., Шнабель Р. Численные методы безусловной оптимизации и решения нелинейных уравнений: Пер. с англ. - М.: Мир, 1988. - 440 с., ил..

Приложение 1

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

W2.m

clear

diap = [-1, -0.5]; % задается диапазон, содержащий простой корень

fun = 'x2-exp(x)' % вводится функция

E = 0.00001; % вводится требуемая точность приближения

%далее выбирается нужный метод решения

[xkn k] = newton1(fun,diap,E) % метод Ньютона

[xkn k] = newton1c(fun,diap,E) % упрощенный метод Ньютона

[xkn k] = newton2(fun,diap,E) % метод секущих

[xkn k] = newton2h(fun,diap,E) % конечно-разностный метод Ньютона

newton1.m ( метод Ньютона)

function [xkn k] = newton1(fun,diap,E)

x0 = diap(1); % нижняя граница интервала

x1 = diap(2); % верхняя граница интервала

dfun = char(diff(sym(fun))); % первая производная

ddfun = char(diff(diff(sym(fun))));% вторая производная

F = inline (fun);

DF = inline (dfun);

DDF = inline (ddfun);

t = 0;

% выбор точки начального приближения

if F(x0)*DDF(x0)>0

t = x0;

else

t = x1;

end

% счетчик итераций

k = 0

xk = t

k = 1

xkn = xk -F(xk)/DF(xk);

xkn = vpa(xkn,9)

vpa(abs(xkn-xk),9) % погрешность приближения

while abs(xkn-xk) > E

k = k + 1

xk = xkn;

xkn = xk - F(xk)/DF(xk);

xkn = vpa(xkn,9)

vpa(abs(xkn-xk),9)

end

Fxkn = vpa(F(xkn),9); % невязка приближенного решения

newton1c.m (упрощенный метод Ньютона)

function [xkn k] = newton1(fun,diap,E)

x0 = diap(1);

x1 = diap(2);

dfun = char(diff(sym(fun)));

ddfun = char(diff(diff(sym(fun))));

F = inline (fun);

DF = inline (dfun);

DDF = inline (ddfun);

t = 0;

if F(x0)*DDF(x0) > 0

t = x0;

else

t = x1;

end

k = 0

xk = t

k = 1

xkn = xk -F(xk)/DF(xk);

xkn = vpa(xkn,9)

vpa(abs(xkn-xk),9)

while abs(xkn-xk) > E

k = k + 1

xk = xkn;

xkn = xk - F(xk)/DF(t);

xkn = vpa(xkn,9)

vpa(abs(xkn-xk),9)

end

Fxkn = vpa(F(xkn),9);

newton2h.m (конечно-разностный метод Ньютона)

function [xkn k] = newton2h(fun,diap,E)

x0 = diap(1);

x1 = diap(2);

dfun = char(diff(sym(fun)));

ddfun = char(diff(diff(sym(fun))));

F = inline (fun);

DF = inline (dfun);

DDF = inline (ddfun);

t = 0;

h = 0.0000001; % задается малая величина h, берется равной на каждой итерации

if F(x0)*DDF(x0) > 0

t = x0;

else

t = x1;

end

k = 0

xk = t

k = 1

xkn = xk -F(xk)*h/(F(xk)-F(xk-h));

xkn = vpa(xkn,9)

vpa(abs(xkn-xk),9)

while abs(xkn-xk)>E

k = k+1

xknn = xkn - F(xk)*h/(F(xk)-F(xk-h));

xk = xkn;

xkn = xknn;

xkn = vpa(xkn,9)

vpa(abs(xkn-xk),9)

end

Fxkn = vpa(F(xkn),9);

newton2.m (метод секущих)

function [xkn k] = newton2(fun,diap,E)

x0 = diap(1);

x1 = diap(2);

dfun = char(diff(sym(fun)));

ddfun = char(diff(diff(sym(fun))));

F = inline (fun);

DF = inline (dfun);

DDF = inline (ddfun);

t = 0;

h = 0.0000001;

if F(x0)*DDF(x0) > 0

t = x0;

else

t = x1;

end

k = 0

xk = t

k = 1

xkn = xk -F(xk)*h/(F(xk)-F(xk-h));

xkn = vpa(xkn,9)

vpa(abs(xkn-xk),9)

while abs(xkn-xk) > E

k = k+1

xknn = xkn - F(xkn)*(xkn-xk)/(F(xkn)-F(xk));

xk = xkn;

xkn = xknn;

xkn = vpa(xkn,9)

vpa(abs(xkn-xk),9)

end

Fxkn = vpa(F(xkn),9);

Приложение 2

В данном приложении представлен программный код, который необходим для корректной работы рассмотренных методов во второй главе, для систем из двух и трех уравнений (n=2 и n=3).

MNN.m

clear

syms x1 x2 % вводятся переменные

% вводится система из двух или трех уравнений

f1 = x13-x22;

f2 = x1+sin(x2-3);

E = 0.00001; % вводится требуемая точность решения

xinput = [0.5; 0.5]; % задается начальное приближение

% выбирается нужный метод решения

[xk k] = newton22(f1,f2,E,xinput) % метод Ньютона для n=2

[xk k] = newton22c(f1,f2,E,xinput) % упрощенный метод Ньютона для n=2

[xk k] = newton22l(f1,f2,E,xinput) % метод секущих Бройдена для n=2

[xk k] = newton22h(f1,f2,E,xinput) % конечно-разностный метод Ньютона для n=2

[xk k] = newton22hh(f1,f2,E,xinput) % метод секущих для n=2

[xk k] = newton33(f1,f2,f3,E,xinput) % метод Ньютона для n=3

[xk k] = newton33c(f1,f2,f3,E,xinput) % упрощенный метод Ньютона для n=3

[xk k] = newton33l(f1,f2,f3,E,xinput) % метод секущих Бройдена для n=3

[xk k] = newton33h(f1,f2,f3,E,xinput) % конечно-разностный метод Ньютона для n=3

[xk k] = newton33hh(f1,f2,f3,E,xinput) % метод секущих для n=3

newton22.m (метод Ньютона)

function [xk k] = newton22(f1,f2,E,xinput)

k=1

xk = xinput - w22(xinput,f1,f2)*f22(xinput,f1,f2);

xk = vpa(xk,10)

vpa(norm(xk-xinput,inf),10)

while norm(xk-xinput,inf)>E

k = k+1

xinput = xk;

xk = xinput - w22(xinput,f1,f2)*f22(xinput,f1,f2);

xk = vpa(xk,10)

vpa(norm(xk-xinput,inf),10)

end

f22(xk,f1,f2);

w22.m (составление матрицы Якоби и подстановка текущего приближения)

function y1 = w22(xinput,f1,f2);

syms x1 x2

df11 = diff(f1, 'x1');

df12 = diff(f1, 'x2');

df21 = diff(f2, 'x1');

df22 = diff(f2, 'x2');

Wx = [df11 df12;

df21 df22];

WW = subs(subs(Wx,x1,xinput(1)),x2,xinput(2));

y1 = inv(WW);

f22.m (подстановка текущего приближения в систему уравнений)

function y2 = f22(xinput,f1,f2);

syms x1 x2

Fx = [f1; f2];

y2=subs(subs(Fx,x1,xinput(1)),x2,xinput(2));

newton22c.m (упрощенный метод Ньютона)

function [xk k] = newton22c(f1,f2,E,xinput)

k = 1

xk = xinput - w22(xinput,f1,f2)*f22(xinput,f1,f2);

xk = vpa(xk,10)

vpa(norm(xk-xinput,inf),10)

Wconst = w22(xinput,f1,f2);

while norm(xk-xinput,inf)>E

k = k+1

xinput = xk;

xk = xinput - Wconst*f22(xinput,f1,f2);

xk =vpa(xk,10)

vpa(norm(xk-xinput,inf),10)

end

f22(xk,f1,f2);

newton22h.m ( конечно-разностный метод Ньютона)

function [xkn k] = newton22h(f1,f2,E,xinput)

h = [0.0000001;0.0000001]

k=1

xkn = xinput - w22h(xinput,f1,f2,h)* f22(xinput,f1,f2)

xkn = vpa(xkn,10)

vpa(norm(xkn-xinput,inf),10)

while norm(xkn-xinput,inf)>E

k = k+1

xinput = xkn;

xkn = xinput - w22h(xinput,f1,f2,h)*f22(xinput,f1,f2);

xkn = vpa(xkn,10)

vpa(norm(xkn-xinput,inf),10)

end

f22(xkn,f1,f2);

w22h.m (аппроксимация матрицы Якоби)

function y1 = w22h(xinput,f1,f2,h);

syms x1 x2

df1h = subs(subs(f1,x1,xinput(1)-h(1)),x2,xinput(2));

df1 = subs(subs(f1,x1,xinput(1)),x2,xinput(2));

df11 = (df1-df1h)/h(1);

df1h = subs(subs(f1,x1,xinput(1)),x2,xinput(2)-h(2));

df1 = subs(subs(f1,x1,xinput(1)),x2,xinput(2));

df12 = (df1-df1h)/h(2);

df1h = subs(subs(f2,x1,xinput(1)-h(1)),x2,xinput(2));

df1 = subs(subs(f2,x1,xinput(1)),x2,xinput(2));

df21 = (df1-df1h)/h(1);

df1h = subs(subs(f2,x1,xinput(1)),x2,xinput(2)-h(2));

df1 = subs(subs(f2,x1,xinput(1)),x2,xinput(2));

df22 = (df1-df1h)/h(2);

Wx = [df11 df12;

df21 df22];

y1 = inv(Wx);

newton22hh.m (метод секущих)

function [xkn k] = newton22hh(f1,f2,E,xinput)

h = [0.0000001;0.0000001]

k = 1

xkn = xinput - w22h(xinput,f1,f2,h)* f22(xinput,f1,f2)

xkn = vpa(xkn,10)

vpa(norm(xkn-xinput,inf),10)

while norm(xkn-xinput,inf)>E

k = k+1

h = xkn-xinput;

xinput = xkn;

xkn = xinput - w22h(xinput,f1,f2,h)*f22(xinput,f1,f2);

xkn = vpa(xkn,10)

vpa(norm(xkn-xinput,inf),10)

end

f22(xkn,f1,f2)

newton22l.m (метод секущих Бройдена)

function [xk k] = newton22l(f1,f2,E,xinput)

k=1

Ak = w22L(xinput,f1,f2);

Sk = - inv(Ak)*f22(xinput,f1,f2);

Xk = xinput + sk;

Xk = vpa(xk,10)

vpa(norm(sk,inf),10)

while norm(sk,inf)>E

k = k+1

yk = f22(xk,f1,f2)-f22(xinput,f1,f2);

Akn = Ak + (yk-Ak*sk)*sk'/(sk'*sk);

Xinput = xk;

sk = - inv(Akn)*f22(xinput,f1,f2);

xk = xinput + sk;

xk =vpa(xk,10)

vpa(norm(sk,inf),10)

Ak = Akn;

end

f22(xk,f1,f2)

w22L.m

function y1 = w22L(xinput,f1,f2);

syms x1 x2

df11 = diff(f1, 'x1');

df12 = diff(f1, 'x2');

df21 = diff(f2, 'x1');

df22 = diff(f2, 'x2');

Wx = [df11 df12;

df21 df22];

y1 = subs(subs(Wx,x1,xinput(1)),x2,xinput(2));

newton33.m (метод Ньютона)

function [xk k] = newton33(f1,f2,f3,E,xinput)

k=1

xk = xinput - w33(xinput,f1,f2,f3)*f33(xinput,f1,f2,f3);

xk = vpa(xk,10)

vpa(norm(xk-xinput,inf),10)

while norm(xk-xinput,inf)>E

k = k+1

xinput = xk;

xk = xinput - w33(xinput,f1,f2,f3)*f33(xinput,f1,f2,f3);

xk = vpa(xk,10)

vpa(norm(xk-xinput,inf),10)

end

fxk = f33(xk,f1,f2,f3);

w33.m

function y1 = w33(xinput,f1,f2,f3);

syms x1 x2 x3

df11 = diff(f1,'x1');

df12 = diff(f1,'x2');

df13 = diff(f1,'x3');

df21 = diff(f2,'x1');

df22 = diff(f2,'x2');

df23 = diff(f2,'x3');

df31 = diff(f3,'x1');

df32 = diff(f3,'x2');

df33 = diff(f3,'x3');

Wx = [df11 df12 df13;

df21 df22 df23;

df31 df32 df33];

WW = subs(subs(subs(Wx,x1,xinput(1)),x2,xinput(2)),x3,xinput(3));

y1=inv(WW);

f33.m

function y2=f33(xinput,f1,f2,f3);

syms x1 x2 x3

Fx = [f1; f2 ;f3];

y2=subs(subs(subs(Fx,x1,xinput(1)),x2,xinput(2)),x3,xinput(3));

newton33c.m (упрощенный метод Ньютона)

function [xk k] = newton33c(f1,f2,f3,E,xinput)

k = 1

xk = xinput - w33(xinput,f1,f2,f3)*f33(xinput,f1,f2,f3);

xk = vpa(xk,10)

vpa(norm(xk-xinput,inf),10)

Wconst = w33(xinput,f1,f2,f3);

while norm(xk-xinput,inf) > E

k = k+1

xinput = xk;

xk = xinput - Wconst *f33(xinput,f1,f2,f3);

xk = vpa(xk,10)

vpa(norm(xk-xinput,inf),10)

end

fxk = f33(xk,f1,f2,f3);

newton33h.m (конечно-разностный метод Ньютона)

function [xkn k] = newton33h(f1,f2,f3,E,xinput)

h = [0.0000001;0.0000001;0.0000001];

k = 1

xkn = xinput - w33h(xinput,f1,f2,f3,h)* f33(xinput,f1,f2,f3);

xkn = vpa(xkn,10)

vpa(norm(xkn-xinput,inf),10)

while norm(xkn-xinput,inf) > E

k = k+1

xinput = xkn;

xkn = xinput - w33h(xinput,f1,f2,f3,h)*f33(xinput,f1,f2,f3);

xkn = vpa(xkn,10)

vpa(norm(xkn-xinput,inf),10)

end

fxk = f33(xkn,f1,f2,f3);

w33h.m

function y1 = w33h(xinput,f1,f2,f3,h);

syms x1 x2 x3

df1h = subs(subs(subs(f1,x1,xinput(1)-h(1)),x2,xinput(2)),x3,xinput(3));

df1 = subs(subs(subs(f1,x1,xinput(1)),x2,xinput(2)),x3,xinput(3));

df11 = (df1-df1h)/h(1);

df1h = subs(subs(subs(f1,x1,xinput(1)),x2,xinput(2)-h(2)),x3,xinput(3));

df1 = subs(subs(subs(f1,x1,xinput(1)),x2,xinput(2)),x3,xinput(3));

df12 = (df1-df1h)/h(2);

df1h = subs(subs(subs(f1,x1,xinput(1)),x2,xinput(2)),x3,xinput(3)-h(3));

df1 = subs(subs(subs(f1,x1,xinput(1)),x2,xinput(2)),x3,xinput(3));

df13 = (df1-df1h)/h(3);

df1h = subs(subs(subs(f2,x1,xinput(1)-h(1)),x2,xinput(2)),x3,xinput(3));

df1 = subs(subs(subs(f2,x1,xinput(1)),x2,xinput(2)),x3,xinput(3));

df21 = (df1-df1h)/h(1);

df1h = subs(subs(subs(f2,x1,xinput(1)),x2,xinput(2)-h(2)),x3,xinput(3));