1.4. Метод Ньютона (метод касательных)

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

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

Из геометрических соотношений рис. 1.6 получим основную формулу метода Ньютона

В общем виде для шага итерационного процесса последнее соотношение принимает вид

Рис. 1.6. Метод Ньютона

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

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

и

так как

Метод Ньютона обладает высокой скоростью сходимости. Обычно абсолютная точность решения достигается через 5-6 итераций.

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

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

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

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

Рис. 1.8. Блок-схема программы решения уравнения методом Ньютона

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

Параметрами задачи будут коэффициенты уравнения (1.15). Левую часть алгебраического уравнения, многочлен степени экономично вычислять по гнездовой схеме или схеме Горнера [1]

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

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

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

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

В подпрограмме метода (строки 100-190) обращаемся к подпрограмме вычисления отношения (строка 100), затем вычисляем очередное приближение к корню по формуле (1.14) (строка 110). Следует обратить

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

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

В блоке 2 в строке 200 находятся операторы инициализации переменных для функции и ее производной В цикле (строка 210) оператор вычисления производной предшествует оператору вычисления функции. Формально первый оператор можно получить путем дифференцирования правой части второго оператора по X по обычным правилам дифференцирования. Такой же способ применим и к оператору инициализации производной.

После вычисления функции и производной определяем их отношение (строка 220).

Вывод на дисплей текущих значений аргумента и погрешности осуществляется для наблюдения за процессом поиска корня (строка 280).

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

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

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

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

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

которое имеет один вещественный и два комплексно сопряженных корня

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

Значение переменной задаем 4, параметры -

Погрешность можно выбрать , тогда программы 1.4 и 1.5 должны выдать результаты (1.18).

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

(см. скан)

(см. скан)

(см. скан)

(см. скан)