Факторизация: различия между версиями
| [отпатрулированная версия] | [отпатрулированная версия] |
Содержимое удалено Содержимое добавлено
Maxal (обсуждение | вклад) переименовал «Факторизация» в «Факторизация целых чисел»: отражает суть статьи |
Нет описания правки |
||
Строка 1:
{{о|математической концепции||Фактор}}
[[Файл:Factorisatie.svg|thumb|rught|Иллюстрация полинома ''x''<sup>2</sup> + cx + d = (x + a)(x + b), где a + b равно c и a * b равно d.]]
В [[Математика|математике]] '''факториза́ция''' или '''фа́кторинг''' — это декомпозиция объекта (например, [[Число|числа]], [[полином]]а или [[Матрица (математика)|матрицы]]) на [[произведение]] других объектов или '''факторов''', которые, будучи [[Умножение|перемноженными]], дают исходный объект. Например, число 15 факторизуется на [[простые числа]] 3 и 5, а полином ''x''<sup>2</sup> - 4 факторизуется на (''x'' - 2)(''x'' + 2). В результате факторизации во всех случаях получается произведение более простых объектов, чем исходный.
Целью факторинга является приведение объекта к «основным строительным блокам», например, число — к простым числам, многочлен — к [[Неприводимый многочлен|неприводимым многочленам]]. Факторинг целых чисел обеспечивается [[Основная теорема арифметики|основной теоремой арифметики]], а факторинг многочленов — [[Основная теорема алгебры|основной теоремой алгебры]]. [[Формулы Виета]] связывают коэффициенты многочлена с его корнями.
Противоположностью факторизации полиномов является их [[Расширенный полином|расширение]], перемножение полиномиальных факторов для получения «расширенного» многочлена, записанного в виде суммы слагаемых.
[[Факторизация целых чисел]] для больших чисел является задачей большой сложности. Не существует никакого известного способа, чтобы решить эту задачу быстро. Её сложность лежит в основе некоторых алгоритмов безопасности с [[Криптосистема с открытым ключом|открытым ключом шифрования]], таких как [[RSA]].
[[Матрица (математика)|Матрица]] может также быть факторизована на произведение матриц специального вида для приложений, в которых эта форма удобна. Одним из основных примеров этого является использование [[Ортогональная матрица|ортогональных]], [[Унитарная матрица|унитарных]] и [[Треугольная матрица|треугольных]] матриц. Существуют различные способы факторизации: [[QR-разложение]], ''LQ'', ''QL'', ''RQ'', ''RZ''.
Ещё одним примером является факторизация [[Функция (математика)|функций]] в виде [[Композиция функций|композиции]] других функций, имеющих определённые свойства. Например, каждая функция может рассматриваться как композиция [[Сюръекция|сюръективной функции]] с [[Инъекция (математика)|инъективной]]. Этот подход является обобщением понятия факторизации систем.
== Целые числа ==
{{Main|Факторизация целых чисел}}
По [[Основная теорема арифметики|основной теореме арифметики]] каждое натуральное [[число]] имеет единственное разложение на простые множители. Существует множество [[алгоритм]]ов факторизации целого, с помощью котрых можно факторизовать любое натуральное число до состава его простых множителей с помощью [[Рекуррентная формула|рекуррентных формул]]. Однако, для очень больших чисел эффективный алгоритм пока неизвестен.
== Квадратичные полиномы ==
Любой квадратичный [[полином]] на [[Комплексное число|комплексных числах]] (полиномы вида <math>ax^2+bx+c</math>, где: <math>a</math>, <math>b</math>, и <math>c</math> ∈ <math>\mathbb{C}</math>) можно факторизовать [[Алгебраическое выражение|выражениями]] вида <math>a(x - \alpha)(x - \beta) \ </math>, используя [[квадратное уравнение]]. Этот метод состоит в следующем:
:<math>
\begin{align}
ax^2 + bx + c & = a(x - \alpha)(x - \beta) \\
& = a\left(x - \frac{-b + \sqrt{b^2-4ac}}{2a}\right) \left(x - \frac{-b - \sqrt{b^2-4ac}}{2a}\right),
\end{align}
</math>
где: <math>\alpha</math> и <math>\beta</math> являются двумя [[Корень многочлена|корнями]] полинома, найденными при решении [[Квадратное уравнение|квадратного уравнения]].
=== Полиномы на целых числах ===
:<math>(mx+p)(nx+q),\,\!</math>
где:
: <math>mn = a,\ pq = c\,\!</math>
и
: <math>pn + mq = b. \,</math>
Можно каждый бином приравнять нулю и найти для ''x'' два корня. Для факторинга достаточно использовать именно эти формулы для решения квадратного уравнения.
Возьмём для примера 2''x''<sup>2</sup> − 5''x'' + 2 = 0. Поскольку ''a'' = 2 и ''mn'' = ''a'', ''mn'' = 2, что означает, что ''m'' и ''n'' равны 1 и 2. Теперь мы имеем (2''x'' + ''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''), мы видим, что 2''x''<sup>2</sup> − 5''x'' + 2 = 0 факторизуется в (2''x'' − 1)(''x'' − 2) = 0, давая корни ''x'' = {0.5, 2}
'''Замечание:''' быстый способ определения, является ли второй член положительным или отрицательным (как в приведённом примере, 1 и 2 или −1 и −2) состоит в проверке второй операции трёхчлена (+ или −). Если стоит +, тогда проверяем первую операцию: если она тоже +, член будет положительным, а если операция −, то член будет отрицательным. Если вторая операция −, то один член будет положительный, второй отрицательный. Такая проверка является единственным способом определения, какой член будет положительным, а какой отрицательным.
Если многочлен с целыми коэффициентами имеет [[дискриминант]], который является полным квадратом, то многочлен факторизуемые целыми числами.
Рассмотрим, например, полином 2''x''<sup>2</sup> + 2''x'' − 12. Если подставить значения в квадратичную формулу, то дискриминант ''b''<sup>2</sup> − 4''ac'' будет 2<sup>2</sup> − 4 × 2 × −12 и равен 100. Число 100 является полным квадратом, поэтому полином 2''x''<sup>2</sup> + 2''x'' − 12 факторизуется целыми числами; эти факторы равны 2, (''x'' − 2), and (''x'' + 3).
Теперь рассмотри полином ''x''<sup>2</sup> + 93''x'' − 2. Его дискриминант 93<sup>2</sup> − 4 × 1 × (−2) равен 8657, что не является полным квадратом. Поэтому выражение ''x''<sup>2</sup> + 93''x'' − 2 нельзя факторизовать целыми числами.
=== Полный квадратный трёхчлен ===
[[Файл:A plus b au carre.svg|thumb|200px|right|Иллюстрация идентичности (''a'' + ''b'')<sup>2</sup> = ''a''<sup>2</sup> + 2''ab'' + ''b''<sup>2</sup>]]
Некоторые квадратные уравнения можно факторизовать двумя одинаковыми биномами. Такие уравнения называются полным квадратным трёхчленом. Полный квадратный трёхчлен можно факторизовать следующим образом:
:<math> a^2 + 2ab + b^2 = (a + b)^2,\,\!</math>
и
:<math> a^2 - 2ab + b^2 = (a - b)^2.\,\!</math>
=== Сумма/разность двух квадратов ===
Другой общий метод алгебраического факторинга называют разностью двух квадратов. Он заключается в применении формулы
:<math> a^2 - b^2 = (a+b)(a-b),\,\!</math>
к любым двум членам, независимо от того, являются они полным квадратным уравнением или нет. Если два члена вычитаются, то нужно просто применить формулу. Если они складываются, то оба бинома, получинные из факторинга, будут иметь мнимый член. Эта формула может быть представлена в виде
:<math> a^2 + b^2 = (a+bi)(a-bi). \,\!</math>
Например, <math>4x^2 + 49</math> можно факторизовать на <math>(2x + 7i)(2x - 7i)</math>.
=== Факторинг группировкой ===
Ещё одним методом факторизации некоторых полиномов является факторинг группировкой. Для тех, кто любит разрабатывать алгоритмы, «факторинг группировкой» может быть самым приятным подходом к факторингу трёхчлена, поскольку в нём нужно строить догадки относительно способа завершения процесса.
Факторинг группировкой делается путём расположения членов многочлена на две или большее количество групп, каждая из которых может быть факторизована известным способом. Результаты этих факторизаций иногда можно скомбинировать так, чтобы сполучить более простое выражение. Например, чтобы факторизовать полином
<math>4x^2+20x+3yx+15y \,</math>
сгруппируем подобные члены: <math>(4x^2+20x)+(3yx+15y)\,</math>
факторизуем через [[наибольший общий делитель]], <math>4x(x+5)+3y(x+5)\,</math>
и факторизуем на биномы <math>(x+5)(4x+3y)\,</math>
=== AC метод ===
Если квадратный трёхчлен имеет решения на рациональных числах, мы можем найти p и q такие, что pq = ac и p + q = b. (Если дискриминант является квадратом числа, то они существуют, в противном случае мы будем иметь иррациональные или комплексные решения, и предположение о рациональном решении является недопустимым.)
:<math>
\begin{align}
ax^2 + bx + c & = \frac{a^2x^2 + abx
+ ac}{a} & = \frac{(ax+p)(ax+q)}{a}
\end{align}
</math>
Верхние члены будут иметь общие факторы, которые могут использоваться для избавления от знаменателя, если он не равен 1. В качестве примера рассмотрим квадратичный полином
:<math>
\begin{align}
6x^2 + 13x + 6
\end{align}
</math>
Проверка факторов ac = 36 приводит к 4 + 9 = 13 = b.
:<math>
\begin{align}
6x^2 + 13x + 6 & = \frac{(6x+4)(6x+9)}{6} \\
&= \frac{2(3x+2)(3)(2x+3)}{6} \\
&= (3x+2)(2x+3)
\end{align}
</math>
== Факторинг других полиномов ==
=== Сумма/разность двух кубов ===
Выполним фактроинг суммы и разности двух кубов. Сумму двух кубов можно представить в виде:
:<math> a^3 + b^3 = (a + b)(a^2 - ab + b^2),\,\!</math>
а разность:
:<math> a^3 - b^3 = (a - b)(a^2 + ab + b^2).\,\!</math>
Например, ''x''<sup>3</sup> − 10<sup>3</sup> (или ''x''<sup>3</sup> − 1000) можно факторизовать в виде: (''x'' − 10)(''x''<sup>2</sup> + 10''x'' + 100).
== См. также ==
*[[Разложение матрицы]]
*[[Треугольник Паскаля]]
*[[Факториальное кольцо]]
== Ссылки ==
* [http://ega-math.narod.ru/Nquant/Infeld.htm Л. Инфельд, Т. Е. Халл Метод факторизации]
* [http://factors.evalwave.com/ One hundred million numbers factored on html pages.]
* [http://library.thinkquest.org/20991/alg/factoring.html?tqskip1=1 A page about factorization, Algebra, Factoring]
* [http://wims.unice.fr/wims/wims.cgi?module=tool/algebra/factor.en WIMS Factoris] is an online factorization tool.
* [[Wolfram Alpha]] [http://www.wolframalpha.com/input/?i=Factor%20-2006+%2B+1155+x+-+78+x^2+%2B+x^3 can factorize too].
[[Категория:Арифметика]]
[[Категория:Алгебра]]
[[af:Priemfaktor]]
[[ar:تحليل (رياضيات)]]
[[bg:Факторизация]]
[[ca:Factorització]]
[[cs:Faktorizace]]
[[cy:Ffactorau cysefin]]
[[da:Faktorisering]]
[[de:Faktorisierung]]
[[el:Παραγοντοποίηση]]
[[en:Factorization]]
[[es:Factorización]]
[[eo:Faktorigo]]
[[eu:Faktorizazio]]
[[fr:Factorisation]]
[[ko:인수 분해]]
[[hi:गुणनखण्ड]]
[[is:Þáttun]]
[[it:Fattorizzazione]]
[[he:פירוק לגורמים]]
[[la:Factoratio]]
[[lt:Faktorizavimas]]
[[nl:Factorisatie]]
[[ja:因数分解]]
[[no:Faktorisering]]
[[pl:Rozkład na czynniki]]
[[pt:Fatoração]]
[[ro:Factorizarea întregilor]]
[[ru:Факторизация целых чисел]]
[[simple:Factorization]]
[[sk:Faktorizácia]]
[[sl:Faktorizacija]]
[[fi:Tekijä]]
[[sv:Faktorisering]]
[[th:การแยกตัวประกอบ]]
[[uk:Факторизація]]
[[ur:اجزائے ضربی]]
[[vi:Phân tích nhân tử]]
[[yi:פאקטאריזאציע]]
[[zh:因式分解]]
| |||