Курсовая работа: Метод Ньютона для решения нелинейных уравнений
Название: Метод Ньютона для решения нелинейных уравнений Раздел: Рефераты по информатике Тип: курсовая работа Добавлен 01:06:49 13 декабря 2010 Похожие работы Просмотров: 3968 Комментариев: 22 Оценило: 5 человек Средний балл: 3.6 Оценка: неизвестно Скачать | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
k | x(k) | f(x(k)) | f’(x(k)) | | x(k+1) — x(k) | |
0 | 0. 565 | -4. 387 | -9. 982 | 0. 473 |
1 | 0. 092 | 0. 088 | -9. 818 | 0. 009 |
2 | 0. 101 | 0. 000 | -9. 800 | 0. 000 |
3 | 0. 101 |
Отсюда следует, что корень уравнения х = 0, 101.
Решить уравнение методом Ньютона.
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.
Теперь составим таблицу значений, для решения данного уравнения.
k | x(k) | f(x(k)) | f’(x(k)) | | x(k+1) — x(k) | |
0 | 2 | 0. 449 | 0. 361 | 1. 241 |
1 | -0. 265 | 0. 881 | 0. 881 | 0. 301 |
2 | -0. 021 | 0. 732 | 0. 732 | 0. 029 |
3 | 0. 000 | 0. 716 | 0. 716 | 0. 000 |
4 | 1. 089 |
Отсюда следует, что корень уравнения х = 1. 089.
Решить уравнение методом Ньютона.
Вычисления производить с точностью ε = 0, 001.
Вычислим первую производную функции.
Теперь вычислим вторую производную от функции.
Построим приближённый график данной функции.
Теперь, исходя из графика, возьмём первый приближённый корень и проверим условие (16) : f(x (0) ) * f’’(x (0) ) > 0.
Пусть x (0) = 1, тогда f(2)*f’’(2) = 0. 632 * 1, 632 = 1, 031 > 0,
Условие выполняется, значит берём x (0) = 1.
Теперь составим таблицу значений, для решения данного уравнения.
k | x(k) | f(x(k)) | f’(x(k)) | | x(k+1) — x(k) | |
0 | 1, 000 | 0, 632 | 2, 368 | 0, 267 |
1 | 0, 733 | 0, 057 | 1, 946 | 0, 029 |
2 | 0, 704 | 0, 001 | 1, 903 | 0, 001 |
3 | 0, 703 |
Отсюда следует, что корень уравнения х = 0, 703.
Решить уравнение методом Ньютона.
Вычислим первую производную функции.
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.
Теперь составим таблицу значений, для решения данного уравнения.
k | x(k) | f(x(k)) | f’(x(k)) | | x(k+1) — x(k) | |
0 | 1, 000 | -0. 066 | 0. 462 | 0. 143 |
1 | 1. 161 | -0. 007 | 0. 372 | 0. 018 |
2 | 1. 162 | 0. 0001. | 0. 363 | 0. 001 |
3 | 1. 162 |
Отсюда следует, что корень уравнения х = 1. 162.
Решить уравнение методом Ньютона.
Вычислим первую производную функции.
Теперь вычислим вторую производную от функции.
Построим приближённый график данной функции.
Теперь, исходя из графика, возьмём первый приближённый корень и проверим условие (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.
Теперь составим таблицу значений, для решения данного уравнения.
k | x(k) | f(x(k)) | f’(x(k)) | | x(k+1) — x(k) | |
0 | 1, 000 | 0, 350 | 3, 086 | 0, 114 |
1 | 0, 886 | 0, 013 | 2, 838 | 0, 005 |
2 | 0, 881 | 0, 001 | 2, 828 | 0, 000 |
3 | 0, 881 |
Отсюда следует, что корень уравнения х = 0, 881.
3.1 Описание программы
Данная программа создана для работы в текстовом и графическом режиме. Она состоит из модуля 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 – процедура, закрывающая графическую систему.
3.2 Тестирование программы
Для тестирования программы возьмем те примеры, которые решали в практической части работы, чтобы сверить результаты и проверить правильность работы программы.
1) sin x 2 + cosx 2 — 10x. = 0.
Данная программа вычисляет корни нелинейного уравнения методом Ньютона с точностью eps и чертит приблизительный график функции на отрезке [a, b].
Введите точность вычисления eps=0. 01
Корень уравнения, найденный методом Ньютона:
сделаем проверку, подставив полученный ответ в уравнение.
Получим : х=0, 0000002
2) cos x – e -x2/2 + x — 1 = 0.
Данная программа вычисляет корни нелинейного уравнения методом Ньютона с точностью eps и чертит приблизительный график функции на отрезке [a, b].
Введите точность вычисления eps=0. 001
Корень уравнения, найденный методом Ньютона:
сделаем проверку, подставив полученный ответ в уравнение.
Получим : х=-0, 0000000
Данная программа вычисляет корни нелинейного уравнения методом Ньютона с точностью eps и чертит приблизительный график функции на отрезке [a, b].
Введите точность вычисления eps=0. 01
Корень уравнения, найденный методом Ньютона:
сделаем проверку, подставив полученный ответ в уравнение.
Получим : х=0, 0000000
4) cos x –e -x/2 +x-1=0.
Данная программа вычисляет корни нелинейного уравнения методом Ньютона с точностью eps и чертит приблизительный график функции на отрезке [a, b].
Введите точность вычисления eps=0. 001
Корень уравнения, найденный методом Ньютона:
сделаем проверку, подставив полученный ответ в уравнение.
Получим : х=0, 0008180
Данная программа вычисляет корни нелинейного уравнения методом Ньютона с точностью eps и чертит приблизительный график функции на отрезке [a, b].
Введите точность вычисления eps=0. 001
Корень уравнения, найденный методом Ньютона:
Сделаем проверку, подставив полученный ответ в уравнение.
Получим : х=0, 0000000
Целью работы было создать программу, которая вычисляет корень нелинейного уравнения методом Ньютона. Исходя из этого, можно сделать вывод, что цель достигнута, так как для ее осуществления были решены следующие задачи:
1.Изучена необходимая литература.
2.Обзорно рассмотрены существующие методы по решению нелинейных уравнений.
3.Изучен метод Ньютона для решения нелинейных уравнений.
4.Рассмотрено решение нелинейных уравнений методом Ньютона на примере.
5.Проведены тестирование и отладка программы.
Список используемой литературы
1. Б.П. Демидович, И.А Марон. Основы вычислительной математики. – Москва, изд. «Наука»; 1970.
2. В.М. Вержбицкий. Численные методы (линейная алгебра и нелинейные уравнения). – Москва, «Высшая школа»; 2000.
3. Н.С.Бахвалов, А.В.Лапин, Е.В.Чижонков. Численные методы в задачах и упражнениях. – Москва, «Высшая школа»; 2000.
4. Мэтьюз, Джон, Г.,Финк, Куртис, Д. Численные методы MATLAB, 3-е издание.- Москва, «Вильяс»; 2001.
Нелинейные системы и уравнения
В более общем случае мы имеем не одно уравнение (1), а систему нелинейных уравнений $$ \begin
Метод Ньютона
Решение нелинейных уравнений
При итерационном решении уравнений (1), (3) задается некоторое начальное приближение, достаточно близкое к искомому решению \( x^* \). В одношаговых итерационных методах новое приближение \( x_
В итерационном методе Ньютона (методе касательных) для нового приближения имеем $$ \begin
Вычисления по (4) проводятся до тех пор, пока \( f(x_k) \) не станет близким к нулю. Более точно, до тех пор, пока \( |f_(x_k)| > \varepsilon \), где \( \varepsilon \) — малая величина.
Простейшая реализация метода Ньютона может выглядеть следующим образом:
Чтобы найти корень уравнения \( x^2 = 9 \) необходимо реализовать функции
Данная функция хорошо работает для приведенного примера. Однако, в общем случае могут возникать некоторые ошибки, которые нужно отлавливать. Например: пусть нужно решить уравнение \( \tanh(x) = 0 \), точное решение которого \( x = 0 \). Если \( |x_0| \leq 1.08 \), то метод сходится за шесть итераций.
Теперь зададим \( x_0 \) близким к \( 1.09 \). Возникнет переполнение
Возникнет деление на ноль, так как для \( x_7 = -126055892892.66042 \) значение \( \tanh(x_7) \) при машинном округлении равно \( 1.0 \) и поэтому \( f^\prime(x_7) = 1 — \tanh(x_7)^2 \) становится равной нулю в знаменателе.
Проблема заключается в том, что при таком начальном приближении метод Ньютона расходится.
Еще один недостаток функции naive_Newton заключается в том, что функция f(x) вызывается в два раза больше, чем необходимо.
Учитывая выше сказанное реализуем функцию с учетом следующего:
- обрабатывать деление на ноль
- задавать максимальное число итераций в случае расходимости метода
- убрать лишний вызов функции f(x)
Метод Ньютона сходится быстро, если начальное приближение близко к решению. Выбор начального приближение влияет не только на скорость сходимости, но и на сходимость вообще. Т.е. при неправильном выборе начального приближения метод Ньютона может расходиться. Неплохой стратегией в случае, когда начальное приближение далеко от точного решения, может быть использование нескольких итераций по методу бисекций, а затем использовать метод Ньютона.
При реализации метода Ньютона нужно знать аналитическое выражение для производной \( f^\prime(x) \). Python содержит пакет SymPy, который можно использовать для создания функции dfdx . Для нашей задачи это можно реализовать следующим образом:
Решение нелинейных систем
Идея метода Ньютона для приближенного решения системы (2) заключается в следующем: имея некоторое приближение \( \pmb
Таким образом, \( k \)-я итерация метода Ньютона состоит из двух стадий:
1. Решается система линейных уравнений (СЛАУ) \( \pmb
2. Находится значение вектора на следующей итерации \( \pmb
Для решения СЛАУ можно использовать приближенные методы. Можно также использовать метод Гаусса. Пакет numpy содержит модуль linalg , основанный на известной библиотеке LAPACK, в которой реализованы методы линейной алгебры. Инструкция x = numpy.linalg.solve(A, b) решает систему \( Ax = b \) методом Гаусса, реализованным в библиотеке LAPACK.
Когда система нелинейных уравнений возникает при решении задач для нелинейных уравнений в частных производных, матрица Якоби часто бывает разреженной. В этом случае целесообразно использовать специальные методы для разреженных матриц или итерационные методы.
Можно также воспользоваться методами, реализованными для систем линейных уравнений.
Численные методы решения нелинейных уравнений. Метод Ньютона для решения уравнений с одной переменной
Численные методы решения нелинейных уравнений. Метод Ньютона для решения уравнений с одной переменной
Метод Ньютона (также известный как метод касательных) — это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (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) будет определяться следующим выражением:
Метод секущих является двух шаговым, то есть новое приближение определяется двумя предыдущими итерациями и . В методе необходимо задавать два начальных приближения и . Скорость сходимости метода будет линейной.
Для того, чтобы добавить Ваш комментарий к статье, пожалуйста, зарегистрируйтесь на сайте.
http://slemeshevsky.github.io/num-mmf/snes/html/._snes-FlatUI001.html
http://simenergy.ru/math-analysis/solution-methods/45-method-newton-s