Факторизация
В математике факториза́ция или фа́кторинг — это декомпозиция объекта (например, числа, полинома или матрицы) в произведение других объектов или факторов, которые, будучи перемноженными, дают исходный объект. Например, число 15 факторизуется на простые числа 3 и 5, а полином x 2 − 4 факторизуется на (x − 2)(x + 2). В результате факторизации во всех случаях получается произведение более простых объектов, чем исходный.
Целью факторизации является приведение объекта к «основным строительным блокам», например, число к простым числам, многочлен — к неприводимым многочленам. Факторизация целых чисел обеспечивается основной теоремой арифметики, а многочленов — основной теоремой алгебры.
Противоположностью факторизации полиномов является их расширение, перемножение полиномиальных факторов для получения «расширенного» многочлена, записанного в виде суммы слагаемых.
Факторизация целых чисел для больших чисел является задачей большой сложности. Не существует никакого известного способа, чтобы решить эту задачу быстро. Её сложность лежит в основе некоторых алгоритмов безопасности с открытым ключом шифрования, таких как RSA.
Матрица может также быть факторизована на произведение матриц специального вида для приложений, в которых эта форма удобна. Одним из основных примеров этого является использование ортогональных, унитарных и треугольных матриц. Существуют различные способы факторизации: QR-разложение, LQ, QL, RQ, RZ.
Ещё одним примером является факторизация функций в виде композиции других функций, имеющих определённые свойства. Например, каждая функция может рассматриваться как композиция сюръективной функции с инъективной. Этот подход является обобщением понятия факторизации систем.
Содержание
Целые числа
По основной теореме арифметики каждое натуральное число имеет единственное разложение на простые множители. Существует множество алгоритмов факторизации целого, с помощью которых можно факторизовать любое натуральное число до состава его простых множителей с помощью рекуррентных формул. Однако, для очень больших чисел эффективный алгоритм пока неизвестен.
Квадратичные полиномы
Любой квадратичный полином на комплексных числах (полиномы вида 
, где: 
, 
, и 
∈ 
, используя квадратное уравнение. Этот метод состоит в следующем:
и 
являются двумя корнями полинома, найденными при решении квадратного уравнения.
Полиномы на целых числах
Можно каждый бином приравнять нулю и найти для x два корня. Для факторинга достаточно использовать именно эти формулы для решения квадратного уравнения. Возьмём для примера 2x 2 − 5x + 2 = 0. Поскольку a = 2 и mn = a, mn = 2, что означает, что m и n равны 1 и 2. Теперь мы имеем (2x + p)(x + q) = 0. Поскольку c = 2 и pq = c, pq = 2, что означает, что p и q равны 1 и 2, или один из них −1, а другой −2. Подстановляя 1 и 2, или −1 и −2 вместо p и q (поскольку pn + mq = b), мы видим, что 2x 2 − 5x + 2 = 0 факторизуется в (2x − 1)(x − 2) = 0, давая корни x =
Замечание: быстый способ определения, является ли второй член положительным или отрицательным (как в приведённом примере, 1 и 2 или −1 и −2) состоит в проверке второй операции трёхчлена (+ или −). Если стоит +, тогда проверяем первую операцию: если она тоже +, член будет положительным, а если операция −, то член будет отрицательным. Если вторая операция −, то один член будет положительный, второй отрицательный. Такая проверка является единственным способом определения, какой член будет положительным, а какой отрицательным.
Если многочлен с целыми коэффициентами имеет дискриминант, который является полным квадратом, то многочлен факторизуемые целыми числами.
Рассмотрим, например, полином 2x 2 + 2x − 12. Если подставить значения в квадратичную формулу, то дискриминант b 2 − 4ac будет 2 2 − 4 × 2 × −12 и равен 100. Число 100 является полным квадратом, поэтому полином 2x 2 + 2x − 12 факторизуется целыми числами; эти факторы равны 2, (x − 2), and (x + 3).
Теперь рассмотри полином x 2 + 93x − 2. Его дискриминант 93 2 − 4 × 1 × (−2) равен 8657, что не является полным квадратом. Поэтому выражение x 2 + 93x − 2 нельзя факторизовать целыми числами.
Полный квадратный трёхчлен
Некоторые квадратные уравнения можно факторизовать двумя одинаковыми биномами. Такие уравнения называются полным квадратным трёхчленом. Полный квадратный трёхчлен можно факторизовать следующим образом:
Сумма/разность двух квадратов
Другой общий метод алгебраического факторинга называют разностью двух квадратов. Он заключается в применении формулы
к любым двум членам, независимо от того, являются они полным квадратным уравнением или нет. Если два члена вычитаются, то нужно просто применить формулу. Если они складываются, то оба бинома, получинные из факторинга, будут иметь мнимый член. Эта формула может быть представлена в виде
Например, 
можно факторизовать на 
.
Группировка
Ещё одним методом факторизации некоторых полиномов является факторинг группировкой. Для тех, кто любит разрабатывать алгоритмы, «факторинг группировкой» может быть самым приятным подходом к факторингу трёхчлена, поскольку в нём нужно строить догадки относительно способа завершения процесса.
Факторинг группировкой делается путём расположения членов многочлена на две или большее количество групп, каждая из которых может быть факторизована известным способом. Результаты этих факторизаций иногда можно скомбинировать так, чтобы получить более простое выражение. Например, чтобы факторизовать полином
сгруппируем подобные члены:
факторизуем через наибольший общий делитель,
и факторизуем на биномы
AC метод
Если квадратный трёхчлен имеет решения на рациональных числах, мы можем найти p и q такие, что pq = ac и p + q = b. (Если дискриминант является квадратом числа, то они существуют, в противном случае мы будем иметь иррациональные или комплексные решения, и предположение о рациональном решении является недопустимым.)
Например, x 3 − 10 3 (или x 3 − 1000) можно факторизовать в виде: (x − 10)(x 2 + 10x + 100).
Факторизация
- В математике факториза́ция или фа́кторинг — это декомпозиция объекта (например, числа, полинома или матрицы) в произведение других объектов или факторов, которые, будучи перемноженными, дают исходный объект. Например, число 15 факторизуется на простые числа 3 и 5, а полином x2 − 4 факторизуется на (x − 2)(x + 2). В результате факторизации во всех случаях получается произведение более простых объектов, чем исходный.
Целью факторизации является приведение объекта к «основным строительным блокам», например, число к простым числам, многочлен — к неприводимым многочленам. Факторизация целых чисел обеспечивается основной теоремой арифметики, а многочленов — основной теоремой алгебры.
Противоположностью факторизации полиномов является их расширение, перемножение полиномиальных факторов для получения «расширенного» многочлена, записанного в виде суммы слагаемых.
Факторизация целых чисел для больших чисел является задачей большой сложности. Не существует никакого известного способа, чтобы решить эту задачу быстро. Её сложность лежит в основе некоторых алгоритмов шифрования с открытым ключом, таких как RSA.
Матрица может также быть факторизована на произведение матриц специального вида для приложений, в которых эта форма удобна. Одним из основных примеров этого является использование ортогональных, унитарных и треугольных матриц. Существуют различные способы факторизации: QR-разложение, LQ, QL, RQ, RZ.
Связанные понятия
В теории чисел гладким числом называется целое число, все простые делители которого малы.
В теории вероятностей случайная величина имеет дискретное равномерное распределение, если она принимает конечное число значений с равными вероятностями.
Не путать с «симплекс-методом» — методом оптимизации произвольной функции. См. Метод Нелдера — МидаСимплекс-метод — алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве.
В теории алгоритмов классами сложности называются множества вычислительных задач, примерно одинаковых по сложности вычисления. Говоря более узко, классы сложности — это множества предикатов (функций, получающих на вход слово и возвращающих ответ 0 или 1), использующих для вычисления примерно одинаковые количества ресурсов.
В информатике временна́я сложность алгоритма определяет время работы, используемое алгоритмом, как функции от длины строки, представляющей входные данные . Временная сложность алгоритма обычно выражается с использованием нотации «O» большое, которая исключает коэффициенты и члены меньшего порядка. Если сложность выражена таким способом, говорят об асимптотическом описании временной сложности, т.е. при стремлении размера входа к бесконечности. Например, если время, которое нужно алгоритму для выполнения.
Методы и примеры факторизации
факторизация это метод, посредством которого многочлен выражается в форме умножения факторов, которые могут быть числами, буквами или и тем, и другим. Чтобы разложить факторы, которые являются общими для терминов, сгруппированы, и таким образом многочлен разлагается на несколько многочленов..
Таким образом, когда множители умножают друг друга, результатом является исходный многочлен. Факторинг является очень полезным методом, когда у вас есть алгебраические выражения, потому что он может быть преобразован в умножение нескольких простых терминов; Например: 2а 2 + 2ab = 2a * (а + б).
Есть случаи, когда многочлен не может быть разложен, потому что между его членами нет общего фактора; таким образом, эти алгебраические выражения делятся только между собой и на 1. Например: x + y + z.
В алгебраическом выражении общий множитель является наибольшим общим делителем членов, составляющих его.
- 1 Факторинговые методы
- 1.1 Факторинг по общему фактору
- 1.2 Пример 1
- 1.3 Пример 2
- 1.4 Факторинг по группам
- 1.5 Пример 1
- 1.6 Факторинг при проверке
- 1.7 Пример 1
- 1.8 Пример 2
- 1.9 Факторинг с замечательными продуктами
- 1.10 Пример 1
- 1.11 Пример 2
- 1.12 Пример 3
- 1.13 Факторинг с правилом Руффини
- 1.14 Пример 1
Методы факторинга
Существует несколько методов факторинга, которые применяются в зависимости от конкретного случая. Вот некоторые из них:
Факторинг по общему фактору
В этом методе идентифицированы те факторы, которые являются общими; то есть те, которые повторяются в терминах выражения. Затем применяется свойство распределения, максимальный общий делитель удаляется и факторизация завершается..
Другими словами, общий фактор выражения идентифицирован, и каждый термин разделен между ним; результирующие условия будут умножены на наибольший общий множитель, чтобы выразить факторизацию.
Пример 1
Фактор (б 2 х) + (б 2 у).
решение
Во-первых, есть общий фактор каждого слагаемого, который в данном случае 2 , и затем термины делятся между общим фактором следующим образом:
Факторизация выражается умножением общего множителя на результирующие условия:
(б 2 х) + (б 2 у) = б 2 (х + у).
Пример 2
Факторизовать (2а) 2 б 3 ) + (3ab 2 ).
решение
В этом случае у нас есть два фактора, которые повторяются в каждом термине: «а» и «б», и которые возводятся в степень. Чтобы учесть их, сначала два термина разбиты на длинные формы:
Можно заметить, что фактор «а» повторяется только один раз во втором члене, а фактор «b» повторяется в нем дважды; поэтому в первом члене есть только 2, фактор «а» и «б»; в то время как во втором семестре есть только 3.
Поэтому мы записываем времена, когда «a» и «b» повторяются и умножаются на факторы, оставшиеся от каждого слагаемого, как показано на рисунке:
Факторизация по группам
Поскольку не во всех случаях максимальный общий делитель многочлена четко выражен, необходимо предпринять другие шаги, чтобы иметь возможность переписать многочлен и, таким образом, вычислить множитель.
Один из этих шагов состоит в том, чтобы сгруппировать члены многочлена в несколько групп, а затем использовать метод общего множителя..
Пример 1
Фактор ac + bc + ad + bd.
решение
Есть четыре фактора, из которых два являются общими: в первом члене это «с», а во втором — «d». Таким образом, два термина сгруппированы и разделены:
Теперь можно применить метод общего множителя, разделив каждый член на его общий множитель, а затем умножив этот общий множитель на итоговые термины, например:
(ac + bc) / c = a + b
(ad + bd) / d = a + b
Теперь вы получаете бином, общий для обоих терминов. Фактор умножается на оставшиеся факторы; Таким образом, вы должны:
ac + bc + ad + bd = (с + д) * (а + б).
Факторизация путем проверки
Этот метод используется для разложения квадратичных полиномов, также называемых триномами; то есть те, которые структурированы как топор 2 ± bx + c, где значение «а» отличается от 1. Этот метод также используется, когда трином имеет форму x 2 ± bx + c и значение «а» = 1.
Пример 1
Фактор х 2 + 5x + 6.
решение
У вас есть квадратичный трехчлен вида х 2 ± bx + c. Чтобы сначала вычислить его, нужно найти два числа, которые при умножении дают в результате значение «с» (то есть 6), а его сумма равна коэффициенту «b», равному 5. Эти числа равны 2 и 3. :
Таким образом, выражение упрощается так:
Каждый термин учтен:
— Для (х 2 + 2x) извлекается общий термин: x (x + 2)
— Для (3x + 6) = 3 (x + 2)
Таким образом, выражение остается:
Поскольку у вас есть общий бином, чтобы уменьшить выражение, умножьте его на лишние термины, и вы должны:
х 2 + 5x + 6 = (x + 2) * (х + 3).
Пример 2
Фактор 4а 2 + 12a + 9 = 0.
решение
У вас есть квадратичный трехчлен в виде топора 2 ± bx + c и все это множитель умножается на коэффициент x 2 ; в этом случае 4.
4-й 2 (4) + 12а (4) + 9 (4) = 0 (4)
16 а 2 + 12а (4) + 36 = 0
4 2 в 2 + 12а (4) + 36 = 0
Теперь мы должны найти два числа, которые при умножении вместе дают в результате значение «с» (которое составляет 36), и что при сложении вместе получим коэффициент термина «а», который равен 6.
Таким образом, выражение переписывается с учетом того, что 2 в 2 = 4а * 4A. Поэтому распределительное свойство применяется для каждого термина:
Наконец, выражение делится на коэффициент 2 ; то есть 4:
(4а + 6) * (4a + 6) / 4 = ((4a + 6) / 2) * ((4a + 6) / 2).
Выражение выглядит следующим образом:
4-й 2 + 12a +9 = (2a +3) * (2а + 3).
Факторинг с замечательными продуктами
Существуют случаи, когда для полного разложения полиномов с помощью предыдущих методов это становится очень длительным процессом..
Вот почему выражение может быть разработано с формулами замечательных продуктов, и, таким образом, процесс становится проще. Среди наиболее популярных продуктов:
— Разница двух квадратов: ( 2 — б 2 ) = (а — б) * (а + б)
— Идеальный квадрат суммы: 2 + 2ab + b 2 = (a + b) 2
— Совершенная площадь разницы: 2 — 2ab + b 2 = (а — б) 2
— Разница двух кубов: 3 — б 3 = (a-b)*(а 2 + ab + b 2 )
— Сумма двух кубов: 3 — б 3 = (a + b) * (а 2 — ab + b 2 )
Пример 1
Фактор (5 2 — х 2 )
решение
В этом случае есть разница двух квадратов; поэтому применяется формула замечательного продукта:
(а 2 — б 2 ) = (а — б) * (а + б)
(5 2 — х 2 ) = (5 — х) * (5 + х)
Пример 2
Фактор 16x 2 + 40x + 25 2
решение
В этом случае у нас есть идеальный квадрат суммы, потому что мы можем идентифицировать два члена в квадрате, а оставшийся член является результатом умножения двух на квадратный корень первого слагаемого на квадратный корень второго слагаемого..
в 2 + 2ab + b 2 = (a + b) 2
Фактором считаются только квадратные корни первого и третьего членов:
Затем два результирующих члена разделяются знаком операции, и весь многочлен возводится в квадрат:
16x 2 + 40x + 25 2 = (4х + 5) 2 .
Пример 3
Фактор 27а 3 — б 3
решение
Выражение представляет собой вычитание, в котором два фактора возводятся в куб. Чтобы их разложить, применяется формула заметного произведения разности кубов:
в 3 — б 3 = (a-b)*(а 2 + ab + b 2 )
Таким образом, для разложения кубический корень каждого члена бинома извлекается и умножается на квадрат первого слагаемого, плюс произведение первого на второе слагаемое, плюс второе слагаемое на квадрат.
двадцать седьмой 3 — б 3
двадцать седьмой 3 — б 3 = (3a — b) * [(3a) 2 + 3ab + b 2 )]
двадцать седьмой 3 — б 3 = (3a — b) * (9а 2 + 3ab + b 2 )
Факторинг с правилом Руффини
Этот метод используется, когда у вас есть многочлен степени больше двух, чтобы упростить выражение до нескольких многочленов меньшей степени.
Пример 1
Коэффициент Q (x) = x 4 — 9х 2 + 4x + 12
решение
Сначала ищите числа, которые являются делителями 12, который является независимым термином; это ± 1, ± 2, ± 3, ± 4, ± 6 и ± 12.
Затем x заменяется этими значениями, от самого низкого до самого высокого, и, таким образом, определяется, с каким из значений деление будет точным; то есть остальное должно быть 0:
Q (-1) = (-1) 4 — 9 (-1) 2 + 4 (-1) + 12 = 0.
Q (1) = 1 4 — 9 (1) 2 + 4 (1) + 12 = 8 ≠ 0.
Q (2) = 2 4 — 9 (2) 2 + 4 (2) + 12 = 0.
И так для каждого делителя. В этом случае найденные факторы для х = -1 и х = 2.
Теперь применяется метод Руффини, согласно которому коэффициенты выражения будут поделены между факторами, найденными для точного деления. Полиномиальные члены упорядочены от старшего к младшему показателю степени; в случае отсутствия члена со степенью, следующей за последовательностью, вместо него ставится 0.
Коэффициенты расположены в схеме, как показано на следующем изображении.
Первый коэффициент уменьшается и умножается на делитель. В этом случае первый делитель равен -1, а результат помещается в следующий столбец. Затем значение коэффициента складывается по вертикали с тем результатом, который был получен, и результат помещается ниже. Таким образом, процесс повторяется до последнего столбца.
Затем та же самая процедура повторяется снова, но со вторым делителем (который равен 2), потому что выражение все еще может быть упрощено.
Таким образом, для каждого полученного корня полином будет иметь член (x — a), где «a» — это значение корня:
С другой стороны, эти условия должны быть умножены на остаток от правила Руффини 1: 1 и -6, которые являются факторами, которые представляют оценку. Таким образом, выражение, которое формируется: (х 2 + х — 6).
Получение результата факторизации полинома методом Руффини является:
х 4 — 9х 2 + 4x + 12 = (x + 1) * (х — 2) * (х 2 + х — 6)
Чтобы закончить, многочлен степени 2, который появляется в предыдущем выражении, может быть переписан как (x + 3) (x-2). Следовательно, окончательная факторизация: