Нахождение корней уравнения методом Ньютона (ЛИСП-реализация) (47718)

Посмотреть архив целиком

СОДЕРЖАНИЕ


Введение

1. Постановка задачи

2. Математические и алгоритмические основы решения задачи

2.1 Описание метода

2.2 Недостатки метода

3. Функциональные модели и блок-схемы решения задачи

4. Программная реализация решения задачи

5. Пример выполнения программы

Заключение

Список использованных источников и литературы



ВВЕДЕНИЕ


Метод Ньютона (также известный как метод касательных)— это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643—1727), под именем которого и обрёл свою известность.

Метод был описан Исааком Ньютоном в рукописи De analysi per aequationes numero terminorum infinitas (лат.Об анализе уравнениями бесконечных рядов), адресованной в 1669 году Барроу, и в работе De metodis fluxionum et serierum infinitarum (лат.Метод флюксий и бесконечные ряды) или Geometria analytica (лат.Аналитическая геометрия) в собраниях трудов Ньютона, которая была написана в 1671 году. В своих работах Ньютон вводит такие понятия, как разложение функции в ряд, бесконечно малые и флюксии (производные в нынешнем понимании). Указанные работы были изданы значительно позднее: первая вышла в свет в 1711 году благодаря Уильяму Джонсону, вторая была издана Джоном Кользоном в 1736 году уже после смерти создателя. Однако описание метода существенно отличалось от его нынешнего изложения: Ньютон применял свой метод исключительно к полиномам. Он вычислял не последовательные приближения xn, а последовательность полиномов и в результате получал приближённое решение x.

Впервые метод был опубликован в трактате Алгебра Джона Валлиса в 1685 году, по просьбе которого он был кратко описан самим Ньютоном. В 1690 году Джозеф Рафсон опубликовал упрощённое описание в работе Analysis aequationum universalis (лат.Общий анализ уравнений). Рафсон рассматривал метод Ньютона как чисто алгебраический и ограничил его применение полиномами, однако при этом он описал метод на основе последовательных приближений xn вместо более трудной для понимания последовательности полиномов, использованной Ньютоном. Наконец, в 1740 году метод Ньютона был описан Томасом Симпсоном как итеративный метод первого порядка решения нелинейных уравнений с использованием производной в том виде, в котором он излагается здесь. В той же публикации Симпсон обобщил метод на случай системы из двух уравнений и отметил, что метод Ньютона также может быть применён для решения задач оптимизации путём нахождения нуля производной или градиента.

В 1879 году Артур Кэли в работе The Newton-Fourier imaginary problem (англ. Проблема комплексных чисел Ньютона-Фурье) был первым, кто отметил трудности в обобщении метода Ньютона на случай мнимых корней полиномов степени выше второй и комплексных начальных приближений. Эта работа открыла путь к изучению теории фракталов.

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



1. Постановка задачи


Дано уравнение:


.


Требуется решить это уравнение, точнее, найти один из его корней (предполагается, что корень существует). Предполагается, что F(X) непрерывна и дифференцируема на отрезке [A;B].

Входным параметром алгоритма, кроме функции F(X), является также начальное приближение - некоторое X0, от которого алгоритм начинает идти.

Пусть уже вычислено Xi, вычислим Xi+1 следующим образом. Проведём касательную к графику функции F(X) в точке X = Xi, и найдём точку пересечения этой касательной с осью абсцисс. Xi+1 положим равным найденной точке, и повторим весь процесс с начала.

Нетрудно получить следующее выражение:


Xi+1 = Xi - F(Xi) / F'(Xi)


Интуитивно ясно, что если функция F(X) достаточно "хорошая", а Xi находится достаточно близко от корня, то Xi+1 будет находиться ещё ближе к искомому корню.

Пример 1.

Требуется найти корень уравнения , с точностью .

Производная функции равна


.



Возьмем за начальную точку , тогда


-9.716215;

5.74015;

3.401863;

-2.277028;

1.085197;

0.766033;

0.739241.


Таким образом, корень уравнения


равен 0.739241.


Пример 2.

Найдем корень уравнения функции методом Ньютона


cosx = x3.


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



f(x) = cosx − x3.


Имеем выражение для производной


.


Так как для всех x и x3 > 1 для x > 1, очевидно, что решение лежит между 0 и 1. Возьмём в качестве начального приближения значение x0= 0.5, тогда:


1.112141;

0.90967;

0.867263;

0.865477;

0.865474033111;

0.865474033102.


Таким образом, корень уравнения функции


cosx = x3 равен 0.86547403.


Пример 3.

Требуется найти корень уравнения , с точностью .

Производная функции


равна .


Возьмем за начальную точку , тогда


-2.3;

-2.034615;

-2.000579;

-2.0.


Таким образом, корень уравнения


равен -2.



2. Математические и алгоритмические основы решения задачи


2.1 Описание метода


Пусть корень x уравнения отделен на отрезке [a, b], причем и непрерывны и сохраняют определенные знаки при . Если на некотором произвольном шаге n найдено приближенное значение корня


,


то можно уточнить это значение по методу Ньютона. Положим


, (1)


где считаем малой величиной. Применяя формулу Тейлора, получим:


.


Следовательно,


.


Внеся эту поправку в формулу (1), найдем следующее (по порядку) приближение корня



. (2)


Геометрически метод Ньютона эквивалентен замене дуги кривой касательной, проведенной в некоторой точке кривой. В самом деле, положим для определенности, что при и (рисунок 1).

Выберем, например, , для которого . Проведем касательную к кривой в точке B0 с координатами .


Рисунок 1. Геометрически показан метод Ньютона


В качестве первого приближения корня x возьмем абсциссу точки пересечения касательной с осью Ox. Через точку снова проведем касательную, абсцисса точки пересечения которой даст второе приближение корня x и т.д.

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

Имеем



.


Так как угол a образован касательной и осью абсцисс, его тангенс численно равен величине производной, вычисленной в точке, соответствующей абсциссе точки касания, т.е.


.


Тогда



или для любого шага n


.


В качестве начальной точки можно принять либо один из концов отрезка [a, b], либо точку внутри этого интервала. В первом случае рекомендуется выбирать ту границу, где выполняется условие


,


т.е. функция и ее вторая производная в точке должны быть одного знака.

В качестве простейших условий окончания процедуры уточнения корня рекомендуется выполнение условия


.


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


.


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


2.2 Недостатки метода


Пусть


.


Тогда


.


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


Рисунок 2. Иллюстрация расхождения метода Ньютона, примененного к функции с начальным приближением в точке


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

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

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

Пусть


.


Тогда и следовательно . Таким образом сходимость метода не квадратичная, а линейная, хотя функция всюду бесконечно дифференцируема.



3. Функциональные модели и блок-схемы решения задачи


Функциональные модели и блок-схемы решения задачи представлены на рисунке 3, 4.

Условные обозначения:

  • FUNCTN, FX – функция;

  • DFUNCTN, DFDX – производная функции;

  • A – рабочая переменная;

  • START, X0 – начальное значение;

  • PRES, E –точность вычисления.


Рисунок 3 – Функциональная модель решения задачи для поиска корня уравнения методом Ньютона


Случайные файлы

Файл
28143.rtf
117236.rtf
30399-1.rtf
13841-1.rtf
28660.rtf




Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.