Численные методы решения нелинейных уравнений - файл n1.doc

Численные методы решения нелинейных уравнений
Скачать все файлы (351.5 kb.)

Доступные файлы (1):
n1.doc352kb.16.02.2014 00:48скачать

n1.doc



Министерство образования и науки Российской Федерации

САРАТОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ИМЕНИ Н.Г. ЧЕРНЫШЕВСКОГО

Кафедра дискретной математики и

информационных технологий

ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ НЕЛИНЕЙНЫХ УРАВНЕНИЙ
КУРСОВАЯ РАБОТА


Студента 2 курса, 221 гр.

дневного отделения факультета КНиИТ

Никитина Сергея Вадимовича


Научный руководитель

доцент каф. ДМиИТ, к.ф.-м.н. ________________ Л.В.Кузнецова


Зав. кафедрой ДМиИТ

к.ф.-м.н., доцент ________________ Л. Б. Тяпаев

Саратов, 2011 г.

Содержание


Введение ................................................................................................................ 3

1. Постановка задачи и общие сведения о нелинейных уравнениях................ 4

2. Основные численные методы решения нелинейных уравнений.................. 8

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

2.2. Метод простых итераций ............................................................................. 11

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

2.4. Модифицированный метод Ньютона (метод секущих)............................. 17

2.5. Метод хорд .................................................................................................... 18

Заключение ........................................................................................................... 20

Список использованных источников ................................................................. 21

Приложения............................................................................................................27

1. Приложение А. Программа поиска решения нелинейного уравнения методом половинного деления.............................................................................................22

2. Приложение Б. Программа поиска решения нелинейного уравнения методом простых итераций. .................................................................................................23

3. Приложение В. Программа поиска решения нелинейного уравнения методом Ньютона (методом касательных)..........................................................................24

4. Приложение Г. Программа поиска решения нелинейного уравнения методом хорд..........................................................................................................................25


Введение

Если законы функционирования модели нелинейны, а моделируемые процесс или система обладают одной степенью свободы (т.е. имеют одну независимую переменную), то такая модель, как правило, описывается одним нелинейным уравнением.

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

Данная работа ориентирована на изучение некоторых численных методов решения нелинейных уравнений (метод половинного деления, метод простых итераций, метод Ньютона (метод касательных), модифицированный метод Ньютона (метод секущих), метод хорд), составление на базе этих методов вычислительных блок-схем алгоритмов и программ на языке C++ (Microsoft Visual Studio 2005).


1. Постановка задачи и общие сведения о нелинейных уравнениях Поставим задачу. Она рассматривается в работе Ю.В. Губарь [1]. Рассмотрим методы численного решения уравнений представленных в формулах (1) и (2):

. (1)
Или
. (2)

где f,f1…fn – некие функции, x1,…xn – аргументы функций.
Численное решение задачи можно проводить как используя численные методы, так и с применением оптимизационных методов, приведя задачу к соответствующему виду. Мы рассмотрим только численные методы решения.

Пусть нам дано нелинейное уравнение f(x)=0.

Нужно найти его корень . Это решение изображено графически на рисунке 1.



Рис 1. Нелинейное уравнение и его решение
Пусть функция имеет вид многочлена степени m.
(3)
где ai - коэффициенты многочлена, 1?i?m, то уравнение f(x)=0 имеет m корней. Схематически это изображено на рисунке 2.

Рис 2. Функция имеющая вид многочлена
Уравнение называется трансцендентным уравнением. Если функция f(x) включает в себя тригонометрические или экспоненциальные функции от некоторого аргумента x
Примеры:




В таких уравнениях обычно нет четкого числа корней – их бесконечное множество. Не все уравнения могут быть решены точно. Главным образом это отражается в большинстве трансцендентных уравнений.

Доказано также, что нельзя построить формулу, по которой можно было бы решать произвольные алгебраические уравнения степени, выше четвертой.

Однако предельно точное решение уравнения не всегда является необходимым. Задачу отыскания корней уравнения можно считать практически решенной, если мы сумеем найти корни уравнения с заданной степенью точности. Для этого используются приближенные (численные) методы решения.

Большинство употребляющихся приближенных методов решения уравнений являются, по существу, способами уточнения корней. То есть получение значения с какой-то определенной точностью. Для этого необходимо определить интервал изоляции [a,b], в котором лежит уточняемый корень уравнения. Это можно увидеть на рисунке 3.



Рис. 3. Функция с интервалом изоляции

Процесс определения интервала изоляции [a,b], содержащего только один из корней уравнения, называется отделением этого корня.

Процесс отделения корней проводят исходя из физического смысла прикладной задачи, графически, с помощью таблиц значений функции f(x) или при помощи специальной программы отделения корней. Процедура отделения корней основана на известном свойстве непрерывных функций: если функция непрерывна на замкнутом интервале [a,b] и на его концах имеет различные знаки, т.е. f(a)f(b)<0, то между точками a и b имеется хотя бы один корень уравнения. Если при этом знак функции f'(x) на отрезке [a,b] не меняется, то корень является единственным на этом отрезке.

Процесс определения корней алгебраических и трансцендентных уравнений проходит в 2 этапов:

  1. отделение корней, - т.е. определение интервалов изоляции [a,b], внутри которого лежит каждый корень уравнения;

  2. уточнение корней, - т.е. сужение интервала [a,b] до величины равной заданной степени точности .

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

  1. метод половинного деления (метод дихотомии);

  2. метод простых итераций;

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

  4. модифицированный метод Ньютона (метод секущих);

  5. метод хорд

Все эти методы будут подробно описаны ниже. Описание взято из работы Ю.В. Губарь [1].







2. Основные численные методы решения нелинейных уравнений

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


Рассмотрим нелинейное уравнение (4):

f(x)=0. (4)

Требуется найти его корень, с заданной точностью , который лежит в интервале [a,b].

В этом методе фактически берется ответ из заданного интервала [a,b] и уточняется до нужной точности .

Для уточнения корня методом половинного деления последовательно осуществляем следующие операции:

  1. Интервал делится пополам (находится его середина t) по формуле (5).

, (5)

где a,b – концы интервала [a,b].

  1. В качестве нового интервала изоляции принимаем ту половину интервала, на концах которого функция имеет разные знаки (рис.4).




Рис.4. Уточнение корня уравнения методом половинного деления
Делается это следующим образом:

a) Вычисляем значение функции f(x) в точках a и t.

b) Проверяем: если f(a)f(t) < 0, то корень находится в левой половине интервала [a,b] (рис.4.а). Тогда отбрасываем правую половину интервала и делаем переприсвоение b=t.

c) Если f(a)f(t) < 0 не выполняется, то корень находится в правой половине интервала [a,b] (рис.4.б). Тогда отбрасываем левую половину и делаем переприсвоение a=t. В обоих случаях мы получим новый интервал [a,b] в 2 раза меньший предыдущего.

  1. Процесс, начиная с пункта 1, циклически повторяем до тех пор, пока длина интервала [a,b] не станет равной либо меньшей заданной точности, т.е. выполняется условие (6)

(6)

В программировании этот метод известен как метод тернарного поиска (разновидность бинарного поиска). Он используется для решения многих геометрических задач.

На рисунке 5 изображена блок-схема с данным алгоритмом уточнения корней по методу половинного деления.




Рис. 5.  Схема алгоритма уточнения корней по методу половинного деления
Также в приложении А представлена программа написанная на языке программирования С++ (Microsoft Visual Studio 2005), описывающяя этот алгоритм на примере функции f(x)=x3-7.

2.2 Метод простых итераций

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

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

Пусть перед нами стоит та же задача: необходимо с точностью   найти корень уравнения f(x)=0, принадлежащий интервалу изоляции [a,b]. Функция f(x) и ее первая производная непрерывны на этом отрезке.

Для применения этого метода исходное уравнение (4) должно быть приведено к виду (7):

. (7)

В качестве начального приближения 0 выбираем любую точку интервала [a,b].

Далее итерационный процесс поиска корня строится по схеме (8)

. (8)

В результате итерационный процесс поиска реализуется рекуррентной формулой (9)

. (9)

Процесс поиска прекращается, как только или число итераций превысит заданное число N.

Для того, чтобы последовательность х1, х2,…, хn приближалась к искомому корню, необходимо, чтобы выполнялось условие сходимости (10)

(10)

Графически это представлено на рисунке 6.




Рис. 6.  Геометрический смысл метода простых итераций

Теперь построим блок-схему алгоритм поиска корня методом простых итераций (рис. 7). Вычисление функции  оформим в виде подпрограммы.



Рис. 7. Схема алгоритма поиска корня методом простых итераций
Реализация в виде программного кода, с подробными комментариями представлена в Приложении Б. В отличие от предыдущего примера функция f(x) (а также функция ) в этом примера не определена, а лишь обозначена. Так как для каждого графика функций они уникальны. Так будут описываться процедуры вычисления функций и производных и в последующих примерах. А именно:
double fi(double x) //функция вычисляющее x=fi(x)

{

...

}
double f(double x) //вычисление значения функции f(x)

{

...

}
Подробности смотреть в приложении Б.

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


Этот метод был предложен И.Ньютоном в 1669 году, однако наиболее полное обоснование было сделано советским математиком Л.В.Канторовичем в 1949 году (см.[4]), поэтому в литературе этот метод часто называют методом Ньютона-Канторовича. Это дает работа Левицкого А.А. [3].

Рассмотренные ранее методы решения нелинейных уравнений являются методами прямого поиска. В них для нахождения корня используется нахождение значения функции в различных точках интервала [a,b].

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

Дано всё тоже нелинейное уравнение (4):

f(x)=0

Найти корень на интервале [a,b] с точностью .

Метод Ньютона основан на замене исходной функции f(x), на каждом шаге поиска касательной, проведенной к этой функции. Пересечение касательной с осью Х дает приближение корня (Рис.8).

Выберем начальную точку x0=b (конец интервала изоляции). Находим значение функции в этой точке и проводим к ней касательную, пересечение которой с осью Х дает нам первое приближение корня x1. См. формулу (11).


Рис. 8. Решение нелинейного уравнения методом половинного деления
x1 = x0 – h0, (11)

где h0, вычисляется по формуле (12)

(12)

Поэтому уравнение (11) примет вид (13)

(13)

В результате итерационный процесс схождения к корню реализуется рекуррентной формулой (14)

. (14)

Процесс поиска продолжаем до тех пор, пока не выполнится условие (15).

. (15)

Упростим условие (15), исходя из формулы (13). И, таким образом, получим неравенство (16)

(16)

Метод обеспечивает быструю сходимость, если выполняется условие (17)

. (17)

Т.е. первую касательную рекомендуется проводить в той точке интервала [a,b], где знаки функции f(x0) и ее кривизны f"(x0) совпадают.

Блок-схема алгоритма уточнения корня методом Ньютона приведена на рисунке 9.




Рис. 9.  Схема алгоритма уточнения корня методом Ньютона
Реализованный на языке C++ алгоритм поиска корней нелинейного уравнения этим методом представлено в приложении В.

2.4 Модифицированный метод Ньютона (метод секущих)


В этом методе для вычисления производных на каждом шаге поиска используется численное дифференцирование по формуле (18):

. (18)
Где ∆f(x) – приращение функции, ∆x – приращение аргумента.

Тогда рекуррентная формула для вычисления xn+1 будет иметь вид (19):

(19)

где 


2.5 Метод хорд


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

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

а) при фиксированном левом конце хорд, т.е. z=a, тогда начальная точка х0=b (рис.10а);

б) при фиксированном правом конце хорд, т.е. z=b, тогда начальная точка х0=a (рис.10б);



а) б)


Рис. 10.  Решение нелинейного уравнения методом хорд

В результате итерационный процесс схождения к корню реализуется рекуррентной формулой (20) для случая а) и формулой (21) для случая б)

(20)

(21)

Процесс поиска продолжается до тех пор, пока не будет достигнута требуемая точность, то есть не выполнится условие (22)

(22)

Метод обеспечивает быструю сходимость, если f(z)f"(z) > 0, т.е. хорды фиксируются в том конце интервала [a,b], где знаки функции f(z) и ее кривизны f"(z) совпадают.

Рассмотрим схему алгоритма уточнения корня методом хорд (рис.11).




Рис. 11.  Схема алгоритма уточнения корня методом хорд
Программа решающая эту задачу представлена в приложении Г.


Заключение

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

К тому же в данной курсовой работе рассмотрены лишь основные методы. Существуют еще некоторые разновидности решения данной задачи. Не говоря уже об оптимизационных методах. На основании всего этого можно заключить то, что данные нелинейные уравнения достаточно хорошо изучены. И что бы их решить нужно всего лишь знать какой метод применить в ходе решения задачи.

Список использованных источников

1. Ю.В. Губарь.  Курс лекций «Введение в математическое моделирование» // Лекция 4. Численные методы решения нелинейных уравнений. Интернет университет информационных технологий – 2011

http://www.intuit.ru/department/calculate/intromathmodel/4/

2. И.Б. Петров, А.И. Лобанов. Курс лекций «Введение в вычислительную математику». Интернет университет информационных технологий – 2011

http://www.intuit.ru/department/calculate/calcmathbase/

3. Левицкий А.А. «Основы численных методов» Красноярск: Издательство «Симафор» – 2006
Приложение А

Программа поиска решения нелинейного уравнения методом половинного деления.
#include

#include

#include

using namespace std;
double f(double x) //функция вычисляющее значение от

{ //аргумента х согласно формуле x*x*x-7

return x*x*x-7;

}

int main()

{

double a,b,e,t,f1,f2,x,F; //a,b - границы интервала, e - //требуемая точность, t - середина //интервала a,b

cin>>a>>b>>e; //считывание переменных

do

{

f1=f(a); //вычисляем значение функции в точке a

t=(a+b)/2;

f2=f(t); //вычисляем значение функции в

//точке(a+b)/2

if(f1*f2<=0) b=t; //если знаки функций в этих точках

//различны то отсекаем правую часть

//интервала (от t до b)

else

{

a=t; //иначе - отсекаем левую (от a до t)

f1=f2;

}

}

while (fabs(b-a)>e); //выполняем цикл пока не достигнем

//нужной точности |b-a|
x=(a+b)/2; //вычисляем значение аргумента

F=f(x); //вычисляем значение функции
printf("x=%0.10lf f(x)=%0.10lf",x,F); //вывод данных

return 0;

}


Приложение Б

Программа поиска решения нелинейного уравнения методом простых итераций.

#include

#include

#include

using namespace std;
double fi(double x) //функция вычисляющее x=fi(x)

{

...

}
double f(double x) //вычисление значения функции f(x)

{

...

}
int main()

{

double e,x0,x; //e - требуемая точность,

//x,x0 - аргументы функции

cin>>x0>>e; //считывание переменных

x=x0; //необходимо для первой итерации цикла

do

{

x0=x; //присваеваем x0 значение х

x=fi(x0); //вычисляем x

}

while (fabs(x-x0)<=e); //выполняем цикл пока не достигнем нужной

//точности |х-х0| printf("x=%0.10lf f(x)=%0.10lf",x,f(x)); //вывод данных

return 0;

}


Приложение В

Программа поиска решения нелинейного уравнения методом Ньютона (методом касательных).
#include

#include

#include

using namespace std;
double d(double x) //нулевая производная (то есть сама функция)

{

...

}
double d1(double x) //первая производная

{

...

}
double d2(double x) //вторая производная

{

...

}
int main()

{

double a,b,e,h,x,f,f1,f2; //e - требуемая точность, a,b - границы

//интервала

cin>>a>>b>>e; //считывание переменных

f=d(b); //значение функции в точке b

f2=d2(b); //значение второй производной функции

//функции в точке b

if(f*f2>0) x=b; //выбираем начальную точку

else x=a;

do

{

f=d(x); //значение функции в точке x

f1=d1(x); //значение первой производной функции

//функции в точке x

h=f/f1; //вычисление h

x=x-h; //вычисление x

}

while (fabs(h)<=e); //выполняем цикл пока не достигнем нужной

//точности |h|<=e
printf("x=%0.10lf f(x)=%0.10lf",x,d(x)); //вывод данных

return 0;

}

Приложение Г

Программа поиска решения нелинейного уравнения методом хорд.
#include

#include

#include

using namespace std;
double d(double x) //нулевая производная (то есть сама

//функция)

{

...

}
double d1(double x) //первая производная

{

...

}
double d2(double x) //вторая производная

{

...

}
int main()

{

double a,b,e,h,x,f,f1,f2,z,fz; //e - требуемая точность, a,b - границы

//интервала

cin>>a>>b>>e; //считывание переменных

f=d(a); //значение функции в точке a

f2=d2(a); //значение второй производной функции

//функции в точке a

if(f*f2>0) //выбираем начальные точки

{

x=b;

z=a;

}

else

{

x=a;

z=b;

}

fz=d(z); //значение функции в точке z

do

{

f=d(x); //значение функции в точке x

h=(x-z)*f/(f-fz); //вычисление h

x=x-h; //вычисление x

}

while (fabs(h)<=e); //выполняем цикл пока не достигнем

//нужной точности |h|<=e
printf("x=%0.10lf f(x)=%0.10lf",x,d(x)); //вывод данных

return 0;

}

Учебный текст
© perviydoc.ru
При копировании укажите ссылку.
обратиться к администрации