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

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

Стерлитамакский филиал

федерального государственного бюджетного образовательного учреждения

высшего профессионального образования

«Башкирский государственный университет»

 

 

Экономический факультет

Кафедра математического моделирования

 

 

 

 

 

 

КУРСОВАЯ РАБОТА

на тему: ««Анализ и сравнение численных методов решения нелинейных

 уравнений»

 

 

 

 

 

Выполнили студенты 3 курса                 

                     группы БИ-31 

                     Серебряков Е.А.________

      Федоров С.О.__________

                   «___»__________2014г.

 

 

Научный руководитель                                       к.ф.-м.н., доцент

                                                                               Карасев Е.М. __________

                      «___»____________2014г.

 

 

 

 

 

СТЕРЛИТАМАК – 2014

Содержание

 

1. Введение            3
2. Численные методы решения нелинейных

уравнений           5

3. Постановка задачи               6
4. Основные методы решения нелинейных 

уравнений                                7

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

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

5.3.  Метод хорд          14

5. Практическая часть         19
6. Заключение          26
7. Список используемой литературы       27

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

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

Решение систем нелинейных алгебраических уравнений – одна из сложных и до конца не решенных задач. Даже о расположении и существовании корней систем нелинейных уравнений почти ничего нельзя сказать. Большинство методов решения систем нелинейных уравнений сходятся к решению, если начальное приближение достаточно близко к нему, и могут вообще не давать решения при произвольном выборе начального приближения. Условия и скорость сходимости каждого итерационного процесса существенно зависят от свойств уравнений, то есть от свойств матрицы системы, и от выбора начальных приближений.

В своей курсовой работе я поставила три основные цели и задачи:

1. Изучение разновидности комбинаторных задач.
2. Изучение основных комбинаторных операций.
3. Изучение комбинаторики как раздел элементарной алгебры.

Для достижения поставленных целей и решения задач в курсовой работе я использовала различные источники информации. В основном это были книги Бахвалов Н. С. Численные методы и Вержбицкий В. М. Численные методы. Линейная алгебра и нелинейные уравнения. В них четко и точно изложен нужный для моей курсовой работы материал.

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

 

Численные методы.

Проблема численного решения линейных уравнений интересует математиков уже несколько столетий. Первые математические результаты появились в XVIII веке. В 1750 году Г. Крамер (1704-1752) опубликовал свои труды по детерминантам квадратных матриц и предложил алгоритм нахождения обратной матрицы, известный как правило Крамера. Гаусс в 1809 году опубликовал работу, посвященную движению небесных тел, в которой был изложен метод для решения линейных систем, известный как метод исключения.

В 40-х годах XX века с появлением компьютеров сильно возрос интерес к численным методам. Тогда же началось активное исследование существующих методов для их реализации на ЭВМ и предпринимались активные попытки увеличить их точность.

Вплоть до 80-х годов решение вычислительных задач было ограничено ресурсами ЭВМ, поэтому особое значение придавалось экономичности алгоритмов.

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

 

 

 

 

 

 

 

 

 

 

 

Постановка задачи.

Пусть имеется уравнение вида

                                   f (x) = 0.                                                 

где f (x)  - заданная алгебраическая или трансцендентная функция. (Функция называется алгебраической, если для получения её значения нужно выполнить арифметические операции и возведение в степень с рациональным показателем. Примеры трансцендентных функций - показательная, логарифмическая, тригонометрические, обратные тригонометрические.)

Решить уравнение - значит найти все его корни, то есть те значения x, которые обращают уравнение в тождество, или доказать, что корней нет. 
Если алгебраическое или трансцендентное уравнение достаточно сложно, то довольно редко удается точно найти его корни. Кроме того, в некоторых случаях уравнение может содержать коэффициенты, известные лишь приблизительно, поэтому сама задача о точном нахождении корней теряет смысл. В таких случаях применяют численные (приближенные) методы решения.

Поставим задачу найти такое приближенное значение корня xпр, которое мало отличается от точного значения корня x*, так что выполняется неравенство │x* – xпр │< e , где e (эпсилон) – малая положительная величина – допустимая ошибка, которую мы можем заранее задать по своему усмотрению. Если корень найден с точностью e, то принято писать x*=xпр±e.

Будем предполагать, что уравнение (1) имеет лишь изолированные корни, т.е. для каждого корня существует окрестность, не содержащая других корней этого уравнения.

 

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

Уравнение типа F(x)=0 или x=f(x) называется нелинейным. Решить уравнение это значит найти такое x, при котором уравнение превращается в тождество. В общем случае уравнение может иметь 0; 1; 2;...∞ корней. Рассмотренные ниже численные методы решения нелинейных уравнений позволяют находить один корень на заданном интервале [a,b]. При этом на интервале должен существовать только один корень. Рассмотрим несколько методов решения нелинейных уравнений.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

Метод деления отрезка пополам имеет другие названия: метод половинного деления, метод дихотомии, метод проб, метод бисекций. 
Пусть корень уравнения f (x) = 0 отделен на отрезке[a;b] , т.е. f(a)∙f(b)<0. 
Алгоритм приближенного вычисления корня методом половинного деления. 
Исходные данные: f (x) – функция; ε – требуемая точность; a, b – границы заданного интервала (границы поиска корня). 
Результат: xпр – приближенный корень уравнения f (x) = 0.

Метод решения:

Шаг 1. Выбрать середину   отрезка[a;b]  в качестве приближенного корня.

Шаг 2. Если f(c)=0, то c – искомый корень уравнения, на этом прекращаем вычисления. В противном случае перейти к шагу 3.

Шаг 3. Точный корень уравнения x* отличается от c не более чем на половину длины отрезка, т.е. не более чем на (полученная точность). Проверяем условие . Если условие не выполняется, т.е. полученная точность нас не устраивает (она больше, чем требуемая), то перейти к шагу 4; в противном случае прекратить вычисления, поскольку мы достигли требуемой точности, и приближенным корнем уравнения f(x) = 0 считать середину c  отрезка [a;b] .

Шаг 4. Определить интервал дальнейшего поиска корня. Из двух образовавшихся при делении отрезков переходим к той из его половин [a;c]  и [c;b] , на концах которого функция принимает значения разных знаков. 
Случай 1 (рис. 1). Корень на отрезке [a;c]. f(a)∙f(c)≤0, граница b сдвигается влево – заменить b на с: b:= c.

 
Рис. 1. Графическая иллюстрация метода половинного деления.

Случай 2 (рис. 1). Корень на отрезке [c;b] . f(a)∙f(c)>0, граница a сдвигается вправо – заменить a на с: a:= c.

Перейти к шагу 1.

Алгоритм деления отрезка пополам довольно медленный, но зато абсолютно застрахован от неудач. Основное достоинство метода состоит в том, что его скорость сходимости не зависит от вида функции f (x). Данный метод не имеет дополнительных условий сходимости, кроме f(a)∙f(b)<0.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                              Блок-схема программы 

 

 

 

 

 

 

 

 НЕТ ДА

 

 

 

 

 ДА НЕТ

 

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

Пусть на отрезке [a; b] отделен корень с уравнения f (x) = 0 и f -функция непрерывна на отрезке [a; b], а на интервале  (a; b) существуют отличные от нуля производные f ’ и f ”.

Так как f ’(x) ¹ 0 , то запишем уравнение f (x) = 0 в виде:

x = x – ( f (x) / f ’(x))     (1)

Решая его методом итераций можем записать:

xn+1 = x n– ( f (x n) / f ’(x n))    (2)

Если на отрезке [a;b]   f ’(x) * f “(x) > 0, то нулевое приближение выбираем x0=a. Рассмотрим геометрический смысл метода. Рассмотрим график функции y=f(x). Пусть для определенности f ‘(x) > 0 и f “(x) > 0 (рис. 1). Проведем касательную к графику функции в точке B (b, f (b)). Ее уравнение будет иметь вид:

y = f (b) + f ’(b) * (x – b)

Полагая в уравнении y = 0 и учитывая, что f ’(x) ¹ 0, решаем его относительно x. Получим :

x = b – (f (b) /f ‘(b))

Нашли абсциссу x1 точки c1 пересечения касательной с осью Оx:

x1 = b – (f (b) – f ’ (b))

Проведем  касательную к графику функции в точке b1 (x1; f (x1)).Найдем абсциссу x2 точки с2 пересечения касательной с осью Ox:

x2 = x1 – (f (x1) / ( f ’(x1))

Вообще :

xk+1 = x k – ( f (x k) / f ’(x k))     (3)

Таким образом, формула (3) дает последовательные приближения (xk) корня, получаемые из уравнения касательной , проведенной к графику функции в точке         b k (x k; f (x k0) метод уточнения корня  c  [a;b] уравнения f (x) = 0 с помощью формулы (3) называется методом касательной или методом Ньютона.

Геометрический смысл метода касательных состоит в замене дуги y = f (x) касательной, одной к одной  из крайних точек . Начальное приближение x 0=a или    x0 = b брать таким, чтобы вся последовательность приближения х k принадлежала интервалу  (a;b). В случае существования производных f ’, f ”, сохраняющих свои знаки в интервале, за х0 берется тот конец отрезка [a;b], для которого выполняется условие  f ’(х0) * f (х0) > 0. Для оценки приближения используется общая формула :

|c-x k-1 | £ | f (x k+1)/m| , где m = min f ’(x) на отрезке [a;b] .

На практике проще пользоваться другим правилом :

Если на отрезке [a;b] выполняется условие  0 < m <  | f (x)|  и e - заданная точность решения, то неравенство | x k+1-x k| £ e влечет выполнение неравенства       |c-x k-1| £ e .

В этом случае процесс последовательного приближения продолжают до тех пор, пока не выполнится неравенство:

|c-x k-1| £ e .

 

 

 

 

 

 

 

 

 

                              Блок-схема программы

 

 

 

 

 

 

 

                                                               НЕТ

 

 

 ДА

 
Метод хорд.

Пусть на отрезке [a;b] функция непрерывна, принимает на концах отрезка значение разных знаков, а производная f '(x) сохраняет знак. В зависимости от знака второй производной возможны следующие случаи расположения кривых (рис. 1).

 
 

Рис. 1. Возможные случаи расположения кривых.

Алгоритм приближенного вычисления корня методом хорд. 
Исходные данные: f (x) – функция; ε – требуемая точность; x0 – начальное приближение. 
Результат: xпр – приближенный корень уравнения f (x) = 0.

Метод решения: 

Рис. 2. Геометрическая интерпретация метода хорд для случая f '(x) f ''(x)>0.

Рассмотрим случай, когда f '(x)  и f ''(x)  имеют одинаковые знаки (рис. 2).

График функции проходит через точки A0(a,f(a)) и B0(b,f(b)). Искомый корень уравнения (точка x*) нам неизвестен, вместо него возьмет точку х1 пересечения хорды А0В0 с осью абсцисс. Это и будет приближенное значение корня. 
В аналитической геометрии выводится формула, задающая уравнение прямой, проходящей через две точки с координатами (х1; у1) и (х2; у2): . 
Тогда уравнение хорды А0В0 запишется в виде: . 
Найдем значение х = х1, для которого у = 0:  . Теперь корень находится на отрезке [x1;b]. Применим метод хорд к этому отрезку. Проведем хорду, соединяющую точки A1(x1,f(x1)) и B0(b,f(b)), и найдем х2 - точку пересечения хорды А1В0 с осью Ох: x2=x1 . 
Продолжая этот процесс, находим: x3=x2. Получаем рекуррентную формулу вычисления приближений к корню xn+1=xn. 
В этом случае конец b отрезка [a;b]  остается неподвижным, а конец a перемещается. 
Таким образом, получаем расчетные формулы метода хорд: