Реферат: Нахождение корней уравнения методом простой итерации ЛИСП-реализация
СОДЕРЖАНИЕ
Введение
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), является также начальное приближение — некоторое X, от которого алгоритм начинает идти.
Пример.
Найдем корень уравнения
/>.
/>
Рисунок 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*.
--PAGE_BREAK--Чтобы пользоваться этим утверждением нужна сходимость последовательности {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)
продолжение--PAGE_BREAK--
Таким образом, для нахождения корней уравнения 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– Выходные данные
ЗАКЛЮЧЕНИЕ
Проблема повышения качества вычислений, как несоответствие между желаемым и действительным, существует и будет существовать в дальнейшем. Ее решению будет содействовать развитие информационных технологий, которое заключается как в совершенствовании методов организации информационных процессов, так и их реализации с помощью конкретных инструментов – сред и языков программирования.
Итогом работы можно считать созданную функциональную модель нахождения корней уравнения методом простой итерации. Данная модель применима к детерминированным задачам, т.е. погрешностью экспериментального вычисления которых можно пренебречь. Созданная функциональная модель и ее программная реализация могут служить органической частью решения более сложных задач.
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ и литературы
Бронштейн, И.Н. Справочник по математике для инженеров и учащихся втузов [Текст] / И.Н.Бронштейн, К.А.Семендяев. – М.: Наука, 2007. – 708 с.
Кремер, Н.Ш. Высшая математика для экономистов: учебник для студентов вузов. [Текст] / Н.Ш.Кремер, 3-е издание – М.: ЮНИТИ-ДАНА, 2006. C. 412.
Калиткин, Н.Н. Численные методы. [Электронный ресурс] / Н.Н. Калиткин. – М.: Питер, 2001. С. 504.
Поиск минимума функции [Электронный ресурс] – Режим доступа: solidbase.karelia.ru/edu/meth_calc/files/12.shtm
Семакин, И.Г. Основы программирования. [Текст] / И.Г.Семакин, А.П.Шестаков. – М.: Мир, 2006. C. 346.
Симанков, В.С. Основы функционального программирования [Текст] / В.С.Симанков, Т.Т.Зангиев, И.В.Зайцев. – Краснодар: КубГТУ, 2002. – 160 с.
Степанов, П.А. Функциональное программирование на языке Lisp. [Электронный ресурс] / П.А.Степанов, А.В. Бржезовский. – М.: ГУАП, 2003. С. 79.
Хювенен Э. Мир Лиспа [Текст] / Э.Хювенен, Й.Сеппянен. – М.: Мир, 1990. – 460 с.
Ссылки (links):solidbase.karelia.ru/edu/meth_calc/files/12.shtm