Знаходження коренів рівняння методом простої ітерації ЛИСП-реалізація

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

ЗМІСТ

Введення

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

2. Математичні та алгоритмічні основи рішення задачі

2.1 Опис методу

2.2 Геометрична інтерпретація

3. Функціональні моделі та блок-схеми виконання завдання

4. Програмна реалізація рішення задачі

5. Приклад виконання програми

Висновок

Список використаних джерел та літератури

ВСТУП

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

a 0 x n + a 1 x n -1 + ... + a n -1 x + a n = 0, a 0 ¹ 0

при n ³ 5 не можна виразити через коефіцієнти за допомогою дій складання, віднімання, множення, ділення, піднесення до степеня і добування кореня.

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

х-cos (x) = 0

завдання ще більш ускладнюється. У цьому випадку знайти для коріння явні вирази, за рідкісним випадком не вдається.

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

Якщо записати рівняння у вигляді

f (x) = 0,

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

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

Метою даної курсової роботи є Лісп - реалізація знаходження коренів рівняння методом простої ітерації.

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

Дано рівняння:

.

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

Вхідним параметром алгоритму, крім функції F (X), є також початкове наближення - деякий X 0, від якого алгоритм починає йти.

Приклад.

Знайдемо корінь рівняння

.

Малюнок 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 *.

Щоб користуватися цим твердженням потрібна збіжність послідовності {x (k)}. Достатня умова збіжності дає:

ТЕОРЕМА 2.1: (про збіжність) Нехай рівняння x = φ (x) має єдиний корінь на відрізку [a, b] і виконані умови:

1) φ (x) C 1 [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)

Якщо ми доведемо, що цей ряд сходиться, то значить сходиться і послідовність його часткових сум

S k = x (0) + (x (1) - x (0)) + ... + (X (k) - x (k-1)).

Але неважко вирахувати, що

S k = 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 - 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 (1) - x (0) | + q k +2 | x (1) - x (0) | + ... = Q k +1 | x (1) - x (0) | / (1-q).

У результаті отримуємо формулу

| X - x (k +1) | ≤ q k +1 | x (1) - x (0) | / (1-q). (2.9)

Взявши за x (0) значення x (k), за x (1) - значення 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 (NEX 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)

(/ (+ (- (* XX) (* 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)

(- (* XX) (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 с.

Посилання (links):
  • http://solidbase.karelia.ru/edu/meth_calc/files/12.shtm
  • Додати в блог або на сайт

    Цей текст може містити помилки.

    Програмування, комп'ютери, інформатика і кібернетика | Реферат
    53.3кб. | скачати


    Схожі роботи:
    Знаходження коренів рівняння методом Ньютона ЛИСП-реалізація
    Методи знаходження коренів поліномів
    Знаходження коренів рівнянь різними методами
    Програма для знаходження нижньої та верхньої межі дійсних коренів
    Обробка результатів психологічних тестів ЛИСП-реалізація
    ЛИСП-реалізація основних операцій над нечіткими множинами
    Розробка програмного забезпечення для пошуку коренів біквадратні рівняння
    Проект програмного модуля для знаходження кореня рівняння
    Знаходження критичного шляху табличним методом
    © Усі права захищені
    написати до нас