Курсовая работа: Приближённые методы решения алгебраического уравнения

Если функция 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) вытекает следующий вывод: