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

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)