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

Тип работы:
Реферат
Предмет:
Программирование


Узнать стоимость

Детальная информация о работе

Выдержка из работы

СОДЕРЖАНИЕ

Введение

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

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

ВВЕДЕНИЕ

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

a0xn+a1xn-1+…+an-1x+an=0, a00

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

Для неалгебраических уравнений типа

х-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] и выполнены условия:

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.

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

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

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

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

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

ПоказатьСвернуть
Заполнить форму текущей работой