Алгебра · объяснение и практика

Почему метод Ньютона может зациклиться или остановиться

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

Неизвестное x показывает найденное значение — пять.

В теме Начала анализа и углубление · Учебная карта

В маршруте Локальные методы исследования функций · 10 тем

Главная мысль

Шаг Ньютона x_next=x−f(x)/f′(x) требует ненулевой производной. Наличие корня не гарантирует сходимость из любого старта; остановку и её причину нужно проверять отдельно.

Касательная предлагает следующий кандидат

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

Для f(x)=x³−8x+16 старт x=0 даёт f=16 и f′=−8, поэтому следующий кандидат равен 2. В точке 2 имеем f=8 и f′=4, поэтому новый кандидат снова равен 0. Получился цикл из двух точек. Обе производные ненулевые, но ни одна точка цикла не является корнем.

Цикл выше — масштабированная запись классического примера из указанного раздела OpenStax. Для g(t)=t³−2t+2 там возникает переход 0→1→0; здесь f(x)=8g(x/2), поэтому точки цикла удваиваются. Это тот же механизм неудачи, а не новый независимый контрпример. Масштабирование удобно для проверки вычислений, но не меняет причину зацикливания.

Пример

Итерации для x³−8x+16 со старта 0 идут 0→2→0→2. При этом f(−4)=−16 и f(−3)=13, так что действительный корень между −4 и −3 существует.

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

Что действительно означает критерий остановки

Малая величина |f(x)| называется малой невязкой. Она показывает близость значения функции к нулю, но без дополнительной информации не задаёт расстояние до корня. Почти плоская функция может иметь маленькую невязку далеко от корня. Аналогично малый шаг может возникнуть из численного округления, а не из успешного поиска.

Если на нужном промежутке доказана нижняя положительная граница |f′|≥m и известен корень в этом промежутке, теорема о среднем может связать расстояние с |f(x)|/m. Но сам алгоритм не получает такое доказательство автоматически. В ответе нужно различать выполненный численный критерий и гарантированную оценку точности аргумента.

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

Пример

Рассмотрим другую проверку остановки: f(x)=exp(−x), x₀=0. Программа сообщает «корень найден», когда |f(x)|<10⁻⁶, не проверяя шаг и существование нуля. После четырнадцати шагов она остановилась. Доказывает ли это, что найден корень?

Нет. Для любого конечного действительного x функция exp(−x) положительна, поэтому нуля нет. Производная равна −exp(−x), и точная формула Ньютона даёт x_next=x+1. Получаем x₁₃=13 и x₁₄=14; exp(−13)≈2,26·10⁻⁶, exp(−14)≈8,32·10⁻⁷. Порог невязки выполнен впервые на четырнадцатом шаге, но последний шаг по аргументу по-прежнему равен единице. Это ложное объявление успеха по выбранному критерию, а не цикл и не деление на нулевую производную.

Как безопасно описать неудачу

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

Даже точный нуль f′ не всегда плох сам по себе: если одновременно f=0, корень уже найден и шаг не нужен. Поэтому проверка значения функции должна предшествовать попытке деления. Такая последовательность не заставляет алгоритм решать все задачи, но позволяет правдиво отличить найденный корень от недопустимой следующей операции.

От чтения к действию

А теперь — вы

Для f(x)=x²−3 выбран старт x=0. Что происходит с обычным шагом Ньютона?

Частые вопросы

Если метод остановился, корней нет?

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

Можно ли использовать производную приближённо?

Можно в численном методе, но погрешность оценки добавляет отдельные риски. Она не отменяет проверку малости делителя, невязки и пределов вычисления.

Может ли невязка стать малой, если конечного корня нет?

Да. Для exp(−x) шаги Ньютона со старта 0 равны 0,1,2,…, а значения функции уменьшаются к нулю. Функция положительна при любом конечном аргументе. Один порог по невязке здесь не подтверждает существование корня или сходимость аргумента.

Углублённый разбор

Ньютон со скобкой сохраняет локализацию корня

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

Перед началом: Бисекция; Шаг Ньютона.

Сначала храните утверждение о корне

Пусть f непрерывна на [a,b] и f(a)f(b)<0. Тогда внутри есть хотя бы один корень. Текущий кандидат x используется только для предложения n=x−f(x)/f′(x), когда производная существует и ненулевая. После выбора новой точки её знак сравнивают со знаками концов и заменяют один конец, сохраняя противоположность.

Если f(new)=0 точно, работа завершена. Иначе новая скобка по-прежнему содержит корень, хотя он не обязан быть единственным без дополнительных условий. В журнале нужно разделять точку предложения, принятую точку и новый интервал. Иначе отказ от опасного шага может выглядеть как незаметное исполнение того же шага.

Одного попадания внутрь недостаточно для равномерного сокращения

Зафиксируем 0<θ<1/2. Принимаем n только при a+θ(b−a)≤n≤b−θ(b−a). Во всех остальных случаях, включая нулевую производную, выбираем середину. Любая принятая точка отделена от краёв, поэтому после обновления длина скобки не больше (1−θ) прежней. Это даёт явную линейную гарантию уменьшения интервала.

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

Предложение Ньютона и принятое действие
ЭтапПредложениеРешениеНовая скобка
Старт 1/101001/15отказ, середина 1[1,2]
Из 14/3принять внутри[5/4,7/4][1,4/3]

Ускорение и сертификат точности работают совместно

Когда условия Ньютона благоприятны, принятые касательные шаги быстро уменьшают ошибку. Независимо от этого середина сохранённого интервала имеет абсолютную ошибку не больше половины его длины. Эта оценка относится к некоторому корню в скобке; для утверждения о конкретном единственном корне отдельно проверяют монотонность либо другой критерий единственности.

Схема требует непрерывной функции без полюса внутри скобки. Разные знаки по сторонам разрыва не гарантируют нуль. Для вычислений с округлением знак возле нуля тоже нуждается в контроле: неопределённый численный знак нельзя объявлять точным математическим сертификатом. Здесь все промежуточные значения считаются рационально.

Отказ от далёкой касательной

Условие. Для f(x)=x³−2 возьмите скобку [0,2], θ=1/4 и старт x=1/10. Выполните защитный шаг, затем предложение из x=1.

  1. При x=1/10 имеем f=−1999/1000, f′=3/100; предложение Ньютона равно 1001/15, далеко вне скобки.
  2. Оно отвергается. Середина равна 1, её значение f(1)=−1, поэтому новая скобка [1,2].
  3. Из x=1 предложение Ньютона равно 4/3. Центральная полоса новой скобки [5/4,7/4] содержит 4/3, значит шаг принимается.
  4. Поскольку f(4/3)=10/27>0, новая скобка равна [1,4/3]. Её длина 1/3 даёт ошибку середины не больше 1/6.

Ответ. Первое принятое значение 1; после второго шага скобка [1,4/3].

Проверка. Знаки f(1)=−1 и f(4/3)=10/27 противоположны. Производная 3x² положительна на этой скобке, поэтому содержащийся корень единственен.

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

Проверьте понимание

Какая точка реально принимается на первом шаге задачи?

Вопросы к этой главе

Зачем центральная полоса, если уже есть бисекция?

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

Можно принять предложение с нулевой производной?

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

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • NIST DLMF §3.8: Nonlinear Equations

    Вебом проверены Newton’s Rule, кратность нуля и условия локальной сходимости. Защитная скобка либо применение к производной объяснены отдельным выводом; примеры и точные расчёты авторские.

Модифицированный Ньютон для кратного корня

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

Перед началом: Кратность корня; Локальная ошибка итерации.

Кратность входит в отношение функции к производной

Пусть f(x)=(x−r)ᵐh(x), h(r)≠0 и h достаточно гладкая. При x около r имеем f/f′=(x−r)/(m+(x−r)h′/h). Для обычного Ньютона ошибка e_next=e−f/f′ имеет главный член (1−1/m)e. При m>1 коэффициент ненулевой, поэтому сходимость обычно только линейная.

Модифицированный шаг x_next=x−m f/f′ сокращает этот главный член. При подходящей гладкости остаётся ошибка порядка e², то есть восстанавливается квадратичная локальная сходимость. Если h постоянна, поправка точно равна e и корень достигается за один шаг. Для произвольной h такое конечное попадание не обещается.

Неверная кратность может ухудшить результат

Если использовать число k вместо истинного m, ведущий коэффициент ошибки становится 1−k/m. Для локального сжатия требуется его модуль меньше единицы; при слишком большом k ошибка может расти или чередоваться без уменьшения. Поэтому множитель не является произвольной настройкой ускорения: он должен соответствовать структуре корня.

Иногда кратность оценивают через f f″/(f′)², стремящуюся к(m−1)/m. Но это отношение чувствительно к округлению около корня, где значения функции и производной малы. В самом корне может возникнуть неопределённость 0/0. Точная проверка f=0 должна предшествовать попытке вычислить следующую поправку.

Малая невязка особенно обманчива при кратности

У функции (x−r)ᵐ значение f имеет порядок eᵐ. Поэтому при большом m невязка становится очень малой, пока ошибка аргумента ещё заметна. Нельзя оценивать точность x тем же численным порогом, который применяется к f(x), без информации о кратности и масштабе h.

Для контроля удобно сравнивать последовательность ошибок и отношение соседних значений. В чистом степенном примере обычный Ньютон даёт точно постоянное отношение(m−1)/m; модифицированный шаг обнуляет ошибку. Это независимая проверка формулы итерации, а не только наблюдение нескольких совпавших десятичных знаков.

Тройной корень

Условие. Для f(x)=(x−2)³ и старта x₀=5 выполните два обычных шага Ньютона и один модифицированный шаг с m=3.

  1. Для x≠2 отношение f/f′=(x−2)/3. Обычная итерация равна x_next=(2x+2)/3.
  2. Из x₀=5 получаем x₁=4, затем x₂=10/3. Ошибки относительно корня равны 3,2,4/3.
  3. Обе соседние ошибки имеют отношение 2/3, что подтверждает линейную, а не квадратичную скорость.
  4. Модифицированный шаг даёт 5−3·(5−2)/3=2. После точного попадания новое деление не выполняется.

Ответ. Обычные шаги 4 и 10/3; модифицированный шаг сразу даёт 2.

Проверка. Прямая подстановка f(2)=0 подтверждает корень. Для обычной схемы e_next=(2/3)e доказывается тождественно для любого ненулевого старта ошибки.

Где легко ошибиться. Поправка m f/f′ нужна при известной кратности m. Нельзя применять произвольный большой множитель и ожидать гарантированного ускорения или глобальной сходимости.

Проверьте понимание

Какое точное отношение ошибок у обычного Ньютона в задаче?

Вопросы к этой главе

Почему обычный Ньютон всё-таки сходится в примере?

Его ошибка умножается на 2/3, то есть строго уменьшается по модулю. Потеря квадратичной скорости не означает отсутствие сходимости, а означает более медленное уменьшение ошибки.

Всегда ли правильная кратность даёт один шаг?

Нет. Это происходит в чистом степенном примере с постоянным h. При переменном ненулевом h модификация обычно оставляет квадратичную локальную ошибку.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • NIST DLMF §3.8: Nonlinear Equations

    Вебом проверены Newton’s Rule, кратность нуля и условия локальной сходимости. Защитная скобка либо применение к производной объяснены отдельным выводом; примеры и точные расчёты авторские.

Ньютон для стационарной точки может искать максимум

Ньютон, применённый к производной, ищет стационарную точку. Это может быть максимум или седло; успешное обнуление градиента само по себе не решает задачу минимизации.

Перед началом: Стационарная точка; Вторая производная.

Уточните уравнение, которое решает итерация

Для оптимизации одной переменной иногда используют x_next=x−f′(x)/f″(x). Это обычный Ньютон для уравнения g(x)=f′(x)=0. Его локальная сходимость при простом корне g зависит от f″(r)≠0, но знак f″(r) при этом не обязан быть положительным. Поэтому одинаково возможна сходимость к строгому минимуму и строгому максимуму.

Классификация стационарной точки является отдельным шагом. При f″(r)>0 получается локальный минимум, при отрицательном значении максимум. Если вторая производная нулевая, нужен анализ высших производных или прямое исследование знака приращения. Ни число итераций, ни малая невязка f′ не заменяют эту проверку.

Направление Ньютона может повышать функцию

Шаг d=−f′/f″ имеет произведение f′d=−(f′)²/f″. Если f″>0 и f′≠0, оно отрицательно и малое движение вдоль d уменьшает f. Если f″<0, знак положителен: малый шаг вдоль предложенного направления, наоборот, повышает значение. Простое уменьшение длины такого шага не превращает направление в направление спуска.

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

Покажите область притяжения нежелательной точки

У f(x)=x⁴−2x² стационарны 0 и±1. Ноль является максимумом, а±1 минимумами. Итерация Ньютона для производной упрощается до N(x)=2x³/(3x²−1), когда знаменатель ненулевой. В достаточно малой окрестности нуля она сжимает модуль x, поэтому может уверенно вести именно к максимуму.

Например, при |x|≤1/4 имеем |N(x)|≤(2/13)|x|. Эта оценка сохраняет окрестность и доказывает стремление к нулю, а не только один неудачный шаг. В результате технически корректный решатель стационарности даёт неправильный ответ на иной вопрос: где достигается минимум исходной функции.

Сходимость к максимуму

Условие. Для f(x)=x⁴−2x² возьмите x₀=1/4. Найдите первый шаг Ньютона для f′=0 и классифицируйте предельную точку в малой окрестности нуля.

  1. В старте f′=−15/16 и f″=−13/4. Производная уравнения ненулевая, поэтому шаг определён.
  2. Отношение f′/f″=15/52. Новый аргумент 1/4−15/52=−1/26.
  3. Для |x|≤1/4 формула N(x)=2x³/(3x²−1) даёт |N(x)|≤(2/13)|x|, следовательно последовательность стремится к 0.
  4. Но f″(0)=−4<0, поэтому ноль — строгий локальный максимум. Минимумы находятся в±1 и имеют значение−1.

Ответ. x₁=−1/26; схема локально сходится к максимуму 0.

Проверка. Знак f(x)=x²(x²−2)<0 при 0<|x|<√2 независимо подтверждает максимум f(0)=0. Стремление итераций к нему не является минимумом.

Где легко ошибиться. Решение f′=0 и минимизация f являются разными задачами. После сходимости проверяйте тип точки и соответствие исходной цели, особенно при отрицательной второй производной.

Проверьте понимание

К какому типу точки ведёт описанная схема из малой окрестности нуля?

Вопросы к этой главе

Если функция всюду строго выпукла, опасность остаётся?

Внутренняя стационарная точка тогда является единственным глобальным минимумом на выпуклой области. Но существование точки и сходимость конкретных шагов всё равно требуют проверки.

Почему уменьшение шага не всегда помогает?

При отрицательной второй производной направление Ньютона является направлением роста первого порядка. Уменьшение длины сохраняет этот знак для достаточно малых положительных шагов.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • NIST DLMF §3.8: Nonlinear Equations

    Вебом проверены Newton’s Rule, кратность нуля и условия локальной сходимости. Защитная скобка либо применение к производной объяснены отдельным выводом; примеры и точные расчёты авторские.

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

При выпуклой возрастающей функции старт справа от корня даёт особое поведение Ньютона: итерации убывают, но не перескакивают корень. Это гарантия из геометрии касательной, а не вывод по нескольким удачным численным шагам.

Перед началом: Выпуклость и касательная; Итерация Ньютона.

Нижняя касательная ограничивает новое приближение

Пусть f непрерывно дифференцируема и выпукла на[r,b], f(r)=0, а f′ положительна на этом отрезке. Для текущего x≥r касательная лежит ниже графика:0=f(r)≥f(x)+f′(x)(r−x). Деление на положительную производную даёт r≤x−f(x)/f′(x). Поскольку f(x)≥0, новая точка не больше x. Значит шаг сохраняет интервал[r,x].

Начав с x₀=b, получаем убывающую последовательность верхних приближений. Она ограничена снизу корнем и потому имеет пределℓ≥r. Непрерывность итерационной формулы и положительность производной дают f(ℓ)=0. Возрастание f обеспечивает единственность корня на отрезке, следовательно ℓ=r. Здесь используются условия на весь сохраняемый интервал, а не только знак производной в стартовой точке.

Квадратичная ошибка объясняет скорость вблизи корня

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

Для квадратного корня положительный верхний x даёт нижний2/x. Если x≥√2, то2/x≤√2. Поэтому одну последовательность Ньютона можно превратить в двусторонний рациональный сертификат без вычисления иррационального корня. Ширина такого интервала удостоверяет абсолютную погрешность любого выбранного приближения внутри него.

Граница модели видна при смене стороны или кривизны

Старт слева не удовлетворяет тому же аргументу: знак f(x) меняется, и шаг обычно движется вправо. Для вогнутой функции расположение касательной обратное. Поэтому нельзя запоминать правило «Ньютон всегда даёт верхние границы». Гарантия относится к конкретной возрастающей выпуклой модели и проверенному начальному отрезку. Защищённый метод с бисекцией решает более общую задачу, но использует иной механизм сохранения интервала.

Рациональный сертификат для √2

Условие. Для f(x)=x²−2 начните с x₀=2. Выполните два шага Ньютона и постройте после них нижнюю и верхнюю рациональные границы корня.

  1. Итерация имеет вид x_next=(x+2/x)/2. На[√2,2] функция возрастает и выпукла, поэтому все полученные x остаются верхними границами.
  2. Первый шаг равен(2+1)/2=3/2. Второй равен(3/2+4/3)/2=17/12.
  3. Нижняя граница после второго шага равна2/(17/12)=24/17. Проверяем квадраты: (24/17)²=576/289<2 и(17/12)²=289/144>2.
  4. Ширина интервала равна17/12−24/17=(289−288)/204=1/204. Следовательно корень заключён между этими точными рациональными числами.

Ответ. x₁=3/2,x₂=17/12; сертификат24/17<√2<17/12, ширина1/204.

Проверка. Обе границы проверены прямым возведением в квадрат, независимо от итерационного вывода. Разность дробей удостоверяет ширину без округления корня.

Где легко ошибиться. Не выводите одностороннюю гарантию из положительности f′ в одной точке. Нужны выпуклость и положительная производная на всём сохраняемом интервале до корня.

Проверьте понимание

Какова точная ширина полученного после двух шагов интервала?

Вопросы к этой главе

Почему точная ошибка здесь квадратична?

Для r=√2 алгебра даёт x_next−r=(x−r)²/(2x). При положительном x правая часть неотрицательна и содержит квадрат старой ошибки, одновременно объясняя сторону и локальную скорость.

Что гарантирует ширина1/204?

Любой корень внутри интервала находится от его середины не дальше1/408. Для правого конца гарантирована ошибка меньше1/204. Эти две оценки относятся к разным выбранным приближениям.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Boyd, Vandenberghe: Convex Optimization

    Прочитаны §3.1.3: касательная как нижняя оценка выпуклой функции, §3.3: сопряжённая функция, неравенство Фенхеля и уравнение градиента. Наши одношаговые границы Ньютона и quartic-сопряжение выведены отдельно.

Интервальный шаг Ньютона: исключение корней и строгий сертификат

Интервальный шаг Ньютона проверяет не одну точку, а все возможные корни начального отрезка. Значение в середине делится на гарантированный интервал производной, затем новый образ пересекается с исходным отрезком. Это даёт исключение или локализацию; существование и единственность нужно обосновать отдельными условиями.

Перед началом: Теорема о среднем значении; Интервальная арифметика.

Любой корень обязан пережить пересечение

Пусть f непрерывно дифференцируема на X=[a,b], m∈X, а интервал D содержит все f′(x) при x∈X. Предположим, что 0∉D. Для любого корня x*∈X теорема о среднем даёт f(m)=f′(ξ)(m−x*) при некоторой ξ между m и x*. Поэтому x*=m−f(m)/f′(ξ) принадлежит N=m−f(m)/D.

Следовательно, все корни исходного отрезка содержатся в X∩N. Если пересечение пусто, корней на X нет. Если оно непусто, это пока лишь необходимая область. Нельзя назвать её доказанным существующим корнем, не предъявив дополнительное основание. В лаборатории ниже существование проверяется знаками f(a),f(b), включая точный ноль на конце.

Ноль в интервале производной означает неудачу этого деления

Когда D содержит ноль, обычное интервальное деление не определено как один ограниченный отрезок. Реализация возвращает отсутствие сертификата. Это одинаково возможно для x² на[−1,1], где корень есть, и для x²+1 на том же отрезке, где действительных корней нет. Сам статус не выбирает между этими случаями.

Интервал D может быть шире настоящего множества производных из-за зависимости повторных вхождений x. Поэтому его попадание на ноль не доказывает даже существования стационарной точки f. Уменьшение X или более точная оценка производной может помочь. Произвольное удаление нуля из D, напротив, уничтожило бы гарантию сохранения всех корней.

Сертификат единственности и область его действия

Если f(a)f(b)≤0, непрерывность даёт хотя бы один корень в X. При 0∉D производная имеет один строгий знак на всём X, поэтому f строго монотонна и корень единственный. Тогда пересечение не только сохраняет все возможные корни, но и действительно содержит этот установленный корень.

Наш вычислитель принимает ограниченный многочлен и получает D точным интервальным Горнером для его производной. Коэффициенты и границы рациональны, округления нет. Однако он выполняет один шаг, а не обещает произвольную точность или полную изоляцию всех корней на прямой. Строгое сужение, отсутствие корня и отсутствие сертификата отображаются разными результатами.

Один точный шаг для кубического многочлена

Условие. Для f(x)=x³−x−1 и X=[1,3/2] вычислите интервальный шаг из середины. Докажите существование и единственность корня в исходном отрезке и укажите полученный рациональный интервал.

  1. Производная равна 3x²−1. На положительном отрезке X её значения лежат в D=[2,23/4], который не содержит нуля. Значения на концах f(1)=−1 и f(3/2)=7/8 имеют разные знаки.
  2. Середина m=5/4. Прямая подстановка даёт f(m)=125/64−5/4−1=−19/64. Отрицательный знак важен для направления обоих концов интервального деления.
  3. Имеем N=5/4+[19/368,19/128]=[479/368,179/128]. Оба конца уже лежат внутри[1,3/2], поэтому пересечение ничего дополнительно не отсекает.
  4. Разные знаки на концах доказывают существование, а положительная производная — единственность. Теорема о среднем сохраняет этот корень в N. Лабораторный ввод коэффициентов −1 −1 0 1 и границ 1,3/2 возвращает те же точные дроби.

Ответ. В X ровно один корень, и он принадлежит [479/368,179/128]. Середина 5/4 сама корнем не является.

Проверка. Независимая подстановка рациональных концов N даёт отрицательное и положительное значения кубика. Это непосредственно проверяет полученную скобку. Отдельно ненулевая невязка−19/64 исключает ошибочную запись x*=m.

Где легко ошибиться. Не переводите статус «производная содержит 0» в сообщение «корней нет». Это отказ выбранного достаточного вычислительного шага; он не является отрицательным ответом исходной математической задачи.

Интервальный шаг Ньютона для многочлена

Коэффициенты от постоянного до старшего: до степени 6, модуль до 10000. Числа — целые, десятичные или дроби. Отрезок a<b, |a|,|b|≤10000. Один точный интервальный шаг. Производная, содержащая 0, означает отсутствие сертификата, а не отсутствие корня.

Данные для расчёта

Проверьте понимание

Что доказано для f(x)=x³−x−1 на X=[1,3/2] в разобранном примере?

Вопросы к этой главе

Если пересечение сузилось, корень уже существует?

Нет. Сохранение всех возможных корней является условным утверждением. В этой главе существование дополнительно удостоверено противоположными знаками исходных концов; без него отчёт оставляет вопрос открытым.

Почему можно включать точный ноль на конце при проверке существования?

Нулевое значение уже предъявляет корень. Если производная не меняет строгого знака на X, других корней на том же отрезке быть не может. Это не требует строгой смены знака.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Andreas Wiethoff: C-XSC Interval Newton Method

    Пример C-XSC: проверка знаков концов, исключение нуля из интервала производной и пересечение ньютоновского образа с исходным интервалом; условия видны в функции criter и строке обновления. Многочлен главы исследуется отдельно.

Сертификат Канторовича даёт область существования корня

Невязка в одной точке ещё не доказывает близость корня. Сертификат Канторовича соединяет невязку, обратимость начальной производной и скорость изменения производной. Из этих данных получаются область сходимости Ньютона и отдельная, обычно большая область единственности.

Перед началом: Метод Ньютона для системы уравнений; Норма линейного оператора и условие Липшица.

Какие три числа нужны до первого шага

Пусть F задано на открытой выпуклой области Ω пространства Rⁿ, непрерывно дифференцируемо и его производная липшицева с константой K. В начальной точке x₀ матрица J₀=F′(x₀) обратима. Обозначим a=‖J₀⁻¹F(x₀)‖, B=‖J₀⁻¹‖ и ℓ=BK. Величина a имеет смысл первого перемещения, а ℓ ограничивает изменение производной после нормировки начальным обратным оператором.

Проверяют h=aℓ≤1/2. Это достаточное условие, а не критерий существования всех корней: его нарушение означает только неудачу данного сертификата. Оценки B и K должны быть верхними границами в одной согласованной норме. Экспериментально малое изменение производной в нескольких точках не заменяет равномерной границы K на нужной области.

Малый и большой радиусы отвечают на разные вопросы

При ℓ>0 вводят r₋=(1−√(1−2h))/ℓ и r₊=(1+√(1−2h))/ℓ. Если замкнутый шар радиуса r₋ вокруг x₀ лежит в Ω, обычные итерации Ньютона определены, остаются в этом шаре и сходятся к корню. При h<1/2 сходимость квадратичная. Мажорантная парабола q(t)=a−t+ℓt²/2 объясняет происхождение двух радиусов.

При h<1/2 единственность относится к Ω, пересечённой с открытым шаром радиуса r₊. Подмена открытого шара замкнутым может добавить второй корень на его границе. Также нельзя заменить Ω всем пространством, если исходная функция задана лишь локально. При ℓ=0 формулы с делением на ℓ не применяют: постоянная производная приводит к отдельному аффинному случаю.

Что именно удостоверяет вычисление

Сертификат не требует заранее знать искомое решение. Сначала оценивают доступные данные в x₀ и на области, затем получают существование и сходимость. Это отличается от утверждения «если старт достаточно близок к уже известному простому корню»: близость здесь заменена проверяемыми величинами. Радиус r₋ не является точной ошибкой каждого последующего приближения.

При машинной реализации нужны надёжные границы норм, а не только округлённые оценки. Малость численной невязки особенно обманчива у плохо обусловленного якобиана, потому что множитель B может быть велик. В одномерном примере ниже все исходные числа рациональны; квадратный корень в радиусе оставлен символически, чтобы отдельно проверить смысл границы единственности.

Два корня и открытая граница

Условие. Для F(x)=x²−2 и x₀=3/2 найдите параметры сертификата и объясните, почему он не противоречит существованию отрицательного корня.

  1. F(x₀)=1/4, F′(x₀)=3, поэтому a=1/12 и B=1/3. Производная F′(x)=2x имеет глобальную константу Липшица K=2.
  2. Получаем ℓ=2/3 и h=1/18<1/2. Область Ω=R содержит требуемый малый замкнутый шар.
  3. Корни мажоранты равны r₋=3/2−√2 и r₊=3/2+√2. Корень √2 находится на левой границе малого замкнутого интервала.
  4. Левая граница большого открытого интервала равна −√2. Поэтому второй корень в область единственности не входит. Первый шаг Ньютона даёт 17/12, согласуясь с малым интервалом.

Ответ. Сходимость к √2 удостоверена; −√2 лежит на исключённой границе большого открытого шара.

Проверка. Подстановка обоих радиусов в q(t)=1/12−t+t²/3 даёт ноль. Независимая факторизация F(x)=(x−√2)(x+√2) подтверждает ровно два действительных корня.

Где легко ошибиться. Не объявляйте корень единственным на замкнутом большом шаре: в этом примере второй корень лежит именно на его границе.

Проверьте понимание

Попадает ли −√2 в область единственности большого шара в разобранном примере?

Вопросы к этой главе

Если h больше половины, корней нет?

Нет. Проверка лишь перестаёт давать достаточную гарантию из выбранного старта и выбранных оценок. Можно улучшить оценки, изменить старт или воспользоваться другим методом локализации.

Почему нужна норма обратной производной?

Невязка измеряет ошибку уравнения, а не перемещение аргумента. Обратная производная переводит одно в другое; при её большой норме маленькая невязка может соответствовать заметному перемещению.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

Порядок сходимости секущих и золотое сечение

Секущая заменяет производную разностью двух значений функции. Это экономит вычисление производной, но новая ошибка зависит от двух прежних ошибок одновременно. Именно эта память даёт обычный порядок золотого сечения, расположенный между линейной и квадратичной сходимостью; из одного удачного шага такой вывод сделать нельзя.

Перед началом: Простой корень и локальное разложение Тейлора; Разделённая разность и ошибка приближения.

Хранить последние точки, а не обязательно скобку

Локальный поиск простого действительного корня гладкой функции двумя последними точками; делители проверяются на каждом шаге.

Итерация записывается xₙ₊₁=xₙ−f(xₙ)(xₙ−xₙ₋₁)/(f(xₙ)−f(xₙ₋₁)). Сначала проверяют, не найден ли уже точный нуль, затем ненулевой делитель. Для следующего шага сохраняют две последние точки независимо от знаков функции. В этом отличие от схемы, которая специально удерживает концы со сменой знака; секущие не гарантируют сохранения исходного интервала.

Пусть r простой корень, e=x−r, d=y−r. Разложение f(r+e)=ae+be²+O(e³), где a=f′(r)≠0 и b=f″(r)/2, даёт новую ошибку e_next=(b/a)ed+члены более высокого порядка. Можно получить это и через разделённые разности: числитель после сокращения содержит оба отклонения. В отличие от Ньютона ведущий член не является квадратом только последней ошибки.

Почему возникает число φ

Предположим, что итерации близки к r, сходятся без конечного попадания, а b/a ненулево. Если |eₙ₊₁| приблизительно равно K|eₙ|ᵖ и |eₙ| приблизительно K|eₙ₋₁|ᵖ, то двухшаговое произведение требует p=1+1/p. Положительное решение больше единицы равно φ=(1+√5)/2. Это объясняет характерный порядок через структуру рекурсии, а не подгонку нескольких десятичных знаков.

То же видно по логарифмам малых ошибок: их главные величины удовлетворяют рекурсии типа Фибоначчи с ограниченной добавкой. При f″(r)=0 главный коэффициент исчезает, и точный порядок может стать выше; для линейной функции возможен один точный шаг. Поэтому φ — невырожденный общий случай, а не запрет на более быстрое поведение специальных функций.

Конечная проверка и асимптотика отвечают на разные вопросы

Локальная теория не обещает сходимости из произвольных двух точек. У f(x)=x²+x−2 значения при x=0 и x=−1 одинаковы и ненулевые: следующий шаг не существует, хотя функция имеет два простых корня. Обнаруженный нулевой знаменатель нужно сообщить как остановку метода, а не доказательство отсутствия корней.

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

Меняющийся знак ошибки при рациональных шагах

Условие. Для f(x)=x²+x−2 начните с x₀=0,x₁=2. Найдите x₂,x₃,x₄ и проверьте двухшаговую ошибку относительно простого корня r=1.

  1. Алгебраическое сокращение секущей даёт следующий аргумент (xy+2)/(x+y+1), где x,y — две последние точки. В начале f(0)=−2,f(2)=4, и знаменатель не нулевой.
  2. Из пары 0,2 получаем x₂=2/3. Затем из 2,2/3 выходит x₃=10/11, а из 2/3,10/11 — x₄=86/85.
  3. Ошибки равны e₀=−1,e₁=1,e₂=−1/3,e₃=−1/11,e₄=1/85. Прямое вычитание единицы из сокращённой формулы даёт точное тождество e_next=ed/(3+e+d).
  4. Проверка последнего перехода: произведение (−1/3)(−1/11)=1/33, делитель 3−1/3−1/11=85/33, результат1/85. При e,d→0 коэффициент перед произведением стремится к 1/3, в согласии с f″(1)/(2f′(1))=1/3.

Ответ. x₂=2/3,x₃=10/11,x₄=86/85; точная двухшаговая ошибка равна ed/(3+e+d), её невырожденная асимптотика имеет порядок φ.

Проверка. Каждый шаг независимо восстанавливается пересечением прямой через две точки графика с горизонтальной осью. Разложение f=(x−1)(x+2) отдельно подтверждает выбранный корень и все указанные рациональные ошибки.

Где легко ошибиться. Не называйте метод квадратичным потому, что ошибка содержит произведение двух множителей. Они относятся к разным итерациям; их связь и даёт φ вместо двух.

Проверьте понимание

Чему равен x₄ после разобранных шагов секущих для x²+x−2 со стартами 0 и 2?

Вопросы к этой главе

Нужно ли вычислять два новых значения функции на каждом шаге?

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

Почему смена знака ошибки в примере не опровергает сходимость?

Сходимость требует уменьшения расстояния, а не нахождения всегда с одной стороны. Знак новой ошибки здесь задаётся произведением двух прежних и знаком делителя.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • NIST DLMF §3.8(iii) — Secant Method

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

Метод Галлея: второй производной достаточно для кубического шага

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

Перед началом: Разложение функции и производных возле простого корня; Рациональный шаг Ньютона.

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

Гладкая функция возле простого корня; рациональный шаг с первой и второй производными и ненулевым общим знаменателем.

Формула имеет вид H(x)=x−2f(x)f′(x)/[2f′(x)²−f(x)f″(x)]. Здесь не требуется извлекать корень из квадратного приближения и выбирать его ветвь. Когда f′≠0, можно записать поправку как (f/f′)/[1−ff″/(2f′²)]. Такое представление показывает, как обычная поправка изменяется с учётом кривизны.

Чтобы понять происхождение, аппроксимируйте f(x+h) дробью (f+αh)/(1+βh) с совпадением первых двух производных в h=0. Получаются β=−f″/(2f′), α=f′−ff″/(2f′). Нуль числителя h=−f/α и даёт записанный шаг. Это локальная рациональная модель функции, а не подстановка неизвестного корня в ряд.

Кубическая ошибка имеет свои предпосылки

Пусть r простой корень и f достаточно гладкая. Введём a=f′(r), b=f″(r)/2, c=f‴(r)/6. Подстановка f(r+e)=ae+be²+ce³+O(e⁴) в рациональную формулу даёт H(r+e)−r=[(b/a)²−c/a]e³+O(e⁴). Два младших члена сократились; возле r знаменатель стремится к 2a²>0 и потому остаётся допустимым.

Если кубический коэффициент нулевой, конкретная функция может сходиться быстрее. При кратном корне a=0 такой вывод неприменим; обычная схема Галлея в общем случае теряет указанную кубическую скорость. Это другой механизм, чем умножение ньютоновской поправки на заранее известную кратность. Наличие второй производной само по себе не отменяет проверки структуры корня.

Дополнительный знаменатель создаёт отдельную остановку

Для g(x)=x³−2 в точке x=−1 значения равны g=−3,g′=3,g″=−6. Общий знаменатель 2·9−(−3)(−6)=0, поэтому шаг Галлея не определён. Обычная производная при этом ненулевая, и действительный корень существует. Таким образом, проверка только f′ не защищает эту рациональную схему.

Сначала проверяйте точное или сертифицированное попадание в корень, затем знаменатель и конечность чисел. Малый знаменатель делает поправку чувствительной к округлению. Кубический локальный порядок не даёт гарантии глобального поиска и не является автоматическим преимуществом по времени: вычисление второй производной тоже имеет стоимость. В защищённой программе отказ шага можно обрабатывать другой схемой, явно сохраняя её условия.

Рациональное приближение кубического корня единицы

Условие. Для f(x)=x³−1 со старта x₀=2 выполните два шага Галлея. Получите точное выражение новой ошибки относительно r=1 и её кубический коэффициент.

  1. Подстановка f′=3x²,f″=6x сокращает шаг при x≠0 до H(x)=x(x³+2)/(2x³+1). На положительных x общий знаменатель не нулевой.
  2. Первый шаг равен 2·10/17=20/17. На втором получаем (20/17)(17826/4913)/(20913/4913)=118840/118507.
  3. Ошибки после шагов равны 3/17 и 333/118507. Точное раскрытие числителя даёт H(x)−1=(x−1)³(x+1)/(2x³+1), поэтому при положительном x>1 новая ошибка положительна.
  4. Отношение новой ошибки к кубу прежней стремится к (1+1)/(2+1)=2/3. В первой точке оно равно3/17, во второй — (37/17)/(20913/4913); оба конечных значения проверяются отдельно от предельного 2/3.

Ответ. x₁=20/17,x₂=118840/118507; точная ошибка (x−1)³(x+1)/(2x³+1), предельный кубический коэффициент 2/3.

Проверка. Независимое умножение (x−1)³(x+1)=x⁴−2x³+2x−1 восстанавливает числитель H(x)−1. Подстановка точных дробей в исходную несокращённую формулу проверяет, что сокращение не потеряло допустимость двух шагов.

Где легко ошибиться. Нельзя проверять лишь f′≠0: знаменатель Галлея содержит дополнительное вычитание и может занулиться. После сокращения также сохраните исключённые точки исходной формулы.

Проверьте понимание

Чему равен первый допустимый шаг Галлея именно для f=x³−1 из x₀=2 в разобранном примере?

Вопросы к этой главе

Почему x=0 исключён у сокращённой кубической формулы, хотя она там имеет значение?

У исходной поправки при x=0 и f=−1 обе части знаменателя нулевые. Упрощённая рациональная функция задаёт продолжение, но это не разрешает задним числом исходный шаг с делением 0/0.

Одинаков ли кубический коэффициент на всех итерациях?

Нет. Постоянное 2/3 является пределом при x→1. Точное отношение равно (x+1)/(2x³+1) и зависит от текущего аргумента.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • NIST DLMF §3.8(v), формула 3.8.12 — Halley’s rule

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

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться