Ім'я файлу: kursova.doc
Розширення: doc
Розмір: 982кб.
Дата: 22.05.2020
Пов'язані файли:
MatLab_lab4.docx

Державний вищий навчальний заклад

«Прикарпатський національний університет імені Василя Стефаника»

Кафедра інформатики

КУРСОВА РОБОТА

«Деякі наближення методи розв’язування алгебрагічних і трансцендентних рівнянь та системи лінійних алгебрагічних рівнянь»


Виконала

студентка групи ПМ-31

Лисканюк І.І

Керівник:

Доц.Василишин П.Б

Національна шкала: ______________

Університетська шкала: ___________

Оцінка ECTS: ____

Івано-Франківськ – 2018

Зміст

Вступ 3

1. Теоретична частина 5

1.1. Метод Гауса 5

1.2 Компактна схема Гауса 9

1.3 Практична реалізація 12

2. Метод хорд 15

2.1 Постановка задачі 15

2.2 Відокремлення коренів. Теорема про оцінку похибки наближеного значення кореня 16

2.3 Метод хорд 18

2.4 Практична реалізація 21

Висновки 29

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



Вступ



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

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

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

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

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




1.1. Метод Гауса



Метод Гауса (або метод послідовного виключення невідомих) застосовний для розв’язання систем лінійних рівнянь, в яких число невідомих може бути або рівно числу рівнянь, або відмінно від нього.

Система т лінійних рівнянь з п невідомими має вигляд:

x1, x2., xn – невідомі.

ai j - коефіцієнти при невідомих.

bi - вільні члени (або праві частини)

Система лінійних рівнянь називається сумісною, якщо вона має розв’язок, і несумісною, якщо вона не має розв’язків.

Сумісна система називається визначеною, якщо вона має єдине розв’язок і невизначеною, якщо вона має незліченну безліч розв’язків.

Дві сумісні системи називаються рівносильними, якщо вони мають одну і ту ж множину розв’язків.

До елементарних перетворень системи віднесемо наступні:

  1. зміна місцями два будь-яких рівнянь;

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

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

Елементарні перетворення переводять систему рівнянь в рівносильну їй.

Для простоти розглянемо метод Гауса для системи трьох лінійних рівнянь з трьома невідомими у разі, коли існує єдиний розв’язок:

Дана система:
(1)
1-й крок методу Гауса.

На першому кроці виключимо невідоме х1 зі всіх рівнянь системи (1), окрім першого. Хай коефіцієнт . Назвемо його провідним елементом. Розділимо перше рівняння системи (1) на а11. Отримаємо рівняння:
(2)

де
Виключимо х1 з другого і третього рівнянь системи (1). Для цього віднімемо з них рівняння (2), помножене на коефіцієнт при х1 (відповідно а21 і а31).

Система прийме вигляд:
(3)
Верхній індекс (1) указує, що мова йде про коефіцієнтах першої перетвореної системи.

2-ий крок методу Гауса. На другому кроці виключимо невідоме х2 з третього рівняння системи (3).

Хай коефіцієнт . Виберемо його за провідний елемент і розділимо на нього друге рівняння системи (3), отримаємо рівняння:
(4)
де
З третього рівняння системи (3) віднімемо рівняння (4), помножене на Отримаємо рівняння:

Припускаючи, що знаходимо:

В результаті перетворень система прийняла вигляд:
(5)
Система вигляду (5) називається трикутною.

Процес приведення системи (1) до трикутного вигляду (5) (кроки 1 і 2) називають прямим ходом методу Гауса.

Знаходження невідомих з трикутної системи називають зворотним ходом методу Гауса.

Для цього знайдене значення х3 підставляють в друге рівняння системи (5) і знаходять х2. Потім х2 і х3 підставляють в перше рівняння і знаходять х1.

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

Звідси інша назва методу Гауса – метод послідовного виключення невідомих.

Якщо в ході перетворень системи виходить суперечливе рівняння вигляду 0 = b, де b  0, то це означає, що система несумісна і розв’язків не має.

У разі сумісної системи після перетворень по методу Гауса, складових прямий хід методу, система т лінійних рівнянь з п невідомими буде приведена або до трикутного або до ступінчастого вигляду.

Трикутна система має вигляд:

Така система має єдине рішення, яке знаходиться в результаті проведення зворотного ходу методу Гауса.

Ступінчаста система має вигляд:


Така система має незліченну множину розв’язків. Щоб знайти їх, у всіх рівняннях системи члени з невідомими хk+1., xk переносять в праву частину. Ці невідомі називаються вільними і надають їм довільні значення. З отриманої трикутної системи знаходимо х1., xk, які виражатимуться через вільних невідомих.

1.2 Компактна схема Гауса



Якщо обчислення по схемі єдиного ділення ведуться за допомогою обчислювальних машин, то багато часу затрачається на запис проміжних результатів. Компактна схема Гауса дає економний спосіб запису. Розглянемо порядок складення схеми для системи:

Всі результати обчислення будемо записувати в одну таблицю (Таблиця 1)



Компактна схема Гауса. Таблиця 1.
Порядок заповнення таблиці.

Прямий хід.

  1. Записуємо коефіцієнти даної системи в чотирьох рядках і п’яти стовпцях розділу І таблиці 1.

  2. Додаємо всі коефіцієнти по рядку і записуємо суму в стовпчик (стовпчик контролю), наприклад .

  3. Ділимо всі числа, які стоять в першому рядку, на і результати записуємо в п’ятому рядку розділу І.

  4. Обчислюємо і робимо перевірку. Якщо обчислення ведуться з постійним числом знаків після коми, то числа і не повинні відрізнятися не більше ніж на одиницю останнього розряду. В іншому випадку потрібно перевірити дії пункту 3).

  5. По формулам (2.4) обчислюємо коефіцієнти:



Результати записуємо в перші три рядки розділу ІІ.

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

  2. Ділимо всі елементи першого рядка розділу ІІ на і результати записуємо в четвертому рядку розділу ІІ.

  3. Робимо перевірку, як в пункті 4).

  4. За формулами (2.7) обчислюємо Результати записуємо в перші два рядки розділу ІІІ.

  5. Робимо перевірку, як в пункті 6).

  6. Ділимо елементи першого рядка розділу ІІІ на і знаходимо числа . Всі результати записуємо в третьому рядку розділу ІІІ.

  7. Робимо перевірку.

  8. Обчислюємо . Результати записуємо в розділі IV.

Обернений хід.

  1. В розділі V записуємо одиниці, як це показано в таблиці 1.

  2. Обчислюємо

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

Таким чином,
.


  1. Обчислюємо , для чого використовуємо елементи поміченого рядка розділу ІІ:





  1. Обчислюємо , для чого використовуємо елементи поміченого рядка розділу І:

Аналогічно проводиться обернений хід в контрольній системі. Розв’язок цієї системи повинен відрізнятися від розв’язку даної системи на 1 (з точністю до одиниці останнього розряду):

Цей контроль здійснюється за допомогою стовпця

1.3 Практична реалізація


Для реалізацій поставленої задачі використовували табличний процесор EXCEL. Результати роботи представлені у наступній таблиці:















вільні члени

контрольні суми

x1

x2

x3

x4







30.1

-1.4

10

-1.5

10

47.2

-17.5

11.1

1.3

-7.5

1.3

-11.3

7.5

-21.1

7.1

-17.1

10

-13.6

2.1

2.1

3.5

3.3

1.7

12.7



















1.0000

-0.0465

0.3322

-0.0498

0.3322

1.5681

0.0000

10.2860

7.1140

-8.3721

7.1140

16.1419

0.0000

-20.7512

4.6083

-16.7262

7.5083

-25.3608

0.0000

2.1977

2.8023

3.4047

1.0023

9.4070



















 

1.0000

0.6916

-0.8139

0.6916

1.5693




0.0000

18.9601

-33.6162

21.8601

7.2039




0.0000

1.2824

5.1934

-0.5176

5.9582



















 

 

1.0000

-1.7730

1.1530

0.3800







0.0000

7.4671

-1.9961

5.4709




























1.0000

-0.2673

0.7327



















x1=

x2=

x3=

x4=







0.0935

0.0044

0.6790

-0.2673








Для даної системи рівнянь отримано розв’язок:


2. Метод хорд

2.1 Постановка задачі



Нехай задано рівняння з однією змінною
F(x)=0,
де функція F(x) визначена і неперервна на деякому проміжку [а; b].

Розв'язати рівняння означає знайти множину його коренів, тобто таких значень xє[а; b], при яких рівняння (1.1) перетвориться в тотожність. Корінь рівняння (1.1) називають ще нулем функції F(x). Якщо функція - алгебраїчний многочлен, то рівняння (1.1) називається алгебраїчним. Якщо функція F(x) містить тригонометричні, показникові або логарифмічні функції, тоді рівняння (1) називають трансцендентним.

Знайти точні значення коренів заданого рівняння можна лише для найпростіших функцій F(x): алгебраїчних многочленів не вище четвертого степеня, деяких многочленів степеня n ≥ 5 і деяких трансцендентних функцій.

Універсальних методів для знаходження точних значень коренів алгебраїчних рівнянь степеня п = 5 і трансцендентних рівнянь не існує. Крім того, розв'язуючи практичні задачі, часто дістають рівняння з коефіцієнтами, які є наближеними числами. Тоді постановка задачі знаходження точних коренів не має смислу. Тому важливого значення набувають наближені методи знаходження коренів рівняння з достатньою для практики точністю. Задача знаходження коренів рівняння (1.1) вважається розв'язаною, якщо корені обчислені із наперед заданою точністю.

Нехай х* - точний корінь, а - його наближене значення. Кажуть, що корінь обчислено з наперед заданою точністю є, якщо | х*- | < ε. Нехай, наприклад, х*є[а; b] і b-a < ε, тоді числа а і b - наближені значення кореня х* відповідно з недостачею і надлишком з точністю є. У цьому випадку за наближене значення з точністю є можна взяти будь-яке число з відрізка [а; b].

Знаходження наближених коренів рівняння (1) складається з двох етапів:

1) відокремлення коренів, тобто знаходження досить малих відрізків, на кожному з яких міститься один і тільки один корінь рівняння;

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

Корені рівняння (1) можуть бути дійсними і комплексними. Далі розглянуто наближені методи обчислення тільки дійсних коренів рівняння (1.1).

2.2 Відокремлення коренів. Теорема про оцінку похибки наближеного значення кореня



Корінь x* рівняння (1.1) вважається відокремленим на відрізку [а; b], якщо х*є[а;b] і на цьому відрізку дане рівняння не має інших коренів. Щоб відокремити корені рівняння (1.1), треба розбити область визначення даного рівняння на проміжки, на кожному з яких міститься один і тільки один корінь або немає жодного кореня. Відокремлюють корені графічним і аналітичним методами, а також методом послідовного перебору.

Для відокремлення коренів графічним методом будують графік функції у=F(х) і знаходять точки перетину графіка з віссю абсцис та кінці відрізків ізоляції коренів.

Аналітичний метод відокремлення коренів ґрунтується на теоремах з курсу математичного аналізу. Сформулюємо їх.

Теорема 1 (теорема існування кореня). Якщо функція неперервна на [а;b] і набуває на кінцях цього відрізка значень протилежних знаків, тобто F(a)F(b)<0, то всередині відрізка [а;b] існує хоча б один корінь рівняння F(х)=0.

Зазначимо, що теорема не дає відповіді на питання про кількість коренів рівняння (1.1), які належать [a; b]. При виконанні умов теореми рівняння може мати й кілька коренів. На рис. 1.1 зображено графік функції у = F(х), яка задовольняє усі вимоги теореми 1 і має на [a;b] чотири нулі. У досить малому околі точки xз теорему існування кореня застосувати не можна, бо при переході зліва направо через точку x3 знак функції F(х) не змінюється. Точка хз - кратний корінь рівняння (1.1) і його не можна відокремити, користуючись теоремою 1. Тому далі вважатимемо, що F'(х)≠ 0 для всіх х є [а; b].

Теорема 2 (теорема існування і єдиності кореня). Якщо функція F(x), неперервна і диференційована на [а; b], набуває на кінцях цього відрізка значень різних знаків, а похідна F'(x) зберігає сталий знак всередині відрізка [а; b], то рівняння F(х) = 0 на цьому відрізку має корінь, причому єдиний.

У відповідності з теоремами 1 і 2 алгоритм відокремлення коренів рівняння (1) можна сформулювати так:

1. Знайти область визначення рівняння.

2. Знайти критичні точки функції F(х).

3. Записати інтервали монотонності функції F(х).

4. Визначити знак функції F(х) на кінцях інтервалів монотонності.

5. Визначити відрізки, на кінцях яких функція F(х) набуває значень протилежних знаків.

6. Знайдені відрізки ізоляції коренів при необхідності звузити.

2.3 Метод хорд



Метод хорд - один з поширених ітераційних методів. Його ще називають методом лінійного інтерполювання, методом пропорційних частин. Нехай задано рівняння f(х) = 0, де f(х) на відрізку [а;b] має неперервні похідні першого й другого порядків, які зберігають сталі знаки на цьому відрізку, і f(a) f(b) < 0, тобто корінь х* рівняння відокремлений на [а;b].

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

Нехай для визначеності f(x) > 0. f'(x) > 0, f(a) < 0. f(b) > 0 (рис. 1.4, а). Візьмемо за початкове наближення шуканого кореня х* значення x0= а. Через точки A0 і В проведемо хорду

і за перше наближення кореня х* візьмемо абсцису x1 точки перетину хорди з віссю Ох. Поклавши y=0, х=x1одержуємо

або

Новий відрізок, що відокремлює корінь, можна визначити, порівнюючи знаки f (а), f (x1) і f (b). Очевидно, що точка x1 ближче до точки х*, чим а, якщо у'у" > 0 (див. рис. 7.4,а), і відрізком, що відокремлює корінь, буде [х1,b] ,у противному випадку, якщо у'у" < 0 (див. рис.1.4, в), відрізком, що відокремлює корінь, буде [а,х1].

Абсциса х2 точки перетину хорди А1В буде другим наближенням кореня. Продовжуючи цей процес необмежено, дістанемо послідовність х0, х1, х2, ..., хn, ... наближених значень кореня х* даного рівняння.

Для хк+1, якщо у'(х)у"(х) > 0 маємо:
к=0,1,2,…
Якщо у'(х)у"(х) < 0 , то для хк+1 можна записати формулу
, к=0,1,2,…
Достатні умови збіжності методу хорд дає така теорема.

Теорема. Нехай на відрізку [а;b] функція f(x) неперервна разом із своїми похідними до другого порядку включно, причому f(a)f(b) < 0, а похідні f'(x) і f''(х) зберігають сталі знаки на [а;b], тоді існує такий окіл кореня х* рівняння f(x)=0, що для будь-якого початкового наближення х0 з цього околу послідовність [хk], обчислена за формулою (1.5) або (1.6), збігатиметься до кореня х*.

Для оцінки похибки можна скористатися формулою
,

де M1= , m1= .
Отже, корінь х* рівняння f(x) =0 буде знайдено методом хорд із наперед заданою точністю є , якщо для двох послідовних наближень хk.і хk-1 справджуватиметься нерівність
.

Блок-схема реалізації методу хорд:



2.4 Практична реалізація


Для розв’язання методом хорд використаємо інтерактивне середовище PYTHON 3.6. У даному середовищі повинні бути встановлені додаткові пакети: sympy та matplotlib.

Це можна зробити якщо перейти у папку де знаходиться Python, і далі в папці Scripts з терміналу/консолі запустити команди
pip install sympy

pip install matplotlib
Наступний текст програми реалізує наближений метод розв’язання рівняння з представленням графіка функції.



Реалізація даної програми



Отримали першу та другу похідні і відповідно графічне представлення нашого графіка у діапазоні [-5, 5 ].



Оскільки розглядається функція tg(0.3 * x + 0.4) яка має сингулярності то і значення на осі ординат приймають величезні значення. Тому необхідно змінити проміжок дослідження і тим самим ми намагаємося виділити корінь даного рівняння.




З даного графіку можна виділити корінь. Зокрема видно що графік перетинає вісь ординат поблизу х=1. Для виділення кореня виберемо діапазон [0, 3 ].





Графік перетинає вісь тільки один раз, тобто корінь виділений.



Ми тримали розв’язки двома методами і вони дають однакові результати в межах похибки.
Аналогічно проводимо розрахунки і для іншого рівняння



Проведемо виділення кореня рівняння



І відповідно графік функції


З графіка видно що у даному діапазоні міститься єдиний корінь рівняння який будемо визначати:


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


Висновки



В курсовій роботі було детально розглянуто такі питання відшукання розв’язків системи рівнянь. Для відшукання було використано метод Гауса. Реалізація даного методу привела нас до використання табличного процесора EXCEL. У даному середовищі проведено розрахунок для системи чотирьох рівнянь і представлені відповідні результати.

Також у курсовій роботі було детально розглянуто такі питання: відокремлення коренів; теорема про оцінку похибки наближеного значення кореня; уточнення кореня методом поділу відрізка пополам; метод хорд.

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

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


  1. Г.Н.Воробьева, А.Н. Данилова. Практикум по вычислительной математике – Москва «Высшая школа», 1990.

  2. Л.И.Турчак. Основы численных методов – Москва «Наука», 1987.

  3. Фельдман Л.П., Петренко А.І., Дмитрієва О.А. Чисельні методи в інформатиці – Київ «Питер», 2006.

  4. Барковський В.В., Барковська Н.В. Математика для економістів: Вища математика. - К.: Національна академія управління, 1997.

  5. Завало С.Т., Костарчук В.М., Хацет Б.І. Алгебра і теорія чисел. 2 том. - К.: Вища школа, 1976. - 384 с.

  6. Каплан И.А. Практические занятия по высшей математике. - Харьков: ХГУ, 1967.

  7. Карасев А.И. и др. Курс высшей математики для экономических вузов. - М.: Высш. шк., 1982. - Ч. 1,2.

  8. Корн Г., Корн Т. Справочник по математике. - М.: Наука, 1980.

  9. Костарчук В.М., Хацет Б.І. Курс вищої алгебри. - К.: Рад. Школа, 1964. - 512 с.

  10. Кудрявцев В. А., Демидович В. П. Краткий курс высшей математики. -М.: Физматгиз, 1962,1975.

  11. Кузнецов Л.А. Сборник заданий по высшей математике (типовые расчеты).- М.: Высш. шк., 1982.

  12. Курош А.Г. Курс высшей алгебры. - М.:Наука, 1968. - 432 с.

  13. Лященко М.Я., Головань М.С. Чисельні методи : Підручник. - К.: Либідь, 1996. - 288 с.

  14. Минорский В. П. Сборник задач по высшей математике. - М.: Наука, 1969.

скачати

© Усі права захищені
написати до нас