Приближённые методы решения алгебраического уравнения (стр. 2 из 4)

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) может быть использована для приближённого определения корня с любой степенью точности. Для этого нужно только провести достаточное количество итераций.

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

Используем теперь производную функции 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 - в методе Ньютона наблюдается ускорение сходимости процесса приближений.

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

Метод касательных, связанный с именем И. Ньютона, является одним из наиболее эффективных численных методов решения уравнений. Идея метода очень проста. Возьмём производную точку 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)

Повторим проделанную процедуру: напишем уравнение касательной к графику функции f(x) при x=x₁ и найдём для неё точку пересечения x₂ с осью Ox (см. рис.1.5) x₂=x₁ – f (x₁)/ f ¢(x₁). Продолжая этот процесс, получим последовательность {x_n}, определён- ную с помощью рекуррентной формулы:

x_{n+ 1}=x_n – f (x_n)/ f ¢(x_n), n=0, 1, 2, … (3.5)

рис. 1.5

Построение последовательности {x_n}по методу касательных