Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

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

Название: Нахождение корней уравнения методом Ньютона (ЛИСП-реализация)
Раздел: Рефераты по информатике, программированию
Тип: курсовая работа Добавлен 21:14:00 29 января 2010 Похожие работы
Просмотров: 492 Комментариев: 2 Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

СОДЕРЖАНИЕ

Введение

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

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

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

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

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

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

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

Заключение

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


ВВЕДЕНИЕ

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

Метод был описан Исааком Ньютоном в рукописи Deanalysiperaequationesnumeroterminoruminfinitas (лат.Об анализе уравнениями бесконечных рядов), адресованной в 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

(DEFUNF(X)

(- (COSX) (* XXX))

)

;ПРОИЗВОДНАЯ -sinx-3x2

(DEFUN DFDX (X)

(- (* -1 (SIN X)) (* 3 X X))

)

(SETQ X0 0.5)

(SETQ E 0.0001)

Файл FUNCTION.txt (Пример 2)

;ФУНКЦИЯ x-cosx

(DEFUN F(X)

(- 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.

4. Метод Ньютона – Википедия [Электронный ресурс] – Режим доступа: http://ru.wikipedia.org/wiki/Метод_Ньютона

5. Семакин, И.Г. Основы программирования. [Текст] / И.Г.Семакин, А.П.Шестаков. – М.: Мир, 2006. C. 346.

6. Симанков, В.С. Основы функционального программирования [Текст] / В.С.Симанков, Т.Т.Зангиев, И.В.Зайцев. – Краснодар: КубГТУ, 2002. – 160 с.

7. Степанов, П.А. Функциональное программирование на языке Lisp. [Электронный ресурс] / П.А.Степанов, А.В. Бржезовский. – М.: ГУАП, 2003. С. 79.

8. Хювенен Э. Мир Лиспа [Текст] / Э.Хювенен, Й.Сеппянен. – М.: Мир, 1990. – 460 с.

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений07:26:45 19 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
19:39:31 28 ноября 2015

Работы, похожие на Курсовая работа: Нахождение корней уравнения методом Ньютона (ЛИСП-реализация)

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

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



Результаты(150276)
Комментарии (1830)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru