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

Алгоритм МН:

1) В качестве начального приближения берем точку, достаточно близкую к точному решению.

2) В этой точке проводим касательную к графику функций до пересечения с Ох – получаем ит.д.

3) Процедура повторяется, пока не будет достигнута заданная точность (универсальный критерий прерывания).

Формула метода Ньютона:

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

(3.2)

П.5 Скорости сходимости МПД, МХ, МН:

 

1)Скорость сходимости МПД:

На каждом шаге длина интервала уменьшается вдвое. Таким образом, через kшагов достигаетсяточность - , решаем неравенство

Необходимое число шагов:

То есть, МПД сходится со скоростью геометрической прогрессии со знаменателем ½ (для добавления одного верного десятичного знака – 3 шага).

 

2) Скорость сходимости МХ:

Теорема 3.1:

Если на интервале [ a,b ] функция f – непрерывна и дифференцируема, ее производная на этом интервале имеет постоянный знак, т.е. f – либо монотонно убывает, либо монотонно возрастает на всем интервале, то верна следующая оценка:

(3.3)

где  - решение, найденное на k -ом шаге,

Следствие 3.2:

Если , то если  (так как  ), т.е. универсальный критерий прерывания работает корректно.

 

Теорема 3.3:

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

 

Комментарии:

Если и очень близки друг к другу, например - ,то тогда искорость сходимости МХ будет выше, чем скорость сходимости МПД.

Итак, выгодно, чтобы и были близки друг к другу, это будет так, если длина интервала будет стремиться к нулю, но в МХ это не так, это происходит в МПД, поэтому выгодно комбинировать МХ и МПД.

 

3) Скорость сходимости МН:

Теорема 3.4:

Если функция f(x) дважды непрерывна и дифференцируемана [ a,b ] и ,и  на нем не

меняет свои знаки, т.е. монотонно возрастает или убывает и при этом не меняет характера выпуклости. Имеет место неравенство:

  (3.4)

;

Комментарии:

Квадрат обеспечивает удваивание числа верных знаков после каждой итерации.

Таким образом, метод Ньютона работает гораздо быстрее, нежели МПД или МХ.

МН имеет гипергеометрическую скорость сходимости.

Тонкие места МН:

1) Какую из 2-х точек интервала [ a,b ] выбрать в качестве начального приближения .

a

b

a

b

 

 

                                                                                                       

 

a

b

a

b

 

 

В качестве стартовой точки выгоднее брать точку, в которой знак 2-ой производной совпадает со знаком функции.

2) В отличие от МПД и МХ – МН сходится не всегда.

 

 

МН может и не сходится(*)

 

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

П.6 Многомерный вариант метода Ньютона:

МПД и МХ применимы только для решения НУ, метод Ньютона может быть легко видоизменен, и его можно применять для решения СНУ.

Рассмотрим СНУ n на n (n – уравнений, n – неизвестных):

F(X)=0, X= .

При решении СНУ поступаем таким же образом, как и при решении НУ.

1) Выбираем стартовую точку , достаточно близкую к корню.

2)В одномерном варианте мы заменяли функцию на касательную и приравнивали её к нулю. Аналогичным образом поступаем и для функции многих переменных, только там заменяем на дифференциал, т.е.:

                      ||

Решаем данное уравнение относительно X:

 

W – матрица частных производных (матрица Якоби)

умножим на матрицу обратную матрице W слева:

      (3.5)

Окончательный вид формулы многомерного варианта метода Ньютона:

    (3.6)

 

Замечание:

есть 2 варианта реализации вычисления по формуле (3.6):

а) Явно вычислить обратную матрицу (например, с помощью присоединенной матрицы)

б) Заметим, что вектор есть ни что иное, как решение СЛАУ

(3.7) , поэтому мы можем не вычислять обратную матрицу, а только решить СЛАУ (3.7) (например методом Гаусса) и решение этой матрицы подставить в (3.7б) .

Пример решения СНУ методом Ньютона:

Приводим к виду F(X)=0:

,в качестве стартовой точки возьмем

Сделаем один шаг по многомерному методу Ньютона:

 

||

Затем находим и т.д., пока не будет достигнута заданная точность:

 

П.7 Вариации метода Ньютона:

7.1 Комбинированный метод (сочетание МН и МХ):

МН быстро сходится, но, увы, не всегда. МХ всегда сходится, но не быстро. Комбинируя оба метода, получаем метод, обладающий достоинствами МХ и МН, а именно – сходится всегда и очень быстро (со скоростью МН).

На каждом шаге КМ проводим и хорду, и касательную, получаем новый интервал.

7.2 Видоизмененный метод Ньютона:

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

(3.8)

Видоизмененный МН сходится хуже, чем обычный МН – со скоростью геометрической прогрессии. Эффекта удваивания числа верных знаков после каждой итерации в нем нет.

 

П.8 Метод итераций, решение НУ и СНУ:

Одномерный вариант МИ.

Предполагается, что НУ приведено к виду удобному для итераций.

(3.9)

Запускаем итерационный процесс (3.10):

(3.10)

Теорема 3.5:

Если итерационный процесс сходится, то сходится к точному решению НУ (3.9), при условии непрерывности функции u.

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

в формуле (3.10) переходим к пределу

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

 

Рассмотрим пример решения НУ:

приводим к виду удобному для итераций, добавим x с обеих сторон:

процесс зациклился – не сходится

Попробуем по-другому: перед тем, как прибавить x, разделим на 2.

запускаем итерационный процесс для данной функции u:

данный итерационный процесс сходится к - .

 

Графическая интерпретация МИ:

итерационный процесс сходится и                     итерационный процесс расходится             

сходится монотонно(рис.1)монотонно (рис.2)

сходится не монотонно, по спирали              расходится не монотонно, по спирали

(рис.3)                                                                (рис.4)

Заметим закономерности:

1) Если возрастает, то итерационный процесс всегда ведет себя монотонно, при этом он может и сходится и расходится.

Если же  убывает, то итерационный процесс ведёт себя не монотонно, идет по спирали, при этом он может, как сходиться, так и расходиться.

2) Если  то итерационный процесс сходится (рис.1 и рис.3).

Если же , то итерационный процесс расходится (рис.2 и рис.4)

 

Метод итераций может применяться не только для решения НУ, но и для решения СНУ. Все происходит точно так же, т.е. СНУ приводим к виду удобному для итераций.

X – вектор, U – вектор функция.

(3.10)

 

Если итерационный процесс (3.10) то он сходится к точному решению - .

Наша задача выяснить условия, при которых итерационный процесс сходится.

Ответ на этот вопрос даёт теорема 3.6.

Теорема 3.6:

Итерационный процесс 3.10 сходится, если отображение U – сжимающее, т.е. для любых

X, Y (3.11),где С – const, С < 1 (коэффициент сжатия).

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

докажем , при k, l тем самым покажем, что итерационный процесс сходится.

= (по формуле геометрической прогрессии со знаменателем С)=