Решение нелинейных уравнений численными методами

ФГОУ ВПО  «Санкт-Петербургский государственный  университет»

Факультет прикладной математики – процессов управления

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Вычислительная  математика

 

Решение нелинейных уравнений численными методами

 

 

 

 

 

 

 

 

 

 

Выполнил: студент 231 группы

Вельямидов Виталий Альбертович

Проверил: д.ф.-м.н., профессор

Перегудин Сергей Иванович

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Санкт-Петербург

2013

1.Метод половинного деления

 

Метод основан на следующем следствии  из теоремы Больцано — Коши:

Пусть непрерывная функция

Тогда, если  то

Таким образом, если мы ищем ноль, то на концах отрезка функция должна быть противоположных знаков. Разделим отрезок  пополам и возьмём ту из половинок, на концах которой функция по-прежнему принимает значения противоположных  знаков. Если значение функции в  серединной точке оказалось искомым  нулём, то процесс завершается.

 

 

2.   Метод хорд

Будем искать нуль функции  . Выберем две начальные точки  ( ; ) и  ( ; ) и проведем через них прямую. Она пересечет ось абсцисс в точке ( ;0). Теперь найдем значение функции с абсциссой  . Временно будем считать   корнем на отрезке [ ; ]. Пусть точка   имеет абсциссу   и лежит на графике. Теперь вместо точек   и   мы возьмём точку   и точку  . Теперь с этими двумя точками проделаем ту же операцию и так далее, то есть будем получать две точки   и   и повторять операцию с ними. Отрезок, соединяющий последние две точки, пересекает ось абсцисс в точке, значение абсциссы которой можно приближённо считать корнем. Эти действия нужно повторять до тех пор, пока не получим значение корня с нужным приближением.

Пусть   − абсциссы концов хорды,   − уравнение прямой, содержащей хорду. Найдем коэффициенты   и   из системы уравнений:

.

Вычтем из первого  уравнения второе:

, затем найдем коэффициенты   и  :

, тогда                .

Уравнение принимает  вид:       

Таким образом, теперь можем найти первое приближение  к корню, полученное методом хорд:

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

 

 

 

 

 

 

3. Метод Ньютона (касательных)

 

Дано нелинейное уравнение (3.1) f(x)=0. Корень отделен x^* Î [a;b]. Требуется уточнить корень с точностью ε.

Метод основан на стратегии постепенного уточнения корня. Формулу уточнения  можно получить из геометрической иллюстрации  идеи метода.

 

 

 

 

 

 

 

 

На отрезке  существования корня  выбирается начальное приближение x₀. К кривой f(x)  в точке А с координатами (x₀, f(x₀)) проводится касательная. Абсцисса  x₁ точки пересечения этой касательной с осью ОХ  является новым приближением корня.

Из рисунка следует, что   x₁ = x₀  − CB

Из  ∆ABC: CD=.    Но  .

Следовательно,

Аналогично, для i-го приближения можно записать формулу итерационного процесса метода Ньютона:

,     где   x₀ Î [a;b]. (3.13)

Условие окончания расчета:  , (3.14)

где −корректирующее приращение или поправка.

Условие сходимости  итерационного  процесса:

(3.15)

Если на отрезке существования  корня знаки  и не изменяются, то начальное приближение, обеспечивающее сходимость, нужно выбрать из условия

,  x₀Î[a;b]. (3.16)

т.е. в точке  начального приближения  знаки функций и ее второй производной должны совпадать. Иначе итерационный процесс будет сходиться медленнее или вообще расходиться.

 

 

 

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

 

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

 

Пусть дано уравнение f(x) = 0, корень отделен на отрезке [a, b].

 

Рассмотрим  случай, когда f ‘(x) f ’’(x)>0:

 

В этом случае метод хорд дает приближенное значение корня с недостатком (конец b неподвижен), а метод касательных – с избытком (за начальное приближение берем точку b).

 

Тогда вычисления следует проводить по формулам:

Теперь корень ξ заключен в интервале [a₁, b₁]. Применяя к этому отрезку комбинированный метод, получим:

и т.д. 

 

 

 

Если же f ‘(x) f ’’(x)<0, то, рассуждая аналогично, получим следующие формулы для уточнения корня уравнения:

 

 

 

 

 

 

Вычислительный  процесс прекращается, как только выполнится условие:

 

 

 

 

 

5.  Пример

 

Рассмотрим  действие численных методов  на примере уравнения 

 функция   определена и непрерывна на

построим ее график:

 

 

 

Как видно по графику, функция  имеет единственный корень на промежутке [2,5].

 

И действительно, f(2)<0, a f(5)>0

что говорит о том, что  на интервале [2,5] есть корень.

 

 

 

 

Таким образом, все условия  для метода половинного деления и метода хорд выполнены.

 

Для метода Ньютона необходимо посчитать производную.

Далее выберем начальную  точку для метода Ньютона, из условия 

,

Следовательно, за начальную  точку примем .

 

Для смешанного метода хорд и касательных мы имеем второй случай (см. п.4), когда

f ‘(x) f ’’(x)<0

 

Поэтому будем пользоваться формулами

 

 

 

 

 

 

 

 

 

 

 

 

6. Реализация( С++ )

#include <iostream>

#include <math.h>

 

double Function( double x )

{

return ( ( log(x) / log(double(10)) ) - ( 7 / ( 2*x + 6 ) ) );

}

double DifFunction( double x )

{

return ( ( 1 / ( x * log(double(10)) ) ) + ( 7 / ( 2 * ( x + 3 ) * ( x + 3 ) ) ) );

}

 

struct MSNE // methods for solving of nonlinear equations

{

double (*func)(double);

double (*diffunc)(double);

double epsilon; // precision

int count;

 

MSNE( double (*function)(double), double (*diffunction)(double), double precision )

: epsilon( precision ), count(0)

{

func = function;

diffunc = diffunction;

}

bool Sign ( double value )

{

return value > 0 ? true : false;

}

bool IsRoot ( double value )

{

return func( value ) == 0 ? true : false;

}

 

 // assumed, must be the root of the [a,b]

double Bisection( double a, double b)

{

count = 0;

if ( IsRoot(a) ) return a;

if ( IsRoot(b) ) return b;

 

double dx = b-a;

double c;

do

{

++count;

dx /= 2;

c = a + dx;

if ( IsRoot(c) ) return c;

if ( Sign( func(a) ) == Sign( func(c) ) ) { a = c; }

else { b=c; }

} while ( dx > epsilon );

 

return ( a + dx/2 );

  }

 

double Chords( double a, double b )

{

count = 0;

if ( IsRoot(a) ) return a;

if ( IsRoot(b) ) return b;

 

while ( abs( b - a ) > epsilon )

{

++count;

a = b - (b - a) * func(b)/(func(b) - func(a));

if ( abs( b - a ) < epsilon ) return a;

++count;

b = a - (a - b) * func(a)/(func(a) - func(b));

}

return b;

}

 

double Newton( double x0 )

{

count = 0;

if ( IsRoot(x0) ) return x0;

double x;

do

{

x = x0 - ( func(x0) / diffunc(x0) );

++count;

if( abs( x - x0 ) < epsilon ) return x;

x0 = x - ( func(x) / diffunc(x) );

++count;

}while( abs( x0 - x ) > epsilon );

 

return x0;

}

 

double ChordsAndTangents ( double a, double b )

{

count = 0;

if ( IsRoot(a) ) return a;

if ( IsRoot(b) ) return b;

while( abs( b-a ) > epsilon )

{

++count;;

b = b - ( ( func(b) * ( b-a ) ) / ( func(b) - func(a) ) );

a = a - ( func(a) / diffunc(a) );

}

return ( a + abs( b - a ) );

}

};

 

int main ( int argc, char argv[] )

{

double precision = 0.0001;

MSNE example( Function, DifFunction,  precision);

 

std:: cout  << "Bisection method\t" << example.Bisection( 2, 5 );

std:: cout << "\tsteps = " << example.count << std :: endl;

 

std:: cout  << "Chord's method\t" << example.Chords( 2, 5 );

std:: cout << "\tsteps = " << example.count << std :: endl;

 

std:: cout  << "Newton's method \t" << example.Newton( 2 );

std:: cout << "\tsteps = " << example.count << std :: endl;

 

std:: cout  << "Chord's and tanget's method\t" << example.ChordsAndTangents( 2, 5 );

std:: cout << "\tsteps = " << example.count << std :: endl;

 

 

system("pause");

return 0;

}

 

 

 

 

 

7. Итог

 

Программа работает корректно.

Для примера, рассмотренного в пункте 5, после запуска программы получаем результат:

 

 

Bisection method    3.47304 steps = 15

Chord's method    3.47301 steps = 5

Newton's method    3.47301 steps = 4

Chord's and tangent's method 3.47301 steps = 4

 

Из чего делаем вывод, что метод половинного деления не сильно эффективен и точен, метод хорд чуть менее эффективен метода касательных и смешанного метода.

В целом, считаю хорошей эффективность и точность вычислений для методов хорд, Ньютона и хорд и касательных.