Знаходження коренів нелінійних рівнянь

 

 

 

АНОТАЦІЯ

 

Дана пояснювальна записка містить опис програми, яка знаходить корені нелінійних алгебраїчних рівнянь за допомогою наближеного методу дихотомії, що включає опис логічної її структури, тобто алгоритм, на основі якого написана програма з використовуваними бібліотеками (CRT) і процедурами, а також константи і перемінні, вхідні і вихідні дані. У даній програмі зазначені її призначення й умови застосування. Тут же описане керівництво користувача.

    Початковий текст програми знаходиться  у файлі KURSOVA.pas и займає об’єм пам’яті рівний 3 Кбайт, а виконуючий модуль знаходиться у файлі KURSOVA.exe и займає 36864 байт.

 

 

     

      

 

 

 

 

 

 

 

 

 

 

 

 

ЗМІСТ

ВСТУП	4
1 ПОСТАНОВКА ЗАДАЧІ	6
2 АНАЛІЗ ЗАВДАННЯ ТА РОЗРОБКА  МЕТОДУ ВИРІШЕННЯ ЗАДАЧІ	7
3 ОПИС ПРОГРАМИ	11
3.1 Алгоритм на основі якого  написана програма	11
3.2 Використання бібліотеки CRT	12
3.3 Опис змінних	13
3.4 Вхідні і вихідні дані	13
4 ОПИС ЗАСТОСУВАННЯ	14
ВИСНОВОК	15
СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ	16
Додаток А	17
Додаток Б	18

 

 

 

ВСТУП

 

Система програмування Turbo Pascal, розроблена американською корпорацією Borland, залишається однієї із найпопулярних систем програмування у світі. Цьому сприяє простота лежачої в її основі мови програмування. Придумана швейцарським ученим Ніколасом Віртом як засіб для навчання студентів програмуванню, мова Pascal перетворилась в могутню сучасну професійну систему програмування, якій по плечу будь-які задачі - від створення простих програм, призначених для рішення нескладних обчислювальних задач, до розробки найважчих реляційних систем керування базами даних.

Як і деякі мови Турбо Паскаль дозволяє писати добре структуровані програми (завдяки в ньому процедур і функцій). У структурованих програмах звичайно легко просліджується основний алгоритм, їх неважко зрозуміти будь-якому читачу, вони простіше в налагодженні і менш чуттєві до помилок програмування. Усі ці властивості є наслідком важливої особливості процедур (функцій), кожна з який являє собою багато в чому самостійний фрагмент програми, зв'язаний з основною програмою лише з допомогою декількох параметрів. Самостійність процедур (функцій) дозволяє локалізувати в них деталі програмної реалізації тієї чи іншої алгоритмічної дії і тому зміна цих деталей, наприклад, у процесі налагодження звичайно не приводить до зміни основної програми. Розбивка основної програми на ряд незалежних одна від одної частин це ще і засіб економії пам'яті : кожна підпрограма існує в програмі в єдиному екземплярі, у той час як звертатися до неї можна багаторазово з різних місць програми.

Слід зазначити надійність синтаксису мови Turbo Pascal, що не допускає неоднозначність трактування умови (на відміну Сі). Так само наслідком твердої вимоги мови є те, що будь-який нестандартний ідентифікатор, використовуваний в операторах, що виконуються, повинний бути попередньо описаний у розділі описів. Такі вимоги здаються надто суворими і роблять мову менш вільною. Насправді ж у цьому виявляється тенденція розвитку мови у сторону підвищення надійності створюваних програм і захист їх від деякого роду помилок. Важлива перевага Турбо Паскаля перед іншими мовами програмування, у яких допускається автоматичне перетворення типів – це контроль за використанням перемінних ще на етапі компіляції. У Турбо Паскалі майже неможливі неявні (автоматичні) перетворення типів. Зрозуміло, це не означає, що в Турбо Паскалі немає засобів перетворення даних. Вони, звичайно ж, є, але їх потрібно використовувати явно.

Розроблювачі Турбо Паскаля включили в мову механізм так званих модулів. Модулі являють собою прекрасний інструмент для розробки бібліотек прикладних програм і могутній засіб модульного програмування. Важлива особливість модулів полягає в тім, що компілятор Турбо Паскаля розміщає їхній програмний код в окремому сегменті пам'яті. Максимальна довжина сегмента не може перевищувати 64 Кбайта, однак кількість одночасна використовуваних модулів обмежується лише доступною пам'яттю, що дає можливість створювати дуже великі програми.

Середовище Турбо Паскаля подає вичерпну інформацію про характер і місце виявлення помилки. Якщо на якому-небудь етапі середовище знайде помилку, вона припиняє подальші дії, відновлює вікно редактора і поміщає курсор на той рядок програми, при чи компіляції виконанні якої виявлена помилка. При цьому у верхньому рядку редактора з'являється діагностичне повідомлення про причину помилки. Усе це дозволяє дуже швидко налагодити програму, тобто усунути в ній синтаксичні помилки і переконатися в правильності її роботи.

 

 1 ПОСТАНОВКА ЗАДАЧІ

 

Скласти програму, яка знаходить корінь рівняння f(x)=0 з точністю E методом дихотомії.

 

 2 АНАЛІЗ ЗАВДАННЯ ТА РОЗРОБКА МЕТОДУ ВИРІШЕННЯ ЗАДАЧІ

 

Розглянемо рівняння і нехай - його дійсний корінь, тобто Геометрично рівність означає, що графік функції проходить через точку осі . Далі ми будемо розв’язувати задачу про знаходження з наперед заданою точністю наближеного значення кореня рівняння Спочатку розглянемо питання про відокремлення коренів рівняння.

Корінь рівняння відокремлений, якщо знайдено відрізок ( позначимо його ), в якому, крім , немає інших коренів цього рівняння.

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

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

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

У цьому випадку числа та є наближеними значеннями кореня відповідно з нестачею і з надлишком. Ці інтервали можна звужувати, тоді границі їх будуть давати все точніші наближення для коренів рівняння.

Нехай корінь рівняння відокремлений, тобто є відрізок , на якому, крім , немає інших коренів цього рівняння.

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

 

Рисунок 1 – Варіанти поведінки функції

 

Отже, розглянемо задачу знаходження коренів рівняння

 

,       (1)

 

де - задана функція дійсного змінного.

Розв’язування даної задачі можна розкласти на декілька етапів:

а) дослідження розташування коренів (в загальному випадку на комплексній площині) та їх кратність;

б) відділення коренів, тобто виділення областей, що містять тільки один корінь;

в) обчислення кореня з заданою точністю за допомогою одного з ітераційних алгоритмів.

Далі розглядаються ітераційні процеси, що дають можливість побудувати числову послідовність xn, яка збігається до шуканого кореня рівняння (1).

Метод ділення проміжку навпіл (метод дихотомії)

Нехай і відомо, що рівняння (1) має єдиний корінь . Покладемо a0=a, b0=b, x0=(a0+b0)/2. Якщо , то . Якщо , то покладемо

 

    (2)

 

    (3)

     (4)

 

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

З формул (2), (3) видно, що і . Тому , а отже шуканий корінь знаходиться на проміжку . При цьому має місце оцінка збіжності

 

.      (5)

Звідси випливає, що кількість ітерацій. які необхідно провести для знаходження наближеного кореня рівняння (1) з заданою точністю e задовольняє співвідношенню

 

.      (6)

 

де [c] - ціла частина числа c.

Серед переваг даного методу слід відзначити простоту реалізації та надійність. Послідовність {xn} збігається до кореня для довільних неперервних функцій f(x). До недоліків можна віднести невисоку швидкість збіжності методу та неможливість безпосереднього узагальнення систем нелінійних рівнянь.

 

3 ОПИС ПРОГРАМИ

Опис логічної структури

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

3.1 Алгоритм на основі якого написана програма

Цей метод дозволяє відшукати корінь рівняння f( )=0 з кожною наперед заданою точністю е.

Передбачається, що шуканий корінь рівняння вже відділений, тобто зазначений відрізок [ a ; b ] безперервності функції f(x) такий, що на кінцях цього відрізка функція приймає різні значення.

Суть методу в тому, що [ a ;b ] ділиться навпіл. Половина, де немає кореня відкидається, а інша ділитися на два.

1-й Крок. Обчислення середини відрізка

 

 

 

Якщо f( )=0, то ми знайшли точний корінь рівняння.

Якщо f( ) · f(x0)<0, то перебуває в інтервалі [ ] отже ;

 Інакше 

 

2-й Крок. Обчислення середини відрізка

 

 

 

Якщо f( )=0, то ми знайшли точний корінь рівняння.

Якщо f( · f(x1)<0, то ;

Інакше

 

n-й Крок. Обчислення середини відрізка

Якщо f( )=0, то ми знайшли точний корінь рівняння.

Якщо f( ·f(xn)<0, то ;

Інакше

 Умовою знаходження кореня  є:

 

 

 

3.2 Використання бібліотеки CRT

   У модулі CRT зосереджені  процедури і функції, що забезпечують  керування текстовим режимом  роботи екрана. За допомогою вхідних  у модуль програм можна переміщати  курсор у довільну позицію  екрана, змінювати колір виведених  символів і навколишнього їхнього тла, створювати вікна. Крім того, до складу цього модуля включили кілька підпрограм, що істотно збільшує можливості текстового введення/висновку. У модуль CRT включені також процедури Sound, NoSound і Delay, що дозволяють програмувати звуковий генератор ПК.

У програмі з модуля CRT використовувалися наступні процедури і функції.

Функція KeyPressed. Повертає значення типу Boolean, що вказує стан буфера клавіатури : False означає, що буфер порожній, а True – що в буфері є хоча б один символ, ще не прочитаний програмою. Звертання до функції KeyPressed не затримує виконання програми : функція негайно аналізує буфер і повертає те чи інше значення, не чекаючи натискання клавіші.

Функція ReadKey. Повертає значення типу Char. При звертанні до цієї функції аналізується буфер клавіатури : якщо в ньому є хоча б один непрочитаний символ, код цього символу береться з буфера і повертається як значення функції, у противному випадку функція буде очікувати натискання на будь-яку клавішу.

3.3 Опис змінних

x0, x1, x2: real ; глобальні змінні дійсного типу, які використовуються для визначення кінців проміжку, на якому шукатиметься корені заданого рівняння. Змінна х2 слугує для знаходження середини проміжку.

 е: real; глобальна змінна, яка використовується для задання точності знаходження кореня заданого рівняння.

 

3.4 Вхідні і вихідні дані

 

Вхідними даними розглянутої програми є наступні параметри:

• задане рівняння, яке треба розв’язати;
• точність знаходження коренів рівняння;
• значення кінців відрізка, на якому шукатимуться корені заданого рівняння.

До вихідних даних належить розв’язок заданого рівняння.

 

 4 ОПИС ЗАСТОСУВАННЯ

 

Розглянута в пояснювальній записці програма, є науково-ознайомлювальної і розрахована для демонстраційного застосування, у зв'язку з її простотою.

Програма KURSOVA реалізує процедуру наближеного розв’язання заданого рівняння за допомогою методу дихотомії.

Оскільки програма була написана мовою програмування Турбо Паскаль, те вихідний текст міститься у файлі з розширенням PAS – KURSOVA.pas і займає обсяг пам'яті рівний 8 Кбайт, а модуль, що виконується, знаходиться у файлі KURSOVA.exe і займає 30 Кбайт.

До мінімальних і необхідних системних вимог програми можна віднести наступні значення :

процесор не нижче IBM-386;

наявність на твердому диску чи дискеті вільного місця не менш, ніж 100 Кбайт.

ОЗУ не менш 1 Мбайт

відео пам'ять не менш 640 Кбайт

необхідно також наявність на диску графічного драйвера розробленого фірмою Borland – EGAVGA.BGI, а також деяких драйверів для підтримки стандартних векторних BGI-шрифтів, використовуваних у програмі.

Програма працює під керуванням операційної системи MS-DOS чи MS-WINDOWS, у емуляційному режимі DOS.

Наявність усіх перерахованих вище технічних засобів дозволяє благополучно запустити програму. Запуск можливий безпосередньо через файл KURSOVA.exe в оболонці перерахованих вище операційних систем, а також у середовищі Турбо Паскаль через файл KURSOVA.pas.