Вступ
Математичне моделювання займає вагоме місце серед інших програм які створюються програмістами. Під таким моделюванням розуміють сукупність математичних співвідношень таких як формули, рівняння, логічні вирази, які визначають характеристики і властивості системи, об’єкта, процесу або ж їх витікаючих, також функціонування залежно від параметрів компонентів, початкових умов, вхідних змін і часу. Загалом математична модель описує функціональну залежність між вихідними залежними змінними, через які відображається функціонування системи, незалежними і змінюваними змінними а також вхідними змінами, які мали вплив на систему.
Для окремого завдання формулюється окрема незалежна математична задача. В загальних випадках, коли функціональна залежність для множини вхідних даних що виступають як множина аргументів, задана неявно, за допомогою математичної моделі необхідно визначити множину вихідних залежних змінних, що виступають як множини значень функцій. При цьому відповідно до виду математичної моделі розрізняють такі базові типи математичних задач: розв’язання системи лінійних рівнянь, алгебраїчних рівнянь, апроксимація, інтегрування, диференціювання, системи диференційних рівнянь і ін. На сьогодні, більшість громіздких і трудоємких робіт по обчисленню різноманітних функцій і виразів, покладається на комп’ютер, але для простішого його використання потрібна програма, тобто зв’язний алгоритм дій, який має створити програміст.
Фізика, хімія, біологія, астрономія, геометрія та багато інших наук використовують спеціальні програми призначені для підрахунку величин в залежності від різних вхідних даних, на основі математичних задач.
Дана курсова робота описує один з типів такого моделювання, а саме розв’язанню нелінійних алгебраїчних рівнянь. Для розв’язання даного рівняння було обрано метод хорд.
1
.
Аналіз завдання та розробка методу вирішення задачі
Нехай дано рівняння і нехай
- його дійсний корінь, тобто
Геометрично рівність
означає, що графік функції
проходить через точку осі .
Далі ми будемо розв’язувати задачу про знаходження з наперед заданою точністю наближеного значення кореня рівняння
Спочатку розглянемо питання про відокремлення коренів рівняння.
Корінь рівняння
відокремлений, якщо знайдено відрізок (позначимо його
), в якому, крім , немає інших коренів цього рівняння.
Задача відокремлення коренів рівняння
розв’язується просто, якщо побудова графіка функції
не є важкою. Дійсно, маючи графік функції
, легко виділити відрізки, в кожному із яких знаходиться лише один корінь розглядуваного рівняння, або, що те саме, виділити відрізки, на кожному із яких є лише одна точка перетину кривої
з віссю .
Відділити корені рівняння
при умові, що
- диференційована функція, можна не лише графічно. Нехай на кінцях деякого відрізка
функція
має значення різних знаків. Тоді за властивістю неперервних функцій ця функція на інтервалі
по меншій мірі один раз обертається в нуль, тобто рівняння
має по меншій мірі один корінь.
Якщо похідна
зберігає знак на відрізку
, то внаслідок монотонності функції
рівняння
на інтервалі
має єдиний корінь.
У цьому випадку числа
та
є наближеними значеннями кореня відповідно з нестачею і з надлишком. Ці інтервали можна звужувати, тоді границі їх будуть давати все точніші наближення для коренів рівняння.
Нехай корінь рівняння
відокремлений, тобто є відрізок
, на якому, крім , немає інших коренів цього рівняння.
Відшукаємо значення з будь-якою точністю за таких допущень: функція
має на відрізку
неперервні похідні до другого порядку включно і, крім того, похідні
і
зберігають знаки на цьому відрізку. Із цих умов випливає, що
- монотонна функція на відрізку
, яка на кінцях має різні знаки, а також, що крива
опукла або вгнута (рис. 1.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). До недоліків можна віднести невисоку швидкість збіжності методу та неможливість безпосереднього узагальнення систем нелінійних рівнянь.
Метод простої ітерації
Метод простої ітерації застосовується до розв’язування нелінійного рівняння виду
. (7)
Перейти від рівняння (1) до рівняння(7) можна багатьма способами, наприклад, вибравши
, (8)
де - довільна неперервна функція.
Вибравши нульове наближення x0
, наступні наближення знаходяться за формулою
. (9)
Наведемо достатні умови збіжності методу простої ітерації.
Теорема 1. Нехай для вибраного початкового наближення x0
на проміжку
(10)
функція j(x) задовольняє умові Лівшиця
(11)
де 0<q<1, і виконується нерівність
. (12)
Тоді рівняння (7) має на проміжку S єдиний корінь , до якого збігається послідовність (9), причому швидкість збіжності визначається нерівністю
. (13)
Зауваження: якщо функція j(x) має на проміжку S неперервну похідну , яка задовольняє умові
, (14)
то функція j(x) буде задовольняти умові (11) теореми 1.
З (13) можна отримати оцінку кількості ітерацій. які потрібно провести для знаходження розв’язку задачі (7) з наперед заданою точністю e:
. (15)
Наведемо ще одну оцінку. що характеризує збіжність методу простої ітерації:
. (16)
Метод релаксації
Для збіжності ітераційного процесу (9) суттєве значення має вибір функції j(x). Зокрема, якщо в (8) вибрати , то отримаємо метод релаксації.
, (17)
який збігається при
. (18)
Якщо в деякому околі кореня виконуються умови
, (19)
то метод релаксації збігаються при . Збіжність буде найкращою при
. (20)
При такому виборі t для похибки буде мати місце оцінка
, (21)
де .
Кількість ітерацій, які потрібно провести для знаходження розв’язку з точністю e визначається нерівністю
. (22)
Зауваження: якщо виконується умова , то ітераційний метод (17) потрібно записати у вигляді .
Метод Ньютона
Метод Ньютона застосовується до розв’язування задачі (1), де f(x)
є неперервно-диференційованою функцією. На початку обчислень вибирається початкове наближення x0
. Наступні наближення обчислюються за формулою
. (23)
З геометричної точки зору xn+1
є значенням абсциси точки перетину дотичної до кривої y=f(x) в точці (xn
, f(xn
)) з віссю абсцис. Тому метод Ньютона називають також методом дотичних.
Теорема 2. Якщо не змінює знака на [a, b], то виходячи з початкового наближення , що задовольняє умові , можна обчислити методом Ньютона єдиний корінь рівняння (1) з будь-якою степінню точності.
Теорема 3. Нехай - простий дійсний корінь рівняння (1) і , де ,
, (24)
причому
. (25)
Тоді для метод Ньютона збігається, причому для похибки справедлива оцінка
. (26)
З оцінки (26) видно, що метод Ньютона має квадратичну збіжність, тобто похибка на (n+1) – й ітерації пропорційна квадрату похибки на n-й ітерації.
Модифікований метод Ньютона
(27)
дозволяє не обчислювати похідну на кожній ітерації, а отже і позбутися можливого ділення на нуль. Однак цей алгоритм має тільки лінійну збіжність.
Кількість ітерацій, які потрібно провести для знаходження розв’язку задачі (1) з точністю e задовольняє нерівності
. (28)
1.1 Розробка методу виконання основного завдання
Проміжок який перетинає функція, вводим через [a; b]. «eps» похибка розв’язку.
Записуєм з клавіатури проміжок та похибку. Користуючись рекурентною формулою складаєм процедуру уточнення кореня методом хорд. Якщо f
(x
) двічі неперервно диференційна функція і знак fnk2 (x) зберігається на розглядуваному відрізку, то отримані наближення будуть сходитись до кореня монотонно. Якщо корінь x
рівняння f
(x
)=0 знаходяться на відрізку [a; b], виробничі fnk(x) і fnk2 (x) на цьому відрізку неперервні і зберігають постійні знаки і fnk(a)*fnk2 (a)>0, то можна доказати, що похибка наближеного розв’язку прямує до нуля n->∞, то метод сходиться і має при цьому лінійну швидкість схожості. (Подібне до швидкості геометричної прогресії). Обчислюємо значення f
(x
) в середині відрізка [a
; b
], тобто в точці x1=x-fnk(x)/fnk1 (x). Залежно від значення f
(x-fnk(x)/fnk1 (x)) вибираємо ту частину інтервалу [a
; b
], де знаки функції f
(x
) є різними. Отже, інтервал, у якому є корінь, змінився. Продовживши процес, ми звужуємо інтервал до такої величини, поки його розмір (який дорівнює абсолютній похибці) не стане меншим від потрібної нам величини.
1.2 Структура даних і функцій
Моя програма складається з 6 модулів і головної функції main(). Характеристика кожного з модулів:
Основний, файл KURSAK.cpp в ньому знаходиться послідовність дій програми, тобто в даному модулі програма викликає інші під модулі які виконуюсь якусь функцію:
MODULE.cpp
HORD.cpp
SHOW.cpp
TITULKA.cpp
GRAFIK.cpp
AUTOR.cpp
Програма спочатку запускає електронну титульну сторінку курсової роботи, потім будує графік функції, корені якої нам потрібно знайти, використовуючи метод хорд знаходить корінь на вказаному з клавіатури проміжку з вказаною точністю, демонструє метод дихотомії графічно та зрештою виводить
драйвер EGAVGA.BGI
.
У головному модулі оголошено такі локальні змінні: int k=0 – для збереження пункту головного меню, яке обирає користувач, int gdriver = DETECT, gmode, errorcode – додаткові змінні для ініціалізації графічного режиму.
Тепер перейдемо до додаткових модулів.
Модуль TUTYLKA.CPP містить лише одну функцію що виводить на екран електронну титульну сторінку розробника курсової роботи. Оголошено такі локальні змінні: int a=5 – значення відступів від краю екрану до рамки, xmax=getmaxx(), ymax=getmaxy() – значення роздільної здатності екрану у
int i; – лічильник циклу;
float x1, x2, y1, y2, xx1, xx2, yy1, yy2; – містять координати точок на площині.
Модуль HORD.CPP містить дві функції: double f (double x) – обчислення значення вказаної в завданні функції для певного значення х, void Hord () – реалізація чисельного методу знаходження кореня рівняння на вказаному проміжку з вказаною точністю. Оголошено такі локальні змінні:
FILE *fp1,*fp2; – вказівники на файли, що містять проміжні результати обчислень;
int k=0; – лічильник ітерацій;
double a, b, c, epsilon; – межі проміжку, середина проміжку та точність.
Модуль Show.CPP містить одну функцію void Show (), що графічно демонструє роботу функції void Hord (). Оголошено такі локальні змінні:
int xmax=getmaxx(), ymax=getmaxy(); – значення роздільної здатності екрану у графічному режимі;
float x, a, b; – значення кореня рівняння та межі проміжку;
int i = 7; – кількість знаків після коми, які виводить функція gcvt();
char *buf; – допоміжна змінна для роботи функції gcvt().
2. Опис структури програмного проекту
Як зазначалося вище, наш проект складається з 6 додаткових модулів, та основного модуля, в якому міститься головна функція main() нашого проекту. Додаткові модулі не зв’язані один з одним, а лише з головним модулем.
Єдиним зв’язком (неявним) між модулями Hord.cpp та Show.cpp є спільне використання файлів KORENI.TXT та MEGI.TXT.
Загальна схема проекту із способами взаємодії між модулями наведена на рисунку 2.1.
Розбиття програми на різні файли визначається логічною структурою програми. Використання додаткових модулів дозволило спростити реалізацію нашого проекту та більш наочно показати взаємодію одних частин проекту з іншими та значно зменшити час на від лагодження та компіляцію цілого проекту.
3. Опис алгоритмів розв’язання задачі
Опишемо алгоритм роботи усіх функцій усіх модулів нашого проекту. Почнемо з основного KURSAK.CPP. Містить функцію void main().
Вона є фактично монітором нашого проекту, спочатку ініціалізує графічний режим, підключаючи BGI
драйвер EGAVGA.BGI
, потім запускає електронну титульну сторінку курсової роботи, потім будує графік функції, корені якої нам потрібно знайти, використовуючи метод хорд знаходить корінь на вказаному з клавіатури проміжку з вказаною точністю, демонструє метод хорд графічно та зрештою виводить головне меню на екран. Після цього програма очікує вибору користувача.
Тепер перейдемо до додаткових модулів. Модуль tytulka.cpp містить лише одну функцію void tytulka(), що виводить на екран електронну титульну сторінку розробника курсової роботи. Алгоритм роботи дуже простий, такій як і void avtor(): очистка екрану -> задання кольору -> отримання розмірів екрану -> замальовування екрану вибраним кольором -> задання кольору та стилю тексту -> вивід тексту на екран.
Модуль grafik.cpp містить функцію void grafik(), що будує Декартову систему координат та графік функції на ній. Алгоритм роботи теж подібний до алгоритму функції void avtor(), але є додатково цикл обчислення значення функції.
Модуль HORD.CPP містить дві функції: double f (double x) – обчислення значення вказаної в завданні функції для певного значення х, void Hord() – реалізація чисельного методу знаходження кореня рівняння на вказаному проміжку з вказаною точністю. Проміжні результати виконання записуються у файли KORENI.TXT та MEGI.TXT.
Алгоритм наступний:
ввід інтервалу (a
; b
) та потрібної точності (D)
якщо fnk(a)*fnk2 (a)>0 то x=a
інакше x=b
і=0
початок циклу
x1=x-fnk(x)/fnk1 (x)
i++
n=100
якщо
i>=n
то кількість ітерацій більше за «n»
Вихід.
Якщо ні, то
х= x1=x-fnk(x)/fnk1 (x)
вивід на екран результатів
і запис необхідних результатів у файли:
«KORENI.TXT», «MEGI.TXT».
Модуль Show.cpp містить одну функцію void Show(), що графічно демонструє роботу функції void Hord (), використовуючи проміжні результати виконання, що записані у файли KORENI.TXT та MEGI.TXT. Алгоритм роботи дуже простий і подібний до алгоритму функцій void avtor() та void tytulka().
Алгоритми всіх функцій у вигляді блок-схем подані в додатку.
4. Розробка та виконання тестового прикладу
Запускаємо на виконання виконавчий файл нашого проекту. Спочатку бачимо зображення електронної титульної сторінки (рисунок 4.1).
Рисунок 4.1 – Зображення електронної титульної сторінки
Програма чекає, поки буде натиснута довільна кнопка. Що ми і робимо. З’являється графік функцій (рисунок 4.2)
Нам потрібний проміжок, де функція перетинає ОХ.
Знову натискаємо довільну кнопку. З’являється вікно із запитом на введення даних (рисунок 4.3). Вводимо послідовно значення межі проміжку та похибки. Отримаємо:
a=0
b=1
eps=0.01
korin rivnjannja 0.500253
kilkist iteratsij 2
Рисунок 4.2 – Графік функцій
Рисунок 4.7 – Інформація про автора
Рисунок 4.3 – Вікно із запитом на введення даних
а=0
b=2
eps=0.01
korin rivnjannja 1.060973
kilkist iteratsij 1
Як бачимо, кількість ітерацій зменшилась.
Перевіримо, чи записано у файл проміжні результати рисунок (4.4)
Рисунок 4.4. – Проміжні результати
Дані записано нормально.
Після отримання числових результатів натискаємо довільну кнопку і переходимо до наступного вікна (рисунок 4.5), яке демонструє графічно реалізацію метода.
Рисунок 4.5 – Вікно демонстрації реалізації метода хорд
Дані для x, a та b завантажуються з текстових файлів KORENI.TXT та MEGI.TXT, точки будуються відповідно до цих даних. Після кожного натиснення будь-якої клавіші зчитуються наступні дані, аж поки не знайдемо значення x із заданою точністю.
Після натискання довільної кнопки переходимо до меню користувача (рисунок 4.6).
Натиснувши «7» – вийдемо з програми, обравши «6» побачимо вікно з інформацією про автора програми, «5» програма запускається заново, «4» запускається демонстрація роботи методу, «3» запускається введення даних, «2» запускається вікно з графіком, «1» запускається титульна сторінка.
Натиснувши довільну кнопку знову переходимо до вікна меню користувача.
Рисунок 4.6
5. Інструкція користувача
Для запуску програми потрібно зайти в папку Kursova і запустити на виконання файл KURSAK.EXE. Для вірної роботи програми у тій же папці має бути файл-драйвер EGAVGA.bgi.
Дана програма може працювати під управлінням операційної системи сімейства Windows, починаючи від версії 95 та під управлінням ОС MS-DOS.
Мінімальні системні вимоги для коректної роботи програми:
– операційна система Windows 95, Windows 98 або MS-DOS;
– процесор – не менше 8038 б;
– оперативної пам’яті – 512 Кб;
– відеокарта – 16 біт;
– вільного місця на жорсткому диску – 2Мб.
Після запуску програми спочатку бачимо зображення електронної титульної сторінки. Програма чекає, поки буде натиснута довільна кнопка. Що ми і робимо. З’являється графік функцій. Знову натискаємо довільну кнопку. З’являється вікно із запитом на введення даних. Вводимо послідовно значення межі проміжка та похибки. Отримаємо результати: корінь рівняння та кількість ітерацій.
Після отримання числових результатів натискаємо довільну кнопку і переходимо до наступного вікна яке демонструє графічно реалізацію метода. Дані для x, a та b завантажуються з текстових файлів KORENI.TXT та MEGI.TXT, точки будуються відповідно до цих даних. Після кожного натиснення будь-якої клавіші зчитуються наступні дані, аж поки не знайдемо значення x із заданою точністю. Після натискання довільної кнопки переходимо до меню користувача (рисунок 4.6).
Натиснувши 7 – вийдемо з програми, а обравши 6 побачимо вікно з інформацією про автора програми (Рисунок 4.7). На інші кнопки програма не реагує. Натиснувши довільну кнопку знову переходимо до вікна меню користувача.
Висновки
Під час виконання даної курсової роботи ми удосконалили свої знання в мові програмування С++. Для знаходження теоретичного і практичного матеріалу використовувався Інтернет, також довідники з програмування.
Серед недоліків програми слід відмітити недостатність у візуальному оформленні, хоча середовище програмування і не дає широких можливостей для цього. Серед переваг помічаємо такі характеристики програми, як швидкодія, легкість у користуванні та невеликі розміри виконавчого файлу.
До недоліків програми можна віднести недосконалість візуального оформлення, яке обмежене 16 кольорами, а також робота програми в DOS режимі.
У пояснювальній записці розглянуто інші математичні способи знаходження коренів рівнянь, а також опис виконаної програми.
Перелік літератури
1. Глинський Я.М., Анохін В.Є., Ряжська В.А. С++ і С++ Builder. Навч. посібн. 3-тє вид. – Львів: СПД Глинський, 2006. – 192 с.
2. Пахомов Б.И. С/С++ и Borland C++ Builder для студента. – Спб.: БХВ-Петербург, 2006. – 448 с.
3. С/С++. Программирование на языке высокого уровня / Т.А. Павловская. СПб.: Питер, 2002. – 464 с
4. Сборник часто задаваемых вопросов и ответов к ним по компиляторам языков Си и C++ http://soft.munic.msk.su/
5. Уоррен Г.С. Алгоритмические трюки для программистов. – М.: Изд.дом «Вильямс», 2003
6. Шилдт Г. Теория и практика С++. – СПб.: BHV, 1996.
Додаток
Як зазначалося вище, наш проект складається з 6 додаткових модулів, та основного модуля, в якому міститься головна функція main() нашого проекту. Додаткові модулі не зв’язані один з одним, а лише з головним модулем.
Єдиним зв’язком (неявним) між модулями dyhotom.cpp та demon.cpp є спільне використання файлів KORENI.TXT та MEGI.TXT.
Загальна схема проекту із способами взаємодії між модулями наведена на рисунку 2.1.
Рисунок 2.1 – Загальна схема проекту