Преимущества и недостатки метода ньютона для решения нелинейных уравнений (2 видео)

Содержание

Численные методы: решение нелинейных уравнений
Метод деления пополам
Метод Ньютона: теоретические основы
Визуализация метода Ньютона
Метод секущих
Метод парабол
Метод простых итераций
Нахождение всех корней уравнения
Численные методы решения нелинейных уравнений. Метод Ньютона для решения уравнений с одной переменной
Численные методы решения нелинейных уравнений. Метод Ньютона для решения уравнений с одной переменной
Метод Ньютона
🔥 Видео

Видео:Метод касательных (метод Ньютона)Скачать

Численные методы: решение нелинейных уравнений

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

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

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

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

В простейшем случае у нас имеется функция , заданная на отрезке ( a , b ) и принимающая определенные значения.

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

Нам нужно найти такое значение при котором такие называются корнями функции

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

Видео:Метод Ньютона (метод касательных) Пример РешенияСкачать

Метод деления пополам

Простейшим методом нахождения корней уравнения является метод деления пополам или дихотомия.

Этот метод является интуитивно ясным и каждый действовал бы при решении задачи подобным образом.

Алгоритм состоит в следующем.

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

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

Тогда либо , либо .

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

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

Заметьте, описанный алгоритм применим для любой непрерывной функции.

К достоинствам метода деления пополам следует отнести его высокую надежность и простоту.

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

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

Видео:МЗЭ 2021 Лекция 11 Метод Ньютона для решения систем нелинейных уравненийСкачать

Метод Ньютона: теоретические основы

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

Уравнение касательной к функции в точке имеет вид:

В уравнении касательной положим и .

Тогда алгоритм последовательных вычислений в методе Ньютона состоит в следующем:

Сходимость метода касательных квадратичная, порядок сходимости равен 2.

Таким образом, сходимость метода касательных Ньютона очень быстрая.

Запомните этот замечательный факт!

Без всяких изменений метод обобщается на комплексный случай.

Если корень является корнем второй кратности и выше, то порядок сходимости падает и становится линейным.

Упражнение 1. Найти с помощью метода касательных решение уравнения на отрезке (0, 2).

Упражнение 2. Найти с помощью метода касательных решение уравнения на отрезке (1, 3).

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

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

Видео:Методы численного анализа - Метод Ньютона, секущих для решения систем нелинейных уравненийСкачать

Визуализация метода Ньютона

Метод Ньютона (метод касательных) применяется в том случае, если уравнение f(x) = 0 имеет корень , и выполняются условия:

1) функция y= f(x) определена и непрерывна при ;

2) f(a)·f(b) 0. Таким образом, выбирается точка с абсциссой x₀, в которой касательная к кривой y=f(x) на отрезке [a;b] пересекает ось Ox. За точку x₀ сначала удобно выбирать один из концов отрезка.

Рассмотрим метод Ньютона на конкретном примере.

Пусть нам дана возрастающая функция y = f(x) =x 2 -2, непрерывная на отрезке (0;2), и имеющая f ‘(x) = 2x > 0 и f »(x) = 2 > 0.

Уравнение касательной в общем виде имеет представление:

В нашем случае: y-y₀=2x₀·(x-x₀). В качестве точки x₀ выбираем точку B₁(b; f(b)) = (2,2). Проводим касательную к функции y = f(x) в точке B₁, и обозначаем точку пересечения касательной и оси Ox точкой x₁. Получаем уравнение первой касательной:y-2=2·2(x-2), y=4x-6.

Точка пересечения касательной и оси Ox: x₁ =

Рисунок 2. Результат первой итерации

Затем находим точку пересечения функции y=f(x) и перпендикуляра, проведенного к оси Ox через точку x₁, получаем точку В₂ =(1.5; 0.25). Снова проводим касательную к функции y = f(x) в точке В₂, и обозначаем точку пересечения касательной и оси Ox точкой x₂.

Точка пересечения касательной и оси Ox: x₂ = .

Рисунок 3. Вторая итерация метода Ньютона

Затем находим точку пересечения функции y=f(x) и перпендикуляра, проведенного к оси Ox через точку x₂, получаем точку В₃ и так далее.

В3 = ()

Рисунок 4. Третий шаг метода касательных

Первое приближение корня определяется по формуле:

= 1.5.

Второе приближение корня определяется по формуле:

Третье приближение корня определяется по формуле:

Таким образом, i-ое приближение корня определяется по формуле:

Вычисления ведутся до тех пор, пока не будет достигнуто совпадение десятичных знаков, которые необходимы в ответе, или заданной точности e — до выполнения неравенства |xi—xi-1|

using namespace std;

float f(double x) //возвращает значение функции f(x) = x^2-2

float df(float x) //возвращает значение производной

float d2f(float x) // значение второй производной

int _tmain(int argc, _TCHAR* argv[])

int exit = 0, i=0;//переменные для выхода и цикла

double x0,xn;// вычисляемые приближения для корня

double a, b, eps;// границы отрезка и необходимая точность

cin>>a>>b; // вводим границы отрезка, на котором будем искать корень

cin>>eps; // вводим нужную точность вычислений

if (a > b) // если пользователь перепутал границы отрезка, меняем их местами

if (f(a)*f(b)>0) // если знаки функции на краях отрезка одинаковые, то здесь нет корня

cout 0) x0 = a; // для выбора начальной точки проверяем f(x0)*d2f(x0)>0 ?

xn = x0-f(x0)/df(x0); // считаем первое приближение

cout eps) // пока не достигнем необходимой точности, будет продолжать вычислять

xn = x0-f(x0)/df(x0); // непосредственно формула Ньютона

> while (exit!=1); // пока пользователь не ввел exit = 1

Посмотрим, как это работает. Нажмем на зеленый треугольник в верхнем левом углу экрана, или же клавишу F5.

Если происходит ошибка компиляции «Ошибка error LNK1123: сбой при преобразовании в COFF: файл недопустим или поврежден», то это лечится либо установкой первого Service pack 1, либо в настройках проекта Свойства -> Компоновщик отключаем инкрементную компоновку.

Рис. 4. Решение ошибки компиляции проекта

Мы будем искать корни у функции f(x) = x2-2.

Сначала проверим работу приложения на «неправильных» входных данных. На отрезке [3; 5] нет корней, наша программа должна выдать сообщение об ошибке.

У нас появилось окно приложения:

Рис. 5. Ввод входных данных

Введем границы отрезка 3 и 5, и точность 0.05. Программа, как и надо, выдала сообщение об ошибке, что на данном отрезке корней нет.

Рис. 6. Ошибка «На этом отрезке корней нет!»

Выходить мы пока не собираемся, так что на сообщение «Exit?» вводим «0».

Теперь проверим работу приложения на корректных входных данных. Введем отрезок [0; 2] и точность 0.0001.

Рис. 7. Вычисление корня с необходимой точностью

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

Чтобы выйти из приложения, введем «Exit?» => 1.

Видео:Способы решения систем нелинейных уравнений. 9 класс.Скачать

Метод секущих

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

Итерационный процесс имеет вид:

где .

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

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

Эта замечательная величина называется золотым сечением:

Убедимся в этом, считая для удобства, что .

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

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

После подстановки имеем: и

Для сходимости необходимо, чтобы было положительным, поэтому .

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

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

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

Такая процедура определения момента окончания итераций называется приемом Гарвика.

Видео:4.2 Решение систем нелинейных уравнений. МетодыСкачать

Метод парабол

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

Для этого заменим, аналогично методу секущих, функцию интерполяционной параболой проходящей через точки , и .

В форме Ньютона она имеет вид:

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

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

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

Этот метод очень удобен для поиска корней многочленов высокой степени.

Видео:10 Численные методы решения нелинейных уравненийСкачать

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

Задачу нахождения решений уравнений можно формулировать как задачу нахождения корней: , или как задачу нахождения неподвижной точки.

Пусть и — сжатие: (в частности, тот факт, что — сжатие, как легко видеть, означает, что).

По теореме Банаха существует и единственна неподвижная точка

Она может быть найдена как предел простой итерационной процедуры

где начальное приближение — произвольная точка промежутка .

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

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

Условие существенно, ибо если, например, на [0,1] , то неподвижная точка отсутствует, хотя производная равна нулю. Скорость сходимости зависит от величины . Чем меньше , тем быстрее сходимость.

Рассмотрим уравнение: .

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

Однако можно в качестве можно взять, например, функцию . Соответствующая итерационная процедура имеет вид: .

Эти итерации сходятся к неподвижной точке для любого начального приближения :

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

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

т.е. такой итерационный процесс всегда сходится.

Метод Ньютона представляет собой частный случай метода простых итераций.

Здесь нетрудно убедиться, что при существует окрестность корня, в которой .

то если корень кратности , то в его окрестности и, следовательно,.

Если — простой корень, то сходимость метода касательных квадратичная (то есть порядок сходимости равен 2).

Поскольку , то

Таким образом, сходимость метода Ньютона очень быстрая.

Видео:Методы решения систем нелинейных уравнений. Метод Ньютона. Численные методы. Лекция 14Скачать

Нахождение всех корней уравнения

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

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

Для поиска других корней используется метод удаления корней.

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

Применяя тот или иной метод нахождения корней к функции , мы найдем новый корень (который может в случае кратных корней и совпадать с ). Далее можно рассмотреть функцию и искать корни у неё.

Повторяя указанную процедуру, можно найти все корни с учетом кратности.

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

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

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

Видео:Вычислительная математика. Лекция 4. Решение нелинейных уравнений и систем уравненийСкачать

Численные методы решения нелинейных уравнений. Метод Ньютона для решения уравнений с одной переменной

Видео:После этого видео, ТЫ РЕШИШЬ ЛЮБУЮ Систему Нелинейных УравненийСкачать

Численные методы решения нелинейных уравнений. Метод Ньютона для решения уравнений с одной переменной

Метод Ньютона (также известный как метод касательных) — это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643-1727), под именем которого и обрёл свою известность.

Метод был описан Исааком Ньютоном в рукописи De analysi per aequationes numero terminorum infinitas ( лат .О б анализе уравнениями бесконечных рядов), адресованной в 1669 году Барроу , и в работе De metodis fluxionum et serierum infinitarum ( лат.Метод флюксий и бесконечные ряды) или Geometria analytica ( лат.Аналитическая геометрия) в собраниях трудов Ньютона, которая была написана в 1671 году. Однако описание метода существенно отличалось от его нынешнего изложения: Ньютон применял свой метод исключительно к полиномам. Он вычислял не последовательные приближения x_n , а последовательность полиномов и в результате получал приближённое решение x.

Впервые метод был опубликован в трактате Алгебра Джона Валлиса в 1685 году, по просьбе которого он был кратко описан самим Ньютоном. В 1690 году Джозеф Рафсон опубликовал упрощённое описание в работе Analysis aequationum universalis (лат. Общий анализ уравнений). Рафсон рассматривал метод Ньютона как чисто алгебраический и ограничил его применение полиномами, однако при этом он описал метод на основе последовательных приближений x_n вместо более трудной для понимания последовательности полиномов, использованной Ньютоном.

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

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

Рис.1 . График изменение функции

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

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

Условием окончания итерационного процесса является выполнение следующего условия:

где ˗ допустимая погрешность определения корня.

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

Математическое обоснование

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

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

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

Производная сжимающего отображения определяется в следующем виде:

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

С учетом этого сжимающая функция прием следующий вид:

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

Алгоритм нахождения корня нелинейного уравнения по методу Ньютона для уравнения с одной переменной

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

2. Выполнить расчет приближенного значения корня функции в соответствии с формулой:

3. Проверяем приближенное значение корня на предмет заданной точности, в случае:

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

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

Пример решения уравнений

по методу Ньютона для уравнения с одной переменной

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

Вариант решения нелинейного уравнения в программном комплексе MathCAD представлен на рисунке 3.

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

Рис.2 . Результаты расчета по методу Ньютона для уравнения с одной переменной

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

Рис.3 . Листинг программы в MathCad

Модификации метода Ньютона для уравнения с одной переменной

Существует несколько модификаций метода Ньютона, которые направлены на упрощение вычислительного процесса.

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

В соответствии с методом Ньютона требуется вычислять производную функции f(x) на каждом шаге итерации, что ведет к увеличению вычислительных затрат. Для уменьшения затрат, связанных с вычислением производной на каждом шаге расчета, можно произвести замену производной f’( x_n ) в точке x_n в формуле на производную f’(x₀) в точке x₀. В соответствии с данным методом расчета приближенное значение корня определяется по следующей формуле:

Таким образом, на каждом шаге расчета строятся прямые , которые параллельны касательной к кривой y=f(x) в точке B₀ (см. рис.4). Преимуществом данного метода является то, что производная функции вычисляется один раз.

Разностный метод Ньютона

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

В результате приближенное значение корня функции f(x) будет определяться выражением разностного метода Ньютона:

Двух шаговый метод Ньютона

В результате приближенное значение корня функции f(x) будет определяться следующим выражением:

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

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

Видео:15 Метод Ньютона (Метод касательных) Ручной счет Численные методы решения нелинейного уравненияСкачать

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

Метод Ньютона заключается в таком выборе матрицы Т в (4.4), при котором спектральный радиус матрицы G_x, характеризующей сходимость итераций, равен нулю при X— X, т.е. р<G^X)) = 0. Поскольку скорость сходимости итераций тем больше, чем ближе к нулю р(G’^X)), то в окрестности точного решения метод Ньютона имеет очень высокую скорость сходимости.

В качестве итерационной матрицы в методе Ньютона выбирается Т= -J

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

Изображение этого итерационного процесса:

Для того чтобы метод сходился к точному решению X, спектральный радиус матрицы G_x должен быть меньше 1, т.е.

X F<X))'_{x J в окрестности точного решения X е . Полагая матрицу Якоби в окрестности X* постоянной, для точного решения имеем}

так как F'(X*) = J(X*). Из этого следует, что для метода Ньютона всегда существует некоторая окрестность точного решения X*, в которой выполняются условия сходимости итераций p(G’_x(X*)) 1, т.е. в случае, если метод Ньютона сходится, то скорость сходимости может быть сверхлинейной, причем в окрестности решения всегда существует область квадратичной сходимости, где р = 1.

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

f(x) = ax-b = 0 функцииg(x) будет соответствовать прямая, параллельная оси х, и проходящая через точку (g(x*),x*), показанная штрихпунктирной линией. Ясно, что из любой начальной точки х₀ на оси х решение будет найдено за одну итерацию.

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

Элементы матрицы Якоби можно вычислять двумя способами: либо аналитически, если известны формулы для расчета элементов dfj(X) / Эх_у, либо с использованием конечно-разностной аппроксимации частных производных. В любом случае матрицу Якоби приводят к виду J =/j + /₂, где У, — постоянная матрица, не изменяющаяся в ходе итераций; J₂ — переменная матрица, зависящая от нелинейных составляющих системы НАУ. Элементы матрицы У, рассчитываются единожды перед началом итерационного процесса, тогда как элементы матрицы У₂ обновляются на каждой итерации.

Практика показала, что метод Ньютона наиболее эффективен при аналитическом вычислении элементов матрицы У₂, особенно с точки зрения скорости сходимости к точному решению. Однако возможность аналитического вычисления элементов матрицы У₂ существует далеко не всегда. Во-первых, точные аналитические формулы могут либо отсутствовать, либо быть слишком громоздкими и неудобными для непосредственной реализации. Во-вторых, сами функции часто бывают заданы не аналитически, а в виде совокупности отдельных значений. В-третьих, в случае ошибочно полученной аналитической формулы для dfj(X)/dXj возникшую ошибку можно проконтролировать только по увеличению числа итераций и плохой сходимости, однако подобный контроль неэффективен и не может обеспечить выявление точной причины ошибки. Тем не менее для нелинейных функций, часто используемых в задачах математического и численного моделирования, следует вычислять элементы df_t(X) / Эх, в аналитическом виде, соответствующим образом выполняя подготовительную вычислительную работу, связанную с наиболее точной аппроксимацией функций f^X) и устранением ошибок в формулах для вычисления dfj(X) / Эх_у.

Для конечно-разностной аппроксимации частных производных применяются две основные формулы:

) — вектор, отличающийся от вектора Xтолько элементом Xj = Xj + Axj (Xj = Xj — Axj;); Ax. — заданный параметр дискретизации.

С учетом ошибок округления более предпочтительной является вторая формула. Параметры дискретизации могут быть постоянными в течение всего итерационного процесса. В этом случае дискретный метод Ньютона не обладает квадратичной сходимостью. Однако Ах. можно сделать зависимым от номера итерации для получения быстрой сходимости в окрестности решения X Дискретный метод Ньютона требует многократного вычисления каждой из нелинейных функций^.(Л) на каждой итерации, поэтому вычисление элементов dfj<X) / dxj будет более ресурсозатратным процессом по сравнению с аналитическим вычислением производных. Однако в реальных задачах, связанных с анализом, функции f_t<X) зависят от небольшого числа переменных*., т.е. для большинства элементов df_t(X) / dxj = О, а значит, затраты будут расти линейно с увеличением размерности матрицы У.

Вычисление обратной матрицы У -1 требует значительных ресурсозатрат; оно осуществляется только в частных случаях систем НАУ невысокой размерности и при малом изменении элементов матрицы Якоби.

На практике вместо обращения матрицы Якоби решают систему ЛАУ. Поскольку АХ_к = Х_к -Х_к__ь формулу (4.7) можно представить в виде системы ЛАУ

Данная система ЛАУ решается на каждой итерации относительно АХ_к после чего вычисляется Х_к=Х_к_₁+АХ_к. Решение системы ЛАУ — это наиболее трудоемкий этап в реализации метода Ньютона, определяющий его вычислительную эффективность на каждой итерации. На практике метод Ньютона применим лишь при учете разреженности матрицы У в процессе решения систем ЛАУ большой размерности.

Наиболее сложным вопросом практической реализации метода Ньютона является правильный выбор начального приближения Х₀. Для каждого конкретного класса задач математического и численного моделирования этот вопрос решается индивидуально в зависимости от характера соответствующих задач. Однако условия теоремы о локальной сходимости итераций подсказывают надежный универсальный критерий области квадратичной сходимости метода Ньютона. На практике этот критерий сводится к следующему: если не удалось найти решение с заданной точностью за 6—7 итераций, то необходимо выбрать новое начальное приближение X_Q.

Простейший способ обеспечения сходимости для любого X_Q состоит в применении формулы Х_к =X_k__l -h_kJ

l F(X_k_Д, где h_k — параметр, выбираемый из условия минимизации нормы вектора )|| или уменьшения этой нормы на каждой итерации. Расходимость при этом исключается, однако сходимость при неудачном выборе Х₀ может быть очень медленной, т.е. теряется основное преимущество метода Ньютона. По этой причине более надежным и эффективным считается метод продолжения решения по параметру.

4.3.3. Метод продолжения решения по параметру

Данный метод (другое его название — метод движущейся области сходимости) является наиболее универсальным. Обозначим через t параметр, изменяющийся от 0 до 1. Введем систему НАУ

такую, что при t = 0 система Н(Х, 0) = 0 имеет известное решение Х₀, а при t = 1 система Н(Х, 1) = 0 имеет решение X*, соответствующее решению системы НАУ (4.1) F(X) = 0.

Систему Ff(X, t) = 0 можно получить различными способами. При этом основное требование заключается в том, чтобы вектор-функция Н(Х, t) была непрерывна на отрезке / = [0, 1J. Тогда, изменяя / в диапазоне от 0 до 1 и решая для каждого /. систему Н(Х, /.) = 0 методом Ньютона, можно последовательно найти Х₀, Х_х, Х₂, . X .

Поскольку при t_Q = 0 значение Х₀ известно, то всегда можно найти достаточно близкое к L = 0, при котором будут выполняться условия сходимости метода Ньютона. Аналогичным образом можно обеспечить условия сходимости метода Ньютона и для /₂ Дз> •••> t„ = 1 • Для промежуточных вычислений Л’*(Л) можно задавать невысокую точность, выполняя с высокой точностью только последние итерации при/= 1.

Первый способ построения вектор-функции Н(Х, t) заключается в формировании очевидной системы НАУ

где X_Q — фиксированное значение вектора X. Часто удобно в качестве Х₀ принять нулевые начальные приближения.

Поскольку Н’_х (X, t)= F’_x =J, то для каждого значения t_j итерационная формула будет иметь вид

при начальных условиях А’₀(/, ) = А’*(/_м), где X*(?_м) — точное решение системы #(AV,_,) = 0. Метод продолжения решения по параметру с использованием данной формулы универсален и всегда приводит к получению решения X*, однако в тех случаях, когда система имеет несколько решений, необходимо задавать разные значения Х₀ либо использовать другие способы построения системы НАУ Н(Х, t) = 0.

Второй способ построения вектор-функции Н(Х, t) заключается в следующем. Введем параметр t и умножим на него каждую нелинейную зависимость системы НАУ F(X) = 0; в результате при ?₀ = 0 получим систему ЛАУ Н<Х, 0) = 0, которая решается за одну итерацию по методу Ньютона и дает X_Q(t_Q). Затем, изменяя t в диапазоне от 0 до 1, получим решение X* для системы F(X)= Н(Х, 1) = 0.

Третий способ построения вектор-функции Н(Х, t) = F(X, ts) основан на том, что во многих практических случаях задача естественным образом зависит от некоторого параметра s, причем при s = 5 ном ( 5 ном — номинальное значение параметра) получается система H(X,l) = F(X) = 0, а при 5 = 0 — система Н(Х,0)= F(X,ts_HOM) = 0, имеющая известное решение X_Q(t_Q). Например, при расчетах устойчивых состояний электронных схем в качестве 5 можно использовать напряжения питания схем, так как при 5 = 0 схема будет обесточена и X₀(t_Q) = 0; следовательно, при 5 = 5 в таком случае полу- чим решение X*, соответствующее устойчивому состоянию электронной схемы.