Знаходження коренів шляхом половинного поділу. Теорія нелінійних рівнянь та метод половинного поділу

Розв'язання рівняння алгебри. Для чисельного рішенняалгебраїчних рівнянь існує безліч способів. Серед найвідоміших можна назвати метод Ньютона, метод Хорд, та «всепереможний» метод Половинного Поділу. Відразу обмовимося, що будь-який метод є наближеним, і по суті лише уточнює значення кореня. Однак таким, що уточнює до будь-якої точності, заданої Нами.

Метод половинного поділуабо дихотомії (дихотомія - зіставленість або протиставленість двох частин цілого) при знаходженні кореня рівняння f (x) = 0 полягає в розподілі навпіл відрізка, де знаходиться корінь. Потім аналізується зміна знака функції половинних відрізках, і з кордонів відрізка переноситься у його середину. Переноситься та межа, з боку якої функція половині відрізка знака не змінює. Далі процес повторюється. Ітерації припиняються при виконанні однієї з умов: або довжина інтервалу стає меншою від заданої похибки знаходження кореня?, або функція потрапляє в смугу шуму?1 - значення функції порівняно з похибкою розрахунків.

Спочатку поставимо завдання. Дана монотонна, безперервна функція f(x), яка містить корінь на відрізку , де b>a. Визначити корінь з точністю, якщо відомо, що f(a)*f(b)<0

Дано рівняння виду:

Необхідно знайти значення, що задовольняють йому x.

Отже, приступимо до вирішення. Насамперед, визначимося, що означає f(x)=0. Подивіться на рис.1. На ньому зображено графік певної функції. У деяких точках цей графік перетинає вісь абсцис. Координати цих точок нам і потрібно знайти. Якщо вид рівняння простий чи стандартний, наприклад, квадратне рівняння чи лінійне, то застосовувати чисельний метод тут зовсім ні до чого. Але якщо рівняння у нас таке:

F(x)=x3-14x2+x+ex; (2)

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

Учням метод половинного поділу можна подати як рішення завдання.

Завдання

Йде облога ворожої фортеці. На деякій відстані від неї встановили нову гармату. Під яким кутом до горизонту треба стріляти з цієї гармати, щоб потрапити у задану ділянку фортечної стіни.

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

Які ж фактори прийняти за суттєві у цьому завданні? Оскільки йдеться про середньовіччя, то швидкість снаряда та дальність польоту невеликі. Отже можна вважати несуттєвим, що Земля кругла (пам'ятайте обговорення у параграфі 27), і знехтувати опором повітря. Залишається єдиний чинник – сила земного тяжіння.

Математик тут сказав би, що треба вирішити рівняння. Ми також вирішуватимемо, тільки наближено і дуже схоже на те, як роблять справжні артилеристи. Вони ж чинять так: роблять кілька пострілів, беручи мету «у вилку», тобто. одне влучення вище мети, а інше нижче. Потім ділять навпіл кут між цими пострілами, і під час стрільби під таким кутом снаряд лягає до мети набагато ближче. Але якщо все ж таки не потрапили, то нову «вилку» знову ділять навпіл і т.д.

Ми заздалегідь можемо вказати «вилку» для кута: 0 і?/4 (ми сподіваємося, що ви пам'ятаєте який кут має радіальну міру?/4 і чому приблизно дорівнює?). А далі ділитимемо навпіл цю «вилку» і дивитися, куди потрапляє снаряд, поки не досягнемо потрібного результату.

Як довго нам доведеться вести «пристрілку», щоб отримати кут?, з потрібною точністю? Щоб відповісти на це питання, відвернемося від нашого завдання і сформулюємо суто математичною мовою, що і як ми знаходили.

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

Як же пропонується шукати цей корінь? А ось так. Ділимо відрізок навпіл, тобто. беремо середину відрізка а+b/2. У цій точці обчислюємо значення функції f(x) (рис. 2). Якщо це значення 0 то корінь знайдений; якщо ні, воно має той самий знак, що і значення на одному з кінців відрізка . Тоді цей кінець заміни крапкою а+b/2. Новий відрізок також містить корінь рівняння f(x)=0, оскільки на його кінцях функція f(x) знову має різні знаки. Однак цей відрізок у 2 рази коротший за попередній. І найголовніше - з ним можна вчинити так само. з наступним відрізком вкотре зробити те саме і т.д. оскільки довжина відрізка щоразу зменшується вдвічі, ми можемо отримати відрізок скільки завгодно малої довжини, всередині якого міститься корінь рівняння f(x)=0. Наприклад, якщо вихідний відрізок був , тобто. мав довжину 1, то через десять кроків ми отримаємо відрізок завдовжки. Це означає, що кінці відрізка дають нам наближене значення кореня з точністю, яка дорівнює довжині відрізка: лівий кінець відрізка - наближене значення кореня з недоліком, правий кінець - наближене значення кореня з надлишком.

Фактично ми сформулювали метод наближеного рішення рівняння f(x)=0. Його можна було б назвати методом артилерійської пристрілки. Але математики називають його методом половинного поділу.

Алгоритм

1) Знайдемо середину відрізка: c = (a + b) / 2;

2) Обчислимо значення функції в точках a та c і знайдемо добуток отриманих значень: d=f(c)?f(a);

3) Якщо d>0, тепер точкою a стане c: a=c; Якщо d<0, то точкой b станет c: b=c;

4) Обчислимо різницю a і b, порівняємо її з точністю?: якщо |a-b|> ?, то йдемо в пункт 1) якщо ні, то корінь з потрібною нам точністю знайдено, і він дорівнює: x=(a+b)/ 2;

ВСТУП 4

1. ПОСТАНОВКА ЗАВДАННЯ 5

2. ВИБІР І ОПИС МЕТОДІВ РІШЕННЯ 6

2.1. МЕТОД ПОЛОВИННОГО ДІЛЕННЯ 6

2.2. МЕТОД ХОРД 9

2.3. МЕТОД НЬЮТОНА (МЕТОД ЩОДО) 12

3 .ВІДПОВІДНІСТЬ МІЖ ЗМІННИМИ, ПРИЙНЯТИМИ ПРИ ОПИСІ ЗАВДАННЯ ТА У ПРОГРАМІ 15

4. СТРУКТУРНА СХЕМА ПРОГРАМ І ЇЇ ОПИС 18

5. ЛІСТИНГ ПРОГРАМИ 26

6. КОНТРОЛЬНИЙ ПРИКЛАД І АНАЛІЗ РЕЗУЛЬТАТУ 27

7. ІНСТРУКЦІЯ КОРИСТУВАЧА 32

ВИСНОВОК 33

СПИСОК ЛІТЕРАТУРИ 34

ДОДАТКИ 35

ДОДАТОК А 36

ДОДАТОК Б. 38

ДОДАТОК Д. 39

ВСТУП

Паскаль – одна з найпоширеніших процедурно-орієнтованих мов програмування 80 - 90-х років, має свою досить цікаву історію, початок якої поклала оголошення у 1965 р. конкурсу зі створення нової мови програмування – наступника Алгола – 60. Участь у конкурсі взяв швейцарський учений Ніколаус Вірт, який працював на факультеті інформатики Стендфордського університету. Проект, запропонований ним, було відкинуто комісією 1967 р. Але Вірт не припинив роботу. Повернувшись до Швейцарії, разом із співробітниками Швейцарського федерального інституту технології в Цюріху, він уже 1968 р. розробив нову версіюмови Паскаль, названого так на честь великого французького математика та механіка Блеза Паскаля, який створив у 1642 р. першу лічильну машину. У 1971 р. Н. Вірт випустив опис своєї мови, а в 1975 р. було розроблено посібник для користувачів версії Паскаля, яка практично лягла в основу стандарту мови. Але стандарт мови з'явився лише 1982 р.

Призначена для навчання, мова виявилася дуже простою і водночас суворою. Однак незабаром з'ясувалося, що він також є досить ефективним у різних додатках. Pascal підтримує найсучасніші методології проектування програм (низхідне, модульне проектування, структурне програмування). У зв'язку з цим з'явилися численні реалізації мови для різних машинних архітектур і найбільш вдалою та популярною виявилася розробка фірми Borland International для персональних IBM - сумісних ЕОМ. Ця реалізація мови отримала назву Turbo Pascal (Турбо Паскаль) і має кілька версій.

Turbo Pascal є системою програмування, що включає текстовий редактор, компілятор, компонувальник, завантажувач, відладчик, файлову систему, системну бібліотеку, довідкову систему. Всі ці компоненти об'єднані в інтегроване середовище з багатовіконним інтерфейсом та розвиненою системою меню, що забезпечує високу продуктивність праці програміста під час створення програм виробничого, наукового та комерційного призначення.

1. ПОСТАНОВКА ЗАВДАННЯ

Написати програму мовою програмування Pascal, яка виконує рішення нелінійного рівняння. Результат роботи програми повинен виводитися на екран та у файл.

У програмі реалізувати наступне меню:

1-Ввести дані з файлу

2-Ввести дані з клавіатури

Налагодити програму на рівнянні f(x)=x 2 -x-6 з точністю 0,001

2. ВИБІР І ОПИС МЕТОДІВ РІШЕННЯ

Процес знаходження наближеного значення коренів рівняння можна поділити на два етапи: 1) відділення коренів; 2) уточнення коренів до заданого ступеня точності. Корінь ξ вважається відокремленимна відрізку, якщо на цьому відрізку рівняння

: метод половинного поділу, Ньютона.

2.1. МЕТОД ПОЛОВИННОГО ДІЛЕННЯ

Нехай дано рівняння f(x) = 0, де f (х) – безперервна функція. Потрібно знайти корінь цього рівняння з точністю до ε, де е - деяке позитивне досить мале число.

Вважатимемо, що корінь ξ відокремлений і знаходиться на відрізку [ а, b], тобто має місце нерівність а ≤ ξ ≤ b. Числа аі b– наближені значення кореня ξ відповідно з недоліком та надлишком. Похибка цих наближень не перевищує довжини відрізка b – а. Якщо b – а≤ε, то необхідну точність обчислень досягнуто, і за наближене значення кореня ξ можна прийняти або а, або b. Але якщо b – а> ε, то необхідна точність обчислень не досягнута і необхідно звузити інтервалів якого знаходиться корінь ξ, тобто підібрати такі числа аі bщоб виконувати нерівності a b та . При обчисленні слід припинити і за наближене значення кореня з точністю до ε прийняти або а, або b. Слід зазначити, що значення кореня буде точнішим, коли за наближене значення кореня прийнято не кінці відрізка аі b, а середина цього відрізка, тобто. . Похибка у разі не перевищує величини
.

Метод проб. Нехай дано рівняння f(x) = 0 [f(x) – безперервна функція] і корінь ε відокремлений на відрізку [ а, b], тобто. f(а) ∙ f(b) b – а> ε. Потрібно знайти значення кореня з точністю до ε (рис. 2.1)

Принцип розв'язання рівняння типу y=f(x) методом проб

Принцип розв'язання рівняння типу y=f(x) методом половинного поділу

На відрізку [ a, b] оберемо довільним чином точку a 1 , яка розділить його на два відрізки і . З цих двох відрізків слід вибрати той, на кінцях якого функція набуває значень, протилежних за знаком. У нашому прикладі f(а) ∙ f(a 1) > 0, f(a 1) ∙ f(b) a 1 , b]. Потім на цьому звуженому відрізку знову довільним чином візьмемо крапку а 2 і знайдемо знаки творів f(a 1) ∙ f(a 2) та f(a 2) ∙ f(b). Так як f(a 2)× f(b) a 2 , b]. Цей процес продовжуємо доти, доки довжина відрізка, на якому знаходиться корінь, не стане меншою від ε. Корінь ξ отримаємо як середнє арифметичне кінців знайденого відрізка, причому похибка кореня не перевищує ε/2.

Метод пробу такому вигляді на ЕОМ не застосовується. Для складання програм та розрахунків на ЕОМ метод проб застосовується у вигляді так званого методу половинного поділу.

Нехай корінь ξ рівняння f(х) = 0 відокремлений і знаходиться на відрізку [ a, b], тобто. f(a) ∙ f(b) b – а> ε [тут f(х) – безперервна функція]. Як і раніше, візьмемо на відрізку [ a, b] проміжну точку, проте не довільним чином, а так, щоб вона була серединою відрізка [ a, b], тобто. з = (а + b)/2. Тоді відрізок [ a, b] точкою з розділиться на два рівні відрізки [ а, з] та [ з, b], довжина яких дорівнює ( b – а)/2 (рис. 2.2). Якщо f(з) = 0, то з- Точний корінь рівняння f(х) = 0. Якщо ж f(з) ≠ 0, то з двох утворених відрізків [ a, з] та [ з, b] виберемо той, на кінцях якого функція f(х) набуває значення протилежних знаків; позначимо його [ a l , b 1]. Потім відрізок [ a l , b 1] також ділимо навпіл і проводимо самі міркування. Отримаємо відрізок [ а 2 , b 2], довжина якого дорівнює ( b – а)/2 2 . Процес поділу відрізка навпіл виробляємо до тих пір, коли на якомусь n-му етапі або середина відрізка буде коренем рівняння (випадок, що дуже рідко зустрічається на практиці), або буде отриманий відрізок [ a n, b n] такий, що b n – а n = ( b– а)/2 n ≤ ε та а n ≤ ξ ≤ b n (число nвказує на кількість проведених поділів). Числа а n та b n – коріння рівняння f(х) = 0 з точністю до ε. За наближене значення кореня, як вказувалося, вище, слід взяти = ( a n+ b n)/2, причому похибка не перевищує ( b – а)/2 n +1.

2.2. МЕТОД ХОРД

Метод хорд є одним із поширених методів розв'язання алгебраїчних та трансцендентних рівнянь. У літературі він також зустрічається під назвами «методу хибного становища» (regula falsi), «методу лінійного інтерполювання» та «методу пропорційних частин».

Нехай дано рівняння f(х) = 0, де f(х) – безперервна функція, що має в інтервалі [а, b] похідні першого та другого порядків. Корінь вважається відокремленим і на відрізку [а, b], тобто. f(a)-f(b)

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

Раніше ми розглянули чотири випадки розташування дуги кривої, враховуючи значення першої та другої похідних.

Розглянемо випадки, коли перша та друга похідні мають однакові знаки, тобто f"(х) ∙ f""(х) > 0.

Нехай, наприклад, f(a) 0, f"(х) > 0, f""(х) > 0 (рис. 3.18, а). Графік функції проходить через точки А 0 (a; f(a)), В(b; f(b))- Шуканий корінь рівняння f(х) = 0 є абсцис точки перетину графіка функції у = f(х) з віссю Ох. Ця точка нам невідома, але замість неї ми візьмемо точку x 1 перетину хорди А і В з віссю Ох, це і буде наближене значення кореня.

Рівняння хорди, що проходить через точки А 0 і В має вигляд

Знайдемо значення х = х 1, для якого у = 0:

Ця формула називається формули методу хорд. Тепер корінь ξ знаходиться всередині відрізка. Якщо значення кореня х 1 нас не влаштовує, його можна уточнити, застосовуючи метод хорд до відрізку [х 1 , b].

З'єднаємо точку А 1 (x 1 ; f (x 1) з точкою В (b; f (b)) і знайдемо х 2 - точку перетину хорди А 1 В з віссю Ох:

Продовжуючи цей процес, знаходимо

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

За наведеними вище формулами обчислюються коріння й у випадку, коли f(а) > 0, f(b)

Тепер розглянемо випадки, коли перша і друга похідні мають різні знаки, тобто. f"(x) ∙ f"(x)

Нехай, наприклад, f(a) > 0, f(b) 0 (рис. 3.19 а). З'єднаємо точки A (a; f (а)) і 0 (b; f (b)) і запишемо рівняння хорди, що проходить через А і B 0:

Знайдемо х 1 як точку перетину хорди з віссю Ох, вважаючи у = 0:

Корінь ξ тепер укладено всередині відрізка. Застосовуючи меч од хорд до відрізка [а, x 1], отримаємоМетоди розв'язання нелінійного рівняння Лабораторна робота >> Математика

Студентів, які вивчають предмет «Кількісні методи»та виконуючих лабораторні роботи... У методичні вказівкирозглянуто ряд методівзнаходження коренів нелінійного рівняння та... Тому велике значеннямають методинаближеного рішення рівняння із заданою...

Методикомп'ютерних обчислень та їх додаток до фізичних завдань

Методичка >> Інформатика

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

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

Методи вирішення нелінійних рівняньділяться на дві групи:

точні методи

ітераційні методи

Точні методи дозволяють записати коріння як деякого кінцевого співвідношення (формули). Зі шкільного курсу алгебри відомі такі методи для рішення тригонометричнихлогарифмічних, показових, а також найпростіших рівнянь алгебри.

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

Нехай дано рівняння

Функція f(x) безперервна на відрізку [ a, b] разом зі своїми похідними 1-го та 2-го порядку.
Значення f(x) на кінцях відрізка мають різні знаки ( f(a) * f(b) < 0).
Перша та друга похідні f"(x) та f""(x) зберігають певний знак на всьому відрізку.

Умови 1) та 2) гарантують, що на інтервалі [ a, b] знаходиться хоча б один корінь, а з 3) випливає, що f(x) на даному інтервалі монотонна і тому корінь буде єдиним.

Розв'язати рівняння (1) ітераційним методомозначає встановити, чи має воно коріння, скільки коренів і знайти значення коріння з необхідною точністю.

Будь-яке значення, що звертає функцію f(x) у нуль, тобто. таке, що:

називається корінням рівняння(1) або нулемфункції f(x).

Завдання знаходження кореня рівняння f(x) = 0 ітераційним методом складається з двох етапів:

відділення коренів

уточнення наближеного коріння

Процес відокремлення коріння починається із встановлення знаків функції f(x) у граничних x=aі x=bточках сфери її існування.

Приклад 1 . Відокремити коріння рівняння:

f( x) є x 3 - 6х + 2 = 0.

Складемо приблизну схему:

Отже, рівняння (2) має три дійсних кореня, що лежать в інтервалах [-3, -1], і .

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

В інженерній практиці поширений графічний спосібвизначення наближеного коріння.

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

Рівняння (4) зручно переписати у вигляді рівності:

Звідси ясно, що коріння рівняння (4) може бути знайдено як абсциси точок перетину логарифмічної кривої y= lg xта гіперболи y = . Побудувавши ці криві, приблизно знайдемо єдиний корінь рівняння (4) або визначимо його відрізок .

Ітераційний процес полягає у послідовному уточненні початкового наближення х 0 . Кожен такий крок називається ітерацією. В результаті ітерацій знаходиться послідовність наближених значень кореня х 1 , х 2 , ..., х n.Якщо ці значення зі збільшенням числа ітерацій nнаближаються до справжнього значення кореня, то кажуть, що ітераційний процес сходиться.

Для знаходження кореня рівняння (1), що належить відрізку [ a, b], ділимо цей відрізок навпіл. Якщо f= 0 , то x = є коренем рівняння. Якщо fне дорівнює 0 (що, практично, найбільш ймовірно), то вибираємо ту з половин або , на кінцях якої функція f(x) має протилежні знаки. Новий звужений відрізок [ а 1 , b 1] знову ділимо навпіл і робимо ті самі дії.

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

Приклад 3. Методом половинного поділу уточнити корінь рівняння

f( x) = x 4 + 2 x 3 - x - 1 = 0

що лежить на відрізку [0, 1].

Послідовно маємо:

f(0) = - 1; f(1) = 1; f(0,5) = 0,06 + 0,25 - 0,5 - 1 = - 1,19;

f(0,75) = 0,32 + 0,84 - 0,75 - 1 = - 0,59;

f(0,875) = 0,59 + 1,34 - 0,88 - 1 = + 0,05;

f(0,8125) = 0,436 + 1,072 - 0,812 - 1 = - 0,304;

f(0,8438) = 0,507 + 1,202 - 0,844 - 1 = - 0,135;

f(0,8594) = 0,546 + 1,270 - 0,859 - 1 = - 0,043 і т.д.

Можна прийняти

x = (0,859 + 0,875) = 0,867

У даному методіпроцес ітерацій полягає в тому, що як наближення до кореня рівняння (1) приймаються значення х 1 х 2 , ..., х nточок перетину хорди АВз віссю абсцис (Малюнок 3). Спочатку запишемо рівняння хорди AB:

Для точки перетину хорди ABз віссю абсцис ( х = х 1 ,y = 0) отримаємо рівняння:

Нехай для певності f""(x) > 0 при а х b(випадок f""(x) < 0 зводиться до нашого, якщо записати рівняння у вигляді - f(x) = 0). Тоді крива у = f(x) буде опукла вниз і, отже, розташована нижче за свою хорду АВ. Можливі два випадки: 1) f(а) > 0 (Малюнок 3, а) і 2) f(b) < 0 (Рисунок 3, б).

Малюнок 3 а, б.

У першому випадку кінець анерухомі та послідовні наближення: x 0 = b;x , де функція f (х) має знак, протилежний знаку її другої похідної f""(х).

Ітераційний процес триває доти, доки не буде виявлено, що

| x i - x i - 1 |< e ,

де e – задана гранична абсолютна похибка.

приклад 4. Знайти позитивний корінь рівняння

f( x) = x 3 - 0,2 x 2 - 0,2 х - 1,2 = 0

з точністю e=0,01.

Насамперед, відокремлюємо корінь. Так як

f(1) = -0,6< 0 и f (2) = 5,6 > 0,

то шуканий корінь x лежить в інтервалі. Отриманий інтервал великий, тому розділимо його навпіл. Так як

f(1,5) = 1,425 > 0, то 1< x < 1,5.

Так як f""(x) = 6 x- 0,4 > 0 при 1< х < 1,5 и f(1,5) > 0, то скористаємося формулою (5) для вирішення поставленого завдання:

= 1,15;

| x 1- x 0 | = 0,15 > e,

отже, продовжуємо обчислення;

f ( х 1) = -0,173;

= 1,190;

|х 2- x 1 | = 0,04 > e,

f (х 2) = -0,036;

= 1,198;

| x 3- x 2 | = 0,008 < e .

Отже, можна прийняти x = 1,198 з точністю e = 0,01.

Зауважимо, що точний корінь рівняння x = 1,2.

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

Поки не буде досягнуто потрібної точності.

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

Метод половинного поділу

Метод половинного поділувідомий також як метод бісекції. У цьому методі інтервал ділиться рівно навпіл.

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

Метод половинного поділу:

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

Метод половинного поділу як метод пошуку коренів функції

Виклад методу

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

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

Нехай функція безперервна на відрізку

і - єдиний корінь рівняння.

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

Розділимо відрізок навпіл. Отримаємо крапку і два відрізки.

Новий відрізок ділимо навпіл. Отримуємо середину цього відрізка і таке інше.

Щоб знайти наближене значення кореня з точністю до 0" alt="(!LANG: \eps >0">, необходимо остановить процесс половинного деления на таком шаге , на котором и вычислить . Тогда можно взять .!}

Реалізація методу на С++ та числовий приклад

Розв'яжемо рівняння методом половинного поділу. Графічним методомзнаходимо відрізок , якому належить шуканий корінь. Бо, то приймаємо.

Нижче наведено приклад програми на С++, яка вирішує поставлене завдання.

Програма 1. Корінь рівняння

#include #include using namespace std; const double epsilon = 1e-2; double f(double x) ( return 4 - exp (x) - 2 * x^ 2 ; ) int main() ( double a, b, c; a = 0 ; b = 2 ; while (b - a > epsilon) (c = (a + b) / 2; if (f(b) * f(c)< 0 ) a = c; else b = c; } cout << (a + b) / 2 << endl; return 0 ; }

Шуканий корінь. Обчислення проводилися з точністю.

Проміжні обчислення представлені у таблиці нижче.

n	a n	b n	c n	b n -c n
1	0	1	0.5	0.5
2	0.5	1	0.75	0.25
3	0.75	1	0.875	0.125
4	0.875	1	0.9375	0.0625
5	0.875	0.9375	0.90625	0.03125
6	0.875	0.90625	0.890625	0.015625
7	0.875	0.890625	0.8828125	0.0078125

Метод половинного поділу як метод оптимізації

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

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

Дана функція. Необхідно знайти , що доставляє мінімум (чи максимум) функції інтервалі із заданою точністю , тобто. знайти

Запишемо словесний алгоритм методу.

Схема алгоритму методу представлена на рис.

- Константа,

При виведенні координата точки, в якій функція має мінімум (або максимум), значення функції в цій точці.

Метод хорд

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

Виклад методу

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

При цьому в процесі пошуку сімейство хорд може будуватися:

В результаті ітераційний процес сходження до кореня реалізується рекурентною формулою:

для випадку а):

для випадку б):

Процес пошуку триває доти, доки не виконається умова або .

Метод забезпечує швидку збіжність, якщо %200" alt="(!LANG:f(z)\cdot f""(z) > 0">, т.е. хорды фиксируются в том конце интервала , где знаки функции и ее кривизны совпадают.!}

Схема алгоритму уточнення кореня методом хорд подано на рис. 4.

Комбінація методу хорд та методу половинного поділу

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

Іванов Іван

Під час проходження теми чисельні методи учні вже вміють працювати з електронними таблицями та складати програми мовою паскаль. Робота комбінованого характеру. Розрахована на 40 хвилин. Мета роботи повторити та закріпити навички паботи з програмами EXCEL, ABCPascal. Матеріал містить 2 файли. Один містить теоретичний матеріал, оскільки він пропонується учневі. У 2-му файлі приклад роботи учня Іванова Івана.

Завантажити:

Попередній перегляд:

Розв'язання рівнянь

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

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

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

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

2) уточнення наближених коренів, тобто. доведення їх до заданого ступеня точності.

Ми розглядатимемо рішення рівнянь виду f(x)=0. Функція f(x)визначена та безперервна на відрізку[А.Ь]. Значення х 0 називається коренем рівняння якщо f(х 0 )=0

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

Якщо f(a)* f(b) \a, b\ існує, принаймні, один корінь
Якщо функція y = f(x) безперервна на відрізкуі f(a)*f(b) і f "(x) на інтервалі (a, b) зберігає знак, то всередині відрізка[а, b] існує єдиний корінь рівняння

Наближене відділення коріння можна провести і графічно. Для цього рівняння (1) замінюють рівносильним рівняннямр(х) = ф(х), де функції р(х) та ф(х) простіші, ніж функція f(x). Тоді, побудувавши графіки функційу = р(х) та у = ф(х), шукане коріння отримаємо, як абсциси точок перетину цих графіків

Метод дихотомії

Для уточнення кореня розділимо відрізок[а, b] навпіл і обчислимо значення функції f(х) у точці x sr =(a+b)/2. Вибираємо ту з половинабо , на кінцях яких функція f(x) має протилежні знаки.. Продовжуємо процес розподілу відрізка навпіл і проводимо той самий розгляд доти, доки. довжина стане менше заданої точності. У разі за наближене значення кореня можна прийняти будь-яку точку відрізка (зазвичай, беруть його середину).Алгоритм високоефективний, оскільки кожному витку (ітерації) інтервал пошуку скорочується вдвічі; отже, 10 ітерацій скоротять його у тисячу разів. Складнощі можуть виникнути з відділенням кореня у складних функцій.

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

ПРИКЛАД : Визначимо графічно корінь рівняння. Нехай f1(х) = х, a та побудуємо графіки цих функцій. (Графік). Корінь знаходиться на інтервалі від 1 до 2. Тут же уточнимо значення кореня з точністю 0,001 (на дошці шапка таблиці)

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

а:=ліва кордон b:= правий кордон
m:= (a+b)/2 середина
визначаємо f(a) та f(m)
якщо f(a)*f(m)
якщо (a-b)/2>e повторюємо, починаючи з пункту 2

Метод хорд.

Точки графіка функції на кінцях інтервалу з'єднуються хордою. Точка перетину хорди та осі Ох (х*) і використовується як пробна. Далі міркуємо так само, як і в попередньому методі: якщо f(x a ) та f(х*) одного знака на інтервалі, нижня межа переноситься в точку х*; в іншому випадку – переносимо верхню межу. Далі проводимо нову хорду тощо.

Залишилося лише уточнити, як знайти х*. По суті завдання зводиться до наступної: через 2 точки з невідомими координатами (х 1 , у 1 ) та (х 2 , у 2 ) Проведена пряма; знайти точку перетину цієї прямої та осі Ох.

Запишемо рівняння прямої по двох точках:

У точці перетину цієї прямої і осі Ох у = 0, а х = х *, тобто

Звідки

процес обчислення наближених значень триває доти, доки для двох послідовних наближень кореня х„ іх п _1 не виконуватиметься умова abs(xn-x n-1) е - задана точність

Збіжність методу набагато вища за попередній

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

Рівняння для самостійного вирішення: (відрізок у excel шукаємо самостійно)

sin(x/2)+1=x^2 (х=1,26)

x-cosx=0 (х=0,739)

x^2+4sinx=0 (х=-1,933)

x=(x+1) 3 (х=-2,325)