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

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

Pers.narod.ru. Алгоритмы. Метод Ньютона решения нелинейного уравнения

В литературе называется также методом касательных.

Рассмотрим графическую иллюстрацию метода (рис. 1). Предположим, что графическим методом определено начальное приближение х₀ к корню. В точке х₀ вычислим левую часть решаемого уравнения f₀ = f(x₀), а также производную в этой точке f'(x₀) = tg α. Следующее приближение к корню найдем в точке х₁, где касательная к функции f(x), проведенная из точки (х₀, f₀), пересекает ось абсцисс. Затем считаем точку х₁ в качестве начальной и продолжаем итерационный процесс. Из рис. видно, что таким способом можно приближаться к корню х*. При этом с каждой итерацией расстояние между очередным х_k+1 и предыдущим х_k приближениями к корню будет уменьшаться. Процесс уточнения корня закончим, когда выполнится условие

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

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

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

Ниже приводится простая консольная программа на Паскале для решения алгебраического уравнения произвольной степени n>1 . Функция f(x) и первая производная f'(x) задаются подпрограммами-функциями f и f1 соответственно.

Решение нелинейных уравнений на языке программирования Pascal

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

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

Данный метод достаточно прост и содержит всего два действия. Сначала находится переменная х – середина интервала [a,b]. После чего вычисляется значение функции в середине интервала. Затем определяется, совпадает ли по знаку значение функции в середине интервала, со знаком функции в левой части. В случаи если их знаки равны, то новой левой границей считается середина интервала, в ином же случаи правой граница интервала считается его середина. Таким образом, при каждой итерации интервал сокращается вдовое то справа, то слева. Очень часто можно встретить следующую реализацию данного метода.

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

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

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

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

В основе метода Ньютона лежит разложения функции в ряд Тейлора:

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

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

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

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

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

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

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

Метод Ньютона (также известный как метод касательных) — это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (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) на каждом шаге итерации, что не всегда удобно, а иногда практически невозможно. Данный способ позволяет производную функции заменить разностным отношением (приближенным значением):

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

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

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