Приблизительное нахождение корней уравнений

МИНИСТЕРСТВО ОБРАЗОВАНИЯ  И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ  БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО  ОБРАЗОВАНИЯ

«МОРДОВСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ

ИНСТИТУТ ИМЕНИ М.Е.ЕВСЕВЬЕВА»

 

 

ФИЗИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

 

КАФЕДРА МАТЕМАТИКИ

 

 

 

 

 

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

по математике

 

 

на тему:

Приблизительное нахождение корней уравнений

 

 

 

 

 

 

 

 

Автор курсовой работы: Д.С. Гусев, студент 3 курса группы МДИ-109 очной формы обучения.

 

Специальность: «Информатика» с дополнительной специальностью «Математика»

 

Руководитель: И.В. Кочетова

 

 

 

 

 

 

 

 

 

 

 

Саранск 2012

 

Содержание

 

1. Введение
2. Численное решение уравнения, условия, наложенные на функцию, графический метод определения корней
3. Метод дихотомии
4. Метод итераций
5. Быстрота сходимости процесса итераций
6. Метод касательных
7. Первые приближения для метода касательных
8. Метод секущих
9. Метод хорд
10. Усовершенствованный метод хорд
11. Комбинированный метод решения уравнения
12. Заключительные замечания
13. Список использованной литературы

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. Введение

 

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

 

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

 

х⁵-4х-2=0

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2. Численное решение уравнений с одним неизвестным

 

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

 

                                                                            f(x)=0                                                                   (1.1)

 

на заданном отрезке [a, b].

         

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

 

f(x) = P(x) = a₀xⁿ + a₁x^{n- 1} + … + a_n-1 x + a_n = 0,  a₀ ¹ 0

 

         Требование a₀ ¹ 0 обязательно, так как при невыполнении этого условия данное уравнение будет на порядок ниже.

         Всякое  уравнение (1.1) называется трансцендентным, если в нём невозможно явным образом найти неизвестное, а можно лишь приближённо.

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

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

 

         Корнем  уравнения (1.1) называется такое число x, где f(x)=0.  

         При определении  приближённых корней уравнения  (1.1) необходимо решить две задачи:

 

1. отделение корней, т. е. определение достаточно малых промежутков, в каждом из которых заключён один и только один корень уравнения (простой и кратный);

 

2. уточнение корней с заданной точностью (верным числом знаков до или после запятой);

 

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

         Вторая  задача решается непосредственно  в методах рассмотренных ниже.

   

         При графическом отделении корней уравнения (1.1) нужно последнее преобразовать к виду: 

                                                                        j₁(x)=j₂(x)                                                              (2.1)

 

и построить  графики функций y₁=j₁(x),  y₂=j₂(x).

 

          Действительно,  корнями уравнения  (1.1)

 

f(x) = j₁(x) - j₂(x) = 0

 

являются абсциссы точек пересечения этих графиков (и только они).

          Из всех  способов, какими можно уравнение  (1.1) преобразовать к виду (2.1) выбираем тот, который обеспечивает наиболее простое построение графиков y₁=j₁(x) и y₂=j₂(x). В частности можно взять j₂(x) = 0 и тогда придём к построению графика функции (1.1), точки пересечения которого с прямой y₂=j₂(x)=0, т. е. с осью абсцисс, и есть искомые корни уравнения (1.0).             

 

          Условия, наложенные на функцию f(x) на  отрезке [a, b].

          Будем  предполагать, что функция  f(x) непрерывна на отрезке [a, b] (для метода хорд можно потребовать на интервале)  и имеет на этом интервале первую и вторую производные, причём обе они знакопостоянны (в частности отличны от нуля). Будем также предполагать, что функция  f(x) принимает на концах отрезка значения разного знака. В силу знакопостоянства первой производной функция f(x) строго монотонна, поэтому при сделанных предположениях уравнение (1.1) имеет в точности один корень на интервале        (a, b).         

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3. Метод дихотомии

   

         Этот метод ещё называется методом вилки.

 

         Нам необходимо найти корень уравнения (1.1) на отрезке [a, b]. Рассмотрим отрезок   [x₀, x₁]: [x₀, x₁]Ì[a, b]. Пусть мы нашли такие точки х₀, х₁, что f (х₀) f(х₁) £ 0, т. е. на отрезке [х₀, х₁] лежит не менее одного корня уравнения. Найдём середину отрезка х₂=(х₀+х₁)/2 и вычислим  f(х₂).  Из двух половин отрезка выберем ту,  для которой выполняется   условие

 f (х₂) f(х_гран.) £ 0, так как один из корней лежит на этой половине. Затем новый отрезок делим пополам и выберем ту половину, на концах которой функция имеет разные знаки, и т. д.  (рис 1.2).

 

          Если  требуется найти корень с точностью Е, то про-

должаем деление пополам до тех пор, пока  длина отрезка

не станет меньше 2Е. Тогда середина последнего отрезка

даст значение корня с требуемой  точностью.

 

          Дихотомия   проста  и  очень  надёжна.  К  простому  

корню она  сходится  для  любых  непрерывных  функций 

в том числе и не дифференцируемых; при этом она устой-

чива  к ошибкам округления. Скорость сходимости не ве-

лика; за одну итерацию  точность  увеличивается пример-

но вдвое, т. е. уточнение трёх  цифр требует 10 итераций.

Зато точность ответа гарантируется.                                                                     рис. 1.2

 

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

         Предположим  для определённости, что функция  f(x) принимает на левом конце отрезка [a, b] отрицательное значение, а на правом – положительное:

 

f(a) < 0,  f(b) > 0.

 

          Возьмём среднюю точку отрезка [a, b], h=(a+b)/2 и вычислим значение в ней функции f(x). Если f(h)=0, то утверждение теоремы доказано: мы нашли такую точку, где функция обращается в нуль. Если f(h)¹ 0, тогда из отрезков [a, h] и [h, b] выберем один из них тот, где функция на его концах принимает значения разных знаков. Обозначим его [a₁, b₁]. По построению: f(a₁)<0, f(b₁)>0. Затем среднюю точку отрезка [a₁, b₁] точку h₁ и проведём тот же алгоритм нахождения другого отрезка [a₂, b₂] где бы по построению f(a₂)<0, f(b₂)>0.              Будем продолжать этот процесс. В результате он либо оборвётся на некотором шаге n в силу того, что f(h_n)=0, либо будет продолжаться неограниченно. В первом случае вопрос о существовании корня уравнения f(x)=0 решён, поэтому рассмотрим второй случай.

 

            Неограниченное продолжение процесса даёт последовательность отрезков [a, b],        [a₁, b₁], [a₂, b₂],… Эти отрезки вложены друг в друга – каждый последующий отрезок принадлежит всем предыдущим:

 

                                                                a_n £ a_{n+ 1} < b_{n+ 1} £  b_n                                                      (1.2)

причём:

 

f(a_n) < 0,  f(b_n) > 0

       

        Длины отрезков с возрастанием номера n стремятся к нулю:

 

 

         Рассмотрим  левые концы отрезков. Согласно (1.2) они образуют монотонно убывающую ограниченную последовательность {a_n}. Такая последовательность имеет предел, который можно обозначить через c₁:

 

Согласно (1.1) и теореме о переходе к пределу в неравенствах имеем:

 

                                                                            c₁ £  b_n                                                                 (2.2)          

 

        Теперь рассмотрим  правые концы отрезков. Они образуют  монотонно не возрастающую ограниченную последовательность {b_n}, которая тоже имеет предел. Обозначим его через    с₂: . Согласно неравенству (2.1) пределы с₁ и с₂ удовлетворяют неравенству с₁ £ с₂. Итак, a_n £ с₁ < с₂ £  b_n, и следовательно:

 

с₂-с₁ £ b_n - a_n=(b-a)/2n.

 

         Таким образом, разность с₂-с₁ меньше любого наперёд заданного положительного числа. Это означает, что с₂-с₁=0, т. е.: с₁=с₂=с

         Найденная точка интересна тем, что она является единственной общей точкой для всех отрезков построенной последовательности  Используя непрерывность функции f(x), докажем, что она является корнем уравнения f(x)=0.

        Мы знаем,  что f(a_n)<0. Согласно определению непрерывности и возможности предельного перехода в неравенствах, имеем:

 

                                                                    f(c)=lim f(a_n)£0                                                           (3.2)

 

         Аналогично, учитывая, что f(b_n)³0, получаем, что:

 

                                                                   f(c)=lim f(b_n) ³0                                                           (4.2)

                                                     

         Из (3.2) и  (4.2) следует, что f(c)=0. т. е. с – корень уравнения.

           

         Процесс  построения последовательности вложенных стягивающих отрезков методом вилки (дихотомии) является эффективным вычислительным алгоритмом решения уравнения f(x)=0. На n-ом шаге процесса получаем:

a_n £ c £ b_n

          Это  двойное неравенство показывает, что число a_n определяет корень с недостатком, а число b_n с избытком, с ошибкой не превышающей длину отрезка Dn=b_n-a_n=(b-a)/2n. При увеличении n ошибка стремится к нулю по закону геометрической прогрессии со знаменателем q=0.5. Если задана требуемая точность e>0, то чтобы её достигнуть достаточно сделать число шагов N, не превышающее log₂[(b-a)/e]:  N>log₂[(b-a)/e].

 

 

 

 

 

 

 

 

 

4. Метод итераций

 

          Этот метод называется ещё  методом последовательных приближений.

          Пусть нам необходимо найти  корень уравнения (1.1) на некотором отрезке [a, b].

 

          Предположим, что уравнение (1.0) можно переписать в виде:

 

                                                                         x=j(x)                                                                    (1.3)

 

          Возьмём произвольное значение  x₀ из области определения функции j(x) и будет строить последовательность чисел {x_n}, определённых с помощью рекуррентной формулы:

 

                                                           x_{n +1}=j(x_n),     n=0, 1, 2, …                                                 (2.3)

 

          Последовательность {x_n} называется итерационной последовательностью. При её изучении встают два вопроса:

 

1. Можно ли процесс вычисления чисел x_n  продолжать неограниченно, т. е. будут ли числа x_n принадлежать отрезку [a, b] ?
2. Если итерационный процесс (2.3) бесконечен, то как ведут себя числа x_n  при n®¥

 

         Исследование  этих вопросов показывает, что  при определённых ограничениях  на функцию j(x) итерационная  последовательность является бесконечной и сходится к корню уравнения (1.3).

                                                          ,    c=j(c)                                                             (3.3)

 

          Однако  для того, чтобы провести это  исследование нам нужно ввести новое понятие.

          Говорят,  что функция  f(x) удовлетворяет на отрезке [a, b] условию Липшица, если существует такая постоянная  a, что для любых x₁, x₂,  принадлежащих отрезку [a, b] имеет место неравенство:

 

                                                               | f(x₁) - f(x₂)| £ a|x₁ - x₂|                                                   (4.3)

 

           Величину a в этом случае называют постоянной Липшица.

           Если  функция  f(x), удовлетворяет на отрезке [a, b] условию Липшица, то она непрерывна на нём. Действительно, пусть x₀ – произвольная точка отрезка. Рассмотрим приращение функции f(x) в этой точке:

 

Df=f(x₀+Dx) – f(x₀)

 

и оценим его с помощью неравенства (4.3)

 

|Df | £ a|Dx|

 

         Таким образом,  , что означает непрерывность функции f(x).

         Условие  Липшица имеет простой геометрический  смысл. Возьмём не графике функции y=f(x) две произвольные точки M₁ и M₂ с координатами (x₁, f(x₁)) и (x₂, f(x₂)). Напишем уравнение прямой линии, проходящей через эти точки:

 

y=f(x₁) + k(x-x₁)

 

         где k– тангенс угла наклона прямой у оси Оx и определяется формулой:

 

 

         Если функция f(x) удовлетворяет на отрезке [a, b]  условию Липшица, то при произвольном выборе точек M₁ и M₂ имеем |k|£a. Таким образом, с геометрической точки зрения условие Липшица означает ограниченность тангенса угла наклона секущих, проведённых через всевозможные пары точек графика функции y=f(x).

 

 

 

 

 

 

 

 

 

      рис 2.3                                                                                     рис 3.3

             геометрическая иллюстрация                                           геометрическая иллюстрация   

             условия Липшица.                                                                cвязи условия Липшица с пред-      

                                                                                                           положением о дифференциру-

                                                                                                           емости  функции.

 

           Предположим,  что функция  f(x) имеет на отрезке [a, b]  ограниченную  производную:

| f ¢(x)| £ m; тогда она удовлетворяет условию Липшица с постоянной a=m. Для доказательс-        тва этого утверждения воспользуемся  формулой конечных приращений Лагранжа:

 

                                                           f(x₂) – f(x₁) = f ¢(x)(x₂-x₁)                                                     (5.3)

 

где x₁, x₂, - произвольные точки отрезка [a, b] x, - некоторая точка отрезка [x₁, x₂]. Возьмём модуль обеих частей равенства (4.3) и заменим в правой части | f ‘(x)| на m. В результате по- лучим неравенство (4.3) с a=m. Рис.2.3 даёт геометрическую иллюстрацию установленного свойства. Согласно формуле Лагранжа (5.3) каждой секущей графика функции y = f(x) мож- но поставить в соответствие параллельную её касательную. Поэтому наибольший тангенс угла наклона касательных, и его можно оценить той же константой  m: |k| £ m.

 

         Познакомившись с условием Липшица, перейдём к изучению итерационной последовательности, предполагая, что уравнение имеет корень x=c. Существование этого корня можно установить с помощью качественного предварительного исследования уравнения с применением теоремы о существовании корня непрерывной функции.

 

        

 

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

 

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

 

         Теорема о сходимости  итерационной последовательности

 

         Пусть с  – корень уравнения (2.3) и пусть  функция j(x) удовлетворяет на некотором отрезке   [c-d, c+d] (d>0) условию Липшица с постоянной a<1. Тогда при любом выборе x₀ на отрезке [c-d, c+d] существует бесконечная итерационная последовательность {x_n} и эта последовательность сходится к корню x=c, который является единственным решением уравнения (1.3) на отрезке [c-d, c+d].

 

         Сформулированная теорема имеет очень простой смысл. Будем говорить, что функция j осуществляет отображение точки x на точку y=j(x). Тогда условие Липшица с постоянной a<1 означает, что отображение j является сжимающим: расстояние между точками x₁ и x₂ больше, чем расстояние между их изображениями y₁=j(x₁) и y₂=j(x₂).

 

         Корень c является  неподвижной точкой отображения j, он преобразуется сам в себя c=j(c). Поэтому каждый шаг в итерационном процессе, сжимая расстояния должен приближать члены последовательности {x_n} к неподвижной точке c.

 

         После таких  соображений поясняющих смысл  теоремы, перейдём к её доказательству. Возьмём произвольную точку x₀ на отрезке [c-d, c+d], она отстоит от точки c не больше чем на d: |c-x₀| £ d.

         Вычислим x₁: x₁=j(x₀), при этом x₁-c =j(x₀)-j(c). Разность j(x₀)-j(c) можно оценить с помощью условия Липшица:

 

                                                        |x₁-c| = |j(x₀)-j(c)| £ |x₀-c| £ ad.                                           (6.3)

 

         Неравенство (6.3) показывает, что x₁ принадлежит отрезку [c-d, c+d] и расположен ближе к точке c, чем x₀.

 

         Продолжим  построение итерационной последовательности. Вычислим x₂: x₂=j(x₁), при  этом:

|x₂-c| = |j(x₁)-j(c)| £ a|x₁-c| £ a²|x₀-c| £ a²d

 

         Точка x₂ опять принадлежит отрезку [c-d, c+d]  и расположена ближе к точке c, чем точка x₁, т.е. мы приблизились к c.

 

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

 

                                                              |x_n-c| £ aⁿ |x₀-c| £ aⁿd                                                       (7.3)

 

         Отсюда  следует, что:

 

,  т. е. 

 

          Остаётся  доказать, что корень x=c (1.3) является единственным решением уравнения на отрезке [c-d, c+d]. Действительно, допустим,  что существует ещё один корень x=c₁.

 

         Примем c₁ за нулевое приближение и будем строить итерационную последователь- ность (2.3). Тогда с учётом (7.3) получим x_n=c₁ (n=0, 1, 2, …). С другой стороны, по доказанному , т. е. c₁=c. Никаких других  решений уравнение на отрезке иметь не может.             

         Сходимость   итерационной  последовательности  к  корню  уравнения  (1.3)  может  быть использована для приближённого определения корня с любой степенью точности. Для этого нужно только провести достаточное количество итераций.

5. Быстрота сходимости процесса итераций

 

          Используем  теперь производную функции j(x) для оценки скорости сходимости итераций при решении уравнения х=j(x). Нужно оценить скорость, с которой убывают погрешности a_n=x-x_n приближённых значений х₁, … , х_n, … корня x.

 

  

                  рис 1.4

 

         Можно заметить,   что   справедливы   равенства  x=j(x)  и х_{n+ 1}=j(х_n).   Из  них   вытекает,  что:

 

a_{n+ 1}= x-х_{n+ 1}=j(x)-j(х_n)

 

         Но по формуле Лагранжа имеем:

 

j(x)-j(х_n)= j ¢(c_n)·( x-x_n)= j ¢(c_n) ·a_n                                 

 

         где  c_n - точка лежащая между точками x и х_n. Поэтому:

 

                                                                    a_{n+ 1}=j ¢(c_n) ·a_n                                                           (1.4)

      

         Из равенства  (1.4) вытекает следующий вывод:

 

        Пусть x – корень уравнения  x=j (x) - лежит на отрезке [a, b]. Если на этом отрезке выполняется неравенство |j ¢(x)|<q<1, а начальное приближение  x₁ также выбрано на отрезке [a, b], то при любом n выполняется соотношение:

 

                                                                      |a_{n+ 1}|<qⁿ·|a₁|                                                             (2.4)

 

           В  самом деле, из равенства (1.4) имеем:

 

|a₂|=|j ¢(c₁)|·|a₁|

 

           Но  точка c₁ лежит на отрезке [a, b] (рис.1.4), и потому:

 

|j ¢(c₁)|<q

 

           Отсюда следует, что:

 

|a₂|<q·|a₁|

 

 

           Точно  так же получаем, что:

 

|a₃|=|j ¢(c₁)|·|a₂|<q·|a₂|< q²·|a₁|

            и вообще:

 

|a_{n+ 1}|=qⁿ·|a₁|

 

           Тем  самым наше утверждение доказано.

      

            Так само при  0<q<1  последовательность чисел q, q₂, q₃, … , q_n, … стремится к нулю, то и погрешность a_{n+ 1} стремится к нулю с возрастанием n. Иными словами, при указанных выше предположениях числа x₁, x₂, … , x_n, … приближаются к числу x, причём разность      |x-x_n|  убывает быстрее, чем qⁿ·|a₁|.

 

        Точно так же можно доказать, что если на отрезке [a, b]  выполнено неравенство:

 

|j ¢(x)|>1,

 

то процесс итераций расходится.

 

          Особенно  быстро сходится процесс последовательных  приближений, если в точке x производная функции j(x) обращается в нуль. В этом случае по мере приближения к x, значение j ¢(x) стремится к нулю. Так как:

 

|a_{n+ 1}|=|j ¢(c_n)|·|a_n|

 

то сходимость процесса ускоряется по мере приближения к точке x.

 

           Однако  то же самое можно наблюдать  в методе Ньютона, при замене f(x)=0 на имеем: и её производная: в точке x:  f(x)=0 - в методе Ньютона наблюдается ускорение сходимости процесса приближений.  

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

         Метод касательных,  связанный с именем И. Ньютона,  является одним из наиболее  эффективных численных методов  решения уравнений. Идея метода  очень проста. Возьмём производную  точку x₀ и запишем в ней уравнение касательной к графику функции f(x):

 

                                                                 y=f(x₀)+ f ¢(x) (x-x₀)                                                       (1.5)

 

          Графики функции f(x) и её касательной близки около точки касания, поэтому естественно ожидать, что точка x₁ пересечения касательной с осью Ox будет расположена недалеко от корня c (рис. 1.5)

 

         Для определения  точки имеем уравнение:

 

f(x₀)+ f ¢(x₀) (x₁-x₀)=0

 

таким образом:                                    x₁=x₀ – f (x₀)/ f ¢(x₀)                                                          (2.5)