Методы решения нелинейных уравнений. Алгоритмы методов хорд и касательных

Метод хорд применяют для решения нелинейных уравнений F(x)=0 обычно в тех случаях , когда получить выражение  для  производной dF(x)/dx либо трудно, либо оно  имеет громоздкий вид . В этом случае выражение для производной в  формуле (4.3) заменяют его разностным аналогом, после чего формула (4.3) принимает вид

  

Можно дать и  геометрическую интерпретацию метода хорд (рис. 3). 
 
 

Рис 3. Геометрическая интерпретация метода хорд для решения

нелинейного уравнения F(x)=0 
 
 
 

Для начала решения выбираются две произвольные точки на оси x. На нашем рисунке это точки x0 и x1. Затем через две точки (x0,F(x0)) и (x1,F(x1)) проводится хорда.  Эта хорда пересекает линию y=0 в точке x2. Эта точка считается первым приближением к корню. Далее, если |F(x2)|>eps или |(x0-x1)|>eps (eps - требуемая погрешность в вычислении корня) , тогда точки x1 и x2 выбирают в качестве новых стартовых точек, т.е. x0=x1, x1=x2 и вновь проводят хорду и т.д. Критерием окончания итерационного прцесса считается достаточная близость модуля значения функции |F(x2)| к нулю, а также достаточно близкие значения двух поледовательных приближений к корню x0 и x1. Чтобы найти, в какой точке хорда, проведенная через точки (x0,F(x0)) и (x1,F(x1)), пересекает ось x, напишем уравнение этой хорды:

                     y(x)=F(x1) + (F(x1)-F(x0))*(x-x1)/(x1-x0).

Решая уравнение  y(x2)=0,  получаем формулу (4.4). Блок-схема программы для решения уравнения F(x)=0 методом хорд имеет следующий вид (рис 4.6).

Блок-схема  программы для  решения нелинейного  уравнения F(x)=0 методом  хорд

 
 
 
 
 
 
 
 

Метод деления отрезка  пополам (бисекций)

Метод бисекции для решения уравнения F(x)=0 можно применять, если Вам известен такой отрезок [x0,x1],  на границах которого функция F(x)  имеет разные знаки. Проверить, что функция имеет разные знаки на концах отрезка [x0,x1], можно, вычислив произведение F(x0)*F(x1). Если у этого произведения отрицательный знак - значит функция имеет разные знаки на концах отрезка. Разные знаки функции на концах отрезка гарантируют, что внутри этого отрезка

имеется хотя бы один корень. В этом случае применяется  следующий алгоритм поиска корня:

1. Находим  середину отрезка x2=(x1+x0)/2.

2. Проверяем,  на какую половину отрезка  попал корень. Для этого проверяем знак произведения F(x0)*F(x2). Если знак этого произведения меньше нуля - значит, корень попал на первую половину отрезка, т. е. на отрезок [x0,x2]. Тогда переносим точку x1 в x2. Если знак произведения положителен - значит, корень попал на вторую половину отрезка т.е. на отрезок [x2,x1]. Тогда переносим точку

x0 в  x2. Таким образом получаем новый отрезок [x0,x1], на котором локализован корень и который в два раза меньше исходного.

3. Проверяем  длину нового отрезка [x0,x1]. Если  она меньше требуемой точности  определения корня - тогда окончание  работы. Если же длина вновь полученного отрезка больше требуемой точности определения корня, тогда переход на пункт 1.

     В дальнейшем требуемую погрешность  в определении корня будем  обозначать eps. Блок-схема программы  для решения уравнения  F(x)=0 методом  бисекций дана на рис. 4. 

    
 
 

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Рис. 4. Блок схема метода деления отрезка  пополам. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Ручной  счет 

1. Метод хорд. 

х³ +3х²-3 = 0    ε = 0,001 уточнить корень [а,b] = [-3,-2] 

1) Первая итерация.

x=-2.5

x1=x-(f(x)*(x-a)/f(x)-f(a))

x1=-2.5-((-15.625+18.75-3)*0.5)/((-15.625+18.75-3)-(-27+27-3))=-2.5-(0.062/3.125)=-2.5-0.02=-2.52

|x1-x|=|-2.52+2.5|=0.02;

0.02>ε

x=x1

2) Вторая итерация.

x=-2.52

x1=-2.52-((-16.003+19.05-3)*0.48)/((-16.003+19.05-3)-(-27+27-3))=-2.52-(0.0225/3.047)= -2.5-0.007=-2.527

|x1-x|=|-2.527+2.52|=0.0076

0.0076>ε

x=x1

3) Третья итерация.

x=-2.527

x1=-2.527-((-16.136+19.157-3)*0.473)/((-16.136+19.157-3)-(-27+27-3))=-2.527-(0.0099/3.021)= -2.57-0.003=-2.53042

|x1-x|=|-2.532+2.527|=0.0028

0.0028>ε

x=x1

4) Четвертая итерация.

x=-2.53042

x1=-2.53042-((-16.194+19.202-3)*0.47)/((-16.194+19.202-3)-(-27+27-3))=-2.53042-(0.0037/3.008)= -2.53042-0.001=-2.5314

|x1-x|=|-2.5314+2.53|=0.0011

0.0011>ε

x=x1

5) Пятая итерация.

x=-2.5314

x1=-2.5314-((-16.22+19.223-3)*0.47)/((-16.194+19.202-3)-(-27+27-3))=-2.527-(0.0018/3.0039)= -2.5314-0.0004=-2.53144

|x1-x|=|-2.53145+2.5314|=0.0004

0.0004<ε

Ответ: количество итераций – 5, x = -2.53144 
 
 
 
 

2. Метод касательных. 

x-sinx = 0,25   ε = 0,001   [а,b] = [0, п/2]

F(x)=x-sinx;

F^|(x)=1-cos(x);

1) Первая итерация.

x=0.2

x1=x-f(x)/f^|(x)

x1=0.2-(0.2-0.198)/(1-0.98)=0.2-(0.002/0.02)= 0.2-0.07=0.13

|x1-x|=|0.13-0.2|=0.07

0.07> ε

x=x1

2) Вторая итерация.

x=0.13

x1=x-f(x)/f^|(x)

x1=0.13-(0.13-0.129)/(1-0.991)=0.13-(0.001/0.009)= 0.13-0.05=0.08

|x1-x|=|0.08-0.13|=0.044

0.044> ε

3) Третья итерация.

x=0.08

x1=x-f(x)/f^|(x)

x1=0.08-(0.08-0.079)/(1-0.996)=0.08-(0.001/0.004)= 0.08-0.03=0.05

|x1-x|=|0.05-0.08|=0.03

0.03> ε

4) Четвертая итерация.

x=0.05

x1=x-f(x)/f^|(x)

x1=0.05-(0.05-0.049)/(1-0.998)=0.05-(0.001/0.002)= 0.05-0.02=0.03

|x1-x|=|0.03-0.05|=0.02

0.02> ε

5) Пятая итерация.

x=0.03

x1=x-f(x)/f^|(x)

x1=0.03-(0.03-0.0299)/(1-0.999)=0.13-(0.0001/0.001)= 0.03-0.01=0.02

|x1-x|=|0.02-0.03|=0.01

0.01> ε

6) Шестая итерация.

x=0.02

x1=x-f(x)/f^|(x)

x1=0.02-(0.02-0.0199)/(1-0.999)=0.02-(0.0101/0.001)= 0.02-0.003=0.017

|x1-x|=|0.017-0.002|=0.008

0.008> ε 
 
 
 
 

7) Седьмая итерация.

x=0.017

x1=x-f(x)/f^|(x)

x1=0.017-(0.017-0.0169)/(1-0.999)=0.017-(0.0001/0.001)= 0.017-0.0591=0.011

|x1-x|=|0.011-0.017|=0.0058

0.0058> ε

8) Восьмая итерация.

x=0.011

x1=x-f(x)/f^|(x)

x1=0.011-(0.011-0.0109)/(1-0.999)=0.011-(0.0001/0.001)= 0.011-0.004=0.007

|x1-x|=|0.007-0.011|=0.0039

0.039> ε

9) Девятая итерация.

x=0.007

x1=x-f(x)/f^|(x)

x1=0.007-(0.007-0.0069)/(1-0.999)=0.007-(0.0002/0.001)= 0.007-0.002=0.005

|x1-x|=|0.005-0.007|=0.0026

0.026> ε

10) Десятая итерация.

x=0.005

x1=x-f(x)/f^|(x)

x1=0.005-(0.005-0.0109)/(1-0.999)=0.005-(0.0002/0.001)= 0.005-0.002=0.003

|x1-x|=|0.003-0.005|=0.0017

0.017> ε

11) Одиннадцатая итерация.

x=0.003

x1=x-f(x)/f^|(x)

x1=0.003-(0.003-0.0299)/(1-0.999)=0.003-(0.0001/0.001)= 0.003-0.001=0.0023

|x1-x|=|0.0022-0.003|=0.0012

0.0012> ε

12) Двенадцатая итерация.

x=0.0023

x1=x-f(x)/f^|(x)

x1=0.0023-(0.0023-0.00219)/(1-0.999)=0.0023-(0.0001/0.001)= 0.0023-0.0006=0.0015

|x1-x|=|0.0015-0.0022|=0.0008

0.0008< ε

Ответ: количество итераций – 12, x=0.0015 
 
 
 
 
 
 

3. Метод хорд и касательных. 

х³+3х²-3 = 0     ε=0.001   [a,b] = [-2,75;-2,5]

f(x)= х³+3х²-3

f^|(x)=3x²+6x

1) Первая итерация

x= -2.6

x1=x-(f(x)*(x-a)/f(x)-f(a))

y1= x-f(x)/f^|(x)

x1=-2.6-((-17.576+20.28-3)*0.15)/((-17.576+20.28-3)-(-20.79+22.68-3))=-2.6-(0.044/1.406)=

=-2.545

y1= -2.6-(-2.6-(-17.576+20.28-3))/(20.28-15.6)=-2.6-(-2.896/4.68)= -2.537

|x1-y1|=|-2.545+2.537|=0.0087

0.0087> ε

x=x1

y=y1

2) Вторая итерация

x= -2.545

y=-2.537

x1=x-(f(x)*(x-a)/f(x)-f(a))

y1= x-f(x)/f^|(x)

x1=-2.545-((-16.48+19.431-3)*0.205)/((-16.48+19.431-3)-(-20.79+22.68-3))=-2.545-                      (-0.001/1.12)=-2.535

y1= -2.537-(-2.537-(-16.329+19.309-3))/(19.309-15.222)=-2.537-(-3.02/4.087)= -2.532

|x1-y1|=|-2.535+2.532|=0.0027

0.0027> ε

x=x1

y=y1

3) Третья итерация

x= -2.535

y= -2.532

x1=x-(f(x)*(x-a)/f(x)-f(a))

y1= x-f(x)/f^|(x)

x1=-2.535-((-16.29+19.27-3)*0.215)/((-16.29+19.27-3)-(-20.79+22.68-3))=-2.535-                   (-0.00431/1.08)=-2.533

y1= -2.532-(-2.532-(-16.329+19.309-3))/(19.309-15.222)=-2.532-(-3.02/4.087)= -2.532

|x1-y1|=|-2.533+2.532|=0.001

0.001 = ε

Ответ: количество итераций - 3, x=2.533, y=2.532 
 
 
 
 
 
 

Блок  – схемы 

1. Метод хорд