Разделы сайта
Выбор редакции:
- Крейсер "красный крым" черноморского флота
- «31 спорный вопрос» русской истории: житие императора Николая II
- Лечебные свойства корня лопуха и его широкое применение в домашних условиях
- Природные ресурсы западной сибири
- Совместимость петуха и змеи в любовных отношениях и браке Он петух она змея совместимость
- Чемерица черная: прекрасная и опасная Противопоказания и побочные действия
- Чем интересна Свято-Михайло-Афонская Закубанская пустынь?
- Порционная сельдь под шубой на праздничный стол
- К чему снится шить во сне
- Примета — разбить зеркало случайно: что делать, если оно треснуло
Реклама
Курсовая работа: Метод Ньютона для решения нелинейных уравнений. Методы решения нелинейных уравнений |
Метод Ньютона (метод касательных)Пусть корень уравнения f(x)=0 отделен на отрезке , причем первая и вторая производные f’(x) и f""(x) непрерывны и знакопостоянны при хÎ . Пусть на некотором шаге уточнения корня получено (выбрано) очередное приближение к корню х n . Тогда предположим, что следующее приближение, полученное с помощью поправки h n , приводит к точному значению корня x = х n + h n . (1.2.3-6) Считаяh n малой величиной, представим f(х n + h n) в виде ряда Тейлора, ограничиваясь линейными слагаемыми f(х n + h n) »f(х n) + h n f’(х n). (1.2.3-7) Учитывая, что f(x) = f(х n + h n) = 0, получим f(х n) + h n f ’(х n) » 0. Отсюда h n » - f(х n)/ f’(х n). Подставим значение h n в (1.2.3-6) и вместо точного значения корня x получим очередное приближение Формула (1.2.3-8) позволяет получить последовательность приближенийх 1 ,х 2 , х 3 …, которая при определенных условиях сходится к точному значению корняx, то есть Геометрическая интерпретация метода Ньютона
состоит в следующем
Расчетная формула метода Ньютона (1.2.3-8) может быть получена из геометрического построения. Так в прямоугольном треугольнике х 0 В 0 х 1 катет (1.2.3-9) (1.2.3-10) Эта формула совпадает с (1.2.3-8) для n-го приближения. Из рис.1.2.3-6 видно, что выбор в качестве начального приближения точки а может привести к тому, что следующее приближение х 1 окажется вне отрезка , на котором отделен корень x . В этом случае сходимость процесса не гарантирована. В общем случае выбор начального приближения производится в соответствии со следующим правилом: за начальное приближение следует принять такую точку х 0 Î,в которой f(х 0)×f’’(х 0)>0, то есть знаки функции и ее второй производной совпадают. Условия сходимости метода Ньютона сформулированы в следующей теореме. Если корень уравнения отделен на отрезке , причем f’(х 0)и f’’(х) отличны от нуля и сохраняют свои знаки при хÎ , то, если выбрать в качестве начального приближения такую точку х 0 Î, что f(х 0).f¢¢(х 0)>0, то корень уравнения f(x)=0может быть вычислен с любой степенью точности. Оценка погрешности метода Ньютона определяется следующим выражением: (1.2.3-11) где -- наименьшее значение при Процесс вычислений прекращается, если , где -- заданная точность. Кроме того, условием достижения заданной точности при уточнении корня методом Ньютона могут служить следующие выражения: Схема алгоритма метода Ньютона приведена на рис. 1.2.3-7. Левая часть исходного уравнения f(x) и ее производная f’(x)в алгоритме оформлены в виде отдельных программных модулей. Рис. 1.2.3-7. Схема алгоритма метода Ньютона Пример 1.2.3-3.Уточнить методом Ньютона корни уравнения x-ln(x+2) = 0при условии, что корни этого уравнения отделены на отрезках x 1 Î[-1.9;-1.1] и x 2 Î [-0.9;2]. Первая производная f’(x) = 1 – 1/(x+2) сохраняет свой знак на каждом из отрезков: f’(x)<0 при хÎ [-1.9; -1.1], f’(x)>0 при хÎ [-0.9; 2]. Вторая производная f"(x) = 1/(x+2) 2 > 0 при любых х. Таким образом, условия сходимости выполняются. Поскольку f""(x)>0на всей области допустимых значений, то для уточнения корня за начальное приближение x 1 выберем х 0 =-1,9(так какf(-1,9)×f”(-1.9)>0). Получим последовательность приближений: Продолжая вычисления, получим следующую последовательность первых четырех приближений: -1.9; –1.8552, -1.8421; -1.8414. Значение функции f(x) в точке x=-1.8414 равно f(-1.8414)=-0.00003. Для уточнения корня x 2 Î[-0.9;2] выберем в качестве начального приближениях 0 =2 (f(2)×f”(2)>0). Исходя из х 0 = 2, получим последовательность приближений: 2.0;1.1817; 1.1462; 1.1461. Значение функции f(x) в точке x=1.1461 равно f(1.1461)= -0.00006. Метод Ньютона обладает высокой скоростью сходимости, однако на каждом шаге он требует вычисления не только значения функции, но и ее производной. Метод хорд Геометрическая интерпретация метода хорд
состоит в следующем Проведем отрезок прямой через точки A и B. Очередное приближение x 1 является абсциссой точки пересечения хорды с осью 0х. Построим уравнение отрезка прямой: Положим y=0и найдем значение х=х 1 (очередное приближение): Повторим процесс вычислений для получения очередного приближения к корню - х 2 : В нашем случае (рис.1.2.11) и расчетная формула метода хорд будет иметь вид Эта формула справедлива, когда за неподвижную точку принимается точка b, а в качестве начального приближения выступает точка a. Рассмотрим другой случай (рис. 1.2.3-9), когда . Уравнение прямой для этого случая имеет вид Очередное приближение х 1 при y = 0 Тогда рекуррентная формула метода хорд для этого случая имеет вид Следует отметить, что за неподвижную точку в методе хорд выбирают тот конец отрезка , для которого выполняется условие f (x)∙f¢¢ (x)>0. Таким образом, если за неподвижную точку приняли точку а, то в качестве начального приближения выступает х 0 = b, и наоборот. Достаточные условия, которые обеспечивают вычисление корня уравнения f(x)=0 по формуле хорд, будут теми же, что и для метода касательных (метод Ньютона), только вместо начального приближения выбирается неподвижная точка. Метод хорд является модификацией метода Ньютона. Разница состоит в том, что в качестве очередного приближения в методе Ньютона выступает точка пересечения касательной с осью 0Х,а в методе хорд – точка пересечения хорды с осью 0Х – приближения сходятся к корню с разных сторон. Оценка погрешности метода хорд определяется выражением (1.2.3-15) Условие окончания процесса итераций по методу хорд (1.2.3-16) В случае, если M 1 <2m 1 , то для оценки погрешности метода может быть использована формула | x n -x n -1 |£e. Пример 1.2.3-4. Уточнить корень уравнения e x – 3x = 0, отделенный на отрезке с точностью 10 -4 . Проверим условие сходимости: Следовательно, за неподвижную точку следует выбрать а=0, а в качестве начального приближения принять х 0 =1, поскольку f(0)=1>0 и f(0)*f"(0)>0. Метод Ньютона (также известный как метод касательных) - это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (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 0) в точке x 0 . В соответствии с данным методом расчета приближенное значение корня определяется по следующей формуле: Модифицированный метод Ньютона Разностный метод Ньютона В результате приближенное значение корня функции f(x) будет определяться выражением разностного метода Ньютона: Двух шаговый метод Ньютона В соответствии с методом Ньютона требуется вычислять производную функции f(x) на каждом шаге итерации, что не всегда удобно, а иногда практически невозможно. Данный способ позволяет производную функции заменить разностным отношением (приближенным значением): В результате приближенное значение корня функции f(x) будет определяться следующим выражением: где Рис.5 . Двух шаговый метод Ньютона Метод секущих является двух шаговым, то есть новое приближение определяется двумя предыдущими итерациями и . В методе необходимо задавать два начальных приближения и . Скорость сходимости метода будет линейной.
Для того, чтобы добавить Ваш комментарий к статье, пожалуйста, зарегистрируйтесь на сайте. | ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ «Приднестровский государственный университет им. Т.Г. Шевченко» Рыбницкий филиал Кафедра физики, математики и информатики Курсовая работа по дисциплине: «Практикум по решению задач на ЭВМ» «Метод Ньютона для решения нелинейных уравнений» Выполнила: студентка III курса; 330 й группы специальности: «Информатика с доп. специальностью английский Нистор А. Г.. Проверила: преподаватель Панченко Т. А. Внедрение ЭВМ во все сферы человеческой деятельности требует от специалистов разного профиля овладения навыками использования вычислительной техники. Повышается уровень подготовки студентов вузов, которые уже с первых курсов приобщаются к использованию ЭВМ и простейших численных методов, не говоря уже о том, при что выполнении курсовых и дипломных проектов применение вычислительной техники становится нормой в подавляющем большинстве вузов. Вычислительная техника используется сейчас не только в инженерных расчетах и экономических науках, но и таких традиционно нематематических специальностях, как медицина, лингвистика, психология. В связи с этим можно констатировать, что применение ЭВМ приобрело массовый характер. Возникла многочисленная категория специалистов - пользователей ЭВМ, которым необходимы знания по применению ЭВМ в своей отрасли - навыки работы с уже имеющимся программным обеспечением, а также создания своего собственного программного обеспечения, приспособленного для решения конкретной задачи. И здесь на помощь пользователю приходят описания языков программирования высокого уровня и численные методы. Численные методы разрабатывают и исследуют, как правило, высококвалифицированные специалисты-математики. Для большинства пользователей главной задачей является понимание основных идей и методов, особенностей и областей применения. Однако, пользователи хотят работать с ЭВМ не только как с высокоинтеллектуальным калькулятором, а еще и как с помощником в повседневной работе, хранилищем информации с быстрым и упорядоченным доступом, а так же с источником и обработчиком графической информации. Все эти функции современной ЭВМ я предполагаю продемонстрировать в настоящей курсовой работе. Цели и задачи.Целью данной курсовой работы является изучение и реализация в программном продукте решения нелинейных уравнений при помощи метода Ньютона. Данная работа состоит из трёх разделов, заключения и приложения. Первый раздел - теоретический и содержит общие сведения о методе Ньютона. Второй – это практическая часть. Здесь описывается метод Ньютона разобранный на конкретных примерах. Третий посвящён тестированию программы и анализу получившихся результатов. В заключении представлен вывод о проделанной работе. Цельюданной курсовой работы является программная реализация метода Ньютона для решения нелинейных уравнений. Для этого необходимо выполнить следующие задачи: 1. Изучить необходимую литературу. 2. Обзорно рассмотреть существующие методы по решению нелинейных уравнений. 3. Изучить метод Ньютона для решения нелинейных уравнений. 4. Рассмотреть решение нелинейных уравнений методом Ньютона на конкретных примерах. 5. Разработать программу для решения нелинейных уравнений методом Ньютона. 6. Проанализировать получившиеся результаты. Рассмотрим задачу нахождения корней нелинейного уравнения Корнями уравнения (1) называются такие значения х, которые при подстановке обращают его в тождество. Только для простейших уравнений удается найти решение в виде формул, т.е. аналитическом виде. Чаще приходится решать уравнения приближенными методами, наибольшее распространение среди которых, в связи с появлением компьютеров, получили численные методы. Алгоритм нахождения корней приближенными методами можно разбить на два этапа. На первом изучается расположение корней и проводится их разделение. Находится область , в которой существует корень уравнения или начальное приближение к корню x 0 . Простейший способ решения этой задачи является исследование графика функции f(x) . В общем же случае для её решения необходимо привлекать все средства математического анализа. Существование на найденном отрезке , по крайней мере, одного корня уравнения (1) следует из условия Больцано: f(a)*f(b)<0 (2) При этом подразумевается, что функция f(x) непрерывна на данном отрезке. Однако данное условие не отвечает на вопрос о количестве корней уравнения на заданном отрезке . Если же требование непрерывности функции дополнить ещё требованием её монотонности, а это следует из знакопостоянства первой производной , то можно утверждать о существовании единственного корня на заданном отрезке. При локализации корней важно так же знание основных свойств данного типа уравнения. К примеру, напомним, некоторые свойства алгебраических уравнений: где вещественные коэффициенты. а) Уравнение степени n имеет n корней, среди которых могут быть как вещественные, так и комплексные. Комплексные корни образуют комплексно-сопряженные пары и, следовательно, уравнение имеет четное число таких корней. При нечетном значении n имеется, по меньшей мере, один вещественный корень. б) Число положительных вещественных корней меньше или равно числа переменных знаков в последовательности коэффициентов . Замена х на –х в уравнении (3) позволяет таким же способом оценить число отрицательных корней. На втором этапе решения уравнения (1), используя полученное начальное приближение, строится итерационный процесс, позволяющий уточнять значение корня с некоторой, наперед заданной точностью . Итерационный процесс состоит в последовательном уточнении начального приближения. Каждый такой шаг называется итерацией. В результате процесса итерации находится последовательность приближенных значений корней уравнения . Если эта последовательность с ростом n приближается к истинному значению корня x , то итерационный процесс сходится. Говорят, что итерационный процесс сходится, по меньшей мере, с порядком m, если выполнено условие: , (4) где С>0 некоторая константа. Если m=1 , то говорят о сходимости первого порядка; m=2 - о квадратичной, m=3 - о кубической сходимостях. Итерационные циклы заканчиваются, если при заданной допустимой погрешности выполняются критерии по абсолютным или относительным отклонениям: или малости невязки: Эта работа посвящена изучению алгоритма решения нелинейных уравнений с помощью метода Ньютона. 1.1 Обзор существующих методов решения нелинейных уравненийСуществует много различных методов решения нелинейных уравнений, некоторые из них представлены ниже: 1)Метод итераций . При решении нелинейного уравнения методом итераций воспользуемся записью уравнения в виде x=f(x). Задаются начальное значение аргумента x 0 и точность ε. Первое приближение решения x 1 находим из выражения x 1 =f(x 0), второе - x 2 =f(x 1) и т.д. В общем случае i+1 приближение найдем по формуле xi+1 =f(xi). Указанную процедуру повторяем пока |f(xi)|>ε. Условие сходимости метода итераций |f"(x)|<1. 2)Метод Ньютона . При решении нелинейного уравнения методом Ньтона задаются начальное значение аргумента x 0 и точность ε. Затем в точке(x 0 ,F(x 0)) проводим касательную к графику F(x) и определяем точку пересечения касательной с осью абсцисс x 1 . В точке (x 1 ,F(x 1)) снова строим касательную, находим следующее приближение искомого решения x 2 и т.д. Указанную процедуру повторяем пока |F(xi)| > ε. Для определения точки пересечения (i+1) касательной с осью абсцисс воспользуемся следующей формулой x i+1 =x i -F(x i)\ F’(x i). Условие сходимости метода касательных F(x 0)∙F""(x)>0, и др. 3). Метод дихотомии. Методика решения сводится к постепенному делению начального интервала неопределённости пополам по формуле С к =а к +в к /2. Для того чтобы выбрать из двух получившихся отрезков необходимый, надо находить значение функции на концах получившихся отрезков и рассматривать тот на котором функция будет менять свой знак, то есть должно выполняться условие f (а к)* f (в к)<0. Процесс деления отрезка проводится до тех пор, пока длина текущего интервала неопределённости не будет меньше заданной точности, то есть в к – а к < E. Тогда в качестве приближенного решения уравнения будет точка, соответствующая середине интервала неопределённости. 4). Метод хорд . Идея метода состоит в том, что на отрезке строится хорда стягивающая концы дуги графика функции y=f(x), а точка c, пересечения хорды с осью абсцисс, считается приближенным значением корня c = a - (f(a)Ч (a-b)) / (f(a) - f(b)), c = b - (f(b)Ч (a-b)) / (f(a) - f(b)). Следующее приближение ищется на интервале или в зависимости от знаков значений функции в точках a,b,c x* О , если f(с)Ч f(а) > 0 ; x* О , если f(c)Ч f(b) < 0 . Если f"(x) не меняет знак на , то обозначая c=x 1 и считая начальным приближением a или b получим итерационные формулы метода хорд с закрепленной правой или левой точкой. x 0 =a, x i+1 = x i - f(x i)(b-x i) / (f(b)-f(x i), при f "(x)Ч f "(x) > 0 ; x 0 =b, x i+1 = x i - f(x i)(x i -a) / (f(x i)-f(a), при f "(x)Ч f "(x) < 0 . Сходимость метода хорд линейная. 1.2 Алгоритм метода НьютонаПостроим эффективный алгоритм вычисления корней уравнения. Пусть задано начальное приближение . Вычислим в этой точке значение функции и её производной . Рассмотрим графическую иллюстрацию метода: . (8) Продолжая этот процесс, получим известную формулу Ньютона: (9) Приведем простейшую рекурсивную подпрограмму-функцию: function X_Newt(x,eps:real):real; y:=x-f(x)/f1(x); if abs(f(x)) > eps then X_Newt:=X_Newt(y,eps) Метод Ньютона (касательных) характеризуется квадратичной скоростью сходимости, т.е. на каждой итерации удваивается число верных знаков. Однако этот метод не всегда приводит к нужному результату. Рассмотрим этот вопрос подробнее. Преобразуем уравнение (1) к эквивалентному уравнению вида: В случае метода касательных . Если известно начальное приближение к корню x=x 0 , то следующее приближение найдем из уравнения x 1 =g(x 0), далее x 2 =g(x 1),... Продолжая этот процесс, получим рекуррентную формулу метода простой итерации x k+1 =g(x k) (11) Итерационный процесс продолжается до тех пор, пока не будут выполнены условия (5-7). Всегда ли описанный вычислительный процесс приводит к искомому решению? При каких условиях он будет сходящимся? Для ответа на эти вопросы опять обратимся к геометрической иллюстрации метода. Корень уравнения представляется точкой пересечения функций y=x и y=g(x). Как видно из рис. 3(а), если выполняется условие , то процесс сходится, иначе – расходится (рис3(б)). Итак, для того чтобы итерационный процесс был сходящимся и приводил к искомому результату, требуется выполнение условия: Переход от уравнения f(x)=0 к уравнению х=g(x) можно осуществлять различными способами. При этом важно, чтобы выбранная функция g(x) удовлетворяла условию (12). К примеру, если функцию f(x) умножить на произвольную константу q и добавить к обеим частям уравнения (1) переменную х, то g(x)=q*f(x)+x . Выберем константу q такой, чтобы скорость сходимости алгоритма была самой высокой. Если 1 Метод Ньютона обладает высокой скоростью сходимости, однако он не всегда сходится. Условие сходимости , где g(x) = x – f(x)/ f’(x), сводится к требованию . В практических расчетах важно выбирать начальное значение как можно ближе к искомому значению, а в программе устанавливать «предохранитель от зацикливания». Недостатком метода является и то, что на каждом шаге необходимо вычислять не только функцию, но и ее производную. Это не всегда удобно. Одна из модификаций метода Ньютона - вычисление производной только на первой итерации: (13) Другой метод модификации – замена производной конечной разностью (14) Тогда (15) Геометрический смысл такого изменения алгоритма Ньютона состоит в том, что от касательной мы приходим к секущей. Метод секущих уступает методу Ньютона в скорости сходимости, но не требует вычисления производной. Заметим, что начальные приближения в методе секущих могут располагаться как с разных сторон от корня, так и с одной стороны. Запишем в общем виде алгоритм метода Ньютона. 1. Задать начальное приближение х (0)
так, чтобы выполнилось условие f(x (0))*f’’(x (0))>0. (16) Задать малое положительное число ε , как точность вычислений. Положить к = 0. 2. Вычислить х (к+1)
по формуле (9) : . 3. Если | x (k+1)
- x (k)
| < ε, то процесс вычисления прекратить и положить х* = x (k+1)
.
Иначе увеличить к на 1 (к = к + 1) и перейти к пункту 2. Решим вручную несколько нелинейных уравнений методом Ньютона, а потом сверим результаты с теми, которые получатся при реализации программного продукта. Пример 1
sin x 2
+ cosx 2
- 10x. = 0. F’(x)=2x cosx 2
- 2x sinx 2
- 10. F’’(x)=2cosx 2
- 4x 2
sinx 2
- 2sinx 2
- 4x 2
cosx 2
= cosx 2
(2-4x 2) - sinx 2
(2+4x 2). Теперь, исходя из графика, возьмём первый приближённый корень и проверим условие (16) : f(x (0)) * f’’(x (0)) > 0. Пусть x (0)
= 0, 565, тогда f(0. 565)*f’’(0. 565) = -4. 387 * (-0. 342) = 1. 5 > 0, Условие выполняется, значит берём x (0)
= 0, 565. Отсюда следует, что корень уравнения х = 0, 101. Пример 2
Решить уравнение методом Ньютона. cos x – e -x2/2
+ x - 1 = 0 Вычисления производить с точностью ε = 0, 001. Вычислим первую производную функции. F’(x) = 1 – sin x + x*e -x2/2
. Теперь вычислим вторую производную от функции. F’’(x) = e -x2/2
*(1-x 2) – cos x. Построим приближённый график данной функции. Теперь, исходя из графика, возьмём первый приближённый корень и проверим условие (16) : f(x (0)) * f’’(x (0)) > 0. Пусть x (0)
= 2, тогда f(2)*f’’(2) = 0. 449 * 0. 010 = 0.05 > 0, Условие выполняется, значит берём x (0)
= 2. Теперь составим таблицу значений, для решения данного уравнения. Отсюда следует, что корень уравнения х = 1. 089. Пример 3
Решить уравнение методом Ньютона. Вычисления производить с точностью ε = 0, 001. Вычислим первую производную функции. F’(x) = 2*x + e -x
. Теперь вычислим вторую производную от функции. F’’(x) = 2 - e -x
. Построим приближённый график данной функции. Теперь, исходя из графика, возьмём первый приближённый корень и проверим условие (16) : f(x (0)) * f’’(x (0)) > 0. Пусть x (0)
= 1, тогда f(2)*f’’(2) = 0. 632 * 1, 632 = 1, 031 > 0, Теперь составим таблицу значений, для решения данного уравнения. Отсюда следует, что корень уравнения х = 0, 703. Решить уравнение методом Ньютона. cos x –e -x/2
+x-1=0. Вычислим первую производную функции. F’(x) = -sin x + e -x/2
/2+1. Теперь вычислим вторую производную от функции. F’’(x) = -cos x - e -x/2
/4. Построим приближённый график данной функции. Теперь, исходя из графика, возьмём первый приближённый корень и проверим условие (16) : f(x (0)) * f’’(x (0)) > 0. Пусть x (0)
= 1, тогда f(2)*f’’(2) = -0. 066 * (-0. 692) = 0. 046 > 0, Условие выполняется, значит берём x (0)
= 1. Теперь составим таблицу значений, для решения данного уравнения. Отсюда следует, что корень уравнения х = 1. 162. Пример 5
Решить уравнение методом Ньютона. 2+e x
- e -x
=0. Вычислим первую производную функции. F’(x) = e x
+e -x
. Теперь вычислим вторую производную от функции. F’’(x) = e x
-e -x
. Построим приближённый график данной функции. Теперь, исходя из графика, возьмём первый приближённый корень и проверим условие (16) : f(x (0)) * f’’(x (0)) > 0. Пусть x (0)
= 1, тогда f(2)*f’’(2) = 0. 350 * 2, 350 = 0. 823 > 0, Условие выполняется, значит берём x (0)
= 1. Теперь составим таблицу значений, для решения данного уравнения. Отсюда следует, что корень уравнения х = 0, 881. Данная программа создана для работы в текстовом и графическом режиме. Она состоит из модуля Graph, Crt, трёх функций и трёх процедур. 1. модуль Crt предназначен для обеспечения контроля над текстовыми режимами экрана, расширенными кодами клавиатуры, цветами, окнами и звуком; 2. модуль Graph предназначен для обеспечения контроля над графическими объектами; 3. procedure GrafInit - инициализирует графический режим; 4. function VF – вычисляет значение функции; 5. function f1 – вычисляет значение первой производной функции; 6. function X_Newt – реализует алгоритм решения уравнения методом Ньютона. 7. procedure FGraf – реализует построение графика заданной функции f(x); Ots=35 - константа, определяющая количество точек для отступа от границ монитора; fmin, fmax – максимальные и минимальные значения функции; SetColor(4) – процедура, которая устанавливает текущий цвет графического объекта, используя палитру, в данном случае это красный цвет; SetBkColor(9) – процедура, которая устанавливает текущий цвет фона, используя палитру, в данном случае – это светло-синий цвет. 8. Procedure MaxMinF – вычислят максимальные и минимальные значения функции f(x). Line – процедура, которая рисует линию из точки с координатами (x1, у1) в точку с координатами (х2, у2); MoveTo – процедура, перемещающая указатель (СР) в точку с координатами (х, у); TextColor(5) – процедура, устанавливающая текущий цвет символов, в данном случае – это розовый; Outtexty(х, у, ‘строка’) – процедура, которая выводит строку, начиная с позиции (х, у) CloseGraph – процедура, закрывающая графическую систему. Для тестирования программы возьмем те примеры, которые решали в практической части работы, чтобы сверить результаты и проверить правильность работы программы. 1) sin x 2
+ cosx 2
- 10x. = 0. Введите а = -1 Введите b=1 = [-1, 1] {вывод графика функции} Получим: х=0, 0000002 2) cos x – e -x2/2
+ x - 1 = 0. Данная программа вычисляет корни нелинейного уравнения методом Ньютона с точностью eps и чертит приблизительный график функции на отрезке . Введите а = -3 Введите b=3 = [-3, 3] {вывод графика функции} Корень уравнения, найденный методом Ньютона: сделаем проверку, подставив полученный ответ в уравнение. Получим: х=-0, 0000000 3) x 2
- e -x
= 0. Данная программа вычисляет корни нелинейного уравнения методом Ньютона с точностью eps и чертит приблизительный график функции на отрезке . Введите а = -1 Введите b=1 = [-1, 1] Введите точность вычисления eps=0. 01 {вывод графика функции} Корень уравнения, найденный методом Ньютона: сделаем проверку, подставив полученный ответ в уравнение. Получим: х=0, 0000000 4) cos x –e -x/2
+x-1=0. Данная программа вычисляет корни нелинейного уравнения методом Ньютона с точностью eps и чертит приблизительный график функции на отрезке . Введите а = -1,5 Введите b=1,5 = [-1,5, 1,5 ] Введите точность вычисления eps=0. 001 {вывод графика функции} Корень уравнения, найденный методом Ньютона: сделаем проверку, подставив полученный ответ в уравнение. Получим: х=0, 0008180 5) -2+e x
- e -x
=0. Данная программа вычисляет корни нелинейного уравнения методом Ньютона с точностью eps и чертит приблизительный график функции на отрезке . Введите а = -0,9 Введите b=0,9 = [-0,9, 0,9] Введите точность вычисления eps=0. 001 {вывод графика функции} Корень уравнения, найденный методом Ньютона: Сделаем проверку, подставив полученный ответ в уравнение. Целью работы было создать программу, которая вычисляет корень нелинейного уравнения методом Ньютона. Исходя из этого, можно сделать вывод, что цель достигнута, так как для ее осуществления были решены следующие задачи: 1.Изучена необходимая литература. 2.Обзорно рассмотрены существующие методы по решению нелинейных уравнений. 3.Изучен метод Ньютона для решения нелинейных уравнений. 4.Рассмотрено решение нелинейных уравнений методом Ньютона на примере. 5.Проведены тестирование и отладка программы. 1. Б.П. Демидович, И.А Марон. Основы вычислительной математики. – Москва, изд. «Наука»; 1970. 2. В.М. Вержбицкий. Численные методы (линейная алгебра и нелинейные уравнения). – Москва, «Высшая школа»; 2000. 3. Н.С.Бахвалов, А.В.Лапин, Е.В.Чижонков. Численные методы в задачах и упражнениях. – Москва, «Высшая школа»; 2000. 4. Мэтьюз, Джон, Г.,Финк, Куртис, Д. Численные методы MATLAB, 3-е издание.- Москва, «Вильяс»; 2001. |
Читайте: |
---|
Новое
- «31 спорный вопрос» русской истории: житие императора Николая II
- Лечебные свойства корня лопуха и его широкое применение в домашних условиях
- Природные ресурсы западной сибири
- Совместимость петуха и змеи в любовных отношениях и браке Он петух она змея совместимость
- Чемерица черная: прекрасная и опасная Противопоказания и побочные действия
- Чем интересна Свято-Михайло-Афонская Закубанская пустынь?
- Порционная сельдь под шубой на праздничный стол
- К чему снится шить во сне
- Примета — разбить зеркало случайно: что делать, если оно треснуло
- Самостоятельные заговоры на удачу и деньги