Численные методы решения нелинейных уравнений. Метод Ньютона для решения уравнений с одной переменной
Численные методы решения нелинейных уравнений. Метод Ньютона для решения уравнений с одной переменной
Метод Ньютона (также известный как метод касательных) — это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643-1727), под именем которого и обрёл свою известность.
Метод был описан Исааком Ньютоном в рукописи De analysi per aequationes numero terminorum infinitas ( лат .О б анализе уравнениями бесконечных рядов), адресованной в 1669 году Барроу , и в работе De metodis fluxionum et serierum infinitarum ( лат.Метод флюксий и бесконечные ряды) или Geometria analytica ( лат.Аналитическая геометрия) в собраниях трудов Ньютона, которая была написана в 1671 году. Однако описание метода существенно отличалось от его нынешнего изложения: Ньютон применял свой метод исключительно к полиномам. Он вычислял не последовательные приближения xn , а последовательность полиномов и в результате получал приближённое решение x.
Впервые метод был опубликован в трактате Алгебра Джона Валлиса в 1685 году, по просьбе которого он был кратко описан самим Ньютоном. В 1690 году Джозеф Рафсон опубликовал упрощённое описание в работе Analysis aequationum universalis (лат. Общий анализ уравнений). Рафсон рассматривал метод Ньютона как чисто алгебраический и ограничил его применение полиномами, однако при этом он описал метод на основе последовательных приближений xn вместо более трудной для понимания последовательности полиномов, использованной Ньютоном.
Наконец, в 1740 году метод Ньютона был описан Томасом Симпсоном как итеративный метод первого порядка решения нелинейных уравнений с использованием производной в том виде, в котором он излагается здесь. В той же публикации Симпсон обобщил метод на случай системы из двух уравнений и отметил, что метод Ньютона также может быть применён для решения задач оптимизации путём нахождения нуля производной или градиента.
В соответствии с данным методом задача поиска корня функции сводится к задаче поиска точки пересечения с осью абсцисс касательной, построенной к графику функции .
Рис.1 . График изменение функции
Проведенная в любой точке касательная линия к графику функции определяется производной данной функции в рассматриваемой точке, которая в свою очередь определяется тангенсом угла α ( ). Точка пересечения касательной с осью абсцисс определяется исходя из следующего соотношения в прямоугольном треугольнике: тангенс угла в прямоугольном треугольнике определяется отношением противолежащего катета к прилежащему катету треугольнику. Таким образом, на каждом шаге строится касательная к графику функции в точке очередного приближения . Точка пересечения касательной с осью Ox будет являться следующей точкой приближения . В соответствии с рассматриваемым методом расчет приближенного значения корня на i -итерации производится по формуле:
Наклон прямой подстраивается на каждом шаге наилучшим образом, однако следует обратить внимание на то, что алгоритм не учитывает кривизну графика и следовательно в процессе расчета остается неизвестно в какую сторону может отклониться график.
Условием окончания итерационного процесса является выполнение следующего условия:
где ˗ допустимая погрешность определения корня.
Метод обладает квадратичной сходимостью. Квадратичная скорость сходимость означает, что число верных знаков в приближённом значении удваивается с каждой итерацией.
Математическое обоснование
Пусть дана вещественная функция , которая определена и непрерывна на рассматриваемом участке. Необходимо найти вещественный корень рассматриваемой функции.
Вывод уравнения основано на методе простых итераций, в соответствии с которым уравнение приводят к эквивалентному уравнению при любой функции . Введем понятие сжимающего отображения, которое определяется соотношением .
Для наилучшей сходимости метода в точке очередного приближения должно выполняться условие . Данное требование означает, что корень функции должен соответствовать экстремуму функции .
Производная сжимающего отображения определяется в следующем виде:
Выразим из данного выражение переменную при условии принятого ранее утверждения о том, что при необходимо обеспечить условие . В результате получим выражение для определения переменной :
С учетом этого сжимающая функция прием следующий вид:
Таким образом, алгоритм нахождения численного решения уравнения сводится к итерационной процедуре вычисления:
Алгоритм нахождения корня нелинейного уравнения по методу Ньютона для уравнения с одной переменной
1. Задать начальную точку приближенного значения корня функции , а также погрешность расчета (малое положительное число ) и начальный шаг итерации ( ).
2. Выполнить расчет приближенного значения корня функции в соответствии с формулой:
3. Проверяем приближенное значение корня на предмет заданной точности, в случае:
— если разность двух последовательных приближений станет меньше заданной точности , то итерационный процесс заканчивается.
— если разность двух последовательных приближений не достигает необходимой точности , то необходимо продолжить итерационный процесс и перейти к п.2 рассматриваемого алгоритма.
Пример решения уравнений
по методу Ньютона для уравнения с одной переменной
В качестве примера, рассмотрим решение нелинейного уравнения методом Ньютона для уравнения с одной переменной . Корень необходимо найти с точностью в качестве первого приближения .
Вариант решения нелинейного уравнения в программном комплексе MathCAD представлен на рисунке 3.
Результаты расчетов, а именно динамика изменения приближенного значения корня, а также погрешности расчета от шага итерации представлены в графической форме (см. рис.2).
Рис.2 . Результаты расчета по методу Ньютона для уравнения с одной переменной
Для обеспечения заданной точности при поиске приближенного значения корня уравнения в диапазоне необходимо выполнить 4 итерации. На последнем шаге итерации приближенное значение корня нелинейного уравнения будет определяться значением: .
Рис.3 . Листинг программы в MathCad
Модификации метода Ньютона для уравнения с одной переменной
Существует несколько модификаций метода Ньютона, которые направлены на упрощение вычислительного процесса.
Упрощенный метод Ньютона
В соответствии с методом Ньютона требуется вычислять производную функции f(x) на каждом шаге итерации, что ведет к увеличению вычислительных затрат. Для уменьшения затрат, связанных с вычислением производной на каждом шаге расчета, можно произвести замену производной f’( xn ) в точке xn в формуле на производную f’(x0) в точке x0. В соответствии с данным методом расчета приближенное значение корня определяется по следующей формуле:
Таким образом, на каждом шаге расчета строятся прямые , которые параллельны касательной к кривой y=f(x) в точке B0 (см. рис.4). Преимуществом данного метода является то, что производная функции вычисляется один раз.
Разностный метод Ньютона
В соответствии с методом Ньютона требуется вычислять производную функции f(x) на каждом шаге итерации, что не всегда удобно, а иногда практически невозможно. Данный способ позволяет производную функции заменить разностным отношением (приближенным значением):
В результате приближенное значение корня функции f(x) будет определяться выражением разностного метода Ньютона:
Двух шаговый метод Ньютона
В соответствии с методом Ньютона требуется вычислять производную функции f(x) на каждом шаге итерации, что не всегда удобно, а иногда практически невозможно. Данный способ позволяет производную функции заменить разностным отношением (приближенным значением):
В результате приближенное значение корня функции f(x) будет определяться следующим выражением:
Метод секущих является двух шаговым, то есть новое приближение определяется двумя предыдущими итерациями и . В методе необходимо задавать два начальных приближения и . Скорость сходимости метода будет линейной.
Для того, чтобы добавить Ваш комментарий к статье, пожалуйста, зарегистрируйтесь на сайте.
Численное решение нелинейных уравнений с одной переменной
Учащимся 10-11 классов
доцент кафедры информатики и информационных технологий ГОУ ВПО ДВГГУ
Численное решение нелинейных уравнений с одной переменной
При решении задач прикладного характера в разнообразных разделах физики, механики, техники и других областях возникает необходимость решения нелинейных уравнений с одной переменной. При этом многие уравнения не имеют аналитических решений. Это относится к большинству трансцендентных уравнений. Также доказано, что нельзя построить формулу, по которой можно было бы решить произвольное алгебраические уравнение выше четвертой степени.
Уравнение будем называть линейным[1], алгебраическим или трансцендентным в зависимости от того, имеет ли оно одно решение, n решений или неопределенное число решений.
Нелинейные уравнения можно разделить на два класса – алгебраические и трансцендентные. Алгебраическими уравнениями называют уравнения, содержащие только алгебраические функции (целые, рациональные, иррациональные). Например, многочлен является целой алгебраической функцией. Уравнения, содержащие другие функции (тригонометрические, показательные, логарифмические и другие) называются трансцендентными.[2]
Методы решения нелинейных уравнений делятся на две группы:
Точные методы позволяют записать корни в виде некоторого конечного соотношения (формулы). Из школьного курса алгебры известны такие методы для решения тригонометрических, логарифмических, показательных, а также простейших алгебраических уравнений.
Если алгебраическое или трансцендентное уравнение достаточно сложное, то его корни сравнительно редко удается найти точно. Поэтому большое значение приобретают способы приближенного нахождения корней уравнения и оценки степени их точности. Если точно определить корни уравнения не представляется возможным, для их решения используют численные итерационные (iteration — повторение) методы с заданной степенью точности.
Далее будут рассмотрены несколько численных методов и приведены алгоритмы нахождения корней уравнений.
В общем случае нелинейное уравнение можно записать в виде:
(1)
где функция F(x) — определена и непрерывна на некотором конечном или бесконечном интервале
(2)
где функции f(x) и g(x) также определены и непрерывны на интервале .
Всякое число обращающее уравнения (1) или (2) в верные числовые равенства называется корнем этого уравнения.
Корни уравнения могут быть действительными и комплексными. В дальнейшем будет идти речь только о вычислении действительных корней.
Решить уравнение численно значит:
1) установить имеет ли оно действительные корни;
2) отделить эти корни (то есть на числовой оси найти достаточно тесные промежутки, называемые интервалами изоляции корня[3], содержащие только один корень данного уравнения);
3) уточнить отделенные корни, т. е. найти значения корней с заданной степенью точности .
Последнее означает следующее.
Пусть x* — точный корень уравнения и x* , то есть x* . Если , тогда числа и могут рассматриваться как приближенные значения корня x* соответственно с недостатком и с избытком с точностью до , так как и .
Любое число, содержащееся между и , можно принять за приближенное значение корня x* с точностью до .
Графические методы решения уравнений[4]
Пусть дано уравнение F (х) = 0. Построим график функции F (х). Абсциссы точек пересечения графика с осью Ох и являются корнями уравнения.
Иногда для графического решения уравнения удобнее записать его в виде и построить графики функций: и Абсциссы точек пересечения этих графиков и являются корнями уравнения F (х) = 0 (рис. 1).
Однако этот метод позволяет получить лишь грубо приближенные значения корней уравнения. Для получения значений корней с большей точностью применяются численные методы. Однако, графический метод очень удобен, так как он позволяет найти корни с точностью, достаточной для решения многих практических задач, а также достаточно нагляден, прост и доступен.
Численные методы решения уравнений
Наиболее распространенными на практике численными методами решения уравнения (1) являются: метод половинного деления, метод хорд, метод касательных, метод простой итерации и т. д.[5]
Процесс численного решения уравнений разбивается на три этапа:
1. Отделение корней уравнения. Этот процесс можно сделать как графически, так и аналитически. Важно найти такие отрезки, которые бы содержали по одному корню уравнения (1).
2. Выбор метода решения и преобразование уравнения к виду, удобному для применения данного метода.
3. Уточнение корней с заданной точностью при помощи выбранного численного метода.
Говорят, что корень x* уравнения отделен на отрезке , если он содержится в данном отрезке, и если на этом отрезке других корней нет.
Провести полное отделение всех корней уравнения – значит разбить всю область допустимых значений на интервалы (или на отрезки), в каждом из которых содержится ровно по одному корню (или не содержится ни одного корня).
Отделение корней обычно начинают проводить графически. Для этого строят графики функций, получают интервалы, в которых находятся корни уравнения. Это предположение затем проверяют аналитически, пользуясь следующим свойством непрерывной функции F(x): если функция непрерывна на интервале и на его концах имеет разные знаки (), то между точками a и b имеется хотя бы один корень уравнения .
При этом корней может оказаться и несколько, как показано на рис. 2. Рис.2
Для того, чтобы на интервале существовал только один корень, должно выполняться следующее свойство: если функция непрерывна и монотонна на отрезке и принимает на концах отрезка значения разных знаков, то внутри отрезка содержится корень уравнения и этот корень единственный (рис. 3, а, b).
Пример 1: Отделить графически положительные корни уравнения
Решение: Найдем приближенные значения корней уравнения графически. Для этого удобно представить уравнение в следующем виде: e0,3x = 2 sin(2x).
Решением данного уравнения будет являться абсцисса x точки пересечения графиков следующих функций:
На рисунке видно, что графики функций y1(x) и y2(x) пересекаются в двух точках A и B, абсциссы которых положительны и лежат соответственно в промежутках и. Следовательно, уравнение имеет два положительных корня x1 и x2, которые лежат в промежутках и.
Примечание: Графики функций можно строить с помощью компьютера, например, в электронных таблицах Excel или в свободно распространяемой системе компьютерной математики Scilab.[7]
Пример 2: Отделить аналитически корни уравнения
Решение: Для аналитического отделения корней найдем производную функции
Производная этой функции
ни в одной точке не обращается в нуль, т. к. D = 36 -4*3*11 0, следовательно, функция f везде возрастает, и уравнение (4) может иметь один корень.
[3] Методы определения интервала изоляции корня основаны на следующем свойстве: если непрерывная функция f(x) на интервале [a, b] поменяла знак, т. е. f(a)*f(b)
Реферат: Решение нелинейных уравнений с одной переменной
Название: Решение нелинейных уравнений с одной переменной Раздел: Рефераты по математике Тип: реферат Добавлен 13:19:15 23 июля 2011 Похожие работы Просмотров: 311 Комментариев: 21 Оценило: 2 человек Средний балл: 5 Оценка: неизвестно Скачать | ||
В рассмотренном выше случае для кривых I-го типа, правым концом всех проведенных хорд была точка В. Если, кривая относится ко II-му типу, то неизменным концом хорд будет точка А. Значит в формуле (1) b поменяется на а. Формула будет иметь вид:
Если на n-ом шаге, то считается, что необходимая точность е достигнута.
1.6. Уточнение корней методом касательных
При уточнении корней методом касательных все функции делятся на два типа, как и в методе хорд. Рассмотрим кривую I-го типа.
Проведем касательную к графику функции в точке В. Она пересечет ось ОХ в точке х1. Через эту точку проведем прямую перпендикулярную оси ОХ до пересечения с графиком функции. Получим точку А1 . Через неё опять проведем касательную. Получим точку х2 . Продолжая этот процесс, получим последовательность х1 , х2 , х3 , …,хn, сходящуюся к х * .
Уравнение касательной к графику функции F(x)=0 в точке х=b имеет вид . Т.к. эта касательная пересекает ось ОХ в точке (х1 , 0), то . Значит
Если, кривая относится ко II-му типу, то первую касательную к графику функции надо проводить в точке А и
Дальнейший расчет значений х2 , х3 , …,хn не зависит от типа кривой и в обоих случаях вычисляется по формуле
Если на n-ом шаге, то считается, что необходимая точность е достигнута.
1.7. Уточнение корней комбинированным методом хорд и касательных
Методы хорд и касательных дают приближение корня с разных сторон. Поэтому их часто применяют в сочетании друг с другом. В этом случае процесс уточнения корня идет быстрее.
Метод реализуется по следующей схеме:
1. По методу хорд находят первое приближение корня .
2. По методу касательных находят . Если кривая относится к I-му типу, то . Если ко II-му типу, то .
3. По методу хорд .
4. По методу касательных .
Шаги 3 и 4 повторяются до тех пор, пока . Как только можно считать корень найденным .
Лабораторная работа №1. Решение нелинейных уравнений с одной переменной.
1. Сделать программу отделения корней уравнения F(x)=0 на [a, b] с шагом 0,5.
2. Сделать программы уточнения корней уравнения F(x)=0 на одном из отрезков, полученных в первой программе с точностью 0,001.
a) Методом половинного деления;
a) Методом итерации;
c) Методом касательных;
d) Комбинированным методом хорд и касательных.
http://pandia.ru/text/77/276/87588.php
http://www.bestreferat.ru/referat-254350.html