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

[max(Im)]

Рассмотрим нелинейное уравнение вида $f(x)=0.$ Замечательный метод Ньютона предлагает строить следующую итерационную последовательность:

$$ x_{k+1}=x_k - \dfrac{f(x_k)}{f'(x_k)} $$

Есть также теорема, которая говорит, что если функция дважды непрерывно дифференцируема в окрестности простого корня, если в этой окрестности $f'(x)\neq 0,$ и если хорошо выбрать начальное приближение, то метод сходится квадратично.
У меня вопрос в том, зачем нужно условие на простоту корня? Как это влияет? В вики предложен пример с $f(x)=x^2,$ где сходимость становится лишь линейной. Но я не могу понять, откуда берется такое плохое влияние. Ну и пусть в нашей окрестности $f(x)=(x-x^*)^pg(x),$ что в этом такого. В доказательстве теоремы явно нигде не используется.
Кроме того, в случае, когда кратность корня $p,$ формулу предлагают заменить на

$$ x_{k+1}=x_k - p\dfrac{f(x_k)}{f'(x_k)} $$

Этого я тоже не пойму, зачем... Помогите разобраться?

[ИСН]

Вы эту функцию в этот метод можете в явном виде подставить? Вот отсюда и берётся. Или о чём вопрос? Где это в теореме? Ну выпишите доказательство теоремы и подставьте опять-таки эту функцию туда. Какое-то из утверждений ВНЕЗАПНО станет ложным.

[max(Im)]

Проблема в том, что теорема требует $f'(x)\neq 0$ в окрестности корня, что в случае $x^2$ неверно. Вообще, да, это будет неверно и в общем случае, если корень не простой (так ведь? Если продифференцировать $(x-x^*)^pg(x)$ ).
А неравенство нулю производной функции необходимо потому, что , если $m_1=\inf |f'(x)| > 0,$ $M_2=\sup |f''(x)|,$ то для сходимости метода теорема требует выбрать начальное приближение $x_0$ так, чтобы $\dfrac{M_2|x_0-x^*|}{2m_1}<1.$
Тогда вопрос, чем помогает вторая формула

$$ x_{k+1}=x_k - p\dfrac{f(x_k)}{f'(x_k)} $$

и зачем вообще условие на простоту корня (о нем везде так пишут...), если есть условие на производную?

[ИСН]

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

[ewert]

max(Im) в сообщении #575860 писал(а):

Кроме того, в случае, когда кратность корня $p,$ формулу предлагают заменить на

$$ x_{k+1}=x_k - p\dfrac{f(x_k)}{f'(x_k)} $$

Этого я тоже не пойму, зачем..

Дело в том, что в формуле метода Ньютона вычитается единица, делённая на логарифмическую производную для предыдущей итерации. Добавление множителя, равного кратности корня, означает, что фактически вместо уравнения $f(x)=0$ мы пытаемся решать уравнение $\sqrt[p]{f(x)}=0$ (там с точностью до знаков), для которого первая производная в окрестности корня уже ненулевая. Поэтому добавление этого множителя восстанавливает квадратичную скорость сходимости.

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