Экономическое обоснование инвестиционного проекта на базе 'Донецкого металлургического завода'
СОДЕРЖАНИЕ
Введение
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 –
Функциональная модель решения задачи для поиска корня уравнения методом Ньютона
Рисунок 4 – Блок-схема
решения задачи для функции NEWTOM
4. Программная реализация
решения задачи
Файл FUNCTION.txt (Пример 1)
;ФУНКЦИЯ
COSX - X3
(DEFUN F(X)
(- (COS X) (* X X X))
)
;ПРОИЗВОДНАЯ
-sinx-3x2
(DEFUN DFDX (X)
(- (* -1 (SIN X)) (* 3 X X))
)
(SETQ X0 0.5)
(SETQ E 0.0001)
Файл FUNCTION.txt (Пример 2)
;ФУНКЦИЯ x-cosx
(- X (COS X))
)
;ПРОИЗВОДНАЯ 1+sinx
(DEFUN DFDX (X)
(+ 1 (SIN X))
)
(SETQ X0 -1)
(SETQ E 0.0001)
Файл FUNCTION.txt (Пример 3)
;ФУНКЦИЯ
X2+2X
(DEFUN F(X)
(+ (* X X) (* 2 X))
)
;ПРОИЗВОДНАЯ
2X+2
(DEFUN
DFDX (X)
(+ 2 (* 2 X))
)
(SETQ X0 -2.3)
(SETQ E 0.0001)
Файл NEWTON.txt
;ПОДГРУЖАЕМ ФУНКЦИЮ
(LOAD "D:\\FUNCTION.TXT" )
;РЕАЛИЗАЦИЯ МЕТОДА
НЬЮТОНА
(DEFUN NEWTOM (START PRES FUNCTN DFUNCTN)
;ОБЪЯВЛЕНИЕ
ПЕРЕМЕННЫХ
(DECLARE
(SPECIAL X))
(DECLARE
(SPECIAL A))
;ЗАДАЕМ
НАЧАЛЬНОЕ ЗНАЧЕНИЕ
(SETQ X START)
(SETQ A (/ (FUNCALL FUNCTN X) (FUNCALL DFUNCTN X)))
(LOOP
(SETQ X (- X A))
(SETQ A (/ (FUNCALL FUNCTN X) (FUNCALL DFUNCTN X)))
;ЕСЛИ
ДОСТИГЛИ ТРЕБУЕМОЙ ТОЧНОСТИ ВЫХОДИМ ИЗ ЦИКЛА
(IF (<= (ABS A) PRES) (RETURN X))
)
)
;ОТКРЫВАЕМ ФАЙЛ
(SETQ OUTPUT_STREAM (OPEN "D:\KOREN.TXT" :DIRECTION :OUTPUT))
;ВЫЗЫВАЕМ
МЕТОД НЬЮТОНА ДЛЯ РАСЧЕТА КОРНЯ
(SETQ KOREN (NEWTOM X0 E (FUNCTION F) (FUNCTION DFDX)))
;ВЫВОДИМ КОРЕНЬ
В ФАЙЛ
(PRINT 'KOREN OUTPUT_STREAM)
(PRINT KOREN OUTPUT_STREAM)
;ЗАКРЫВАЕМ ФАЙЛ
(TERPRI OUTPUT_STREAM)
(CLOSE
OUTPUT_STREAM)
5. Пример выполнения
программы
Пример 1.
Рисунок 5 – Входные
данные.
Рисунок 6 – Выходные
данные.
Пример 2.
Рисунок 7 – Входные
данные.
Рисунок 8 – Выходные
данные.
Пример 3.
Рисунок 9 – Входные
данные.
Рисунок 10 – Выходные
данные.
ЗАКЛЮЧЕНИЕ
Проблема
повышения качества вычислений, как несоответствие между желаемым и
действительным, существует и будет существовать в дальнейшем. Ее решению будет
содействовать развитие информационных технологий, которое заключается как в
совершенствовании методов организации информационных процессов, так и их
реализации с помощью конкретных инструментов – сред и языков программирования.
Итогом
работы можно считать созданную функциональную модель нахождения корней уравнения методом
Ньютона. Данная модель может быть
использована для решения задач оптимизации, в которых требуется определить нуль
первой производной либо градиента в случае многомерного пространства. Созданная функциональная модель и ее
программная реализация могут служить органической частью решения более сложных
задач.
СПИСОК
ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ и литературы
1.
Бронштейн, И.Н. Справочник по математике для инженеров и учащихся втузов
[Текст] / И.Н.Бронштейн, К.А.Семендяев. – М.: Наука, 2007. – 708 с.
2.
Кремер, Н.Ш.
Высшая математика для экономистов: учебник для студентов вузов. [Текст] /
Н.Ш.Кремер, 3-е издание – М.:ЮНИТИ-ДАНА, 2006. C. 412.
3.
Калиткин,
Н.Н. Численные методы. [Электронный ресурс] / Н.Н. Калиткин. – М.: Питер, 2001.
С. 504.
5.
Семакин, И.Г.
Основы программирования. [Текст] / И.Г.Семакин, А.П.Шестаков. – М.: Мир, 2006. C. 346.
6.
Симанков,
В.С. Основы функционального программирования [Текст] / В.С.Симанков,
Т.Т.Зангиев, И.В.Зайцев. – Краснодар: КубГТУ, 2002. – 160 с.
7.
Степанов, П.А.
Функциональное программирование на языке Lisp. [Электронный ресурс] / П.А.Степанов,
А.В. Бржезовский. – М.: ГУАП, 2003. С. 79.
8.
Хювенен Э. Мир Лиспа [Текст] / Э.Хювенен, Й.Сеппянен. – М.: Мир, 1990. –
460 с.