Xreferat.com » Рефераты по информатике и программированию » Нахождение корней уравнения методом простой итерации (ЛИСП-реализация)

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

СОДЕРЖАНИЕ


Введение

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

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

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

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

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

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

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

Заключение

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


ВВЕДЕНИЕ


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


a0xn+a1xn-1+…+an-1x+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=(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")

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

(SETQ START (/ (- (CADR INTERVAL) (CAR INTERVAL)) 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– Выходные данные


ЗАКЛЮЧЕНИЕ


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

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


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


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

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

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

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

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

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

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

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

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту

Похожие рефераты: