2004-gre-cs-practice-book.pdf/Q45 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: « == Вопрос: Q45-4c9f66 == <i>Тут вставьте перевод вопроса. Используйте [https://wiki.4intra.net/Help:%D0%A4%D0%BE%D1%80…») |
StasFomin (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | |||
== Вопрос: Q45-4c9f66 == | == Вопрос: Q45-4c9f66 == | ||
| + | Чтобы найти решение <m>x^*</m> уравнения <m>f(x)=0</m> для полинома <m>f(x)</m> степени <m>\ge 2</m> с производной <m>f'(x^*)\ne0</m>, [https://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%9D%D1%8C%D1%8E%D1%82%D0%BE%D0%BD%D0%B0 метод Ньютона] делает итерации вида | ||
| − | < | + | <m>x_{t+1} = x_t - \frac{f(x_t)}{f'(x_t)}</m> |
| − | + | ||
| − | + | начиная с некоторого начального значения <m>x_0 \ne x^*</m>, достаточно близкого к желаемому решению <m>x^*</m>, чтобы обеспечить сходимость к <m>x^*</m> для фиксированных значений <m>x_0</m> и <m>x^*</m>. | |
| − | + | ||
| + | Что из приведенного ниже представляет порядок увеличения минимального числа итераций, необходимого для вычисления <m>x^*</m> с точностью до <m>b</m> бит как функции из <m>b</m>? | ||
=== Ответы === | === Ответы === | ||
| − | < | + | * <m>O(1)</m> |
| − | ( | + | * <m>O(\log \log b)</m> |
| + | * Правильный ответ: <m>O(\log b)</m> | ||
| + | * <m>O(\sqrt{b})</m> | ||
| + | * <m>O(b)</m> | ||
| − | + | === Объяснение === | |
| − | + | {{cstest-source|2004-gre-cs-practice-book.pdf|32|45}} | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | * У «Ньютона», если все норм с производными и попаданием начальной точки в локальный минимум, квадратичная сходимость — т.е. ошибка на каждой итерации убывает каждый раз как квадрат. | |
| − | + | <m> | |
| − | + | e_{k+1} \approx C \cdot e_k^2 \approx C \cdot (e_0)^{2^{k+1}} \leq 2^{-b} | |
| + | </m> | ||
| + | откуда | ||
| − | + | <m> | |
| − | < | + | 2^k \cdot \log e_0 \geq b |
| − | + | </m> | |
| + | |||
| + | <m> | ||
| + | k \approx \log_2 b | ||
| + | </m> | ||
| − | + | {{question-ok|[[Участник:StasFomin|StasFomin]] 14:56, 15 декабря 2024 (UTC)}} | |
| − | + | [[Категория:Алгоритмы оптимизации]] | |
Текущая версия на 14:56, 15 декабря 2024
Вопрос: Q45-4c9f66
Чтобы найти решение уравнения для полинома степени с производной , метод Ньютона делает итерации вида
начиная с некоторого начального значения , достаточно близкого к желаемому решению , чтобы обеспечить сходимость к для фиксированных значений и .
Что из приведенного ниже представляет порядок увеличения минимального числа итераций, необходимого для вычисления с точностью до бит как функции из ?
Ответы
- Правильный ответ:
Объяснение
Исходники — вопрос 45 на 32 странице книги «2004-gre-cs-practice-book.pdf»
- У «Ньютона», если все норм с производными и попаданием начальной точки в локальный минимум, квадратичная сходимость — т.е. ошибка на каждой итерации убывает каждый раз как квадрат.
откуда