Df=f(x0+Dx) – f(x0)
и оценим его с помощью неравенства (4.3)
|Df | £ a|Dx|
Таким образом,
, что означает непрерывность функции f(x).Условие Липшица имеет простой геометрический смысл. Возьмём не графике функции y=f(x) две произвольные точки M1 и M2 с координатами (x1, f(x1)) и (x2, f(x2)). Напишем уравнение прямой линии, проходящей через эти точки:
y=f(x1) + k(x-x1)
где k– тангенс угла наклона прямой у оси Оx и определяется формулой:
Если функция f(x) удовлетворяет на отрезке [a, b] условию Липшица, то при произвольном выборе точек M1 и M2 имеем |k|£a. Таким образом, с геометрической точки зрения условие Липшица означает ограниченность тангенса угла наклона секущих, проведённых через всевозможные пары точек графика функции y=f(x).
рис 2.3 геометрическая иллюстрация условия Липшица.
рис 3.3 геометрическая иллюстрация cвязи условия Липшица с предположением о дифференцируемости функции.
Предположим, что функция f(x) имеет на отрезке [a, b] ограниченную производную:
| f ¢(x)| £ m; тогда она удовлетворяет условию Липшица с постоянной a=m. Для доказательс- тва этого утверждения воспользуемся формулой конечных приращений Лагранжа:
f(x2) – f(x1) = f ¢(x)(x2-x1) (5.3)
где x1, x2, - произвольные точки отрезка [a, b] x, - некоторая точка отрезка [x1, x2]. Возьмём модуль обеих частей равенства (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. Тогда при любом выборе x0 на отрезке [c-d, c+d] существует бесконечная итерационная последовательность {xn} и эта последовательность сходится к корню x=c, который является единственным решением уравнения (1.3) на отрезке [c-d, c+d].
Сформулированная теорема имеет очень простой смысл. Будем говорить, что функция j осуществляет отображение точки x на точку y=j(x). Тогда условие Липшица с постоянной a<1 означает, что отображение j является сжимающим: расстояние между точками x1 и x2 больше, чем расстояние между их изображениями y1=j(x1) и y2=j(x2).
Корень c является неподвижной точкой отображения j, он преобразуется сам в себя c=j(c). Поэтому каждый шаг в итерационном процессе, сжимая расстояния должен приближать члены последовательности {xn} к неподвижной точке c.
После таких соображений поясняющих смысл теоремы, перейдём к её доказательству. Возьмём произвольную точку x0 на отрезке [c-d, c+d], она отстоит от точки c не больше чем на d: |c-x0| £ d.
Вычислим x1: x1=j(x0), при этом x1-c =j(x0)-j(c). Разность j(x0)-j(c) можно оценить с помощью условия Липшица:
|x1-c| = |j(x0)-j(c)| £ |x0-c| £ ad. (6.3)
Неравенство (6.3) показывает, что x1 принадлежит отрезку [c-d, c+d] и расположен ближе к точке c, чем x0.
Продолжим построение итерационной последовательности. Вычислим x2: x2=j(x1), при этом:
|x2-c| = |j(x1)-j(c)| £ a|x1-c| £ a2|x0-c| £ a2d
Точка x2 опять принадлежит отрезку [c-d, c+d] и расположена ближе к точке c, чем точка x1, т.е. мы приблизились к c.
По индукции легко доказать, что последующие итерации также существуют и удовлетворяют неравенствам.
|xn-c| £ an |x0-c| £ and (7.3)
Отсюда следует, что:
, т. е.Остаётся доказать, что корень x=c (1.3) является единственным решением уравнения на отрезке [c-d, c+d]. Действительно, допустим, что существует ещё один корень x=c1.
Примем c1 за нулевое приближение и будем строить итерационную последователь- ность (2.3). Тогда с учётом (7.3) получим xn=c1 (n=0, 1, 2, …). С другой стороны, по доказанному
, т. е. c1=c. Никаких других решений уравнение на отрезке иметь не может.Сходимость итерационной последовательности к корню уравнения (1.3) может быть использована для приближённого определения корня с любой степенью точности. Для этого нужно только провести достаточное количество итераций.
4. Быстрота сходимости процесса итераций
Используем теперь производную функции j(x) для оценки скорости сходимости итераций при решении уравнения х=j(x). Нужно оценить скорость, с которой убывают погрешности an=x-xn приближённых значений х1, … , хn, … корня x.
рис 1.4
Можно заметить, что справедливы равенства x=j(x) и хn+ 1=j(хn). Из них вытекает, что:
an+ 1= x-хn+ 1=j(x)-j(хn)
Но по формуле Лагранжа имеем:
j(x)-j(хn)= j ¢(cn)·( x-xn)= j ¢(cn) ·an
где cn - точка лежащая между точками x и хn. Поэтому:
an+ 1=j ¢(cn) ·an (1.4)
Из равенства (1.4) вытекает следующий вывод:
Пусть x – корень уравнения x=j (x) - лежит на отрезке [a, b]. Если на этом отрезке выполняется неравенство |j ¢(x)|<q<1, а начальное приближение x1 также выбрано на отрезке [a, b], то при любом n выполняется соотношение:
|an+ 1|<qn·|a1| (2.4)
В самом деле, из равенства (1.4) имеем:
|a2|=|j ¢(c1)|·|a1|
Но точка c1 лежит на отрезке [a, b] (рис.1.4), и потому:
|j ¢(c1)|<q
Отсюда следует, что:
|a2|<q·|a1|
Точно так же получаем, что:
|a3|=|j ¢(c1)|·|a2|<q·|a2|< q2·|a1|
и вообще:
|an+ 1|=qn·|a1|
Тем самым наше утверждение доказано.
Так само при 0<q<1 последовательность чисел q, q2, q3, … , qn, … стремится к нулю, то и погрешность an+ 1 стремится к нулю с возрастанием n. Иными словами, при указанных выше предположениях числа x1, x2, … , xn, … приближаются к числу x, причём разность |x-xn| убывает быстрее, чем qn·|a1|.
Точно так же можно доказать, что если на отрезке [a, b] выполнено неравенство:
|j ¢(x)|>1,
то процесс итераций расходится.
Особенно быстро сходится процесс последовательных приближений, если в точке x производная функции j(x) обращается в нуль. В этом случае по мере приближения к x, значение j ¢(x) стремится к нулю. Так как:
|an+ 1|=|j ¢(cn)|·|an|
то сходимость процесса ускоряется по мере приближения к точке x.
Однако то же самое можно наблюдать в методе Ньютона, при замене f(x)=0 на
имеем: и её производная: в точке x: f(x)=0 - в методе Ньютона наблюдается ускорение сходимости процесса приближений.5. Метод касательных (метод Ньютона)
Метод касательных, связанный с именем И. Ньютона, является одним из наиболее эффективных численных методов решения уравнений. Идея метода очень проста. Возьмём производную точку x0 и запишем в ней уравнение касательной к графику функции f(x):
y=f(x0)+ f ¢(x) (x-x0) (1.5)
Графики функции f(x) и её касательной близки около точки касания, поэтому естественно ожидать, что точка x1 пересечения касательной с осью Ox будет расположена недалеко от корня c (рис. 1.5)
Для определения точки имеем уравнение:
f(x0)+ f ¢(x0) (x1-x0)=0
таким образом: x1=x0 – f (x0)/ f ¢(x0) (2.5)
Повторим проделанную процедуру: напишем уравнение касательной к графику функции f(x) при x=x1 и найдём для неё точку пересечения x2 с осью Ox (см. рис.1.5) x2=x1 – f (x1)/ f ¢(x1). Продолжая этот процесс, получим последовательность {xn}, определён- ную с помощью рекуррентной формулы:
xn+ 1=xn – f (xn)/ f ¢(xn), n=0, 1, 2, … (3.5)
рис. 1.5
Построение последовательности {xn}по методу касательных