Конспект лекций (стр. 4 )

Итак, пусть функция и требуется решить уравнение

, (1)

решение которого будем называть корнем (нулем) функции . Отметим, что каких-либо общих правил анализа расположение корней произвольной непрерывной функции на отрезке не существует.

Определение 1.

Корень функции будем называть изолированным корнем кратности , если

, (2)

где функция g(x) непрерывна на отрезке и знакоопределена в некоторой окрестности .

Очевидно, что, найдя один изолированный корень функции и определив его кратность, следующий корень мы можем искать как корень функции .

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

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

принцип сжимающих отображений.

Принцип сжимающих отображений

Пусть − метрическое пространство с расстоянием :

Определение 2. Отображение

, (3)

называется сжимающим, если такое, что

. (4)

Определение 3.

Элемент называется неподвижной точкой отображения , если

. (5)

Теорема 1 (принцип сжимающих отображений).

Сжимающее отображение из полного метрического пространства в имеет одну и только одну неподвижную точку .

Более того, последовательность метода простой итерации (метода последовательных приближений)

, (6)

сходится к неподвижной точке и имеет место оценка

. (7)

Доказательство.

Очевидно, что предел (если он существует) последовательности (6) является неподвижной точкой отображения . Для существования предела достаточно показать, что последовательность фундаментальна по Коши, так как пространство полно.

Из определений последовательности и сжимающего отображения следует:

Из этого неравенства (и неравенства треугольника) следует, что

и, значит,

(8)

т. е. последовательность фундаментальна по Коши и .

Более того, переходя в неравенстве (8) к пределу при , получим оценку сходимости (7).

Единственность неподвижной точки устанавливается элементарно:

пусть – два решения уравнения (5). Тогда

и, так как , то .

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

Вернемся к уравнению (1) на отрезке и преобразуем его к виду

, (9)

задав, например, , где − непрерывная, знакоопределенная на отрезке функция.

Рассмотрим для решения уравнения (9) метод простой итерации (6):

, (10)

Теорема 2. Если функция непрерывна по Липшицу:

, (11)

и преобразует интервал в , т. е.

, (12)

то уравнение (9) имеет единственное на решение , к которому сходится последовательность метода простой итерации (10) при любом начальном приближении и имеет место оценка

. (13)

Доказательство.

Определим метрическое пространство с расстоянием . Очевидно, что оно полно, а из условий (11) и (12) следует, что − сжимающее отображение из в и, значит, утверждения этой теоремы являются прямым следствием теоремы 1.

Проверка условий теоремы 2 для конкретных функций может вызвать определенные затруднения. Действительно, условие (11) для непрерывно дифференцируемой функции означает ограниченность на интервале модуля ее первой производной постоянной Липшица , а проверка условия (12) заключается в поиске (или оценке) экстремальных значений самой функции, что может оказаться более сложной задачей по сравнению с решением уравнения (9).

Если константа Липшица известна, то при достаточно удачном выборе начального приближения метода простой итерации удается избавиться от проверки условия (12).

Теорема 3. Если функция непрерывна по Липшицу с постоянной и известно (хорошее) такое, что

(14)

(это условие можно проверить, если известна константа Липшица), то уравнение (9) имеет в единственное решение ,

к которому сходится последовательность метода простой итерации и имеет место оценка

.

Доказательство.

Функция отображает отрезок в себя. Действительно,

Следовательно, выполняются все условия теоремы 2 на интервале , откуда следует сходимость и оценка сходимости метода простой итерации.

Следующая теорема характеризует кратность корня функции .

Теорема 4. Если функция непрерывна по Липшицу:

,

и преобразует интервал в , т. е.

,

то функция имеет единственный на корень кратности единица.

Доказательство.

Существование и единственность корня функции на отрезке следует из теоремы 2.

Используя непрерывность по Липшицу функции , получим неравенство

.

Но, т. к. , то

, и

т. к. , то

, следовательно,

и, значит в представлении непрерывная функция знакоопределена, т. е. кратность корня равна 1.

Постройте и исследуйте сходимость метода простой итерации для решения уравнения на интервале .

Решение. Преобразуем уравнение к виду

,

где постоянную надлежит выбрать из условий:

Начнем с условия b). Так как минимальное и максимальное значения линейной функции достигаются на концах интервала :

.

То для того, чтобы , необходимо и достаточно выбрать из условий:

Замечание. Минимум коэффициента на интервале достигается при и . Докажите эти формулы (вспомните курс вычислительных методов линейной алгебры: оптимизация метода простой итерации для решения системы ).

Теперь проверим условие a) при . Минимальное и максимальное значения функции достигаются либо при , либо в корне её производной, либо при :

,

так как неравенства

справедливы при ;

далее,

так как неравенства

справедливы при .

Итак, при отображение является сжимающим с , к его неподвижной точке сходится последовательность приближений метода простой итерации:

при любом начальном приближении ,

а для погрешности справедлива оценка

.

Метод Эйткена ускорения сходимости метода простой итерации

Пусть для функции выполняются условия теоремы 2, т. е. уравнение

(15)

имеет единственное решение , к которому сходятся приближения

. (16)

Тогда, так как

(17)

то для погрешности метода простой итерации имеем соотношение , т. е. за одну итерацию она уменьшается в раз, если . Говорят, что метод простой итерации имеет линейную скорость сходимости (при она была бы квадратичной).

Предположим, что , и рассмотрим три последовательных приближения , и . Согласно (17), они связаны следующими соотношениями:

(18)

Вычитая из второго равенства первое, получим

(19)

Заменяя производную в первом равенстве по формуле (19), получим

,

(20)

Проанализируем коэффициенты при и в (20):

(21)

(22)

Так как константа и , то эти коэффициенты являются величинами порядка в некоторой (малой) окрестности неподвижной точки и “линейная” комбинация приближений и метода простой итерации имеет своим пределом :

(23)

а также оценку ошибки приближения

(24)

так как

1) первый множитель в правой части ,

2) ,

3) ,

4) множитель перед разностью также :

Обычно записывают в виде

(25)

и называют методом Эйткена ускорения простой итерации по её трем последовательным приближениям:

,

Замечание. Метод Эйткена ускорения простой итерации решения уравнения можно переписать в виде

.

Проверьте, что и .

Докажем, что точка является точкой пересечения прямой и прямой, проходящей через точки и .

Геометрическая интерпретация метода простой итерации и его ускорения методом Эйткена.

Действительно, мы находили, решая уравнение

,

которое преобразуется к виду

и, следовательно, его решение является точкой пересечения прямой и прямой , проходящей через точки и .

Лекция 6.

Метод Ньютона

Пусть функция и требуется решить уравнение

, (1)

Идея метода Ньютона чрезвычайно проста: если − приближение к корню , то функция заменяется интерполяционным полиномом первой степени по ее значению и значению ее первой производной :

,

а корень этого полинома объявляется следующим приближением:

. (2)

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

Геометрическая интерпретация метода Ньютона.

Очевидно, что метод Ньютона (2) решения уравнения (1) совпадает с методом простой итерации решения эквивалентного уравнения

(3)

и все результаты предыдущей лекции можно применить для исследования сходимости метода, в основном теорему 5.2, где требуется, чтобы и для всех .

Пусть − изолированный корень кратности функции :

, (4)

где функция знакоопределена в некоторой окрестности корня.

Тогда, так как

то

и приближения метода Ньютона (2) к корню функции удовлетворяют соотношениям

Из этого соотношения можно сделать следующие предположения:

·  метод Ньютона не сходится, если , так как ;

·  метод Ньютона сходится, если , так как ;

·  метод Ньютона сходится с линейной скоростью, если и, так как
то

; (5)

·  метод Ньютона сходится с квадратичной скоростью, если .

Случай простого корня:

Здесь мы докажем две теоремы, содержащие условия существования простого корня функции и сходимости к нему приближений метода Ньютона.

Теорема 1. Если выпукла вниз на отрезке и

, , то

уравнение имеет единственное решение ;

приближения метода Ньютона при , например, , строго возрастают и сходятся к этому корню.

Доказательство.

Метод Ньютона для выпуклой вниз функции

Существование решения уравнения следует из того, что принимает все значения между и . На картинке единственность корня очевидна, но картинка не доказательство! Пусть − корни функции . Из определения выпуклости вниз и условия следует, что и, значит, .

Теперь покажем, что последовательность метода Ньютона определена и строго возрастает.

Прежде всего, заметим, что на интервале функция и строго убывает, т. е. (докажите этот факт).

Тогда для мы можем вычислить и (докажите этот факт: график выпуклой вниз функции выше касательной в любой ее точке), т. е. .

Ограниченная строго возрастающая последовательность имеет и, переходя к пределу в равенстве , убеждаемся, что он является корнем функции , а в силу единственности корня .

Замечание. Аналогичные теоремы можно сформулировать и доказать для случая вогнутых (выпуклых вверх) функций и изменения функции от отрицательных значений к положительным:

сформулируйте и докажите эти теоремы для нахождения корня функций методом Ньютона в соответствии с нижеприведенными картинками:

Метод Ньютона для выпуклой вниз функции

Метод Ньютона для выпуклой вверх функции

Метод Ньютона для выпуклой вверх функции

Прежде чем сформулировать и доказать вторую теорему мы рассмотрим пример применения теоремы 1 для приближения меньшего корня полинома второй степени

, (6)

с положительными корнями .

Из теоремы 1 следует, что последовательность метода Ньютона

, (7)

строго возрастает и сходится к , если (условие положительности корней полинома) .

Если (7) переписать в виде

(8)

то погрешность метода удовлетворяет неравенствам

, (9)

так как

,

т. е. скорость сходимости не хуже линейной (линейна при , почему?).

Если , то

и

.

Но

и

(10)

т. е. скорость сходимости метода Ньютона квадратичная.

Заметим, что в этом примере выполняются условия:

(11)

Теорема 2. Пусть , и

а полином имеет положительные корни и .

Тогда имеет корень , к которому сходится последовательность метода Ньютона:

,

и имеет место оценка

,

где − приближения по методу Ньютона (7) для корня полинома .

Доказательство.

Прежде всего, напомним, что последовательность

, (7)

строго возрастает и сходиться к .

При по условию теоремы и , значит определен и

.

Предположим, что для некоторого доказано, что

(12)

Покажем, что эти неравенства будут выполняться при .

Для вычисления необходимо и достаточно показать, что :

Значит существует.

Теперь нужно показать, что .

Сначала оценим .

Так как и

то

,

т. е. выполняется второе из предположений (12).

Теперь оценим :

т. е. выполняется и первое из предположений (12).

И, наконец, из неравенств , справедливых для любого целого , следует фундаментальность по Коши последовательности , так как

(13)

а сходящаяся последовательность фундаментальна по Коши.

Следовательно,

,

и

,

а переходя к пределу при в (13), получим оценку сходимости:

, что и требовалось доказать.

Метод Ньютона с параметром

Рассмотрим частный случай уравнения (1) на интервале

т. е. – корень кратности . Метод Ньютона в этом случае

при не сходится, а при остальных скорость его сходимости линейна.

Определим метод Ньютона с параметром:

. (14)

Очевидно, что для нашего примера этот метод дает решение за одну итерацию

при любом .

Метод Ньютона с параметром можно трактовать как метод простой итерации (последовательных приближений) решения уравнения

(15)

вместо уравнения .

Так как , то и

т. е. метод Ньютона с параметром сходится при любой положительной кратности корня функции и скорость его сходимости квадратичная (естественно при некоторых условиях на функцию ).

Если кратность корня функции неизвестна, то, разрешая относительно , получим .

Тогда итерационный процесс

, (16)

будет сходиться при достаточно близком к корню приближении , так как он является методом простой итерации для уравнения

(17)

и .

Литература

1.  Бахвалов методы. - М.: Наука, 1975.

2.  , Жидков вычислений. Ч.1. - М.: Наука, 1966.

3.  Волков методы. - М.: Наука, 1987.

4.  , , Монастырный методы. Т.1. - М.: Наука, 1976.

5.  , Гулин методы. - М.: Наука, 1989.