Контрольная работа по "Программированию и компьютерам"

ЗМІСТ

1.   Завдання…...………………………………………………...…………………3

2.   Вступ …………………………………………………………...……………...4

3. Теоретична частина…………………………………………..………….…….5
1. Метод Ньютона…………………………………………………………..…….5
2. Метод хорд…………………………………………………………………….6
3. Метод простих ітерацій………………………………………………………7
4. Метод послідовних кроків……………………………………………………7
4. Практична частина…………..………...………………….…………………..8
1. Блок-схема……….…..………………………………………………………..8

4.2. Контрольний приклад………………………………………………………13

4.3 Дослідження ефективності  методів………………..……………………….15

5.  Висновки…………………………..………………………………………….16

6.   Перелік посилань…………………………………………………………….17

7.  Додаток………………………………………………………………………..18

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1.Завдання

Розробити алгоритм і програму, що реалізують методи дотичних(Ньютона), хорд та простих ітерацій. Попередні значення коренів рівняння знайти за допомогою методу послідовних кроків (в загальному виді).

Побудувати блок-схему  алгоритму і зробити описання його блоків. Алгоритм повинен в  діалоговому режимі передбачати  вибір методу.

Порівняти ефективність методів (на прикладі алгебраїчних і трансцендентних рівнянь 10cosx-0.1x²=0, x⁴-x³-4x²+34x-120=0).

Побудувати блок схему  алгоритму програми на екрані комп’ютера.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

  

 

 

 

2.Вступ

Чисельні методи є потужним математичним апаратом для вирішення майже будь-яких задач.

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

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

 Данна робота присвячена  розробці програмного забезпечення  для числового розв¢язання алгеброічних і трансендентних рівняннь та дослідження ефективності використання методів.

 

 

 

 

 

 

 

 

 

 

 

 

 

       3. Теоретична частина

Чисельне рішення алгеброічних і трансендентних рівняннь виду ¦ = 0 розбивається на декілька етапів:

1. Дослідження кількості, характеру і розташування коренів рівняння.
2. Виділення цікавлячих нас і знаходження наближено їх розв¢язку.
3. Знаходження коренів з заданою точністю. 

       3.1Метод Ньютона  (метод дотичних).

                                                                                                                ¦

                                                                                                ¦   

                                                                                            

                                                                            ¦

                                                                                    

                                                 ¦

0                                                                                                            

 

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

   Дотичну в точці можна побудувати з допомогою похідної df(X_i)/dX . Роздивимось трикутник ¦ ,   i  , з нього слідує:  

                 d¦ /d = ¦¢ = ¦ / -

   Після простих перетворень отримуємо формулу метода Ньютона:

                 = - ¦ /¦¢      

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

3.2  Метод хорд.

                                                                                                        ¦

 

 

 

                                                              

0                                                                                                                                                       

                                         

          ¦               ¦

 

     

    Пошук точки, в якій функція ¦ =0 обертається в нуль, починається з того, що через дві точки, що лежать на графіку функції ¦ , проводять пряму. Точку перетину цієї прямої з віссю приймають за нове значення . Такі побудови дають набір променів:

                    ¦ -0 / - = ¦ -0 / -

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

 

3.3  Метод простих ітерацій.

    Y

 

            =j                    

                                                 =

 

 

 

 

0                                                                                               X  

   Метод простих ітерацій заснований  на представленні рівняннь:

     F = 0  у вигляді = ¦ і багатократному застосуванні ітераційної формули = ¦ до тих пір, доки не стане виконуватись умова       | - |£ , де - задана точність. Ітераційний процес збігається при  n , якщо виконується умова ¦¢ < 1 при a< <b, де [a,b] межі на якому знаходиться корінь.

   Метод послідовних кроків.

Ідея  методу така: ділимо відрізок на якому  знаходиться корінь рівняння виду F =0 на n частин з кроком h.

      , ,….. , ,…… .

   А потім перевіряємо умову F ´F <0 і якщо |b-a|< то задача вирішена.

 

4.1. Блок-схема

Блок-схема алгоритму програми.

                                               

 

          

                     

           

 

                  

 

                       

                                        

 

Після запуску програми (1) на екрані з¢являються попередні значення коренів рівняння (2). Користувачеві потрібно ввести відрізок на якому буде вестися пошук кореня рівняння (3). Далі користувач вибирає метод за допомогою якого будуть знайдені корені рівняння (4). Після цього цього йде реалізація даного методу (5). Програма виводить корені на екран (6) після чого завершує свою роботу (7).

 

 

    Блок-схема до  методу Ньютона:

                  

 

 

 

 

                                                                                                              ні                            

                                                                   

                                                     так

 

 

 

Після запуску програми (1) користувач задає початкове наближення (2). Потім  розраховуємо значення функції і  значення похідної в заданій точці (3). Потім йде підстановка у  формулу Ньютона (4) і перевіряємо  чи різниця між розрахованим коренем і початковим не є величиною меншою за задану точність (6). Якщо ця різниця більша то значеню початкового наближеня присвоюємо значення розрахованого кореня (5), якщо ж ця різниця менше то виводимо корінь на екран (7), після цього програма завершує роботу (8).

 

 

  

Блок-схема до методу хорд.

            

 

 

 

 

 

                                                                                                                 Ні 

                                                     Так

 

 

 

Після початку програми (1), користувач задає два значення та (2). Для обох вибраних розраховуємо значеня функції (3) і підставляємо отримані значеня в формулу методу (4). Потім проводиться порівняння останніх значень (5), якщо вони близькі то виводимо корінь на екран (7), якщо ж ні то значенння присвоюємо змінній після того, як її значення було присвоєно змінній (6). Змінна має тепер значення кореня рівняння, після цього програма завершує роботу (8).

  

 

Блок схема до методу простих  ітерацій.

                                                         

 

 

 

 

                                                                                                                 Ні

                                                     Так           

 

 

  Після початку програми (1) користувач вводить початкове значення (2). Підраховуємо значення функції в заданій точці (3). Перевіряємо чи різниця між значеннями ¦ і не є меншою від заданої точності (4). Якщо вона менша то виводимо значення кореня на екран (6), а якщо більша то присвоюємо значення ¦ (5) і повторюємо процедуру спочатку. Після чого програма завершує роботу (7).

 

 

 

 

 

  

 

Блок-схема до методу послідовних  кроків.

 

 

                     Ні                                                                      Так

А=А+Н 

 

                                                                                                          Ні

Так

 

 

 

 

Після початку програми (1) користувач вводить відрізок пошуку кореня і кількість частин розбиття (2). Після цього йде перевірка добутку значень функції у двох сусідніх точках (3), якщо це значення менше 0, то даний відрізок буде новим наближенням (5). Якщо ні то треба розглянути відрізок, що залишився (3). Коли відрізок стане меншим за точність (6) то відбувається виведення кореня на екран (7) після чого програма закінчує роботу (8).

 

     

      4.1. Контрольний приклад.

У якості контрольного прикладу нам дано трансендентне рівняння: 10cosx-0.1x²=0 корінь Х=

Рішення цього рівняння ми розбили  на декілька етапів: 

1. Дослідження кількості коренів та їх розташування.
2. Визначення коренів з заданою точністю.

   Á Î [a,b] - наближений інтервал

     e - задана точність

Загальний розв¢язок було знайденно за допомогою методу послідовних кроків.

Запуск програми

Введіть відрізок [a,b]

a=1, b=2

Введіть кількість відрізків розбиття N

N = 100                    

1

1,01

1,02

1,03

1,04

1,05

1,06

1,07

1,08

1,09

1,1

1,11

1,12

1,13

1,14

1,15

1,16

1,17-корінь

Отже попереднє значення кореня знайденого за допомогою методу послідовних кроків дорівнює 1,17

 

4.3.   Дослідження ефективності  методів

Для трансендентних рівнянь в результаті дослідження методів, найефективнішим  виявився метод Ньютона. Для досягнення точності e=10^-8 потрібно 4 ітерації при вдалому початковому наближені і 5-6 при недуже вдалому.