Алгоритм методів

3. Алгоритм методів

На основі теоретичного матеріалу, розглянутого в попередньому розділі роботи, було розроблено алгоритми методів.

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

х_n+1= х_n-,

де х_n+1 – значення х на наступній ітерації, а х_n – значення х на попередній ітерації. Ця операція повторюється до тих пір, поки не виконається умова < Δ, тобто різниця значень наступної ітерації і попередньої менше за задану похибку.

Алгоритм розвязку цього ж рівняння за методом хорд полягає в тому, що визначаються значення функції до зміни знаку при переході від  до  поки кінці інтервалів x_n+1 , х_nне будуть мати різні знаки.

Після цього визначають f(x*) і порівнюють його з f(x_n). Надалі користуються x_n+1 замість того значення, з яким воно збіглося за знаком.

Знаходимо ряд значень х до тих пір, поки не виконається умова < Δ де Δ - задана допустима похибка.

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

3.1 Вибір інструментальних засобів

Для вирішення цієї задачі було обрано середовище програмування С, так як воно має ряд вагомих переваг перед іншими середовищами і мовами програмування. Зокрема такими перевагами є те, що:

-           не вимагає великих затрат як апаратної частини комп’ютера так і програмної

-           дозволяє досить просто реалізовувати поставлені задачі

-           є дуже візуальним і наглядним що робить його зручним інструментом в користуванні

-           ця мова є досить гнучка і дозволяє використовувати технології обєктно-орієнтованого програмування.

3.2 Вхідні та вихідні дані

Для даних методів розв’язку нелінійного рівняння вхідними даними є початкове рівняння; похідна від нього; початкові наближення х₀ (1,75; -1,8; 0,1) і допустима похибка Δ , яка вводиться з клавіатури .

Вихідними даними є знайдені корені х, які задовольняють умову:

< Δ та кількість кроків для отримання розвязку із заданою похибкою.

3.3 Структура програми

Програму можна умовно розділити на чотири такі частини:

1. блок опису вхідних та вихідних даних

2. введення початкових даних

3. процедури розвязку рівняння методом хорд та Ньютона

4. виведення результатів

Програма, написана для вирішення поставленої задачі, містить кілька підпрограм. Спочатку програма пропонує ввести похибку, після чого виконує розвязок рівняння заданими методами. Для розвязку рівняння методом хорд використовується функція chords, що приймає в якості параметрів верхній х_в та нижній х_а проміжки х та кількість ітерацій iter. . Для розвязку рівняння методом Ньютона використовується функція Nuton з параметрами значень х на наступному та попередньому кроках: х , хlast та кількість ітерацій iter.

Для виведення отриманих значень х використовується функція res.

Лістінг програми наведений в додатку В.

3.4 Інструкція користувачеві

Для завантаження програми необхідно запустити програмний файл KURSOVA.EXE. При цьому з’явиться вікно (Рис. 3.4)

 

Рис. 3.4.

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

4. Аналіз результатів розрахунку

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

За методом хорд: х₁=-1,801176 (5 ітерацій); х₂=0,00001(3 ітерації); х₃₌ 1,748379 (5 ітерацій).

За методом Ньютона: х₁=-1,802453 (3 ітерації); х₂=0,00001(2 ітерації); х₃₌ 1,752384 (3 ітерації).

Комплексні корені : _,

Порівнявши отримані результати з наступними результатами,

що отримані за допомогою автоматизованого математичного пакету Mathcad, можна зробити висновок що корені рівняння розраховані за допомогою чисельних методів є досить точними і похибка для методу Ньютона складає не більше 0,0001,а для методу хорд не більше 0,001.За отриманими результатами також можна зробити висновок щодо швидкодії кожного з методів, а саме при однакових початкових умовах метод Ньютона працює дещо швидше, ніж метод хорд. Крім того, метод Ньютона дає точніший результат.

Висновки

В даній курсовій роботі було проаналізовано розв’язок нелінійних рівнянь методами Ньютона та хорд. В результаті роботи було досліджено існуючі методи для розв’язання таких рівнянь, а більш детально розглянуті вищезгадані два методи. Для цих методів було складено блок-схему, а також написано програму на мові програмування С++. В результаті роботи за допомогою складеної програми було отримано певні корені заданого рівняння і порівняно їх зі значеннями коренів цього ж рівняння, але розв’язаного за допомогою спеціалізованого математичного програмного пакету Mathcad. Також було доведено, що метод Ньютона має значно вищу швидкість збіжності і для знаходження коренів потрібно значно менше ітерацій.

Література

1. Квєтний Р. Н. Методи комп’ютерних обчислень: Навчальний посібник. – Вінниця.: ВДТУ, 2001. – С. 35.

2. Вержбицький В. М. Основы численных методов. – М.: Высшая школа, 2002. – С. 43.

3. Волков Е. А. Численные методы. – М.: Наука, 1982. – С. 102.

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

5. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. – М.: Наука, 1987. – С. 83.

Додаток А

(Алгоритм методів)

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

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

Додаток Б

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

Додаток В

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

#include <math.h>

#include <stdio.h>

#include <conio.h>

double e; // похибка

// f(x)=x^5-10x+1 - функция

double f(double x)

 {

return pow(x,5) - 10*x + 1;

 }

// f'(x)=5x^4-10 - перша похідна f(x) для метода Ньютона

double f_der(double x)

 {

return 5*pow(x,4) - 10;

 }

int chords(double xa, double xb, double &x, int &iter)

// метод Хорд

{

double xlast;

x = 0;

if (f(xa)*f(xb) >= 0)

return 0;

iter = 0;

do

{

xlast = x;

x = xb - f(xb)*(xb-xa)/(f(xb)-f(xa));

if (f(x)*f(xa) > 0)

xa = x;

else

xb = x;

iter++;

}

while (fabs(x-xlast)>e);

return 1;

}

double Nuton(double x, int &iter)

// метод Ньютона

{

double xlast;

iter = 0;

do

{

xlast = x;

x = x - f(x)/f_der(x);

iter++;

}

while (fabs(x-xlast)>e);

return x;

}

int main()

// основна програма

{

double res;

int iter;

clrscr();

printf(" Enter the accuracy : ");

scanf("%f", &e);

printf("\n-------------------------Chord's method--------------\n");

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

if (chords(i, i+1, res, iter))

printf("\n x= %f (%d iterations)\n", res, iter);

printf("\n-------------- Nuton's method----------------------\n");

res = Nuton(-2, iter);

printf("\n x= %f (%d iterations)\n", res, iter);

res = Nuton(0, iter);

printf("\n x= %f (%d iterations)\n", res, iter);

res = Nuton(2, iter);

printf("\n x= %f (%d iterations)\n", res, iter);

getch();

return 0;

}