Алгоритм нахождения эквивалентных точек оси абсцисс функции многочлена



    Уважаемые хабровчане, приветствую! Продолжаем цикл околоматематических статей, предыдущая расположена тут. Напомню, что я лишь дилетант математики, занимающийся её морально-эстетической стороной, и мои идеи могут показаться вам неинтересными/бесполезными/etc. Итак:

    Для начала верным шагом будет введение аксиоматики на счет термина «эквивалентности» в данном контексте:

    • Если некоторая координата оси абсцисс image из числового множества удовлетворяет следующему условию:

      image

      То считается, что image (то есть image эквивалентна image)

    Такая аксиоматика в рамках этой статьи удобства ради, и, строго говоря, не совсем корректна.

    И сразу бы неплохо ответить на традиционный вопрос: «извините, а зачем это надо?». Отвечаю — как минимум, для поиска остальных корней уравнения многочлена (перейдя от уравнения к функции), зная лишь один корень. А также многообразие менее очевидных вещей. Сейчас мы и займемся разрешением этой задачи, а затем приведем алгоритм в общем виде. Для заинтересовавшихся милости прошу под кат.

    Отметим, что мы будем работать над следующим классом функций:

    image

    Для тех, кто не знает, что такое сигма, нужно пояснить, что это равносильно следующему:

    image

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

    image

    Задача: зная один из корней уравнения (из любого числового множества — будь он хоть рациональным, хоть комплексным и т.д.), найти остальные корни уравнения. Да не просто найти, а путем решения уравнения меньшей степени!

    Что же, самое время перейти от уравнения к функции:

    image

    А дальше, забавы ради, найдем все ненулевые производные функции:

    image
    image
    image

    Ну раз уж нашли, давайте и в ряд Тейлора функцию разложим (где image):

    image

    Дальше вспомним вышеописанную аксиоматику эквивалентности image для нашего контекста:

    image [в силу равенства справедливо и image]

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

    image

    Воспользуемся следующим очевидным правилом:

    • Произведение равно нулю тогда и только тогда, когда хотя бы один или несколько множителей равны нулю.

    А мы как раз можем множитель image вынести за скобки:

    image

    Тогда:

    1. image

      не подойдет, т.к. image, ибо будет тавтология вида image

    2. image

    Вот второй случай обращения в произведение в ноль нам вполне подойдет! Давайте же скорее подставим производные:

    image

    Подсократим немного:

    image

    И о чудо! Уравнение получилось второй степени (квадратное), в то время как исходное уравнение было кубическим (третей степени).

    Решая его относительно image получим следующие корни:

    image

    Очевидно, из этого для нашей функции следует следующее:

    image

    Что это нам дает для нашего уравнения? А то, что зная один из корней уравнения, мы сможем найти остальные два (причем за квадратичную сложность).

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

    Давайте рассмотрим на более конкретном примере:

    image

    Я знаю, что из корней искомого уравнение равен image. А если представить уравнение как кубическую функцию (по алгоритму, описанному выше), то получим следующее:

    image

    График выглядит следующим образом:


    Тогда для нашего корня image:

    image

    То есть:

    image

    Таким образом, мы нашли остальные два корня кубического уравнения путем решения квадратного уравнения. В общеизвестных кругах есть метод деления уголком, которые позволяет также понизить степень. Но он работает только при целочисленных коэффициентах (т.е. рациональные придется приводить к целым, а комплексные вообще не возможно).

    Также интересен тот факт, что из подобной формулы «эквивалентности» следуют условия (не)монотонности для многочлена n-ой степени. Сформировать его можно так:
    При обнаружении в многочлене image четного радикала image (где image — любое подкоренное выражение) можно сформировать следующее свойство:

    Если при любых image выполняется неравенство image, то график искомой функции является монотонным на всем множестве image. Также справедливо и обратное, если image.

    Почему так? Да потому что если оное не выполняется, то мы просто напросто не сможем вычислить image из-за ОДЗ подкоренного выражения.

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

    image

    Перейдем от уравнения к функции:

    image

    Разложим функцию в ряд Тейлора, где image:

    image

    Нам необходимо найти image, следовательно:

    image

    Тогда:

    1. image

      не подойдет, т.к. image, ибо будет тавтология вида image

    2. image

    Решим уравнение относительно image (степень которого меньше исходного), корни которого и будут эквивалентностью image.

    Теперь, в частности, справедливо следующее:

    1. image
    2. image

    Эквивалентные точки найдены.

    Также не забываем про условие (не)монотонности и другие разнообразные следствия из искомого алгоритма. Также стоит отметить, что обычно условия монотонности определяют по ОДЗ радикала корней уравнения image. Напомню, что так можно искать не только «остальные корни», но и любые image, такие что:

    image

    Ещё стоит упомянуть что, согласно теореме Абеля — Руффини, алгоритм будет работать только до многочлена общего вида 5-ой степени включительно (т.к. корни уравнения высших порядков больше четвертой нельзя представить в виде рациональных функций (корней то бишь и т.д.).

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

    Спасибо за внимание!
    Поделиться публикацией

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

      +3
      Но ведь можно просто поделить в столбик исходный многочлен на многочлен (x-x0).
        0
        Об этом сказано в статье. И «понижение степени» лишь один из вариантов использования :)
          +1
          В общеизвестных кругах есть метод деления уголком, которые позволяет также понизить степень. Но он работает только при целочисленных коэффициентах (т.е. рациональные придется приводить к целым, а комплексные вообще не возможно).

          А вы не могли бы пояснить? В моем мире можно делить друг на друга многочлены с любыми коэффициентами.
            –3
            Поделите на иррациональное (pi/etc) в общем случае, либо на комплексное число. Если получится — значит я ошибся, спорить не буду.
            В любом случае я не утверждаю что алгоритм вышеописанный есть панацея.
            Спасибо вам за внимание!
              +1
              Рассмотрим для простоты квадратный многочлен
              (x-a)*(x-b)*(x-c)*...*(x-v)*(x-w)
              где буквы от a до w — произвольные числа, можно иррациональные. Раскрыть этот многочлен (т.е. преобразовать его в привычную форму) я предоставляю желающим.

              Теперь разделим в столбик этот многочлен на (x-w) — совершенно очевидно, что получится
              (x-a)*(x-b)*(x-c)*...*(x-v)
              только в раскрытом виде.
              Причём не важно, делим мы в столбик или каким-то другим способом — главное, что мы знаем, что способ делить многочлены есть.

              Почему Вы решили, будто делить можно только многочлены с целыми коэффициентами — я не понимаю. Вероятно, Вы перепутали деление многочленов с методом угадыванием корня, который действительно требует целочисленных коэффициентов, ибо сказано: «целочисленный корень есть делитель последнего члена полинома, прочие же корни — иррациональные».
                0
                «главное мы знаем, что способ делить многочлены есть» — осталось его найти :)
                А до того момента можно использовать вышеприведенный алгоритм.
                  0
                  Да «в столбик» многочлены делятся, в любых полях.
                  Позиционная запись числа это тоже многочлен. И вообще непонятно, откуда столько шума изза теоремы Безу, про которую рассказывают еще в школе.
                    0
                    Я думаю, Вы легко нагуглите этот метод. Изложу его тут как я понимаю:

                    Разделим
                    3*x^4 + 4*x^3 + 7*x^2 + 2*x + 9
                    на
                    x+2

                    Для этого разделим первый член делителя (3*x^4) на первый член делимого (x) — получим 3*x^3.

                    Умножим 3*x^3 на весь делитель — получим
                    3*x^4 + 6*x^3

                    Вычтем это из делимого — получим
                    (3*x^4 + 4*x^3 + 7*x^2 + 2*x + 9) — (3*x^4 + 6*x^3) =
                    -2*x^3 + 7*x^2 + 2*x + 9

                    Повторим эту операцию. При делении получим -2*x^2

                    Вот так у нас и вырисовывается
                    3*x^3 — 2*x^2…

                    Там всё просто. Ну очень просто.
                +3
                В поле у любого элемента кроме 0 есть обратный по умножению. И у по и у е и и даже у pi+i*e. Из написанного непонятно, что вам мешает делить комплексные числа.
                0
                Лишь один из вариантов использования чего?
                  0
                  Лишь один из вариантов использования алгоритма. Он может использоваться для выявления некоторых свойств(монотонность, экстремальные точки и т.д.). Да и его преимущество в том, что можно в общем случае выявить формулы «эквивалентности» заранее, и затем лишь подставить коэффициенты. Спасибо за комментарий!
              +2
              На момент написания этого комментария пост лайкнули 17 человек. Именем Зевса я призываю кого-нибудь из них сюда, чтобы он дал мне ответ: за что? о_О Это же очевидный велосипед на костылях.
                0
                Вы мою статью про решение квадратных уравнений видели? Костыли — мой конек! Всегда все делается эстетики ради, если даже на ваш взгляд это не рационально (о чем я честно предупредил в начале статьи).
                  0
                  Костыли чаще всего антиэстетичны, и этот случай не исключение.
                    –1
                    Что на счет условия не монотонности?
                      +1
                      Я смогу высказаться насчёт «условия не монотонности», ежели вы изволите сформулировать его человеческим языком. Что такое «обнаружение в многочлене x0 чётного радикала», современной науке неизвестно.
                        0
                        Это означает, что в формуле «эквивалентности» обнаружен корень(радикал) с целочисленной четной степенью. Например — квадратный корень (как в случае с функцией — полиномом третьей степени). Теперь проанализируйте его подкоренное выражение и вы заметите свойства, описанные в статье. Буду дома — смогу рассказать более подробно, будет желание — поговорим в лс.
                          +1
                          Если возникает необходимость объяснять что-то в ЛС, значит, наблюдается недостаток объяснений в посте.

                          В текущей формулировке утверждение очевидно неверно. В любую формулу можно добавить что-нибудь типа + (-1)1/2-(-1)1/2, что никак не изменит её значение, но сделает её формально соответствующей вашему «условию». Собственно, комплексные числа появились отчасти благодаря тому, что решая кубические уравнения по формуле Кардано, математики сталкивались с квадратными корнями из отрицательных чисел, которые потом, однако, сокращались, оставляя вполне вещественное выражение для единственного вещественного корня. Соответственно, отсюда возник вопрос: а может, корень из отрицательного числа — это не так страшно?
                            0
                            В любую формулу можно добавить что-нибудь типа + (-1)1/2-(-1)1/2, что никак не изменит её значение, но сделает её формально соответствующей вашему «условию».

                            Искомое «условие» верно лишь для вышеописанного алгоритма.
                            Это вытекающее отсюда следствие, которое можно доказать.
                            Например, зная, что формула «эквивалентности» для кубической функции общего вида есть:
                            image
                            Становится совершенно очевидно, что чтобы нашлись эквивалентные точки во множестве чисел image — подкоренное выражение должно быть меньше либо равно нулю. Иными словами, условие немонотонности следующее:
                            1. image
                            2. image

                            Подобную операцию мы можем проделать и в общем случае алгоритма.
                              +1
                              «В общем случае» не указано, как именно должна находиться формула эквивалентности. Там присутствует этап «решая относительно х0», но конкретный метод решения не указывается. Соответственно, я могу начать вычислять её таким способом, что получатся лишние корни из отрицательных выражений.
                                0
                                Соответственно, я могу начать вычислять её таким способом, что получатся лишние корни из отрицательных выражений.

                                Так это будет ошибкой, лишние корни нужно иссечь. Или будете меня упрекать в том, что я не указал этого в статье? Ну, извините. Принцип от этого не меняется.
                                  0
                                  То есть ваш велосипед полагается на то, что использующие его не станут использовать своих велосипедов?
                                    +1
                                    Короче, мне надоела эта эвристическая беседа, и я её немного подсокращу. Через несколько комментариев мы придём к выводу, что в ваше «условие не монотонности» нужно добавить «и от этого радикала никакими преобразованиями не избавиться». Потом я замечу, что это такой очень сложный способ сказать «многочлен не принимает вещественных значений». Потом внезапно окажется, что всё ваше «условие» сводится к утверждению «если для всякого x0 уравнение f(x) — x0 имеет не более одного вещественного решения, то f(x) монотонна». А это утверждение тривиально, как и всё, что написано в этом посте, кроме, разумеется, того, что в нём неверно.
                  0
                  В общеизвестных кругах есть метод деления уголком

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

                    –1
                    Очень рад, что подобные чувства вызвала у вас математика! :)
                    –1
                    Насчёт корней sigma функции image есть гипотеза, что они все действительные, как и корни её производной (приз = $1 млн.!). Мысли есть?
                      –2
                      Для решения этой задачки проблемы необходимо сперва взять энергию из эфира!

                    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                    Самое читаемое