Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания
Сегодня четвергпродвинутая математика7-я статья темы.
В предыдущей статье я говорил с вами о множестве математических теорий, а сегодня я поговорю с вами о чем-то полезном.
Все мы знаем, что многие задачи в индустрии являются абстрактными и моделирующими, сущностными или математическими вопросами. В плане задач по математике нельзя оставлять уравнения, В математике мы можем использовать самые разные расчеты, формулы, а задумывались ли вы когда-нибудь о том, как мы в компьютерных областях?Решите более сложное уравнение?
Если вы не думали об этом раньше, вам, возможно, придется подумать об этом, потому что очень вероятно, что вы столкнетесь с этим в вопросах на собеседовании в будущем.
дихотомия
Первый метод, который мы собираемся представить, — это дихотомия.
Когда дело доходит до дихотомии, с ней должен быть знаком каждый.Честно говоря, когда я впервые увидел слово дихотомия в учебнике по математике для продвинутых, я был просто в шоке. Позже, когда я увидел много других алгоритмов в книгах по математике, таких как статистика, я постепенно привык к ним. С тех пор, как я переключился на алгоритмы, я все больше и больше осознавал важность математики. Хотя это не означает, что вы должны быть учителем математики, важно, по крайней мере, слушать уроки математики, если вы еще не закончили учебу.
Вернемся к дихотомии. Если вы изучили дихотомию, вы подумаете, что это очень простой алгоритм, но если вы сделалиLeetCode Вопрос 4, и вы обнаружите, что чисто дихотомические задачи могут быть очень сложными. Если мы просто объясним принцип дихотомии, нам будет трудно полностью понять этот алгоритм. Чтобы добиться этого, я долго думал и, наконец, решил следовать теории дзен о том, является ли гора горой или нет, и разделить дихотомию на три уровня.
First – это первый уровень, т.е. мыРазбивайте одну вещь пополам за раз.
Это должно быть нашей начальной и наиболее интуитивной концепцией, такой как самая классическая задача о золотых монетах. Скажем, у нас есть несколько монет, одна из которых золотая, золотая монета тяжелее, а остальные монеты одинакового веса. У нас есть только одна шкала, как найти золотые монеты с наименьшим количеством раз.
В этой задаче нам нужно продолжать делить монету на две части и запирать одну из них балансом. Быстро находите ответы, повторяя вышеуказанные операции снова и снова.
На втором уровне дихотомия — это уже не просто деление объекта на две части, аФункции поиска пополам. Это также метод решения уравнений, которому посвящена эта статья.
если есть функция
, который увеличивается или уменьшается на интервале [a, b], и
. Тогда мы знаем, что функция должна иметь решение, равное 0, и это решение мы можем использовать методом деления пополам, чтобы найти приближенное решение.
На картинке выше
приращение, и
. Продолжаем получать середины a и b
. По приведенному выше рисунку получаем
, поэтому мы можем положить
считается новым б. Итак, мы продолжаем находить и
Середина , повторите вышеописанный процесс, так как наша самая большая ошибка - это длина интервала, поэтому, когда мыДлина интервала достаточно сокращена, то мы нашли достаточно приближенное решение.
В методе деления пополам мы не выполняем ни одной итерации пополам, а длина интервала уменьшается вдвое, что является экспоненциальным уменьшением. Таким образом, даже если в начале интервал велик, его можно быстро сократить после итерации деления пополам, и можно получить очень точный результат, и, подобно ряду Тейлора, помимо достаточно точного значения, можно получить еще и диапазон ошибок.
Если мы подумаем глубже, мы обнаружим, что некоторые условия можно снова ослабить. Как нам действительно нужноЯвляется ли функция строго возрастающей или убывающей?? Например, давайте посмотрим на следующую картинку:
На интервале (b2, b1) функция строго не убывает, а сначала убывает, а затем возрастает. Но на правильность результата это не влияет, ибо в данном вопросе дихотомия не по суждению
и размер значения функции при сужении интервала, но на
Знак значения функции. То есть необходимо только удовлетворить
, и есть только одна точка, где функция непрерывна и равна 0, вы можете найти ее с помощью деления пополам.
Глубоко подумав, вы перейдете к третьему уровню дихотомии, который заключается в том, чтобы отпустить предел приращения и вернуться к исходной концепции деления пополам.
Суть дихотомии в том, чтоНайдите место пополам, а что касается приращения функции или приращения элементов в массиве, то это только видимость, это просто условие для нас вдвое. Другими словами, если мы сможем найти другие условия для сокращения пространства поиска вдвое, то мы также сможем получить эффект дихотомии, независимо от того, упорядочена она или нет.
То есть мы пошли по кругу и, наконец, вернулись к самому основному понятию деления «объекта» на два. Просто мы прошли через такое метание, и на поверхности вроде бы то же самое, что и изначальное понимание, а на самом деле уже давно другое.
Я не ожидал, что смогу играть в дзен-буддизм в области алгоритмов: видеть гору — это гора, видеть, что гора — не гора, и, наконец, вернуться к видению горы или горы.
Итерационный метод Ньютона
Прочитав метод деления пополам, давайте рассмотрим еще один метод быстрого нахождения корня.Как и метод деления пополам, это также метод итеративной аппроксимации, но скорость аппроксимации выше. Этот метод был впервые предложен Ньютоном, поэтому он также известен какИтерационный метод Ньютона, я думаю имя Ньютон написано, и каждый должен уметь получить его вес.
Название метода итераций Ньютона выглядит очень блефовым, но принцип на самом деле не сложный, грубо говоря, есть только одно предложение, то естьПодход по касательной, например, давайте посмотрим на следующий рисунок:
На приведенной выше схеме нам требуется
Корень мы нашли первый
точка, мы
Вывод при , получает его тангенс. Очевидно, что пока наклон этой касательной не равен 0, мы должны получить ее пересечение с осью абсцисс. Мы принимаем это пересечение как следующее значение, т.е.
смысл. Повторяем описанный выше процесс итеративно, и вскоре мы сможем получить достаточно близкое решение.
для точки
Для касательной при , ее наклон равен
, точка пересечения b
. Его касательное уравнение легко получить, то есть
Используя это уравнение, мы можем найти его пересечение с осью абсцисс, т.е.
Значение:
Решив это уравнение, получим:
Вышеприведенная формула является итеративной формулой метода итераций Ньютона, который является очень хорошим методом, гораздо более мощным, чем метод деления пополам, поскольку скорость сходимости выше, а вычисления несложны.
Давайте посмотрим на его мощность, посмотрим на ЧжихуМалый крючок Key Mountain[1]Пример от ответа Бога:
мы используем
пришел спросить
Значение , мы все знаем, что в
в диапазоне,
, поэтому мы просим
Решение может быть получено косвенным путем
значение .
В этой задаче итерационная формула:
В качестве отправной точки итерации выполняется итерация, и получаются следующие результаты:
x0=3.0(1位)
x1=3.1411...(4位)
x2=3.14159265357...(11位)
x3=3.1415926535897932384626433832795020...(34位)
x4=3.14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706786...(102位)
x5=3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446095505822317253594081284811174502841027019385211055596446229489549303819644288109756659334461284756482337867831652712019091456485669234603486104543266482133936072602491412734...(301位)
Видно, что всего за пять итераций вычисленное нами число пи превысило 300 цифр, а наша точность увеличивалась более чем в три раза с каждой итерацией, что очень шокирует.
Невозможно сойтись
Но, к сожалению, не все уравнения могут иметь такой хороший эффект при использовании метода итераций Ньютона, а для некоторых уравнений даже может быть все больше и больше отклонений. Возьмем другой пример, такой как уравнение
. Если изобразить его итерационный процесс, то он выглядит так:
Мы также можем видеть, что, соблюдая приведенную выше формулу итерации, мы полагаем
рассматриваемые как коэффициенты, имеем
Выведите этот коэффициент, вы можете получить его коэффициент
, вы можете видеть, что с увеличением x этот коэффициент также увеличивается. То есть по мере повторения это значение будет становиться все больше и больше, а это значит, что наша амплитуда все больше и больше, что все дальше и дальше от сходимости.
Хотя в некоторых случаях итерационный метод Ньютона не сходится, в большинстве случаев он работает очень хорошо. Метод деления пополам фиксирует интервал, который каждый раз сокращается вдвое, в то время как итерационная эффективность метода итераций Ньютона часто выше.В целом, метод итераций Ньютона можно использовать для получения более высокой скорости сходимости. По сравнению с методом дихотомии, формулу метода итераций Ньютона написать несложно, а еще он используется в машинном обучении, выучить его действительно экономически выгодно!
Сегодняшняя статья о бинарных и ньютоновских итерациях здесь.Если вы найдете что-то полезное, пожалуйста, нажмитеобрати внимание наЧто ж, твое маленькое усилие много значит для меня.
использованная литература
[1]Знаю почти:"https://www.zhihu.com/question/20690553"