
In algebra, la decomposizione in fratti semplici di una funzione razionale, anche detta decomposizione in frazioni semplici o espansione in fratti semplici, è la scrittura della frazione tramite un polinomio (che può essere nullo) sommato ad una o più frazioni con un denominatore più semplice. Tale metodo fornisce un algoritmo che consente di valutare le primitive di una funzione razionale.
Per illustrare l'idea del procedimento, sia data una funzione razionale formula_1, in cui formula_2 e formula_3 sono polinomi, e si consideri la fattorizzazione formula_4 del denominatore. Per ogni fattore che ha la forma formula_5 si considerano le frazioni formula_6, mentre per ogni fattore che ha la forma formula_7 si considerano le frazioni:
Si ottiene così la scrittura:
e calcolando i coefficienti formula_10 e formula_11 si trova una decomposizione che consente, analizzandone ogni singolo termine, di integrare la frazione di partenza. Essa conduce quindi formula_12 ad un'espressione del tipo:
dove formula_14 e formula_15 sono polinomi di grado inferiore rispetto a formula_2 e formula_3.
Se si applica la decomposizione fin dove è possibile si ottiene che il denominatore di ogni termine è una potenza di un polinomio non fattorizzabile e il numeratore è un polinomio di grado inferiore di quello del polinomio non fattorizzabile.
Si consideri una funzione razionale formula_18 nella variabile formula_19 il cui denominatore si può fattorizzare come:
sul campo formula_21, che può essere ad esempio formula_22 o formula_23. Se formula_24 e formula_25 non hanno nessun fattore comune, allora formula_12 si può scrivere come:
per qualche coppia di polinomi formula_28 e formula_29 su formula_21. L'esistenza di tale decomposizione è una conseguenza del fatto che l'anello dei polinomi su formula_21 è un dominio ad ideali principali, sicché:
per qualche coppia di polinomi formula_33 e formula_34 (si veda l'identità di Bézout).
Con tale approccio si può induttivamente scrivere formula_35 come una somma di frazioni i cui denominatori sono potenze di polinomi irriducibili.
In modo più rigoroso, siano formula_2 e formula_3 polinomi non nulli su formula_21. Si scriva formula_3 come prodotto di potenze di polinomi non fattorizzabili:
Allora esistono unici i polinomi formula_41 e formula_42, di cui formula_42 hanno grado inferiore a quello di formula_44, tali che:
e se il grado di formula_2 è minore di quello di formula_3 allora formula_48.
Si può verificare tale teorema scrivendo formula_49 come una somma in cui i denominatori sono potenze di formula_50 ed i numeratori sono polinomi di grado inferiore a quello di formula_50, più un eventuale polinomio aggiuntivo. Per fare ciò si può utilizzare l'algoritmo di Euclide applicato ai polinomi.
Se formula_21 è il campo dei numeri complessi formula_23 allora per il teorema fondamentale dell'algebra si può assumere che ogni formula_44 ha grado 1.
Siano formula_2 e formula_3 polinomi non nulli sul campo formula_21. Si scriva formula_3 come prodotto di potenze di polinomi vicendevolmente primi che non hanno radici multiple in un campo algebricamente chiuso:
Allora esistono unici i polinomi formula_41 e formula_61, di cui formula_61 hanno grado inferiore a quello di formula_44, tali che:
dove l'apice denota la derivata. Questo risultato consente di ridurre il calcolo della primitiva di una funzione razionale all'integrazione della somma al secondo membro, detta "parte logaritmica" a causa del fatto che la sua primitiva è una combinazione lineare di logaritmi. Infatti, si ha:
Vi sono diversi metodi per calcolare tale decomposizione, il più semplice dei quali è il metodo di Hermite: si basa sul fatto che formula_61 ha grado inferiore a quello di formula_44, e che il grado di formula_68 è la differenza (positiva) tra i gradi di formula_2 e formula_3: questo consente di scrivere tali polinomi incogniti come polinomi noti con coefficienti ignoti. Riducendo i due termini della formula precedente in un'unica frazione si ottiene un sistema di equazioni lineari che consente di trovare tali coefficienti.
Si vuole decomporre l'espressione:
ovvero scriverla nella forma:
in cui i parametri formula_73, formula_74 e formula_75 sono ignoti. Moltiplicando queste due espressioni per formula_76 ed uguagliandole si ottiene:
Raccogliendo i termini che moltiplicano le potenze di formula_19 si ha:
Il polinomio al secondo membro ha solo il coefficiente di grado zero non nullo, e si possono uguagliare i coefficienti che moltiplicano le potenze di formula_19 di entrambi i membri. In questo modo si ottiene il sistema di equazioni lineari:
che fornisce:


In matematica la fattorizzazione è la riduzione in fattori: "fattorizzare" un numero intero positivo formula_1 significa trovare un insieme di numeri interi positivi formula_2 tali che il loro prodotto sia il numero originario (formula_3).
I numeri interi di poche cifre si possono fattorizzare velocemente a mano aiutandosi con i criteri di divisibilità o, per numeri di qualche decina di cifre, con un computer. Per numeri con più di un centinaio di cifre il problema di fattorizzazione rimane tuttavia un problema complesso nonché un argomento di ricerca fondamentale per la teoria dei numeri computazionale e la crittografia.
Innanzitutto bisogna tenere presente che un qualunque numero intero ha infinite fattorizzazioni: lo si può infatti moltiplicare quante volte si vuole per 1. In pratica, però, non si considerano i fattori 1 nella fattorizzazione: è questa tra l'altro la ragione per cui si preferisce non considerare 1 come un numero primo.
La maggior parte dei numeri ha comunque svariate fattorizzazioni possibili: ad esempio, formula_4. Per convenzione, ci si concentra su una sola tra tutte queste, che è anche la più importante: la fattorizzazione in numeri primi, che consiste nel cercare un insieme di fattori del numero che siano tutti primi (generalmente indicati con formula_5 per ricordare la loro primalità). Per il teorema fondamentale dell'aritmetica, ogni numero intero ha una ed una sola fattorizzazione in numeri primi. Ad esempio
Nel corso della storia sono stati ideati molti algoritmi per rendere la fattorizzazione un problema sempre più veloce. Il problema però rimane tuttora un problema complesso. Tra i metodi utilizzati vi sono i seguenti:
Nel 1994 Peter Shor ha sviluppato un algoritmo di fattorizzazione polinomiale (cubico, per la precisione). Questo algoritmo, noto come algoritmo di fattorizzazione di Shor, richiede tuttavia un computer quantistico.
Segue un'implementazione dell'algoritmo per la fattorizzazione in numeri primi.
