Банк рефератов содержит более 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)

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

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

СОДЕРЖАНИЕ

Введение

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

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

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

2.2 Геометрическая интерпретация

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

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

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

Заключение

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


ВВЕДЕНИЕ

Методы решения линейных и квадратных уравнений были известны еще древним грекам. Решение уравнений третьей и четвертой степеней были получены усилиями итальянских математиков Ш. Ферро, Н. Тартальи, Дж. Картано, Л. Феррари в эпоху Возрождения. Затем наступила пора поиска формул для нахождения корней уравнений пятой и более высоких степеней. Настойчивые, но безрезультатные попытки продолжались около 300 лет и завершились благодаря работам норвежского математика Н. Абеля. Он доказал, что общее уравне6ие пятой и более высоких степеней неразрешимы в радикалах. Решение общего уравнения n-ой степени

a0 xn +a1 xn -1 +…+an -1 x+an =0, a0 ¹0

при n³5 нельзя выразить через коэффициенты с помощью действий сложения, вычитания, умножения, деления, возведения в степень и извлечения корня.

Для неалгебраических уравнений типа

х–cos(x)=0

задача еще более усложняется. В этом случае найти для корней явные выражения, за редким случаем не удается.

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

Если записать уравнение в виде


f(x) =0,

то для применения этих алгоритмов нет необходимости накладывать какие-либо ограничения на функцию f(x), а предполагается только что она обладает некоторыми свойствами типа непрерывности, дифференцируемости и т.д.

Это итерационный численный метод нахождения корня (нуля) заданной функции.

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


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

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

.

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

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

Пример.

Найдем корень уравнения

.

Рисунок 1. Функция

Будем искать простой корень уравнения, находящийся на отрезке локализации [-0.4,0].

Приведем уравнение к виду x=f(x), где


.

Проверим условие сходимости:

.

Рисунок 2. График производной

Максимальное по модулю значение производной итерационной функции достигается в левом конце отрезка

.

.

Выполним 3 итерации по расчетной формуле

x= (x),

1 итерация .

2 итерация .

3 итерация .


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

2.1 Описание метода простых итераций

Рассмотрим уравнение

f(x)=0 (2.1)

с отделенным корнем X[a, b]. Для решения уравнения (2.1) методом простой итерации приведем его к равносильному виду:

x=φ(x). (2.2)

Это всегда можно сделать, причем многими способами. Например:

x=g(x) · f(x) + x ≡ φ(x),

где g(x) - произвольная непрерывная функция, не имеющая корней на отрезке [a,b].

Пусть x(0) - полученное каким-либо способом приближение к корню x (в простейшем случае x(0) =(a+b)/2). Метод простой итерации заключается в последовательном вычислении членов итерационной последовательности:

x(k+1) =φ(x(k) ), k=0, 1, 2, ... (2.3)

начиная с приближения x(0) .

УТВЕРЖДЕНИЕ: 1 Если последовательность {x(k) } метода простой итерации сходится и функция φ непрерывна, то предел последовательности является корнем уравнения x=φ(x)

ДОКАЗАТЕЛЬСТВО: Пусть


. (2.4)

Перейдем к пределу в равенстве x(k+1) =φ(x(k) ) Получим с одной стороны по (2.4), что а с другой стороны в силу непрерывности функции φ и (2.4)

.

В результате получаем x* =φ(x* ). Следовательно, x* - корень уравнения (2.2), т.е. X=x* .

Чтобы пользоваться этим утверждением нужна сходимость последовательности {x(k) }. Достаточное условие сходимости дает:

ТЕОРЕМА 2.1: (о сходимости) Пусть уравнение x=φ(x) имеет единственный корень на отрезке [a,b] и выполнены условия:

1) φ(x) C1 [a,b];

2) φ(x) [a,b] " x [a,b];

3) существует константа q > 0: | φ '(x) | ≤ q < 1 x [a,b]. Tогда итерационная последовательность {x(k) }, заданная формулой x(k+1) = φ(x(k) ), k=0, 1, ... сходится при любом начальном приближении x(0) [a,b].

ДОКАЗАТЕЛЬСТВО: Рассмотрим два соседних члена последовательности {x(k) }: x(k) = φ(x(k-1) ) и x(k+1) = φ(x(k) ) Tак как по условию 2) x(k) и x(k+1) лежат внутри отрезка [a,b], то используя теорему Лагранжа о средних значениях получаем:

x (k+1) - x (k) = φ(x (k) ) - φ(x (k-1) ) = φ '(c k )(x (k) - x (k-1) ),

где c k (x (k-1) , x (k) ).

Отсюда получаем:

| x (k+1) - x (k) | = | φ '(c k ) | · | x (k) - x (k-1) | ≤ q | x (k) - x (k-1) | ≤

≤ q ( q | x (k-1) - x (k-2) | ) = q 2 | x (k-1) - x (k-2) | ≤ ... ≤ q k | x (1) - x (0) |. (2.5)

Рассмотрим ряд

S = x (0) + ( x (1) - x (0) ) + ... + ( x (k+1) - x (k) ) + ... . (2.6)

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

Sk = x (0) + ( x (1) - x (0) ) + ... + ( x (k) - x (k-1) ).

Но нетрудно вычислить, что

Sk = x (k)) . (2.7)

Следовательно, мы тем самым докажем и сходимость итерационной последовательности {x(k) }.

Для доказательства сходимости pяда (2.6) сравним его почленно (без первого слагаемого x(0) ) с рядом

q 0 | x (1) - x (0) | + q 1 |x (1) - x (0) | + ... + |x (1) - x (0) | + ..., (2.8)

который сходится как бесконечно убывающая геометрическая прогрессия (так как по условию q < 1). В силу неравенства (2.5) абсолютные величины ряда (2.6) не превосходят соответствующих членов сходящегося ряда (2.8) (то есть ряд (2.8) мажорирует ряд (2.6). Следовательно ряд (2.6) также сходится. Tем самым сходится последовательность {x(0) }.

Получим формулу, дающую способ оценки погрешности

|X - x (k+1) |

метода простой итерации.

Имеем

X - x( k +1) = X - Sk +1 = S - Sk +1 = (x( k +2) - ( k +1) ) + (x( k +3) - x( k +2) ) + ... .

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

|X - x(k+1) | ≤ |x(k+2) - (k+1) | + |x(k+3) - x(k+2) | + ... ≤ qk+1 |x(1) - x(0) | + qk+2 |x(1) - x(0) | + ... = qk+1 |x(1) - x(0) | / (1-q).

В результате получаем формулу

|X - x(k+1) | ≤ qk+1 |x(1) - x(0) | / (1-q). (2.9)

Взяв за x(0) значение x(k) , за x(1) - значение x(k+1) (так как при выполнении условий теоремы такой выбор возможен) и учитывая, что при имеет место неравенство qk+1 ≤ q выводим:

|X - x(k+1) | ≤ qk+1 |x(k+1) - x(k) | / (1-q) ≤ q|x(k+1) - x(k) | / (1-q).

Итак, окончательно получаем:

|X - x(k+1) | ≤ q|x(k+1) - x(k) | / (1-q). (2.10)

Используем эту формулу для вывода критерия окончания итерационной последовательности. Пусть уравнение x=φ(x) решается методом простой итерации, причем ответ должен быть найден с точностью ε, то есть

|X - x(k+1) | ≤ ε.

С учетом (2.10) получаем, что точность ε будет достигнута, если выполнено неравенство

|x(k+1) -x(k) | ≤ (1-q)/q. (2.11)

Таким образом, для нахождения корней уравнения x=φ(x) методом простой итерации с точностью нужно продолжать итерации до тех пор, пока модуль разности между последними соседними приближениями остается больше числа ε(1-q)/q.

ЗАМЕЧАНИЕ 2.2: В качестве константы q обычно берут оценку сверху для величины

.

2.2 Геометрическая интерпретация

Рассмотрим график функции . Это означает, что решение уравнения и - это точка пересечения с прямой :


Рисунок 3.

И следующая итерация - это координата x пересечения горизонтальной прямой точки с прямой .

Рисунок 4.

Из рисунка наглядно видно требование сходимости . Чем ближе производная к 0, тем быстрее сходится алгоритм. В зависимости от знака производной вблизи решения приближения могут строится по разному. Если , то каждое следующее приближение строится с другой стороны от корня:


Рисунок 5.


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

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

Используемые обозначения:

·FN, F – уравнение для поиска корня;

·X, START – начальное значение;

·E, PRECISION – точность вычисления;

·N, COUNT_ITER –количество итераций.

Рисунок 6 – Функциональная модель решения задачи для функции SIMPLE_ITER


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


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

Файл SIMPLE_ITER.txt

;ФУНКЦИЯ, РЕАЛИЗУЮЩАЯ МЕТОД ПРОСТЫХ ИТЕРАЦИЙ

(DEFUN SIMPLE_ITER (N E X FN)

(COND

((AND (<= N 0) (> (ABS (- (FUNCALL FN X) X)) (* E (FUNCALL FN X)))) X)

(T (SIMPLE_ITER (- N 1) E (FUNCALL FN X) FN))

)

)

;ПОДГРУЖАЕМУРАВНЕНИЕ

(LOAD "D:\\FUNCTION.TXT")

;РАССЧИТЫВАЕМ НАЧАЛЬНОЕ ПРИБЛИЖЕНИЕ К КОРНЮ

(SETQSTART (/ (- (CADRINTERVAL) (CARINTERVAL)) 2))

;ВЫЧИСЛЯЕМКОРЕНЬ

(SETQ ROOT (SIMPLE_ITER COUNT_ITER PRECISION START (FUNCTION F)))

;ОТКРЫВЕМФАЙЛДЛЯЗАПИСИ

(SETQ OUTPUT_STREAM (OPEN "D:\\ROOT.TXT" :DIRECTION :OUTPUT))

;ПЕЧАТАЕМВФАЙЛКОРЕНЬ

(PRINT 'ROOT OUTPUT_STREAM)

(PRINT ROOT OUTPUT_STREAM)

;ЗАКРЫВАЕМФАЙЛ

(TERPRI OUTPUT_STREAM)

(CLOSE OUTPUT_STREAM)

Файл FUNCTION.txt (пример 1)

;ФУНКЦИЯ

(DEFUN F (X)

(/ (+ (- (* X X) (* 5 (COS X))) 3.25) 3)

)

;КОЛИЧЕСТВО ИТЕРАЦИЙ

(SETQ COUNT_ITER 100)

;ПРОМЕЖУТОК, НА КОТОРОМ ИЩЕМ КОРЕНЬ

(SETQ INTERVAL '(-0.4 0))

;ТОЧНОСТЬ ВЫЧИСЛЕНИЯ

(SETQ PRECISION 0.0001)

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

;ФУНКЦИЯ

(DEFUN F (X)

(- (* X X) (COS X))

)

;КОЛИЧЕСТВО ИТЕРАЦИЙ

(SETQ COUNT_ITER 60)

;ПРОМЕЖУТОК, НА КОТОРОМ ИЩЕМ КОРЕНЬ

(SETQ INTERVAL '(1 1.5))

;ТОЧНОСТЬ ВЫЧИСЛЕНИЯ

(SETQ PRECISION 0.0001)


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

Пример 1.

Рисунок 8 – Входные данные

Рисунок 9 – Выходные данные

Пример 2.

Рисунок 10 – Входные данные


Рисунок 11– Выходные данные


ЗАКЛЮЧЕНИЕ

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

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


СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ и литературы

1. Бронштейн, И.Н. Справочник по математике для инженеров и учащихся втузов [Текст] / И.Н.Бронштейн, К.А.Семендяев. – М.: Наука, 2007. – 708 с.

2. Кремер, Н.Ш. Высшая математика для экономистов: учебник для студентов вузов. [Текст] / Н.Ш.Кремер, 3-е издание – М.:ЮНИТИ-ДАНА, 2006. C. 412.

3. Калиткин, Н.Н. Численные методы. [Электронный ресурс] / Н.Н. Калиткин. – М.: Питер, 2001. С. 504.

4. Поиск минимума функции [Электронный ресурс] – Режим доступа: http://solidbase.karelia.ru/edu/meth_calc/files/12.shtm

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:29 28 ноября 2015

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

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

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



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

Рейтинг@Mail.ru