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

Введение



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

Для нелинейных уравнений не всегда работают формулы, позволяющие получить точное решение за конечное число операций. Так, в 30е годы XIX века Н. Абелем и Э. Галуа был установлен факт, что аналитических формул для  решения уравнений пятой и более высоких степеней не существует. Для решения таких уравнений были разработаны универсальные численные алгоритмы, которые позволяют находить приближенный корень практически для любой функции . Такие алгоритмы не накладывают ограничения на вид функции , а требуют лишь общих свойств: непрерывности, существования производной и т. д.

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

Цель работы: изучить численные методы решения нелинейных уравнений (метод касательных, метод хорд).   

Задачи: исследовать свойства метода хорд и метода касательных, показать применение методов на примерах с помощью MS Excel,  провести сравнительный анализ методов и сделать выводы.

Курсовая работа состоит из введения, двух глав (теоретическая и практическая части), заключения и списка литературы.



Глава 1. Теоретическая часть.



1.1 Анализ задачи нахождения корня нелинейного уравнения



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



Уравнения, которые не могут быть представлены в таком виде и содержат логарифмические, показательные, тригонометрические функции, называют трансцендентными, например,



Рассмотрим постановку задачи для нелинейного уравнения. Пусть уравнение задано в виде



где функция  определена и непрерывна на некотором интервале. Корнем уравнения будут те значения переменной , которые обращают функцию в нуль:



Задача отыскания корней разделяется на два этапа: 1) отделение корня, то есть нахождение промежутков, содержащих только один корень и 2) уточнение корня, то есть определение корня на этом промежутке с заданной наперед точностью. 

Для отыскания промежутка локализации корня используется следующая теорема:

Теорема о существовании корня непрерывной функции

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

Таким образом, установлено, что если для концов промежутка выполняется условие



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

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

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

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



где  и  – приближения на двух соседних итерациях с номерами n и n+1,  – корень уравнения.

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



Метод хорд

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



Точка пересечения с  имеет ординату . Найдем ее абсциссу , полагая в уравнении :







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

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





Тогда формула для приближения:



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

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

Рассмотрим распространенный частный случай, когда вторая производная сохраняет свой знак на . Пусть, например, , то есть функция выпукла вниз. Тогда возможны два случая: 1)  и 2) . Эти два случая изображены на рисунках 2 и 3.



Рис.2. 





Рис.3. 



В случае, когда , как видно на рисунке 2, за неподвижный конец берется , а за начальное приближение  – точка .  Формула последовательных приближений будет иметь вид:



Получим последовательность , которая приближается к корню справа:



Во втором случае (рисунок 3)  и функция возрастает. Теперь за неподвижный конец берем точку , а за начальное приближение  – точку .  Формула итерационного процесса в этом случае:



Получим последовательность , которая приближается к корню слева:



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

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



то будет гарантирована точность:



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



Комбинированный метод хорд и касательных. 



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

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

1. 

2. 

3. 

3. .

Рассмотрим наглядно первый случай, когда обе производные положительны, то есть функция возрастает и ее график выпуклый вниз (рис. 4). Будем считать, что итерации ведутся не независимо, и за новый конец отрезка для метода хорд принимается приближение, найденное по методу касательных.



Рис. 4



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

Обозначим  – приближение на n-ном шаге, полученное по формуле Ньютона,  – приближение, полученное по формуле хорд. Расчет будем вести по формулам:





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



а корень находится как среднее арифметическое  и :



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









Практическая часть.



Задача 1.

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

Задачу извлечения корня  можно переписать в виде нелинейного уравнения:





Тогда 



Формула итерационного процесса:



Пусть , нулевое приближение 

Рекуррентная формула:


Cделаем три итерации по рекуррентной формуле:







Сравним с точным значением: 



Погрешность:



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



Задача 2.

Пусть требуется найти корень уравнения 



методом  хорд с точностью .

Выполним отделение корней графическим методом. Построим график функции





Рис. 4

Выберем в качестве промежутка локализации отрезок . Для точки   справедливо:



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

Расчеты ведутся по формуле:



до тех пор, пока не будет выполнено условие



обеспечивающее заданную точность.

Сведем результаты расчетов в таблицу.

итерация







1

0,5

0,974061

0,474061

2

0,974061

1,172989

0,198928

3

1,172989

1,235842

0,062853

4

1,235842

1,253830

0,017988

5

1,253830

1,258829

0,004999

6

1,258829

1,260207

0,001378

7

1,260207

1,260586

0,000379

8

1,260586

1,260690

0,000104

9

1,260690

1,260719

2,86e-05



На девятой итерации выполнено условие:



Таким образом, решение с заданной точностью получено за 9 итераций.





Задача 3.

Найдем теперь корень того же уравнения 



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

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



  Расчетная формула метода касательных:



Производную можно находить численными методами, но в данном примере ее ввиду простоты функции ее удобнее задать аналитически:



итерация









1

1,421282

-2,158529

-3,729849

0,578718

2

1,272019

-0,367724

-2,463593

0,149263

3

1,260794

-0,024043

-2,141802

0,011226

4

1,260730

-0,000135

-2,117691

6,36e-05



На четвертой итерации выполнено условие:



Решение  получено за 4 итерации.



















Литература

Амосов А. А., Дубинский Ю. А., Копченова Н. В. Вычислительные методы для инженеров. – М.: Высшая школа, 1994. – 544 с.  

Бахвалов Н. С. Численные методы (анализ, алгебра, обыкновенные дифференциальные уравнения). – М.: Наука, 1975. – 632 с.  

Калиткин Н. Н. Численные методы. – М.: Наука, 1978. – 512 с.  

Б. П. Демидович, И. А. Марон. Основы вычислительной математики – М.: Наука, 1966. – 664 с.  

Бахвалов Н. С., Жидков Н. П., Кобельков Г. М. Численные методы – М.: Наука, 1987. – 

Самарский А. А., Гулин А. В. Численные методы. – М.: Наука, 1989. – 432 с.  

Костомаров Д. П., Фаворский А. П.  Вводные лекции по численным методам. – М.: Логос, 2004. – 184 с.  

Формалев В. Ф., Ревизников Д. Л. Численные методы. – М.: Физматлит, 2004. – 400 с.  

Вержбицкий В. М. Основы численных методов. – М.: Высшая школа, 2002. – 840 с.  

 Вержбицкий В. М. Численные методы. Линейная алгебра и нелинейные уравнения. – М.: Высшая школа, 2000. – 266 с........................