Нахождение корней уравнения методом простой итерации (ЛИСП-реализация)
СОДЕРЖАНИЕ
Введение
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=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] и выполнены условия:
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– Выходные
данные
ЗАКЛЮЧЕНИЕ
Проблема
повышения качества вычислений, как несоответствие между желаемым и
действительным, существует и будет существовать в дальнейшем. Ее решению будет
содействовать развитие информационных технологий, которое заключается как в
совершенствовании методов организации информационных процессов, так и их
реализации с помощью конкретных инструментов – сред и языков программирования.
Итогом
работы можно считать созданную функциональную модель нахождения корней уравнения методом
простой итерации. Данная модель применима к
детерминированным задачам, т.е. погрешностью экспериментального вычисления которых
можно пренебречь. Созданная функциональная модель и ее программная реализация
могут служить органической частью решения более сложных задач.
СПИСОК
ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ и литературы
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 с.