Уточнение отделенного корня методом итераций

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

Заменим уравнение (1) равносильным уравнением x=f(x) (2). Пустьx–корень уравнения (2), x₀ –полученное каким–либо способом нулевое приближение к корнюx. Подставляя x₀ в правую часть уравнения (2), получим некоторое число x₁=f(x₀). Проделаем тоже самое с x₁ , получим x₂=f(x₁) и т. д. Применяя шаг за шагом соотношение x_n=f(x_n-1), для n= 1, 2,..., образуем числовуюпоследовательность x_0, x_1,..., x_n,(3)_..., которую называют последовательностью приближений или итерационной последовательностью. Процесс построения итерационной последовтельности имеет простую геометрическую интерпретацию.

y

f(x₁)

f(x₂)

x₀ x₁ x₂x x

Последовательность приближений может быть как сходящейся, так и расходящейся.

Применение метода итерации может и не привести к уточнению корня. Достаточное условие сходимости итерационного процесса выясняется следующей теоремой.

ТЕОРЕМА 1

Пусть уравнение (2) имеет единствнный корень на отрезке [a;b] и выполнены условия:

1) f(x) –определена и дифференцируема на [a;b]

2) f(x) Î[a;b] для всех xÎ[a;b]

3) $ такое вещественное q, что ½ f^’(x) ½£ q<1 для всех x Î[a;b]

Тогда итерационная последовательность x_n=f(x_n-1), для n= 1, 2,..., сходится при любом начальном члене x₀Î[a;b]

Доказательство: Построим итерационную последовательность вида(3) с любым начальным значением x₀Î[a;b] в силу условия 2) все члены последовательности находятся в отрезке[a;b]. Рассмотрим два последовательных приближения x_n=f(x_n-1) и x_n+1=f(x_n). По теореме Лагранжа о кончных приращениях имеем x_n+1–(x_n)= f(x_n)– f(x_n-1)= f^’(c) (x_n– x_n-1), cÎ[x_n-1– x_n] Переходя к модулям и принимая во внимание условие 3) теоремы, получим ½ x_n+1– x_n=½= ½f^’(c)½½x_n– x_n-1½£q ½x_n– x_n-1½,½ x_n+1–x_n½£q ½x_n– x_n-1½. При n=1,2,... будем иметь ½ x_n+1– x_n=½£qⁿ½x₁–x₀½(4). Рассмотрим ряд

x_{0 +}(x₁–x₀)+ (x₂-x₁) +...+(x_n-x_n-1)+...(5)

составим частичные суммы этого ряда: S₁=x₀, S₂=x_1,..., S_n+1= x_n (6). заметим,что (n+1) частичная сумма радя(5) совпадает с n–м членом итерационной последовательности (3), т.е. S_n+1= x_n, Сравним ряд (5) с рядом½x₁–x₀½+ q½x₁–x₀½+ q²½x₁–x₀½+... Заметим, что в силу соотношений (4) абсолютные величины членов ряда (5) (член x₀ не берется во внимание) не превосходят соответствующих членов ряда (6).Но ряд (6) сходится как ¥ убывающая геометрическая прогрессия(q<1по условию), следовательно и ряд (5) сходится, т. е его частичная сумма S_n+1= x_n имеет предел. Пусть lim x_n=x

n®¥

В силу непрерывности функции f получаем x= f(x), т. е x–корень уравнения (2).В заключение заметим, что условие теоремы 1 не являются необходимыми, это означает, что итерационная последовательность может оказаться сходящейся и пр невыполнении этих условий.

Метод Ньютона (также известный как метод касательных) — это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643—1727), под именем которого и обрёл свою известность. Поиск решения осуществляется путём построения последовательных приближений и основан на принципах простой итерации. Метод обладает квадратичной сходимостью. Улучшением метода является метод хорд и касательных. Также метод Ньютона может быть использован для решения задач оптимизации, в которых требуется определить нуль первой производной либо градиента в случае многомерного пространства.

Чтобы численно решить уравнение методом простой итерации, его необходимо привести к следующей форме: , где — сжимающее отображение.

Для наилучшей сходимости метода в точке очередного приближения должно выполняться условие . Решение данного уравнения ищут в виде , тогда:

В предположении, что точка приближения «достаточно близка» к корню , и что заданная функция непрерывна , окончательная формула для такова:

С учётом этого функция определяется выражением:

Эта функция в окрестности корня осуществляет сжимающее отображение^[1], и алгоритм нахождения численного решения уравнения сводится к итерационной процедуре вычисления:

По теореме Банаха последовательность приближений стремится к корню уравнения .