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

Дослідження двох чисельних методів вирішення нелінійних рівнянь: половинного ділення та Ньютона. Загальний вигляд та основні властивості алгебраїчного рівняння. Теореми Декарта, Лагранжа та Гюа. Розкладення функції в ряд Тейлора, похибка методів.

Рубрика Программирование, компьютеры и кибернетика
Вид курсовая работа
Язык украинский
Дата добавления 18.09.2010
Размер файла 37,2 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

15

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

Курсова робота

з дисципліни

"Обчислювальні методи та застосування ЕОМ"

Анотація

В даній курсовій роботі проведено дослідження двох чисельних методів вирішення нелінійних рівнянь: половинного ділення та Ньютона. Дослідження проводиться на прикладі заданого нелінійного рівняння.

Зміст

  • Анотація
    • 1. Теоретичні відомості
    • 2. Практична реалізація
    • 3. Використані технічні засоби
    • 4. Опис логічної структури
    • 5. Вхідні дані
    • 6. Вихідні дані
    • 7. Інструкція користувача
    • 8. Результати обчислень
    • Висновки
    • Література
    • Додатки
    • Додаток В

1. Теоретичні відомості

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

Можна вказати ряд властивостей, застосування яких дозволяє прискорити процес вирішення задачі.

Загальний вигляд алгебраїчного рівняння:

f (x) = anxn + an-1xn-1 + … + a! x + a0 = 0 (1.1)

Властивості алгебраїчних рівнянь:

Основна теорема алгебри. Алгебраїчне рівняння порядку n має n коренів, які можуть бути як дійсними, так і комплексними.

Кожен корінь рахується стільки раз, яка його кратність.

Якщо всі коефіцієнти аі рівняння (1.1) дійсні, то всі комплексні корені утворюють комплексно спряжені пари.

3. Теорема Декарта. Число додатніх коренів дорівнює або менше числа зміни знаків в послідовності коефіцієнтів аі (те ж твердження справедливе відносно числа від'ємних дійсних коренів при заміні в (1.1) х на ()).

4. Теорема Лагранжа. Верхня границя додатніх дійсних коренів визначається як:

R = 1 + kv (B/a0), а0 > 0

де аk - перший від'ємний коефіцієнт;

В - найбільша абсолютна величини від'ємного коефіцієнту.

5. Теорема Гюа. Якщо рівняння (1.1) має дійсні корені і дійсні коефіцієнти, то:

ak2 > ak-1 ak+1,Тобто, знайшовши один корінь х1, можна розділити рівняння на (х-х1), тим самим понизивши його степінь. Однак ця процедура може привести до накопичування помилок в коефіцієнтах отриманих рівнянь, а відповідно, і в коренях.

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

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

Теорема 2. Нехай - точний, а - наближений корені рівняння f (x) = 0, що знаходяться на одному й тому ж відрізку , причому m, .

Тоді

.

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

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

Метод половинного ділення. В цьому методі спочатку обчислюються значення функції в точках, що розміщені через рівні інтервали на осі ОХ. Коли f (xn) і f (xn+1) мають протилежні знаки, знаходять xcp= (xn+1 + xn) /2 та f (xcp).

Якщо знак f (xcp) cпівпадає за знаком з f (xn), то далі замість f (xn) використовується f (xcp). Якщо ж f (xcp) має знак, протилежний до знаку f (xn), тобто співпадає зі знаком f (xn+1), то на f (xcp) замінюється це значення. Якщо f (xcp) досить близьке до 0, то обчислення припиняється. Відмітимо, що в цьому і в подальших методах в якості умови припинення ітераційного процесу часто користуються умовою е, де е - задана похибка знаходження кореня.

Структура алгоритму представлена на рис.1.1, а графічне його застосування проілюстровано на рис.1.2

Цей метод має малу швидкість збіжності. Порівнюючи з першим знайденим інтервалом, в якому є корінь, його ширина після N ітерацій зменшується в 2N раз:

Xn+1 - xn = (x2 - x1) /2N

Похибка знайденого рішення лежить в межах:

.

Метод Ньютона (дотичних). Метод Ньютона дуже широко використовується при побудові ітераційних алгоритмів. Його популярність пояснюється тим, що в відмінності від методу половинного ділення, для визначення інтервалу, в якому є корінь, не потрібно знаходити значення функції з протилежними знаками. Замість інтерполяції (наближення) по двом значенням функції в методі Ньютона виконується екстраполяція (передбачування) з допомогою дотичної до кривої в даній точці. Структура алгоритму представлена на рис.1.3, а графічна інтерпретація - на рис.1.4

В основі алгоритму лежить розкладення функції в ряд Тейлора:

f (xn + h) =f (xn) + hf' (xn) + h2f" (xn) /2 +…

Члени, які містять h в другій і в вищих степенях, відкидаються. Використовується співвідношення xn + h = xn+1. Пропонується, що перехід від хn до xn+1 наближає значення функції до нуля тим, що f (xn + h). Тоді

xn+1 = xn - f (xn) /f' (xn).

Це значення відповідає точці, в якій дотична до кривої пересікає вісь ОХ. Потім процедура повторюється, причому замість xn використовується xn+1. Обчислення припиняється при досягненні достатньо малого значення f (xn+1).

Швидкість сходження в великій мірі залежить від успішного вибору початкової точки. Якщо в процесі ітерацій тангенс кута нахилу дотичної f' (x) перетворюється в нуль, то використання методу ускладнюється. Можна також показати, що в випадку дуже великого f" (x) або кратних коренів, метод Ньютона не ефективний.

Початкове наближення х0 вибирається із умови:

(f' (x0)) 2 >f (x0) f (x0) >0.

Похибка методу визначаються порядком відкинутих членів при розкладенні в ряд Тейлора і оцінюється як:

,

де М2 -найбільше значення модуля другої похідної на відрізку [x1,x2],

т1 - найменше значення першої похідної. [1] [2]

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

Розроблена програма розв'язує нелінійне рівняння:

х5 -4 + 6х3 + 5х2 - 1 = 0

методами половинного ділення та Ньютона. Знаходить комплексні корені і кількість кроків до отримання розв'язку з заданою похибкою = 0.01. Результати обчислень виводяться на екран монітора.

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

3. Використані технічні засоби

Для написання програми використовувалась мова програмування Turbo C++ версії 3.0. Скомпільована програма не вимагає наявності середовища Windows та не потребує великих системних ресурсів. Щоб забезпечити нормальне функціонування програми, необхідна наявність в робочому каталозі, звідки виконується завантаження програми, стандартних бібліотек мови С ++.

Результати програми виводяться на монітор, що не потребує додаткових ресурсів пам'яті.

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

Спочатку оцінимо скільки коренів і яких буде мати дане рівняння. За основною теоремою алгебри визначаємо, що рівняння 5-го порядку має 5 коренів. Кожен корінь рахується один раз, оскільки кратність кожного кореня дорівнює одиниці. Всі коефіцієнти даного рівняння є дійсними, тобто комплексні корені утворять комплексно спряжені пари. Використовуючи теорему Декарта замітимо, що оскільки в даному рівнянні є три зміни знаків, то дійсних коренів буде три, які можуть бути як від'ємними, так і додатними. Звідси слідує, що комплексних коренів буде два і вони будуть утворювати комплексно спряжені пари.

Розроблена програма складається з трьох підпрограм:

dilen1. cpp - знаходить корені методом половинного ділення і визначає кількість кроків до отримання розв'язку з похибкою 0.01. Блок - схема даної підпрограми зображена на рис.2.31.

nuton2. cpp - знаходить корені рівняння методом Ньютона і визначає кількість кроків до отримання розв'язку з похибкою 0.01. Блок - схема даної підпрограми зображена на рис.2.32.

komp3. cpp - знаходить комплексні корені рівняння. Тобто задане рівняння записується у формі:

(x - x1) (x - x2) (x - x3) (x2 + px + q) = 0,

де х1, х2, х3 - дійсні знайдені корені, які беруться з методу Ньютона (оскільки метод Ньютона має меншу кількість кроків, тобто значення коренів є точнішим).

Далі прирівнюються коефіцієнти при однакових степенях х. В даному випадку для знаходження p та q не потрібно розв'язувати декілька рівнянь з декількома невідомими, оскільки отримується два явних рівняння:

p = - 7 + x1 + x2 + x3,q = 1/x1x2x3,

звідки, підкладаючи значення х1, х2, х3, знаходимо p та q.

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

5. Вхідні дані

Вхідними даними є нелінійне рівняння:

х5 -4 + 6х3 + 5х2 - 1 = 0,

та задана похибка = 0.01.

Для знаходження комплексних коренів вхідними вважаються значення дійсних коренів х1, х2, х3.

6. Вихідні дані

Вихідними даними є:

Для методу половинного ділення:

х1 = 0.398438, kilkist' krokiv: 7

х2 = 1.648438, kilkist' krokiv: 7

х3= 5.820312, kilkist' krokiv: 7

2. Для методу Ньютона:

х1 = 0.397210, kilkist' krokiv: 4

х2 = 1.646145, kilkist' krokiv: 4

х3= 5.823016, kilkist' krokiv: 3

3. Для знаходження комплексних коренів:

х1 = - 0.433186 + і * 0.273847

х2 = - 0.433186 - і * 0.273847

7. Інструкція користувача

Для виклику та завантаження програми необхідно наявність середовища Turbo C++.

Для того, щоб запустити на виконання скомпільовану програму вирішення рівняння за методом половинного ділення необхідно і достатньо натиснути два рази на файлі “dilen1. exe", за методом Ньютона - “nuton2. exe", для знаходження комплексних коренів - “komp3. exe”. Після перегляду результатів натиснути клавішу “Esc” на клавіатурі.

8. Результати обчислень

Результатами обчислення є знайдені п'ять коренів нелінійного рівняння та кількість кроків для їх знаходження для кожного методу:

1. За методом половинного ділення:

х1 = 0.398438, kilkist' krokiv: 7

х2 = 1.648438, kilkist' krokiv: 7

х3= 5.820312, kilkist' krokiv: 7

2. За методом Ньютона:

х1 = 0.397210, kilkist' krokiv: 4

х2 = 1.646145, kilkist' krokiv: 4

х3= 5.823016, kilkist' krokiv: 3

3. Для знаходження комплексних коренів:

х1 = - 0.433186 + і * 0.273847

х2 = - 0.433186 - і * 0.273847

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

Висновки

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

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

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

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

Література

1. Самарський А.А. Вступ в чисельні методи. - М.: Наука, 1987. - 286 с.

2. Квєтний Р.Н., Маліков В.Т. Обчислювальні методи та використання ЕОМ. Вища школа, 1989 - 55 с., 104 с.

Додатки

Додаток В

Лістинг програми

Programm dilen1. cpp // Обчислення коренiв за методом половинного дiлення

#include<stdio. h>

#include<math. h>

#include<conio. h>

float f (float x)

{

float result=pow (x,5) - 7*pow (x,4) +6*pow (x,3) +5*pow (x,2) - 1;

return result;

}

void findroot (float x1, float x2)

{

float e=0.01;

int counter=0;

while (1)

{

float x3= (x1+x2) /2;

counter++;

if (fabs (x3-x1) <=e)

{

printf ("x=%f, kilkist' krokiv%d\n",x3,counter);

break;

}

if (f (x3) <0)

x1=x3;

else x2=x3;

}

}

void main ()

{

for (int i=-5000; i<5000; i++)

{

if (f (i-1) *f (i) <=0)

if (f (i-1) <=f (i))

findroot (i-1, i);

else

findroot (i, i-1);

}

getch ();

}

Programm nuton2. cpp // Обчислення коренiв за методом Ньютона

#include<stdio. h>

#include<math. h>

#include<conio. h>

float f (float x)

{

float result=pow (x,5) - 7*pow (x,4) +6*pow (x,3) +5*pow (x,2) - 1;

return result;

}

float f_shtrih (float x)

{

float result=5*pow (x,4) - 28*pow (x,3) +18*pow (x,2) +10*x;

return result;

}

void findroot (float x)

{

float e=0.01;

int counter=0;

while (1)

{

float xnew=x-f (x) /f_shtrih (x);

counter++;

if (fabs (xnew-x) <=e)

{

printf ("x=%f, kilkist' krokiv:%d\n",xnew,counter);

break;

}

x=xnew;

}

}

void main ()

{

for (int i=-5000; i<5000; i++)

if (f (i-1) *f (i) <=0)

findroot (i);

getch ();

}

// Programm komp3. cpp // Знаходження комплексних коренів

#include<stdio. h>

#include<math. h>

#include<conio. h>

void findcomplexroots (float x1, float x2, float x3)

{

float p=-7+x1+x2+x3;

float q=1/ (x1*x2*x3);

float d=pow (p,2) - 4*q;

float real=-p/2;

float imag=sqrt (fabs (d)) /2;

printf ("x=%f + i*%f\n",real, imag);

printf ("x=%f - i*%f\n",real, imag);

}

void main ()

{

findcomplexroots (0.397210,1.646145,5.823016);

getch ();

}


Подобные документы

  • В роботі розглянуто наближені методи розв'язку нелінійних рівнянь для методів Ньютона та хорд, складено блок-схеми та написано програму, за допомогою якої розв'язується задане рівняння. Аналіз рівняння, методів його розв'язання і результатів обрахунку.

    курсовая работа [380,9 K], добавлен 30.11.2009

  • Дослідження методів чисельного інтегрування Чебишева та Трапеції, порівняння їх точності. Способи розробки програми на компіляторі Turbo C++, яка знаходить чисельне значення вказаного інтегралу. Обґрунтування вибору інструментальних засобів програми.

    курсовая работа [262,4 K], добавлен 18.09.2010

  • Характеристика основних методів чисельного інтегрування та розв’язання інтегралу методом Чебишева третього, четвертого та п’ятого порядків. Оцінка похибок та порівняння їх з точним обчисленнями отриманими в математичному пакеті Mathcad 2001 Professional.

    курсовая работа [127,7 K], добавлен 03.12.2009

  • Графічне зображення методу половинного ділення. Вибір методу інструментальних засобів вирішення задач. Розробка логічної частини програми для розв’язання нелінійного рівняння методами половинного ділення та січних. Особливість кодування на мові Паскаль.

    курсовая работа [135,5 K], добавлен 30.11.2009

  • В роботі розглянуто наближені методи розв’язку нелінійних рівнянь. Для вказаних методів складено блок-схеми та написано програму, за якою розв’язується задане рівняння. Аналіз як самого рівняння і методів його розв’язання так і результатів обрахунку.

    курсовая работа [302,8 K], добавлен 03.12.2009

  • Аналіз методу чисельного інтегрування, з використанням методу Гауса при обчисленні інтегралу третього, четвертого та п’ятого порядків. Алгоритм та лістинг програми, що розв’язує інтеграл методом Гауса, знаходить похибку, виводить і порівнює результати.

    курсовая работа [140,4 K], добавлен 09.02.2010

  • Огляд та аналіз методів розв’язання системи диференціальних рівнянь та вибір методів рішення. Алгоритми методів Ейлера. Вибір методу рішення задачі Коші. Рішення диференціальних рівнянь. Отримання практичних навиків програмування на мові Паскаль.

    курсовая работа [174,3 K], добавлен 06.03.2010

  • Розвиток виробництва і широке використання промислових роботів. Алгоритми методів, блок-схеми алгоритмів розв'язку даного диференційного рівняння. Аналіз результатів моделювання, прямий метод Ейлера, розв’язок диференціального рівняння в Mathcad.

    контрольная работа [59,1 K], добавлен 30.11.2009

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

    курсовая работа [698,4 K], добавлен 03.12.2009

  • Застосовування графічних методів розв’язку рівнянь та нерівностей. Проведення інтегрування та диференціюванні за допомогою засобів MathCAD. Змінення вигляду графіків у програмі. Освоєння методів аналітичних обрахунків та графічного відображення даних.

    лабораторная работа [833,5 K], добавлен 23.09.2009

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.