Главная Учебники - Разные Лекции (разные) - часть 33
Введение 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= 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) ДОКАЗАТЕЛЬСТВО: Пусть Перейдем к пределу в равенстве x(k+1)
=φ(x(k)
) Получим с одной стороны по (2.4), что В результате получаем x*
=φ(x*
). Следовательно, x*
- корень уравнения (2.2), т.е. X=x*
. Чтобы пользоваться этим утверждением нужна сходимость последовательности {x(k)
}. Достаточное условие сходимости дает: ТЕОРЕМА 2.1: (о сходимости) Пусть уравнение x=φ(x) имеет единственный корень на отрезке [a,b] и выполнены условия: 1) φ(x) 2) φ(x) 3) существует константа q > 0: | φ '(x) | ≤ q < 1 x ДОКАЗАТЕЛЬСТВО: Рассмотрим два соседних члена последовательности {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. И следующая итерация Рисунок 4. Из рисунка наглядно видно требование сходимости Рисунок 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.
|