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

СОДЕРЖАНИЕ Введение

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

• 2. Математические и алгоритмические основы решения задачи
• 2.1 Описание метода
• 2.2 Геометрическая интерпретация
• 3. Функциональные модели и блок-схемы решения задачи
• 4. Программная реализация решения задачи
• 5. Пример выполнения программы
• Заключение

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

  и литературы

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

a₀xⁿ+a₁x^n-1+…+a_n-1x+a_n=0, a₀0

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

Для неалгебраических уравнений типа х-cos (x)=0

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

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

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

f (x) =0,

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

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

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

1. Постановка задачи Дано уравнение:

.

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

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

Пример.

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

.

Рисунок 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⁽⁰⁾ — полученное каким-либо способом приближение к корню x (в простейшем случае x⁽⁰⁾=(a+b)/2). Метод простой итерации заключается в последовательном вычислении членов итерационной последовательности:

x^(k+1)=?(x^(k)), k=0, 1, 2, … (2.3)

начиная с приближения x⁽⁰⁾.

УТВЕРЖДЕНИЕ: 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) C¹[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⁽⁰⁾ [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 ² | x ^(k-1) — x ^(k-2) |? …? q ^k | x ⁽¹⁾ — x ⁽⁰⁾ |. (2.5)

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

S_? = x ⁽⁰⁾ + (x ⁽¹⁾ — x ⁽⁰⁾) + … + (x ^(k+1) — x ^(k)) + …. (2.6)

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

S_k = x ⁽⁰⁾ + (x ⁽¹⁾ — x ⁽⁰⁾) + … + (x ^(k) — x ^(k-1)).

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

S_k = x ^(k)). (2.7)

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

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

q ⁰ | x ⁽¹⁾ — x ⁽⁰⁾ | + q ¹ |x ⁽¹⁾ — x ⁽⁰⁾| + … + |x ⁽¹⁾ — x ⁽⁰⁾| + …, (2.8)

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

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

|X — x ^(k+1)|

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

Имеем

X — x^(k+1) = X — S_k+1 = S_? — S_k+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) | + …? q^k+1 |x⁽¹⁾ — x⁽⁰⁾ | + q^k+2 |x⁽¹⁾ — x⁽⁰⁾ | + … = q^k+1|x⁽¹⁾ — x⁽⁰⁾ | / (1-q).

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

|X — x^(k+1)|? q^k+1|x⁽¹⁾ — x⁽⁰⁾ | / (1-q). (2.9)

Взяв за x⁽⁰⁾ значение x^(k), за x⁽¹⁾ — значение x^(k+1) (так как при выполнении условий теоремы такой выбор возможен) и учитывая, что при имеет место неравенство q^k+1? q выводим:

|X — x^(k+1)|? q^k+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.

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

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

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

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

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