Вступ
Математичнемоделювання займає вагоме місце серед інших програм які створюютьсяпрограмістами. Під таким моделюванням розуміють сукупність математичнихспіввідношень таких як формули, рівняння, логічні вирази, які визначаютьхарактеристики і властивості системи, об’єкта, процесу або ж їх витікаючих, такожфункціонування залежно від параметрів компонентів, початкових умов, вхідних зміні часу. Загалом математична модель описує функціональну залежність міжвихідними залежними змінними, через які відображається функціонування системи,незалежними і змінюваними змінними а також вхідними змінами, які мали вплив на систему.
Дляокремого завдання формулюється окрема незалежна математична задача. В загальнихвипадках, коли функціональна залежність для множини вхідних даних що виступаютьяк множина аргументів, задана неявно, за допомогою математичної моделінеобхідно визначити множину вихідних залежних змінних, що виступають як множинизначень функцій. При цьому відповідно до виду математичної моделі розрізняютьтакі базові типи математичних задач: розв’язання системи лінійних рівнянь, алгебраїчнихрівнянь, апроксимація, інтегрування, диференціювання, системи диференційнихрівнянь і ін. На сьогодні, більшість громіздких і трудоємких робіт пообчисленню різноманітних функцій і виразів, покладається на комп’ютер, але дляпростішого його використання потрібна програма, тобто зв’язний алгоритм дій,який має створити програміст.
Фізика,хімія, біологія, астрономія, геометрія та багато інших наук використовуютьспеціальні програми призначені для підрахунку величин в залежності від різнихвхідних даних, на основі математичних задач.
Данакурсова робота описує один з типів такого моделювання, а саме розв’язаннюнелінійних алгебраїчних рівнянь. Для розв’язання даного рівняння було обрано методхорд.
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
/>. (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
Програмаспочатку запускає електронну титульну сторінку курсової роботи, потім будуєграфік функції, корені якої нам потрібно знайти, використовуючи метод хорд знаходитькорінь на вказаному з клавіатури проміжку з вказаною точністю, демонструє методдихотомії графічно та зрештою виводить головне меню на екран. Всі ці дії, крімвиводу головного меню на екран, виконуються лише запуском відповідних функцій здодаткових модулів. Крім того, функція void main() ініціалізує графічний режим,підключаючи BGI драйвер EGAVGA.BGI.
Уголовному модулі оголошено такі локальні змінні: int k=0 – для збереженняпункту головного меню, яке обирає користувач, int gdriver = DETECT, gmode,errorcode – додаткові змінні для ініціалізації графічного режиму.
Теперперейдемо до додаткових модулів.
МодульTUTYLKA.CPP містить лише однуфункцію що виводить на екран електронну титульну сторінку розробника курсовоїроботи. Оголошено такі локальні змінні: int a=5 – значення відступів від краюекрану до рамки, xmax=getmaxx(), ymax=getmaxy() – значення роздільної здатностіекрану у
inti; – лічильник циклу;
floatx1, x2, y1, y2, xx1, xx2, yy1, yy2; – містять координати точок на площині.
МодульHORD.CPP містить дві функції: double f (double x) – обчислення значеннявказаної в завданні функції для певного значення х, void Hord () – реалізаціячисельного методу знаходження кореня рівняння на вказаному проміжку з вказаноюточністю. Оголошено такі локальні змінні:
FILE*fp1,*fp2; – вказівники на файли, що містять проміжні результати обчислень;
intk=0; – лічильник ітерацій;
doublea, b, c, epsilon; – межі проміжку, середина проміжку та точність.
МодульShow.CPP містить одну функцію void Show (), що графічно демонструє роботуфункції void Hord (). Оголошено такі локальні змінні:
intxmax=getmaxx(), ymax=getmaxy(); – значення роздільної здатності екрану уграфічному режимі;
floatx, 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. Алгоритм роботи дуже простий і подібний до алгоритму функцій voidavtor() та void tytulka().
Алгоритмивсіх функцій у вигляді блок-схем подані в додатку.
4.Розробка та виконання тестового прикладу
Запускаємона виконання виконавчий файл нашого проекту. Спочатку бачимо зображенняелектронної титульної сторінки (рисунок 4.1).
/>
Рисунок4.1 – Зображення електронної титульної сторінки
Програмачекає, поки буде натиснута довільна кнопка. Що ми і робимо. З’являється графікфункцій (рисунок 4.2)
Нам потрібнийпроміжок, де функція перетинає ОХ.
Зновунатискаємо довільну кнопку. З’являється вікно із запитом на введення даних(рисунок 4.3). Вводимо послідовно значення межі проміжку та похибки. Отримаємо:
a=0
b=1
eps=0.01
korinrivnjannja 0.500253
kilkistiteratsij 2
/>
Рисунок4.2 – Графік функцій
/>
Рисунок4.7 – Інформація про автора
/>
Рисунок4.3 – Вікно із запитом на введення даних
а=0
b=2
eps=0.01
korinrivnjannja 1.060973
kilkistiteratsij 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++ soft.munic.msk.su/
5. Уоррен Г.С. Алгоритмическиетрюки для программистов. – М.: Изд.дом «Вильямс», 2003
6. ШилдтГ. Теория ипрактика С++. – СПб.: BHV, 1996.
Додаток
Якзазначалося вище, наш проект складається з 6 додаткових модулів, та основного модуля, вякому міститься головна функція main() нашого проекту. Додаткові модулі незв’язані один з одним, а лише з головним модулем.
Єдинимзв’язком (неявним) між модулями dyhotom.cpp та demon.cpp є спільне використанняфайлів KORENI.TXT та MEGI.TXT.
Загальнасхема проекту із способами взаємодії між модулями наведена на рисунку 2.1.
/>
Рисунок2.1 – Загальна схема проекту