Сите луѓе по природа се стремат кон знаење. (Аристотел. Метафизика)

Нумерички методи: решавање нелинеарни равенки

Проблемите за решавање равенки постојано се појавуваат во пракса, на пример, во економијата, кога развивате бизнис, сакате да знаете кога профитот ќе достигне одредена вредност, во медицината, кога ги проучувате ефектите на лековите, важно е да знаете кога концентрацијата на супстанцијата ќе достигне дадено ниво итн.

Во проблемите со оптимизација, често е неопходно да се одредат точките во кои изводот на функцијата станува 0, што е неопходен услов локалниекстремен.

Во статистиката, кога се конструираат проценки со користење на методот на најмали квадрати или максимална веројатност, треба да се решаваат и нелинеарни равенки и системи на равенки.

Значи, се јавува цела класа на проблеми поврзани со изнаоѓање решенија нелинеарниравенки, како што се равенки или равенки, итн.

Во наједноставниот случај, имаме функција дефинирана на интервалот ( а, б ) и земајќи одредени вредности.

Секоја вредност x од овој сегмент можеме да го споредиме бројот, ова е функционалнизависност, клучен концепт во математиката.

Треба да најдеме вредност на која тие се нарекуваат корени на функцијата

Визуелно треба да ја одредиме пресечната точка на графикот на функцијатасо оската на апсцисата.

Метод на преполовување

Наједноставниот метод за наоѓање на корените на равенката е методот на преполовување, или дихотомија.

Овој метод е интуитивен и секој би постапил на сличен начин при решавање на некој проблем.

Алгоритмот е како што следува.

Да претпоставиме дека наоѓаме две точки и , такви што имаат различнизнаци, тогаш помеѓу овие точки има барем еден корен од функцијата.

Ајде да го поделиме сегментот на половина и да влеземе просекточка .

Потоа или , или .

Да ја оставиме таа половина од сегментот за кој вредностите на краевите имаат различни знаци. Сега повторно го делиме овој сегмент на половина и го оставаме тој дел на чии граници функцијата има различни знаци и така натаму, за да ја постигнеме потребната точност.

Очигледно, постепено ќе ја стеснуваме областа каде што се наоѓа коренот на функцијата и, според тоа, ќе ја одредиме со одреден степен на точност.

Забележете дека опишаниот алгоритам е применлив за која било континуирана функција.

Предностите на методот на преполовување ја вклучуваат неговата висока сигурност и едноставност.

Недостаток на методот е фактот што пред да започнете да го користите, треба да најдете две точки каде вредностите на функциите имаат различни знаци. Очигледно е дека методот не е применлив за корени со рамномерна мноштво и исто така не може да се генерализира во случај на сложени корени и системи на равенки.

Редоследот на конвергенција на методот е линеарен, на секој чекор точноста се удвојува; колку повеќе повторувања се прават, толку попрецизно се одредува коренот.

Њутнов метод: теоретски основи

Њутнов класичен методили тангентие дека ако е одредено приближување до коренот на равенката , тогаш следното приближување се дефинира како корен на тангентата на функцијата нацртана во точката.

Тангентата равенка на функција во точка има форма:

Во тангентната равенка ставаме и .

Тогаш алгоритмот за секвенцијални пресметки во методот на Њутн е како што следува:

Конвергенцијата на методот на тангента е квадратна, редоследот на конвергенција е 2.

Така, конвергенцијата на Њутновата тангента метода е многу брза.

Запомнете го овој прекрасен факт!

Без никакви промени, методот се генерализира на сложениот случај.

Ако коренот е корен од второ множество или поголем, тогаш редоследот на конвергенција паѓа и станува линеарен.

Вежба 1. Користејќи го методот на тангента, пронајдете решение за равенката на отсечката (0, 2).

Вежба 2.Користејќи го методот на тангента, пронајдете решение за равенката на отсечката (1, 3).

Недостатоците на Њутновиот метод ја вклучуваат неговата локалитет, бидејќи е загарантирана да се конвергира за произволна почетна апроксимација само ако условот е задоволен насекаде , во спротивна ситуација, конвергенција се јавува само во одредено соседство на коренот.

Недостаток на методот на Њутн е потребата да се пресметаат деривати на секој чекор.

Визуелизација на методот на Њутн

Њутновиот метод (метод на тангента) се користи ако равенката ѓ(x) = 0 има корен и се исполнети следниве услови:

1) функција y= ѓ(x) дефинирани и континуирани на ;

2) ѓ(а)· ѓ(б) < 0 (функцијата зема вредности на различни знаци на краевите на сегментот [ а; б]);

3) деривати ѓ"(x) И ѓ""(x) зачувај знак на интервалот [ а; б] (т.е. функција ѓ(x) или се зголемува или намалува на сегментот [ а; б], додека се одржува насоката на конвексноста);

Главната идеја на методот е како што следува: на сегментот [ а; б] се избира таков број x 0 , на кој ѓ(x 0 ) го има истиот знак како ѓ"" (x 0 ), односно условот е задоволен ѓ(x 0 )· ѓ"" (x) > 0 . Така, точката со апсциса е избрана x 0 , во која тангентата на кривата y= ѓ(x) на сегментот [ а; б] ја пресекува оската Вол. По поен x 0 Прво, погодно е да се избере еден од краевите на сегментот.

Да го разгледаме методот на Њутн користејќи конкретен пример.

Дозволете ни да ни се даде растечка функција y = f(x) =x 2 -2,континуирано на сегментот (0;2), а има ѓ"(x) = 2 x > 0 И ѓ "" (x) = 2 > 0 .

Цртеж1 . f(x) =x 2 -2

Тангентната равенка во општа форма го има следниов приказ:

y-y 0 = f" (x 0)·(x-x 0).

Во нашиот случај: y-y 0 =2x 0 ·(x-x 0).За точката x 0 ја избираме точката B 1 (b; f (b)) = (2,2).Нацртајте тангента на функцијата y = f(x)во точката B 1 и означете ја точката на пресек на тангентата и оската Волточка x 1. Ја добиваме равенката на првата тангента: y-2=2·2(x-2), y=4x-6.

Вол: x 1 =

Цртеж2. Резултат од првата итерација

y=f(x) Волпреку точката x 1, ја сфаќаме поентата B 2 = (1,5; 0,25). Повторно нацртајте тангента на функцијата y = f(x)во точката B 2, и означете ја точката на пресек на тангентата и оската Волточка x 2.

Равенка на втората тангента: y-0.25=2*1.5(x-1.5), y = 3 x - 4.25.

Пресечна точка на тангента и оска Вол: x 2 =.

Цртеж3. Второ повторување на методот на Њутн

Потоа ја наоѓаме пресечната точка на функцијата y=f(x)и нормален нацртан на оската Волпреку точката x 2, ја добиваме точката B 3 и така натаму.

Цртеж4. Трет чекор од методот на тангента

Првото приближување на коренот се одредува со формулата:

= 1.5.

Второто приближување на коренот се одредува со формулата:

Третото приближување на коренот се одредува со формулата:

Така , јасАпроксимацијата на коренот се одредува со формулата:

Пресметките се вршат додека не се совпаднат децималните цифри што се потребни во одговорот или не се постигне наведената прецизност e - додека не се задоволи неравенството | xi- xi-1 | < д.

Во нашиот случај, да ја споредиме приближноста добиена во третиот чекор со реалниот одговор пресметан на калкулатор:

Слика 5. Корен од 2, пресметан на калкулатор

Како што можете да видите, веќе на третиот чекор добивме грешка помала од 0,000002.

На овој начин, можете да ја пресметате вредноста на вредноста на „квадратен корен од 2“ со кој било степен на точност. Овој извонреден метод беше измислен од Њутн и ви овозможува да најдете корени многу сложени равенки.

Њутнов метод: примена во C++

Во оваа статија, ќе го автоматизираме процесот на пресметување на корените на равенките со пишување конзолна апликација во C++. Ќе го развиеме во Visual C++ 2010 Express, ова е бесплатна и многу погодна околина за развој на C++.

Прво, да го стартуваме Visual C++ 2010 Express. Ќе се појави прозорецот за почеток на програмата. Во левиот агол, кликнете на „Креирај проект“.

Ориз. 1. почетна страница Visual C++ 2010 Express

Во менито што се појавува, изберете „Win32 Console Application“ и внесете го името на апликацијата „Newton_Method“.

Ориз. 2. Направете проект

// Метод Newton.cpp: ја дефинира влезната точка за апликацијата на конзолата

#include "stdafx.h"

#вклучи

користејќи именски простор std;

float f(double x) //ја враќа вредноста на функцијата f(x) = x^2-2

float df(float x) //ја враќа вредноста на изводот

float d2f(float x) // вредност на вториот извод

int _tmain (int argc, _TCHAR* argv)

int exit = 0, i=0;//променливи за излез и циклус

двојни x0,xn;//пресметани апроксимации за коренот

двојно a, b, eps; // границите на сегментот и потребната точност

коут<<"Please input \n=>";

cin>>а>>б; // внесете ги границите на сегментот на кој ќе го бараме коренот

коут<<"\nPlease input epsilon\n=>";

cin>>eps; // внесете ја потребната точност на пресметката

ако (а > б) // ако корисникот ги измешал границите на сегментот, заменете ги

ако (f(a)*f(b)>0) // ако знаците на функцијата на рабовите на отсечката се исти, тогаш тука нема корен

коут<<"\nError! No roots in this interval\n";

ако (f(a)*d2f(a)>0) x0 = a; // за да ја изберете почетната точка, проверете f(x0)*d2f(x0)>0 ?

xn = x0-f(x0)/df(x0); // разгледајте ја првата апроксимација

коут<<++i<<"-th iteration = "<

while(fabs(x0-xn) > eps) // ќе продолжи да пресметува додека не ја достигнеме потребната точност

xn = x0-f(x0)/df(x0); // директно Њутнова формула

коут<<++i<<"-th iteration = "<

коут<<"\nRoot = "<

коут<<"\nExit?=>";

) while (излез!=1); // додека корисникот не влезе во излез = 1

Ајде да видиме како функционира. Кликнете на зелениот триаголник во горниот лев агол на екранот или притиснете F5.

Ако се појави грешка при компилацијата „Грешка, грешка LNK1123: неуспех да се конвертира во COFF: датотеката е неважечка или оштетена“, тогаш ова може да се излечи или со инсталирање на првиот Service pack 1 или во поставките на проектот Својства -> Linker оневозможува поединечно поврзување.

Ориз. 4. Решавање на грешката при компилацијата на проектот

Ќе ги бараме корените на функцијата f(x) =x2-2.

Прво, да ги провериме перформансите на апликацијата на „погрешните“ влезни податоци. Нема корени на сегментот, нашата програма треба да прикаже порака за грешка.

Сега имаме прозорец со апликација:

Ориз. 5. Внесување на влезни податоци

Да ги воведеме границите на сегментот 3 и 5, а точноста е 0,05. Програмата, како што се очекуваше, произведе порака за грешка дека нема корени на овој сегмент.

Ориз. 6. Грешка „Нема корени на овој сегмент!“

Сè уште нема да заминеме, па што е со пораката „Излези?“ внесете „0“.

Сега да ја провериме апликацијата користејќи ги точните влезни податоци. Да го внесеме сегментот и точноста 0,0001.

Ориз. 7. Пресметка на коренот со потребната точност

Како што можеме да видиме, потребната точност беше постигната веќе на 4-та итерација.

За да излезете од апликацијата, внесете „Излези?“ => 1.

Секантен метод

За да се избегне пресметување на изводот, методот на Њутн може да се поедностави со замена на изводот со приближување пресметано од претходните две точки:

Повторувачкиот процес изгледа вака:

Ова е итеративен процес во два чекора, бидејќи ги користи претходните два за да ја пронајде следната апроксимација.

Редоследот на конвергенција на методот на секант е помал од оној на методот на тангента и е еднаков во случај на еден корен.

Оваа извонредна количина се нарекува златен сооднос:

Дозволете ни да го потврдиме ова, под претпоставка за погодност дека .

Така, до бесконечно малици од повисок ред

Отфрлајќи го преостанатиот член, добиваме рекурентна релација, чиешто решение природно се бара во формата.

По замена имаме: и

За конвергенција потребно е таа да биде позитивна, затоа .

Бидејќи не е потребно познавање на изводот, со исто толку пресметки во методот на секант (и покрај помалиот ред на конвергенција) може да се постигне поголема точност отколку во методот на тангента.

Забележете дека во близина на коренот треба да се подели со мал број, а тоа доведува до губење на точноста (особено во случај на повеќе корени), затоа, откако избравте релативно мал број, извршете пресметки пред да извршите и продолжуваме со нив додека не се намали модулот на разликата меѓу соседните апроксимации.

Штом ќе започне растот, пресметките се прекинуваат и последната итерација не се користи.

Оваа постапка за одредување на крајот на повторувањата се нарекува техника Гарвика.

Метод на парабола

Да разгледаме метод од три чекори во кој приближувањето се одредува со трите претходни точки и .

За да го направиме ова, ја заменуваме, слично на методот на секант, функцијата со интерполациона парабола што минува низ точките и .

Во форма на Њутн изгледа вака:

Точка се дефинира како еден од корените на овој полином што е поблиску во апсолутна вредност до точката.

Редоследот на конвергенција на методот на парабола е повисок од оној на секантниот метод, но понизок од оној на методот на Њутн.

Важна разлика од претходно разгледаните методи е фактот дека дури и ако реалните за реално и почетните приближувања се избрани да бидат реални, методот на парабола може да доведе до сложен корен на првобитниот проблем.

Овој метод е многу лесен за наоѓање корени на полиноми со висок степен.

Едноставен метод на повторување

Проблемот за наоѓање решенија на равенките може да се формулира како проблем за наоѓање корени: , или како проблем за наоѓање фиксна точка.

Нека и - компресија: (особено, фактот дека - компресија, како што е лесно да се види, значи дека).

Според теоремата на Банах, постои единствена фиксна точка

Може да се најде како граница на едноставна итеративна постапка

каде што почетната апроксимација е произволна точка во интервалот.

Ако функцијата може да се разликува, тогаш пригоден критериум за компресија е бројот . Навистина, според теоремата на Лагранж

Така, ако дериватот е помал од еден, тогаш тоа е компресија.

Состојба е од суштинско значење, бидејќи ако, на пример, на , тогаш нема фиксна точка, иако изводот е еднаков на нула. Брзината на конвергенција зависи од вредноста на . Колку е помало, толку е побрза конвергенцијата.

Нека коренот на равенката f(x)=0 е одделен на отсечката , со првиот и вториот извод f’(x) и f""(x)се континуирани и со постојан знак за xÎ.

Нека во некој чекор од рафинирање на коренот се добие следното приближување до коренот x n (избрано) . Потоа да претпоставиме дека следното приближување е добиено со помош на исправката h n , доведува до точната вредност на коренот

x = xn + hn. (1.2.3-6)

Броење h nмала вредност, ние претставуваме f(х n + h n) во форма на Тејлор серија, ограничувајќи се на линеарни членови

f(x n + h n) »f(x n) + h n f’(x n). (1.2.3-7)

Имајќи предвид дека f(x) = f(x n + h n) = 0, добиваме f(x n) + h n f '(x n) »0.

Оттука h n » - f(x n)/ f’(x n). Ајде да ја замениме вредноста h nво (1.2.3-6) и наместо точната вредност на коренот xдобиваме уште едно приближување

Формулата (1.2.3-8) ни овозможува да добиеме низа од приближувања x 1, x 2, x 3 ..., која, под одредени услови, конвергира до точната вредност на коренот x,тоа е

Геометриска интерпретација на методот на Њутне како што следува
(Сл.1.2.3-6). Да го земеме десниот крај на отсечката b како почетна апроксимација x 0 и да конструираме тангента во соодветната точка B 0 на графикот на функцијата y = f(x). Точката на пресек на тангентата со x-оската се зема како ново, попрецизно приближување x 1. Повторувањето на оваа постапка многу пати ни овозможува да добиеме низа од приближувања x 0, x 1, x 2 , . . ., што се стреми кон точната вредност на коренот x.

Формулата за пресметка на Њутновата метода (1.2.3-8) може да се добие од геометриска конструкција. Значи во правоаголен триаголник x 0 B 0 x 1 крак
x 0 x 1 = x 0 V 0 /tga. Имајќи предвид дека точката B 0 е на графикот на функцијата f (x),а хипотенузата е формирана од тангентата на графикот f(x) во точката B 0, добиваме

(1.2.3-9)

(1.2.3-10)

Оваа формула се совпаѓа со (1.2.3-8) за n-то приближување.

Од Сл. 1.2.3-6 е јасно дека изборот на точка a како почетна апроксимација може да доведе до фактот дека следното приближување x 1 ќе биде надвор од сегментот на кој е одделен коренот x. Во овој случај, конвергенцијата на процесот не е загарантирана. Во општиот случај, изборот на почетната апроксимација се врши во согласност со следново правило: почетната апроксимација треба да се земе како точка x 0 О, при која f(x 0)×f''(x 0)>0 , односно знаците на функцијата и нејзиниот втор извод се совпаѓаат.

Условите за конвергенција на Њутновиот метод се формулирани во следната теорема.

Ако коренот на равенката е одделен на отсечката, и f’(x 0) и f’’(x) се разликуваат од нула и ги задржуваат своите знаци кога xО, тогаш ако избереме таква точка како почетна апроксимација x 0 О , Што f(x 0).f¢¢(x 0)>0 , потоа коренот на равенката f(x)=0 може да се пресмета со кој било степен на точност.

Проценката на грешката на Њутновиот метод се одредува со следниот израз:

(1.2.3-11)

каде е најмалата вредност на

Највисока вредност на

Процесот на пресметка запира ако ,

каде е наведената точност.

Дополнително, следните изрази можат да послужат како услов за постигнување на одредена точност при рафинирање на коренот со помош на Њутновата метода:

Дијаграмот на алгоритмот на Њутнов метод е прикажан на сл. 1.2.3-7.

Левата страна на оригиналната равенка f(x) и нејзиниот дериват f’(x) во алгоритмот се дизајнирани како посебни софтверски модули.

Ориз. 1.2.3-7. Њутн метод алгоритам дијаграм

Пример 1.2.3-3 Рафинирај ги корените на равенката x-ln(x+2) = 0 користејќи го Њутнов метод, под услов корените на оваа равенка да се одделат на отсечките x 1 О[-1.9;-1.1] и x 2 О [-0,9;2].

Првиот извод f’(x) = 1 – 1/(x+2) го задржува својот знак на секоја од отсечките:

f'(x)<0 при хÎ [-1.9; -1.1],

f’(x)>0 на xО [-0,9; 2].

Вториот извод f"(x) = 1/(x+2) 2 > 0 за кој било x.

Така, условите за конвергенција се задоволени. Бидејќи f""(x)>0 во целиот опсег на дозволени вредности, тогаш да се разјасни коренот на почетната апроксимација x 1изберете x 0 = -1,9 (бидејќи f(-1,9)×f”(-1,9)>0). Добиваме низа приближувања:

Продолжувајќи со пресметките, ја добиваме следната низа од првите четири приближувања: -1,9; –1,8552, -1,8421; -1,8414 . Вредноста на функцијата f(x) во точката x=-1,8414 е еднаква на f(-1,8414)=-0,00003 .

За појаснување на коренот x 2 О[-0.9;2] избираме 0 =2 (f(2)×f”(2)>0) како почетна апроксимација. Врз основа на x 0 = 2, добиваме низа од приближувања: 2.0;1.1817; 1.1462; 1.1461. Вредноста на функцијата f(x) во точката x=1,1461 е еднаква на f(1,1461)= -0,00006.

Њутновиот метод има висока стапка на конвергенција, но на секој чекор бара да се пресмета не само вредноста на функцијата, туку и нејзиниот извод.

Метод на акорд

Геометриска интерпретација на методот на акорде како што следува
(Сл.1.2.3-8).

Да повлечеме отсечка низ точките A и B. Следното приближување x 1 е апсцисата на точката на пресек на акордот со оската 0x. Да ја конструираме равенката на права отсечка:

Да поставиме y=0 и да ја најдеме вредноста x=x 1 (следна приближување):

Да го повториме процесот на пресметување за да го добиеме следното приближување до коренот - x 2 :

Во нашиот случај (сл. 1.2.11) а формулата за пресметка за методот на акорд ќе изгледа вака

Оваа формула е валидна кога точката b се зема како фиксна точка, а точката a делува како почетна апроксимација.

Да разгледаме друг случај (сл. 1.2.3-9), кога .

Правилната равенка за овој случај ја има формата

Следното приближување x 1 на y = 0

Тогаш рекурентната формула на методот на акорд за овој случај ја има формата

Треба да се забележи дека фиксната точка во методот на акорд е избрана да биде крај на отсечката за која е задоволен условот f (x)∙f¢¢ (x)>0.

Така, ако точката a се земе како фиксна точка , тогаш x 0 = b делува како почетна апроксимација, и обратно.

Доволните услови кои обезбедуваат пресметување на коренот на равенката f(x) = 0 со помош на формулата на акордот ќе бидат исти како кај методот на тангента (Њутнов метод), само наместо првичното приближување се избира фиксна точка. Методот на акорд е модификација на методот на Њутн. Разликата е во тоа што следното приближување во Њутновиот метод е точката на пресек на тангентата со оската 0X, а во методот на акорд - точката на пресек на акордот со оската 0X - приближувањата се спојуваат до коренот од различни страни. .

Проценката на грешката за методот на акорд е дадена со изразот

(1.2.3-15)

Услов за завршување на процесот на повторување со помош на методот на акорд

(1.2.3-16)

Во случајот М 1<2m 1 , то для оценки погрешности метода может быть использована формула | x n -x n -1 |£д.

Пример 1.2.3-4. Појасни го коренот на равенката e x – 3x = 0, одделен на отсечката со точност од 10 -4.

Ајде да ја провериме состојбата на конвергенција:

Следствено, a=0 треба да се избере како фиксна точка, а x 0 =1 треба да се земе како почетна апроксимација, бидејќи f(0)=1>0 и f(0)*f"(0)>0.

Додека се борат на училиште со решавање равенки на часовите по математика, многу ученици честопати се убедени дека сосема залудно го трошат своето време, а сепак таквата вештина ќе биде корисна во животот не само на оние кои ќе одлучат да ги следат стапките на Декарт. Ојлер или Лобачевски.

Во пракса, на пример во медицината или економијата, често има ситуации кога специјалист треба да открие кога е концентрацијата активна супстанцијана одреден лек ќе го достигне потребното ниво во крвта на пациентот или потребно е да се пресмета времето потребно за одреден бизнис да стане профитабилен.

Најчесто зборуваме за решавање нелинеарни равенки разни видови. Нумеричките методи овозможуваат тоа да се направи што е можно побрзо, особено со користење на компјутер. Тие се добро проучени и долго време ја докажаа нивната ефикасност. Тие го вклучуваат Њутновиот тангентен метод, кој е предмет на овој напис.

Формулирање на проблемот

Во овој случај, постои функција g, која е дефинирана на сегментот (a, b) и зема одредени вредности на неа, т.е., секој x што припаѓа на (a, b) може да се поврзе со одреден број g. (x).

Потребно е да се утврдат сите корени на равенката од интервалот помеѓу точките a и b (вклучувајќи ги и краевите), за кои функцијата е поставена на нула. Очигледно, тоа ќе бидат точките на пресек на y = g(x) со OX.

Во некои случаи, попогодно е да се замени g(x)=0 со слична, како g 1 (x) = g 2 (x). Во овој случај, апсцисите (вредност x) на пресечните точки на графиконите g 1 (x) и g 2 (x) дејствуваат како корени.

Решението на нелинеарна равенка е исто така важно за оптимизациските проблеми за кои услов за локален екстрем е дериватот на функцијата да се претвори во 0. Со други зборови, таков проблем може да се сведе на наоѓање на корените на равенката p(x) = 0, каде што p(x) е идентично со g"(x).

Методи на решение

За некои видови нелинеарни равенки, како што се квадратни или едноставни тригонометриски равенки, корените може да се најдат на прилично едноставни начини. Особено, секој ученик знае формули со кои може лесно да се најдат вредностите на аргументот на точките каде што исчезнува квадратниот трином.

Методите за извлекување корени на нелинеарни равенки обично се поделени на аналитички (директни) и итеративни. Во првиот случај, саканото решение има форма на формула, со која, во одреден број аритметички операции, може да се најде вредноста на саканите корени. Слични методи се развиени за експоненцијални, тригонометриски, логаритамски и едноставни алгебарски равенки. За останатото, треба да користите специјални нумерички методи. Тие се лесни за имплементација со користење на компјутери, кои ви овозможуваат да ги пронајдете корените со потребната точност.

Тие вклучуваат т.н нумерички методтангенти. Во следните векови, методот постојано се подобруваше.

Локализација

Нумеричките методи за решавање на сложени равенки кои немаат аналитички решенија обично се изведуваат во 2 фази. Прво треба да ги локализирате. Оваа операција се состои од пронаоѓање на такви сегменти на OX на кои има еден корен од равенката што се решава.

Да го разгледаме сегментот. Ако g(x) нема дисконтинуитети на него и зема вредности на различни знаци на крајните точки, тогаш помеѓу a и b или во нив има најмалку 1 корен од равенката g(x) = 0. да биде единствен, потребно е g(x) да не е монотоно. Како што е познато, ќе го има ова својство под услов знакот g’(x) да е константен.

Со други зборови, ако g(x) нема дисконтинуитети и монотоно се зголемува или намалува, а неговите вредности на крајните точки немаат исти знаци, тогаш има 1 и само 1 корен од g(x).

Сепак, треба да знаете дека овој критериум нема да важи за корените на равенките кои се повеќекратни.

Решавање на равенка со преполовување

Пред да се разгледаат посложени нумерички тангенти и нивните сорти, вреди да се запознаете со најмногу на едноставен начинидентификување на корените. Се нарекува дихотомија и се однесува на интуитивниот начин на пронаоѓање корени, врз основа на теоремата дека ако за g(x), континуирано, условот на различни знаци е исполнет, тогаш на сегментот што се разгледува има најмалку 1 корен g( x) = 0.

За да го најдете, треба да ја поделите отсечката на половина и да ја означите средната точка како x 2. Тогаш можни се две опции: g(x 0) * g(x 2) или g(x 2) * g(x 1) се еднакви или помали од 0. Ја избираме онаа за која една од овие неравенки е точно. Ја повторуваме постапката опишана погоре додека должината не стане помала од одредена однапред избрана вредност што ја одредува точноста на одредување на коренот на равенката на .

Предностите на методот ја вклучуваат неговата веродостојност и едноставност, но недостаток е потребата првично да се идентификуваат точките во кои g(x) има различни знаци, па затоа не може да се користи за корени со рамномерна множина. Покрај тоа, тој не се генерализира во случај на систем на равенки или ако зборуваме за сложени корени.

Пример 1

Да сакаме да ја решиме равенката g(x) = 2x 5 + x - 1 = 0. За да не потрошиме долго време во потрага по соодветен сегмент, градиме график користејќи, на пример, добро познатата програма Excel . Гледаме дека е подобро да се земат вредности од интервалот како сегмент за локализирање на коренот. Можеме да бидеме сигурни дека на него постои барем еден корен од потребната равенка.

g"(x) = 10x 4 + 1, т.е. е монотоно растечка функција, така што има само 1 корен на избраниот сегмент.

Крајните точки ги заменуваме во равенката. Имаме 0 и 1 соодветно. На првиот чекор ја земаме точката 0,5 како решение. Потоа g(0,5) = -0,4375. Тоа значи дека следниот сегмент за преполовување ќе биде . Неговиот средна точка- 0,75. Во него, вредноста на функцијата е 0,226. Го земаме предвид сегментот и неговата средина, која се наоѓа на точката 0,625. Вредноста на g(x) ја пресметуваме да биде 0,625. Тоа е еднакво на -0,11, односно негативно. Врз основа на овој резултат, го избираме сегментот. Добиваме x = 0,6875. Тогаш g(x) = -0,00532. Ако точноста на решението е 0,01, тогаш можеме да претпоставиме дека посакуваниот резултат е 0,6875.

Теоретска основа

Овој метод за наоѓање корени со помош на Њутновата тангента метода е популарен поради неговата многу брза конвергенција.

Се заснова на докажаниот факт дека ако x n е приближување на коренот f(x) = 0, така што f" C 1, тогаш следното приближување ќе биде во точката каде што равенката на тангентата на f(x) се нула, т.е.

Заменете го x = x n+1 и поставете го y на нула.

Тогаш тангентите изгледаат вака:

Пример 2

Ајде да се обидеме да го користиме Њутновиот класичен метод на тангента и да најдеме решение за некоја нелинеарна равенка што е тешко или невозможно да се најде аналитички.

Нека биде неопходно да се идентификуваат корените за x 3 + 4x - 3 = 0 со одредена точност, на пример 0,001. Како што е познато, графикот на која било функција во форма на полином со непарен степен мора да ја пресече оската OX барем еднаш, т.е. нема сомнеж за постоењето на корените.

Пред да го решиме нашиот пример користејќи го методот на тангента, градиме график f(x) = x 3 + 4x - 3 точка. Ова е многу лесно да се направи, на пример, со користење на процесор за табели на Excel. Од добиениот график ќе биде јасно дека тој не се вкрстува со оската OX и функцијата y = x 3 + 4x - 3 монотоно се зголемува. Можеме да бидеме сигурни дека равенката x 3 + 4x - 3 = 0 има решение и тоа е единствено.

Алгоритам

Секое решение на равенките со методот на тангента започнува со пресметка на f "(x). Имаме:

Тогаш вториот дериват ќе биде x * 6.

Користејќи ги овие изрази, можеме да напишеме формула за идентификување на корените на равенката користејќи го методот на тангента во форма:

Следно, треба да изберете почетна апроксимација, т.е., да одлучите која точка да ја земете во предвид како почетна точка (волумен x 0) за итеративниот процес. Ги разгледуваме краевите на сегментот. Ќе го користиме оној за кој е точно условот дека функцијата и нејзиниот 2-ри извод на x 0 се со различни знаци. Како што можеме да видиме, при замена на x 0 = 0, тој е скршен, но x 0 = 1 е сосема погоден.

тогаш ако сме заинтересирани да го решиме методот на тангента со точност e, тогаш вредноста x n може да се смета дека ги задоволува барањата на задачата, под услов неравенката |f(x n) / f’(x n)|< e.

На првиот тангентен чекор имаме:

x 1 = x 0 - (x 0 3 + 4x 0 - 3) / (3x 0 2 + 4) = 1- 0,2857 = 0,71429;
бидејќи условот не е исполнет, продолжуваме понатаму;
добиваме нова вредност за x 2, што е еднакво на 0,674;
забележуваме дека односот на вредноста на функцијата со неговиот извод во x 2 е помал од 0,0063, го запираме процесот.

Метод на тангента во Excel

Претходниот пример може да го решите многу полесно и побрзо ако не ги извршувате пресметките рачно (на калкулатор), туку ги користите можностите на процесорот за табеларни пресметки од Microsoft.

За да го направите ова, треба да креирате нова страница во Excel и да ги пополните нејзините ќелии со следните формули:

во C7 пишуваме „= СТЕПЕН (B7;3) + 4 * B7 - 3“;
во D7 внесуваме „= 4 + 3 * СТЕПЕН (B7;2)“;
во E7 пишуваме „= (СТЕПЕН (B7;3)- 3 + 4 * B7) / (3* СТЕПЕН (B7;2) + 4)“;
во D7 го внесуваме изразот „=B7 - E7“;
во B8 ја внесуваме формулата за услов „=IF(E7< 0,001;"Завершение итераций"; D7)».

Во специфичен проблем, натписот „Завршувам повторувања“ ќе се појави во ќелијата Б10, а за да го решите проблемот ќе треба да го земете бројот напишан во ќелијата лоцирана една линија погоре. Можете исто така да изберете посебна „растеглива“ колона за неа со внесување формула-услов таму, според која резултатот ќе биде напишан таму ако содржината во една или друга ќелија од колоната Б има форма „Завршување на повторувања“.

Имплементација во Паскал

Ајде да се обидеме да добиеме решение за нелинеарната равенка y = x 4 - 4 - 2 * x користејќи го методот на тангента во Паскал.

Користиме помошна функција која ќе помогне да се изврши приближна пресметка f"(x) = (f(x + delta) - f(x)) / делта. Како услов за завршување на итеративниот процес го избираме исполнувањето на неравенката |x 0 -x 1 |< некого малого числа. В Паскале его запишем, как abs(x0 - x1)<= epsilon.

Програмата е забележлива по тоа што не бара рачна пресметка на дериватот.

Метод на акорд

Ајде да разгледаме друг начин да ги идентификуваме корените на нелинеарните равенки. Процесот на повторување се состои во тоа што како последователни приближувања до саканиот корен за f(x) = 0, се земаат вредностите на точките на пресек на акордот со апсцисата на крајните точки a и b со OX, означено како x 1, ..., x n. Ние имаме:

За точката каде што акордот ја пресекува оската OX, изразот ќе биде напишан како:

Нека вториот извод е позитивен за x £ (спротивниот случај ќе се сведе на разгледуваниот ако напишеме f(x) = 0). Во овој случај, графикот y = f(x) е крива, конвексна на дното и лоцирана под акордот АБ. Може да има 2 случаи: кога функцијата има позитивна вредност во точката a или е негативна во точката b.

Во првиот случај, го избираме крајот a како фиксен, а точката b ја земаме како x 0. Потоа последователните приближувања според формулата претставена погоре формираат низа што монотоно се намалува.

Во вториот случај, крајот b е фиксиран на x 0 = a. Вредностите x добиени при секој чекор на повторување формираат низа што монотоно се зголемува.

Така, можеме да констатираме дека:

во методот на акорди, фиксниот крај на сегментот е оној каде што знаците на функцијата и нејзиниот втор извод не се совпаѓаат;
апроксимации за коренот x - x m - лежат од него на страната каде што f(x) има знак што не се совпаѓа со знакот f"" (x).

Итерациите може да се продолжат додека не се исполнат условите за близина на корените на овој и претходниот чекор на повторување модуло abs(x m - x m - 1)< e.

Изменет метод

Комбинираниот метод на акорди и тангенти ви овозможува да ги утврдите корените на равенката со приближување до нив од различни страни. Оваа вредност, на која графикот f(x) го сече OX, ви овозможува да го рафинирате решението многу побрзо отколку да користите секој од методите посебно.

Да претпоставиме дека треба да ги најдеме корените на f(x)=0, ако тие постојат на . Можете да примените кој било од методите опишани погоре. Сепак, подобро е да пробате комбинација од нив, што значително ќе ја подобри точноста на коренот.

Го разгледуваме случајот со почетно приближување кое одговара на условот првиот и вториот извод да се со различни знаци во одредена точка x.

Во такви услови, решавањето на нелинеарни равенки со методот на тангента овозможува да се најде корен со вишок ако x 0 =b, а методот со помош на акорди со фиксен крај b води до пронаоѓање приближен корен со недостаток.

Користени формули:

Сега потребниот корен x мора да се пребарува во интервалот. На следниот чекор, треба да го примените комбинираниот метод на овој сегмент. Постапувајќи на овој начин, добиваме формули од формата:

Ако првиот и вториот дериват имаат различни знаци, тогаш, размислувајќи на сличен начин, за да го разјасниме коренот, ги добиваме следните повторувачки формули:

Условот што се користи е проценетата нееднаквост| b n +1 - a n +1 |< e. Иными словами, на практике приходится находить решение при помощи двух методов, но на каждом шаге требуется выяснять, насколько полученные результаты близки друг другу.

Ако горната неравенка е вистинита, тогаш како корен на нелинеарната равенка на даден сегмент, земете ја точката што е точно на половина пат помеѓу решенијата пронајдени на одреден чекор на повторување.

Комбинираниот метод лесно се имплементира во околината TURBO PASCAL. Ако навистина сакате, можете да се обидете да ги извршите сите пресметки користејќи го табеларниот метод во Excel.

Во вториот случај, неколку колони се распределени за решавање на проблемот со помош на акорди и одделно за методот предложен од Исак Њутн.

Во овој случај, секоја линија се користи за снимање на пресметките во одреден чекор на повторување користејќи два методи. Потоа, на левата страна од областа на решението, на активната работна страница е означена колона, во која се внесува резултатот од пресметувањето на модулот на разликата во вредностите на следниот итеративен чекор за секој од методите. Друг може да се користи за внесување на резултатите од пресметките врз основа на формулата за пресметување на логичката конструкција „АКО“, која се користи за да се открие дали условот е вистинит или не.

Сега знаете како да решавате сложени равенки. Методот на тангента, како што веќе видовте, се имплементира прилично едноставно, и во Pascal и Excel. Затоа, секогаш можете да ги одредите корените на равенката што е тешко или невозможно да се реши со помош на формули.

Исто како и приближување. Терминот P. понекогаш се користи во смисла на приближување на предметот (на пример, почетната P.) ... Математичка енциклопедија

Њутнов метод- Њутновиот метод, Њутновиот алгоритам (познат и како метод на тангента) е итеративен нумерички метод за наоѓање на коренот (нула) на дадена функција. Методот првпат го предложи англискиот физичар, математичар и астроном Исак Њутн... ... Википедија

Еден тангентен метод

Гаус-Њутн метод- Њутновиот метод (познат и како метод на тангента) е итеративен нумерички метод за наоѓање на коренот (нула) на дадена функција. Методот првпат беше предложен од англискиот физичар, математичар и астроном Исак Њутн (1643 1727), под името ... ... Википедија

Њутн-Рафсон метод- Њутновиот метод (познат и како метод на тангента) е итеративен нумерички метод за наоѓање на коренот (нула) на дадена функција. Методот првпат беше предложен од англискиот физичар, математичар и астроном Исак Њутн (1643 1727), под името ... ... Википедија

Метод на тангента- Њутновиот метод (познат и како метод на тангента) е итеративен нумерички метод за наоѓање на коренот (нула) на дадена функција. Методот првпат беше предложен од англискиот физичар, математичар и астроном Исак Њутн (1643 1727), под името ... ... Википедија

Метод на тангента (метод на Њутн)- Њутновиот метод (познат и како метод на тангента) е итеративен нумерички метод за наоѓање на коренот (нула) на дадена функција. Методот првпат беше предложен од англискиот физичар, математичар и астроном Исак Њутн (1643 1727), под името ... ... Википедија

Нумеричко решение на равенките- и нивните системи се состојат од приближно определување на коренот или корените на равенката или систем на равенки и се користат во случаи кога е невозможно или многу макотрпно да се пресмета точната вредност. Содржина 1 Изјава за проблем 2 Нумерички методи ... Википедија

Метод на последователна апроксимација- метод за решавање на математички задачи со помош на низа од приближувања што се конвергира во решение и се конструира рекурзивно (т.е. секое ново приближување се пресметува врз основа на претходното; почетната апроксимација се избира во ... ... Голема советска енциклопедија

Во проблемот на минимизирање на функцијата од огромно значење е успешниот избор на почетната апроксимација.Секако дека е невозможно да се дојде до општо правило кое би било задоволително за сите случаи, односно за сите можни нелинеарни функции. Секој пат кога треба да барате сопствено решение. Подолу предлагаме збир на неколку методи за пронаоѓање груби почетни приближувања, кои во пракса можат да послужат како почетна точка за пребарување на задоволителни приближувања во одреден проблем.

9.6.1. Пребарување на мрежа. Овој метод е особено ефикасен со мал број реални нелинеарни параметри. Често функциите се дизајнирани на таков начин што кога вредностите на некои параметри (кои ги нарекуваме нелинеарни) се фиксирани, останатите параметри стануваат линеарни.

Откако ќе ги наведете долните и горните граници за нелинеарните параметри, со одреден чекор е можно да се набројат опциите на добиената мрежа на вредности на самите овие нелинеарни параметри и да се идентификува линеарната регресија што доведува до минимален збир на квадрати. .

Како пример, разгледајте ја функцијата

Тука вистинскиот нелинеарен параметар ќе биде . Да речеме дека се знае дека . Нека h е чекорот за параметарот. Ајде да пресметаме линеарни регресии

каде што го наоѓаме минималниот збир на квадрати за секој од нив. Најмалиот од нив одговара на оптималната почетна апроксимација. Во принцип, чекорот од кој зависи „густината“ на решетката може да варира, така што со намалување на вредноста на h, вредностите на параметрите може да се најдат со секаква точност.

9.6.2. Трансформација на моделот.

Понекогаш, со одредена трансформација, моделот може да се намали на линеарен или бројот на вистински нелинеарни параметри може да се намали (види дел 6.2.3). Дозволете ни да покажеме како тоа може да се постигне користејќи го примерот на логистичка крива

Вршејќи ја инверзната трансформација на соодветните регресивни равенки, добиваме

Со означување доаѓаме до нова функција чиј број на линеарни параметри е зголемен од еден на два. Проценката за параметарот во новиот модел може да се најде, на пример, со користење на претходниот метод.

Овде е соодветно да се направи следната забелешка за трансформациите на регресивните модели. Треба да се има на ум дека грешката што беше адитивна во првобитната равенка, генерално кажано, повеќе нема да биде адитивна по трансформацијата.

Користејќи го проширувањето на серијата Тејлор и означувајќи ја трансформацијата со, добиваме, занемарувајќи ги условите за нарачка

Го следи тоа

Последната еднаквост може да се земе како основа за анализа на проблемот со трансформиран модел.

9.6.3. Поделба на примерокот во подпримероци.

За да ја пронајдете почетната апроксимација, можете да го поделите целиот примерок на подпримероци (со приближно еднакви волумени), каде што е бројот на непознати параметри. За секој потпримерок ги наоѓаме просеците над y и над X кои ги означуваме соодветно со m. Да го решиме системот на нелинеарни равенки за

Решението за овој систем ќе биде првичното приближување на параметрите. Очигледно, за да може овој метод да „работи“, неопходно е овој систем на нелинеарни равенки да се реши прилично лесно, на пример аналитички.

9.6.4. Проширување на серијата Тејлор во независни променливи.

Основата на итеративното минимизирање на збирот на квадрати е проширувањето на функцијата за регресија во Тејлоровата серија до линеарни членови во параметрите. За да се најде груба почетна апроксимација, понекогаш е корисна процедурата за апроксимација на регресија со нејзино проширување во Тејлор серија во независни променливи. За едноставност, ќе претпоставиме дека е еднодимензионален. Нека е просечната вредност, тогаш приближно

Означуваме , така што доаѓаме до линеарниот модел

Нека се проценките на најмалите квадрати на параметрите на оваа линеарна регресија. Како почетни апроксимации ќе го земеме решението на нелинеарен систем на равенки во однос на